PREFACE xi
INTRODUCTION xv
PART 1. RANDOMNESS IN OPTIMIZATION 1
CHAPTER 1. NECESSARY RISK 3
1.1. No better than random search 3
1.1.1. Uniform random search 4
1.1.2. Sequential search 5
1.1.3. Partial gradient 5
1.2. Better or worse than random search 7
1.2.1. Positive correlation problems 8
1.2.2. Negative correlation problems 10
CHAPTER 2. RANDOM NUMBER GENERATORS (RNGS) 13
2.1. Generator types 14
2.2. True randomness 15
2.3. Simulated randomness 15
2.3.1. KISS 16
2.3.2. Mersenne-Twister 16
2.4. Simplified randomness 17
2.4.1. Linear congruential generators 18
2.4.2. Additive 20
2.4.3. Multiplicative 22
2.5. Guided randomness 24
2.5.1. Gaussian 24
2.5.2. Bell 24
2.5.3. Cauchy 27
2.5.4. Levy 28
2.5.5. Log-normal 28
2.5.6. Composite distributions 28
CHAPTER 3. THE EFFECTS OF RANDOMNESS 33
3.1. Initialization 34
3.1.1. Uniform randomness 34
3.1.2. Low divergence 36
3.1.3. No Man's Land techniques 37
3.2. Movement 37
3.3. Distribution of the Next Possible Positions (DNPP) 40
3.4. Confinement, constraints and repairs 42
3.4.1. Strict confinement 44
3.4.2. Random confinement 44
3.4.3. Moderate confinement 45
3.4.4. Reverse 45
3.4.5. Reflection-diffusion 45
3.5. Strategy selection 46
PART 2. OPTIMIZER COMPARISON 49
CHAPTER 4. ALGORITHMS AND OPTIMIZERS 53
4.1. The Minimaliste algorithm 54
4.1.1. General description 54
4.1.2. Minimaliste in practice 54
4.1.3. Use of randomness 57
4.2. PSO 59
4.2.1. Description 59
4.2.2. Use of randomness 60
4.3. APS 62
4.3.1. Description 62
4.3.2. Uses of randomness 65
4.4. Applications of randomness 66
CHAPTER 5. PERFORMANCE CRITERIA 69
5.1. Eff-Res: construction and properties 69
5.1.1. Simple example using random search 71
5.2. Criteria and measurements 74
5.2.1. Objective criteria 77
5.2.2. Semi-subjective criteria 87
5.3. Practical construction of an Eff-Res 94
5.3.1. Detailed example: (Minimaliste, Alpine 2D) 95
5.3.2. Qualitative interpretations 106
5.4. Conclusion 108
CHAPTER 6. COMPARING OPTIMIZERS 109
6.1. Data collection and preprocessing 111
6.2. Critical analysis of comparisons 114
6.2.1. Influence of criteria and the number of attempts 115
6.2.2. Influence of effort levels 115
6.2.3. Global comparison 117
6.2.4. Influence of the RNG 121
6.3. Uncertainty in statistical analysis 123
6.3.1. Independence of tests 125
6.3.2. Confidence threshold 125
6.3.3. Success rate 125
6.4. Remarks on test sets 125
6.4.1. Analysis grid 126
6.4.2. Representativity 129
6.5. Precision and prudence 130
PART 3 . APPENDICES 131
CHAPTER 7. MATHEMATICAL NOTIONS 133
7.1. Sets closed under permutations 133
7.2. Drawing with or without repetition 133
7.3. Properties of the Additive and Multiplicative generators 135
7.3.1. Additive 136
7.3.2. Multiplicative 136
CHAPTER 8. BIASES AND SIGNATURES 139
8.1. The impossible plateau 139
8.2. Optimizer signatures 140
CHAPTER 9. A PSEUDO-SCIENTIFIC ARTICLE 147
9.1. Article 147
9.2. Criticism 151
CHAPTER 10. COMMON MISTAKES 155
CHAPTER 11. UNNECESSARY RANDOMNESS? LIST-BASED OPTIMIZERS 159
11.1. Truncated lists 160
11.2. Semi-empirical lists 162
11.3. Micro-robots 163
CHAPTER 12. PROBLEMS 167
12.1. Deceptive 1 (Flash) 167
12.2. Deceptive 2 (Comb) 167
12.3. Deceptive 3 (Brush) 168
12.4. Alpine 168
12.5. Rosenbrock 168
12.6. Pressure vessel 169
12.7. Sphere 169
12.8. Traveling salesman: six cities 170
12.9. Traveling salesman: fourteen cities (Burma 14) 170
12.10. Tripod 171
12.11. Gear train 171
CHAPTER 13. SOURCE CODES 173
13.1. Random generation and sampling 173
13.1.1. Preamble for Scilab codes 174
13.1.2. Drawing of a pseudo-random number, according to options 174
13.1.3. True randomness 178
13.1.4. Guided randomness 179
13.1.5. Uniform initializations (continuous, combinatorial) 183
13.1.6. Regular initializations (Sobol, Halton) 183
13.1.7. No Man's Land techniques 184
13.1.8. Sampling 186
13.1.9. Movements and confinements 189
13.2. Useful tools 191
13.3. Combinatorial operations 191
13.4. Random algorithm 198
13.5. Minimaliste algorithm 200
13.6. SPSO algorithm 205
13.7. APS algorithm 216
13.8. ?PSO algorithm 234
13.9. Problems 241
13.9.1. Problem definitions 241
13.9.2. Problem landscape 254
13.10. Treatment of results 255
13.10.1. Quality (including curves) 255
13.10.2. Other criteria (including curves) 256
13.10.3. Construction of an Eff-Res 261
13.11. Treatment of the Eff-Res 263
13.11.1. Graphic representation 263
13.11.2. Interpolation 264
13.11.3. Performance criteria (including curves) 265
13.12. Histograms, polar diagrams 271
13.13. Other figures 273
13.14. Tests (bias, correlation) 277
BIBLIOGRAPHY 285
INDEX 293
