Guided Randomness in Optimization, Volume 1

ISBN-13: 9781848218055 / Angielski / Twarda / 2015 / 316 str.

Maurice Clerc

Opis

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.

Spis treści

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

O autorze

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.