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. INDICE: 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
- ISBN: 978-1-84821-805-5
- Editorial: ISTE Ltd.
- Encuadernacion: Cartoné
- Páginas: 316
- Fecha Publicación: 05/06/2015
- Nº Volúmenes: 1
- Idioma: Inglés