Guided Randomness in Optimization, Volume 1

The performance of an algorithm used depends on the GNA. This book focuses on the comparison of optimizers, it defines a stress-outcome approach which can be derived all the classic criteria (median, average, etc.) and other more sophisticated.   Source-codes used for the examples are also presented, this allows a reflection on the "superfluous chance," succinctly explaining why and how the stochastic aspect of optimization could be avoided in some cases.

Table of Contents:
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. Lévy 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