Genetic algorithms + data structures = evolution programs

Genetic algorithms are founded upon the principle of evolution, i.e., survival of the fittest. Hence evolution programming techniques, based on genetic algorithms, are applicable to many hard optimization problems, such as optimization of functions with linear and nonlinear constraints, the traveling salesman problem, and problems of scheduling, partitioning, and control. The importance of these techniques is still growing, since evolution programs are parallel in nature, and parallelism is one of the most promising directions in computer science.
The book is self-contained and the only prerequisite is basic undergraduate mathematics. This third edition has been substantially revised and extended by three new chapters and by additional appendices containing working material to cover recent developments and a change in the perception of evolutionary computation.

Table of contents :
Introduction ..... 1

Part I. Genetic Algorithms ..... 11

1 GAs: What Are They? ..... 13

1.1 Optimization of a simple function ..... 18

1.1.1 Representation ..... 19
1.1.2 Initial population ..... 20
1.1.3 Evaluation function ..... 20
1.1.4 Genetic operators ..... 21
1.1.5 Parameters ..... 21
1.1.6 Experimental results ..... 22

1.2 The prisoner's dilemma ..... 22

1.2.1 Representing a strategy ..... 23
1.2.2 Outline of the genetic algorithm ..... 23
1.2.3 Experimental results ..... 24

1.3 Traveling salesman problem ..... 25
1.4 Hill climbing, simulated annealing, and genetic algorithms ..... 26
1.5 Conclusions ..... 30

2 GAs: How Do They Work? ..... 33

3 GAs: Why Do They Work? ..... 45

4 GAs: Selected Topics ..... 57

4.1 Sampling mechanism ..... 58
4.2 Characteristics of the function ..... 65
4.3 Contractive mapping genetic algorithms ..... 68
4.4 Genetic algorithms with varying population size ..... 72
4.5 Genetic algorithms, constraints, and the knapsack problem ..... 80

4.5.1 The 0/1 knapsack problem and the test data ..... 81
4.5.2 Description of the algorithms ..... 82
4.5.3 Experiments and results ..... 84

4.6 Other ideas ..... 88

Part II. Numerical Optimization ..... 96

5 Binary or Float? ..... 98

5.1 The test case ..... 101
5.2 The two implementations ..... 101

5.2.1 The binary implementation ..... 102
5.2.2 The floating point implementation ..... 102

5.3 The experiments ..... 103

5.3.1 Random mutation and crossover ..... 103
5.3.2 Non-uniform mutation ..... 104
5.3.3 Other operators ..... 104

5.4 Time performance ..... 105
5.5 Conclusions ..... 105

6 Fine Local Tuning ..... 106

6.1 The test cases ..... 106

6.1.1 The linear-quadratic problem ..... 108
6.1.2 The harvest problem ..... 108
6.1.3 The push-cart problem ..... 110

6.2 The evolution program for numerical optimization ..... 111

6.2.1 The representation ..... 112
6.2.2 The specialized operators ..... 112

6.3 Experiments and results ..... 113
6.4 Evolution program versus other methods ..... 114

6.4.1 The linear-quadratic problem ..... 114
6.4.2 The harvest problem ..... 115
6.4.3 The push-cart problem ..... 116
6.4.4 The significance of non-uniform mutation .....117

6.5 Conclusions ..... 118

7 Handling Constraints ..... 121

7.1 An evolution program: the GENOCOP system ..... 122

7.1.1 An example ..... 125
7.1.2 Operators ..... 127
7.1.3 Testing GENOCOP ..... 130

7.2 Nonlinear optimization: GENOCOP II ..... 134
7.3 Other techniques ..... 141

7.3.1 Five test cases ..... 144
7.3.2 Experiments ..... 147

7.4 Other possibilities ..... 150
7.5 GENOCOP III ..... 154

8 Evolution Strategies and Other Methods ..... 159

8.1 Evolution of evolution strategies ..... 160
8.2 Comparison of evolution strategies and genetic algorithms ..... 164
8.3 Multimodal and multiobjective function optimization ..... 168

8.3.1 Multimodal optimization ..... 168
8.3.2 Multiobjective optimization ..... 171

8.4 Other evolution programs ..... 172

Part III. Evolution Programs ..... 179

9 The Transportation Problem ..... 181

9.1 The linear transportation problem ..... 181

9.1.1 Classical genetic algorithms ..... 183
9.1.2 Incorporating problem-specific knowledge ..... 185
9.1.3 A matrix as a representation structure ..... 188
9.1.4 Conclusions ..... 194

9.2 The nonlinear transportation problem ..... 196

9.2.1 Representation ..... 196
9.2.2 Initialization ..... 196
9.2.3 Evaluation ..... 196
9.2.4 Operators ..... 196
9.2.5 Parameters .....198
9.2.6 Test cases ..... 198
9.2.7 Experiments and results ..... 201
9.2.8 Conclusions ..... 206

10 The Traveling Salesman Problem ..... 209

11 Evolution Programs for Various Discrete Problems ..... 239

11.1 Scheduling ..... 239
11.2 The timetable problem ..... 246
11.3 Partitioning objects and graphs .... .247
11.4 Path planning in a mobile robot environment ..... 253
11.5 Remarks ..... 261

12 Machine Learning ..... 267

12.1 The Michigan approach ..... 270
12.2 The Pitt approach ..... 274
12.3 An evolution program: the GIL system ..... 276

12.3.1 Data structures ..... 276
12.3.2 Genetic operators ..... 277

12.4 Comparison ..... 280
12.5 REGAL ..... 281

13 Evolutionary Programming and Genetic Programming ..... 283

13.1 Evolutionary programming ..... 283
13.2 Genetic programming ..... 285

14 A Hierarchy of Evolution Programs ..... 289

15 Evolution Programs and Heuristics ..... 307

15.1 Techniques and heuristics: a summary ..... 309
15.2 Feasible and infeasible solutions ..... 312
15.3 Heuristics of reevaluating individuals ..... 314

16 Conclusions ..... 329

Appendix A ..... 337

Appendix B ..... 349

Appendix C ..... 353

Appendix D ..... 359

References .....363

Index ..... 383