Contents
Preface xi
List of contributors xv
Glossary xix
PART 1 FITNESS EVALUATION
1 Introduction to fitness evaluation 1
Hitoshi Iba
1.1 Fitness evaluation 1
1.2 Related problems 2
References 3
2 Encoding and decoding functions 4
Kalyanmoy Deb
2.1 Introduction 4
2.2 Binary strings 4
2.3 Gray coded strings 6
2.4 Messy coding 7
2.5 Floating-point coding 7
2.6 Coding for binary variables 9
2.7 Coding for permutation problems 9
2.8 Coding for control problems 9
2.9 Conclusions 10
References 10
3 Competitive fitness evaluation 12
Peter JAngeline
3.1 Objective fitness 12
3.2 Relative and competitive fitness 12
References 14
4 Complexity-based fitness evaluation 15
Hitoshi Iba
4.1 Introduction 15
4.2 Model selection criteria 15
4.3 An example: minimum-description-length-based fitness evaluation 17
4.4 Recent studies on complexity-based fitness 22
4.5 Conclusion 23
TEAM LRN v
vi Contents
References 24
5 Multiobjective optimization 25
С M Fonseca and P J Fleming
5.1 Introduction 25
5.2 Fitness evaluation 25
5.3 Current evolutionary approaches to multiobjective optimization 26
5.4 Concluding remarks 35
References 36
PART 2 CONSTRAINT-HANDLING TECHNIQUES
6 Introduction to constraint-handling techniques 38
Zbigniew Michalewicz,
References 40
7 Penalty functions 41
Alice E Smith and David W Coit
7.1 Introduction to penalty functions 41
7.2 Static penalty functions 43
7.3 Dynamic penalty functions 44
7.4 Adaptive penalty functions 45
7.5 Future directions in penalty functions 47
References 47
8 Decoders 49
Zbigniew Michalewicz,
8.1 Introduction 49
8.2 The traveling salesman problem 49
8.3 Formal description 50
References 55
9 Repair algorithms 56
Zbigniew Michalewicz
9.1 Introduction 56
9.2 First example 58
9.3 Second example 59
9.4 Conclusion 61
References 61
10 Constraint-preserving operators 62
Zbigniew Michalewicz.
10.1 Introduction 62
10.2 The transportation problem 62
10.3 Nonlinear optimization with linear constraints 64
10.4 Traveling salesman problem 65
References 68
TEAM LRN
Contents vii
11 Other constraint-handling methods 69
Zbigniew Michalewicz.
11.1 Introduction 69
11.2 Multiobjective optimization methods 69
11.3 Coevolutionary model approach 70
11.4 Cultural algorithms 71
11.5 Segregated genetic algorithm 72
11.6 Genocop III 73
References 73
12 Constraint-satisfaction problems 75
Л Е Eiben and Zs Ruttkay
12.1 Introduction 75
12.2 Free optimization, constrained optimization, and constraint
satisfaction 76
12.3 Transforming constraint-satisfaction problems to EA-suited
problems 77
12.4 Solving the transformed problem 82
12.5 Conclusions 83
References 84
PART 3 POPULATION STRUCTURES
13 Niching methods 87
Samir W Mahfoud
13.1 Introduction 87
13.2 Fitness sharing 87
13.3 Crowding 89
13.4 Theory 90
References 91
14 Speciation methods 93
Kalyanmoy Deb and William M Spears
14.1 Introduction 93
14.2 Booker's taxon-exemplar scheme 94
14.3 The tag-template method 95
14.4 Phenotypic and genotypic mating restriction 96
14.5 Speciation using tag bits 97
14.6 Relationship with parallel algorithms 99
References 99
15 Island (migration) models: evolutionary algorithms based
on punctuated equilibria 101
W N Martin, Jens Lienig and James P Cohoon
15.1 Parallelization 101
15.2 Theories of natural evolution 102
TEAM LRN
viii Contents
15.3 The island model 105
15.4 The island model genetic algorithm applied to a VLSI design
problem 108
15.5 The influence of island model parameters on evolution 113
15.6 Final remarks and conclusions 119
References 122
16 Diffusion (cellular) models 125
Chrisila С Pettey
16.1 A formal description of the diffusion model 125
16.2 Diffusion model implementation techniques 126
16.3 Theoretical research in diffusion models 131
16.4 Conclusion 132
16.5 Additional sources of information 132
References 132
PART 4 ADVANCED TECHNIQUES IN EVOLUTIONARY
COMPUTATION
17 Population sizing 134
Robert E Smith
17.1 Introduction 134
17.2 Sizing for optimal schema processing 135
17.3 Sizing for accurate schema sampling 136
17.4 Final comments 139
References 140
18 Mutation parameters 142
Thomas Back
18.1 Introduction 142
18.2 Mutation parameters for self-adaptation 143
18.3 Mutation parameters for direct schedules 144
18.4 Summary 150
References 150
19 Recombination parameters 152
William M Spears
19.1 General background 152
19.2 Genotypic-level recombination 153
19.3 Phenotypic-level recombination 157
19.4 Control of recombination parameters 159
19.5 Discussion 164
References 166
20 Parameter control 170
A E Eiben, Robert Hinterding and Zbigniew Michalewicz,
TEAM LRN
Contents ix
References 186
21 Self-adaptation 188
Thomas Back
21.1 Introduction 188
21.2 Mutation operators 189
21.3 Recombination operators 205
21.4 Conclusions 208
References 209
22 Meta-evolutionary approaches 212
Bernd Freisleben
22.1 Working mechanism 212
22.2 Formal description 214
22.3 Pseudocode 215
22.4 Parameter settings 216
22.5 Theory 217
22.6 Related work 217
22.7 Conclusions 220
References 221
23 Coevolutionary algorithms 224
Jan Paredis
23.1 Introduction 224
23.2 Competitive fitness 225
23.3 Coevolving sorting networks 227
23.4 A general coevolutionary genetic algorithm 228
23.5 Discussion 234
References 236
PART 5 IMPLEMENTATION OF EVOLUTIONARY
ALGORITHMS
24 Efficient implementation of algorithms 239
John Grefenstette
24.1 Introduction 239
24.2 Random number generators 239
24.3 The selection operator 242
24.4 The mutation operator 242
24.5 The evaluation phase 243
References 246
25 Computation time of evolutionary operators 247
Gunter Rudolph andJb'rg Ziegenhirt
25.1 Asymptotical notations 247
25.2 Computation time of selection operators 247
TEAM LRN
x Contents
25.3 Computation time of mutation operators 250
25.4 Computation time of recombination operators 251
25.5 Final remarks 251
References 251
26 Hardware realizations of evolutionary algorithms 253
Tetsuya Higuchi and Bernard Manderick
26.1 Introduction 253
26.2 Parallel genetic algorithms 253
26.3 Dedicated hardware implementations for evolutionary algorithms 256
26.4 Evolvable hardware 258
26.5 Conclusion 261
References 261
Further reading 263
Index 265