Guided Randomness in Optimization, Volume 1

Maurice Clerc is recognized as one of the foremost PSO specialists in the world. A former France Telecom Research and Development engineer, he maintains his research activities as a consultant for the XPS (eXtended Particle Swarm) project.

• PREFACE xi INTRODUCTION xvPART 1. RANDOMNESS IN OPTIMIZATION  1CHAPTER 1. NECESSARY RISK 31.1. No better than random search 31.1.1. Uniform random search 41.1.2. Sequential search 51.1.3. Partial gradient 51.2. Better or worse than random search 71.2.1. Positive correlation problems 81.2.2. Negative correlation problems 10CHAPTER 2. RANDOM NUMBER GENERATORS (RNGS) 132.1. Generator types 142.2. True randomness 152.3. Simulated randomness 152.3.1. KISS 162.3.2. Mersenne-Twister 162.4. Simplified randomness 172.4.1. Linear congruential generators 182.4.2. Additive 202.4.3. Multiplicative 222.5. Guided randomness 242.5.1. Gaussian 242.5.2. Bell 242.5.3. Cauchy 272.5.4. Lévy 282.5.5. Log-normal 282.5.6. Composite distributions 28CHAPTER 3. THE EFFECTS OF RANDOMNESS 333.1. Initialization 343.1.1. Uniform randomness 343.1.2. Low divergence 363.1.3. No Man’s Land techniques 373.2. Movement 373.3. Distribution of the Next Possible Positions (DNPP) 403.4. Confinement, constraints and repairs 423.4.1. Strict confinement 443.4.2. Random confinement 443.4.3. Moderate confinement 453.4.4. Reverse 453.4.5. Reflection-diffusion 453.5. Strategy selection 46PART 2. OPTIMIZER COMPARISON 49CHAPTER 4. ALGORITHMS AND OPTIMIZERS 534.1. The Minimaliste algorithm 544.1.1. General description 544.1.2. Minimaliste in practice 544.1.3. Use of randomness 574.2. PSO 594.2.1. Description 594.2.2. Use of randomness 604.3. APS 624.3.1. Description 624.3.2. Uses of randomness 654.4. Applications of randomness 66CHAPTER 5. PERFORMANCE CRITERIA 695.1. Eff-Res: construction and properties 695.1.1. Simple example using random search 715.2. Criteria and measurements 745.2.1. Objective criteria 775.2.2. Semi-subjective criteria 875.3. Practical construction of an Eff-Res 945.3.1. Detailed example: (Minimaliste, Alpine 2D) 955.3.2. Qualitative interpretations 1065.4. Conclusion 108CHAPTER 6. COMPARING OPTIMIZERS 1096.1. Data collection and preprocessing 1116.2. Critical analysis of comparisons 1146.2.1. Influence of criteria and the number of attempts 1156.2.2. Influence of effort levels 1156.2.3. Global comparison 1176.2.4. Influence of the RNG 1216.3. Uncertainty in statistical analysis 1236.3.1. Independence of tests 1256.3.2. Confidence threshold 1256.3.3. Success rate 1256.4. Remarks on test sets 1256.4.1. Analysis grid 1266.4.2. Representativity 1296.5. Precision and prudence 130PART 3 . APPENDICES 131CHAPTER 7. MATHEMATICAL NOTIONS 1337.1. Sets closed under permutations 1337.2. Drawing with or without repetition 1337.3. Properties of the Additive and Multiplicative generators 1357.3.1. Additive 1367.3.2. Multiplicative 136CHAPTER 8. BIASES AND SIGNATURES 1398.1. The impossible plateau 1398.2. Optimizer signatures 140CHAPTER 9. A PSEUDO-SCIENTIFIC ARTICLE 1479.1. Article 1479.2. Criticism 151CHAPTER 10. COMMON MISTAKES 155CHAPTER 11. UNNECESSARY RANDOMNESS? LIST-BASED OPTIMIZERS 15911.1. Truncated lists 16011.2. Semi-empirical lists 16211.3. Micro-robots 163CHAPTER 12. PROBLEMS 16712.1. Deceptive 1 (Flash) 16712.2. Deceptive 2 (Comb) 16712.3. Deceptive 3 (Brush) 16812.4. Alpine 16812.5. Rosenbrock 16812.6. Pressure vessel 16912.7. Sphere 16912.8. Traveling salesman: six cities 17012.9. Traveling salesman: fourteen cities (Burma 14) 17012.10. Tripod 17112.11. Gear train 171CHAPTER 13. SOURCE CODES 17313.1. Random generation and sampling 17313.1.1. Preamble for Scilab codes 17413.1.2. Drawing of a pseudo-random number, according to options 17413.1.3. True randomness 17813.1.4. Guided randomness 17913.1.5. Uniform initializations (continuous, combinatorial) 18313.1.6. Regular initializations (Sobol, Halton) 18313.1.7. No Man’s Land techniques 18413.1.8. Sampling 18613.1.9. Movements and confinements 18913.2. Useful tools 19113.3. Combinatorial operations 19113.4. Random algorithm 19813.5. Minimaliste algorithm 20013.6. SPSO algorithm 20513.7. APS algorithm 21613.8. μPSO algorithm 23413.9. Problems 24113.9.1. Problem definitions 24113.9.2. Problem landscape 25413.10. Treatment of results 25513.10.1. Quality (including curves) 25513.10.2. Other criteria (including curves) 25613.10.3. Construction of an Eff-Res 26113.11. Treatment of the Eff-Res 26313.11.1. Graphic representation 26313.11.2. Interpolation 26413.11.3. Performance criteria (including curves) 26513.12. Histograms, polar diagrams 27113.13. Other figures 27313.14. Tests (bias, correlation) 277BIBLIOGRAPHY 285INDEX 293