دانلود کتاب Introduction to Evolutionary Computing

فهرست مطالب :

Preface......Page 6
Contents......Page 8
Part I The Basics......Page 14
1.1 Optimisation, Modelling, and Simulation Problems......Page 15
1.1.1 Optimisation......Page 16
1.1.2 Modelling......Page 17
1.2 Search Problems......Page 19
1.3 Optimisation Versus Constraint Satisfaction......Page 20
1.4 The Famous NP Problems......Page 23
2.1 The Main Evolutionary Computing Metaphor......Page 27
2.2 Brief History......Page 28
2.3.1 Darwinian Evolution......Page 29
2.3.2 Genetics......Page 31
2.3.3 Putting It Together......Page 33
2.4 Evolutionary Computing: Why?......Page 34
3.1 What Is an Evolutionary Algorithm?......Page 39
3.2.1 Representation (Definition of Individuals)......Page 42
3.2.3 Population......Page 44
3.2.5 Variation Operators (Mutation and Recombination)......Page 45
3.2.6 Survivor Selection Mechanism (Replacement)......Page 47
3.3 An Evolutionary Cycle by Hand......Page 48
3.4.1 The Eight-Queens Problem......Page 50
3.4.2 The Knapsack Problem......Page 53
3.5 The Operation of an Evolutionary Algorithm......Page 55
3.6 Natural Versus Artificial Evolution......Page 58
3.7 Evolutionary Computing, Global Optimisation, and Other Search Algorithms......Page 60
4.1 Representation and the Roles of Variation Operators......Page 63
4.2 Binary Representation......Page 65
4.2.2 Recombination for Binary Representation......Page 66
4.3 Integer Representation......Page 68
4.3.1 Mutation for Integer Representations......Page 69
4.4.1 Mutation for Real-Valued Representation......Page 70
4.4.2 Self-adaptive Mutation for Real-Valued Representation......Page 71
4.4.3 Recombination Operators for Real-Valued Representation......Page 79
4.5 Permutation Representation......Page 81
4.5.1 Mutation for Permutation Representation......Page 83
4.5.2 Recombination for Permutation Representation......Page 84
4.6 Tree Representation......Page 89
4.6.1 Mutation for Tree Representation......Page 91
4.6.2 Recombination for Tree Representation Tree-based recombination creates offspring by swapping genetic material......Page 92
5.1 Population Management Models......Page 93
5.2.1 Fitness Proportional Selection......Page 94
5.2.2 Ranking Selection......Page 95
5.2.3 Implementing Selection Probabilities......Page 97
5.2.4 Tournament Selection......Page 98
5.2.6 Overselection for Large Populations......Page 100
5.3 Survivor Selection......Page 101
5.3.2 Fitness-Based Replacement......Page 102
5.4 Selection Pressure......Page 104
5.5.1 Multimodal Problems......Page 105
5.5.3 Fitness Sharing......Page 106
5.5.4 Crowding......Page 107
5.5.6 Running Multiple Populations in Tandem: Island Model EAs......Page 109
5.5.7 Spatial Distribution Within One Population: Cellular EAs......Page 111
6.1 Genetic Algorithms......Page 113
6.2 Evolution Strategies......Page 115
6.3 Evolutionary Programming......Page 117
6.4 Genetic Programming......Page 118
6.5 Learning Classifier Systems......Page 121
6.6 Differential Evolution......Page 124
6.7 Particle Swarm Optimisation......Page 126
6.8 Estimation of Distribution Algorithms......Page 127
Part II Methodological Issues......Page 131
7.1 Evolutionary Algorithm Parameters......Page 132
7.2 EAs and EA Instances......Page 133
7.3 Designing Evolutionary Algorithms......Page 134
7.4 The Tuning Problem......Page 136
7.5 Algorithm Quality: Performance and Robustness......Page 138
7.6 Tuning Methods......Page 141
8.1 Introduction......Page 143
8.2 Examples of Changing Parameters......Page 144
8.2.1 Changing the Mutation Step Size......Page 145
8.2.2 Changing the Penalty Coefficients......Page 146
8.3.2 How Are Changes Made?......Page 148
8.3.4 What Is the Scope of the Change?......Page 150
8.4.1 Representation......Page 151
8.4.2 Evaluation Function......Page 152
8.4.4 Crossover......Page 153
8.4.6 Population......Page 154
8.4.7 Varying Several Parameters Simultaneously......Page 155
8.5 Discussion......Page 156
9.1 What Do You Want an EA to Do?......Page 159
9.2 Performance Measures......Page 162
9.2.1 Different Performance Measures......Page 163
9.2.2 Peak Versus Average Performance......Page 167
9.3.1 Using Predefined Problem Instances......Page 170
9.3.3 Using Real-World Problems......Page 172
9.4.1 Bad Practice......Page 173
9.4.2 Better Practice......Page 174
Part III Advanced Topics......Page 176
10.1 Motivation for Hybridising EAs......Page 177
10.2 A Brief Introduction to Local Search......Page 180
10.2.1 Lamarckianism and the Baldwin Effect......Page 181
10.3.1 Heuristic or Intelligent Initialisation......Page 182
10.3.2 Hybridisation Within Variation Operators: Intelligent Crossover and Mutation......Page 184
10.3.3 Local Search Acting on the Output from Variation Operators......Page 185
10.3.4 Hybridisation During Genotype to Phenotype Mapping......Page 186
10.4 Adaptive Memetic Algorithms......Page 187
10.5 Design Issues for Memetic Algorithms......Page 189
10.6 Example Application: Multistage Memetic Timetabling......Page 191
11.1 Characterisation of Nonstationary Problems......Page 194
11.2 The Effect of Different Sources of Uncertainty......Page 196
11.3.2 Pure Evolutionary Approaches to Dynamic Environments......Page 198
11.3.4 Explicitly Increasing Diversity in Dynamic Environments......Page 199
11.3.5 Preserving Diversity and Resampling: Modifying Selection and Replacement Policies......Page 200
11.3.6 Example Application: Time-Varying Knapsack Problem......Page 202
12.1 Multiobjective Optimisation Problems......Page 204
12.2 Dominance and Pareto Optimality......Page 205
12.3.1 Nonelitist Approaches......Page 207
12.3.3 Diversity Maintenance in MOEAs......Page 208
12.4 Example Application: Distributed Coevolution of Job Shop Schedules......Page 209
13.1 Two Main Types of Constraint Handling......Page 212
13.2 Approaches to Handling Constraints......Page 213
13.2.1 Penalty Functions......Page 215
13.2.2 Repair Functions......Page 217
13.2.3 Restricting Search to the Feasible Region......Page 218
13.2.4 Decoder Functions......Page 219
13.3 Example Application: Graph Three-Colouring......Page 220
14.1 Characteristics of Interactive Evolution......Page 223
14.1.2 The Effect of Context: What Has Gone Before......Page 224
14.2.1 Interactive Selection and Population Size......Page 225
14.2.3 Methods for Reducing the Frequency of User Interactions......Page 226
14.3 Interactive Evolution as Design vs. Optimisation......Page 227
14.4 Example Application: Automatic Elicitation of User Preferences......Page 228
15.1 Coevolution in Nature......Page 231
15.2 Cooperative Coevolution......Page 232
15.2.1 Partnering Strategies......Page 233
15.3 Competitive Coevolution......Page 234
15.4 Summary of Algorithmic Adaptations for Context-Dependent Evaluation......Page 235
15.5 Example Application: Coevolving Checkers Players......Page 236
16 Theory......Page 238
Holland’s Formulation for the SGA......Page 239
Walsh Analysis and Deception......Page 241
16.2 Criticisms and Recent Extensions of the Schema Theorem......Page 243
16.3 Gene Linkage: Identifying and Recombining Building Blocks......Page 244
16.4 Dynamical Systems......Page 245
16.5 Markov Chain Analysis......Page 246
16.7 Reductionist Approaches......Page 248
16.8 Black Box Analsyis......Page 249
16.10 No Free Lunch Theorem......Page 250
17.1 What Is It All About?......Page 252
17.2 Introductory Example......Page 253
17.3 Offline and Online Evolution of Robots......Page 255
17.4 Evolutionary Robotics: The Problems Are Different......Page 257
17.5 Evolutionary Robotics: The Algorithms Are Different......Page 260
17.6 A Glimpse into the Future......Page 263
References......Page 266
Index......Page 290