139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 263
Veröffentlichungsjahr: 2015
Ähnliche
Table of Contents
Cover
Dedication
Title Page
Copyright
Preface
Introduction
PART 1: Randomness in Optimization
1: Necessary Risk
1.1. No better than random search
1.2. Better or worse than random search
2: Random Number Generators (RNGs)
2.1. Generator types
2.2. True randomness
2.3. Simulated randomness
2.4. Simplified randomness
2.5. Guided randomness
3: The Effects of Randomness
3.1. Initialization
3.2. Movement
3.3. Distribution of the Next Possible Positions (DNPP)
3.4. Confinement, constraints and repairs
3.5. Strategy selection
PART 2: Optimizer Comparison Introduction to Part 2
4: Algorithms and Optimizers
4.1. The Minimaliste algorithm
4.2. PSO
4.3. APS
4.4. Applications of randomness
5: Performance Criteria
5.1. Eff-Res: construction and properties
5.2. Criteria and measurements
5.3. Practical construction of an Eff-Res
5.4. Conclusion
6: Comparing Optimizers
6.1. Data collection and preprocessing
6.2. Critical analysis of comparisons
6.3. Uncertainty in statistical analysis
6.4. Remarks on test sets
6.5. Precision and prudence
PART 3: Appendices
7: Mathematical Notions
7.1. Sets closed under permutations
7.2. Drawing with or without repetition
7.3. Properties of the Additive and Multiplicative generators
8: Biases and Signatures
8.1. The impossible plateau
8.2. Optimizer signatures
9: A Pseudo-Scientific Article
9.1. Article
9.2. Criticism
10: Common Mistakes:
11: Unnecessary Randomness? List-based Optimizers
11.1. Truncated lists
11.2. Semi-empirical lists
11.3. Micro-robots
12: Problems
12.1. Deceptive 1 (Flash)
12.2. Deceptive 2 (Comb)
12.3. Deceptive 3 (Brush)
12.4. Alpine
12.5. Rosenbrock
12.6. Pressure vessel
12.7. Sphere
12.8. Traveling salesman: six cities
12.9. Traveling salesman: fourteen cities (Burma 14)
12.10. Tripod
12.11. Gear train
13: Source Codes
13.1. Random generation and sampling
13.2. Useful tools
13.3. Combinatorial operations
13.4. Random algorithm
13.5. Minimaliste algorithm
13.6. SPSO algorithm
13.7. APS algorithm
13.8. μ PSO algorithm
13.9. Problems
13.10. Treatment of results
13.11. Treatment of the Eff-Res
13.12. Histograms, polar diagrams
13.13. Other figures
13.14. Tests (bias, correlation)
Bibliography
Index
Both
End User License Agreement
Guide
Cover
Table of Contents
Begin Reading
List of Tables
1: Necessary Risk
Table 1.1. Permutation test cases. Probability of success after one, two and three attempts. The three algorithms are repetition-free and present the same average performance, as the conditions of the No Free Lunch Theorem (NFLT) are fulfilled
Table 1.2. Examples of positive correlation problems. The precise definitions of these problems are given in the appendix
Table 1.3. Three simple functions showing negative correlation
3: The Effects of Randomness
Table 3.1. Examples of algorithms inspired by the natural world, in approximate chronological order. This table is far from exhaustive. For certain methods, such as genetic algorithms, it is hard to identify a single founding article. In this case, one possible original reference has been given, but other articles may be just as relevant
4: Algorithms and Optimizers
Table 4.1. Use of randomness in Minimaliste
Table 4.2. Uses of randomness in PSO
5: Performance Criteria
Table 5.1. Global quality. Values for two optimizers for the square root problem, with threshold ε =0.01
6: Comparing Optimizers
Table 6.1. Nine problems, five optimizers. The values given, in descending order, are the minimum, mean, standard deviation and median. For the “deceptive” functions, the Random and Minimaliste algorithms proved to be most efficient
Table 6.2. Normalized means for three optimizers
Table 6.3. (SPSO, Pressure vessel). Performance can differ greatly in relation to the number of attempts (10,000 evaluations each, in this case), and these results may be unusable in cases of nonconvergence. The success rate is given with an acceptable error of 10
−6
Table 6.4. Minimaliste (40), pressure vessel problem. Results obtained using three different RNGs (100 attempts, 10,000 evaluations each). If the median or success rate criteria are used with a maximum acceptable error of 10
−9
, Mersenne-Twister is considerably inferior to the other two options
Table 6.5. Analysis grid for a test set
Table 6.6. Examples of test set analysis. The 0% in the fourth line shows that the test set given in this chapter is not suitable for use in comparing generalist algorithms
Table 6.7. Data can only be used to confirm (or reject) sufficiently precise assertions
9: A Pseudo-Scientific Article
Test functions
Test conditions
Results obtained using the test functions. The four values indicated in each cell are the median, the mean error, the standard deviation (in brackets) and the success rate. Note the strong performance of Zebra-G, even for notoriously difficult problems such as Rastrigin 30D
11: Unnecessary Randomness? List-based Optimizers
Table 11.1. Minimaliste (population 40), Alpine 2D, L-truncated lists using Mersenne-Twister. One hundred attempts, 1,000 evaluations. The performances obtained are only acceptable when the length exceeds the size of the population, where they become equivalent, or better, than those obtained using sequences of “infinite” length
Table 11.2. Comparison (SPSO, Mersenne-Twister) and (μPSO, L
5
) using Alpine 2D. Effort: 100 evaluations. For SPSO, 100 attempts are made in order to obtain strong convergence of the indicators. For μPSO, we simply carry out the five different possible attempts
Pages
Cover
ii
iii
iv
v
xi
xii
xiii
xiv
xv
xvi
1
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
49
51
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
133
134
135
136
137
139
140
141
142
143
144
145
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
293
294
“Le hasard ne fait toujours que la moitié du chemin”
(Luck will only get you halfway)
Yvon Rivard
Guided Randomness in Optimization
Volume 1
Maurice Clerc
Metaheuristics Set
coordinated by Nicolas Monmarché and Patrick Siarry
First published 2015 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2015
The rights of Maurice Clerc to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2015937136
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-805-5
Preface
About this book
This book is the final fruit of a long process, spanning almost 20 years. In 1997, I was involved in translating Earl D. Cox’s seminal book on fuzzy logic [COX 95] into French. At that time, I was a regular contributor to an online discussion board on this topic, through which I “met” James Kennedy, the co-inventor of particle swarm optimization (PSO), with Russell Eberhart [EBE 95]. I rapidly became involved in work on this method, with a focus on its mathematical aspects.
The original idea was to model interpersonal relationships (Jim is a social psychologist) and not, as is often stated, on the social behavior of bees, fish or other animals. The model was too simplistic to be useable; on the other hand, however, the resulting algorithm seemed to be able to identify the minimum of numerical functions, even in relatively complex cases, at a remarkable speed.
The situation was, in fact, too good to be true: solutions were being found too quickly. For the problems we were dealing with (still in 1995), the minimum was situated at the origin of the coordinate system, and PSO has a strong tendency to prioritize this area of the search space. The very first code also included an error which reinforced this bias.
This tendency was confirmed using more systematic experimentation, which also highlighted an additional bias, favoring the axes and diagonals of the coordinate system. A theoretical explanation was established considerably later [SPE 10]. Improved versions were created in the meantime, making PSO an efficient and widely used metaheuristic.
Observation of the bias led me to wonder whether this type of effect was a result of the way in which chance was used. One thing led to another, and I started to consider a number of different elements: the possibility of using tools to detect intrinsic biases in optimizers, the random number generators used in the context of optimization, the validity of comparisons of stochastic optimizers, and even the very necessity of chance and the possibility of replacing this element with deterministic techniques.
Most of these questions have also been considered by other researchers, and at least partial responses have been provided. Generally speaking, I receive around two articles on the subject of optimization to read each week: some already published and some awaiting publication. During the time I have been working on the subject, and particularly since the publication of my book on particle swarm optimization [CLE 06], I have read more than one thousand research papers, in addition to a number of theses and monographs.
In the case of pseudo-random number generators, authors generally either describe and use a stochastic algorithm, or prefer a deterministic method. The basic questions underpinning this technique, however, are rarely discussed at any length. For example, all of these algorithms presume that a structure is present to allow a problem to be solved, without the structure being explicitly discussed. Moreover, there is no systematic detection of intrinsic bias. To give a third example, in reality, there is no clear-cut distinction between random and deterministic elements, but rather a continuum of levels of randomness produced by generators; consequently, the same algorithm may perform differently based on the choice of pseudo-random generator. Furthermore, the best performance is not always obtained using the “best” generator.
Issues also exist concerning the reliability of the tests used to compare two algorithms, or to compare results when an arbitrary parameter, defined by the user, is introduced (e.g. a threshold value used to decide whether or not a test may be considered successful).
The aim of this book is to address these issues in greater detail.
In the course of my reading, I have noted a certain number of methodological errors or unfounded claims made in published works on the subject (including my own). As part of this book, I have compiled a list of these errors, which will be discussed in detail, for the benefit of future authors.
Organization of the book
This book is split into three main parts: reflections on the nature of chance, a comparison of optimizers and a comparison of tests. The book also includes a number of appendices. Readers are strongly advised to read chapters in this order. However, the book may also be considered as a collection of instructions and source codes (some of which are included in full and others are available online). Certain chapters may also be taken in isolation, such as Chapters 9 and 10.
Certain information that might be expected to be present in this book has been excluded, as it is readily available in published books or articles or online. This essentially concerns detailed information on certain pseudo-random number generators and the details of statistical tests which may be used to analyze the results produced by stochastic optimizers.
Any scientific document should provide with the elements necessary for reproduction of the experiment. In this case, the source codes used throughout the book are included.
Tools
A number of free programs were used in creating this book, and they come highly recommended. A significant part of the documentation for the book was collected online using the Startpage meta-search engine (https://startpage.com). The main advantage of this tool is that the same request is sent to several search engines simultaneously; results are then aggregated and presented to the user. Only a bare minimum of information concerning the origin of the request is transmitted to the search engines themselves.
The actual writing of the book was carried out using LYX (http://lyx.org), which allows simple generation of LATEX files, without requiring knowledge of the language. The bibliography was generated using Zotero (https://www.zotero.org/) with the LyZ extension to facilitate interfacing with LYX. Graphics were created using LibreOffice Calc (http://www.libreoffice.org/), Gimp (http://www.gimp.org/), Inkscape (http://www.inkscape.org), and SciLab (http://www.scilab.org), which is almost identical to MATLAB®.
The programs used were also written using SciLab.
All of the computer processes discussed in the book were carried out using the Linux Ubuntu operating system, on a 32-byte micro-computer, with a machine epsilon of 2.22 × 10−16 (this means that all calculations using positive numbers supposed to be lower than this value should be treated with extreme suspicion).
Key points
Following the principle of the “elevator pitch”, in our opinion, readers may wish to retain three key elements:
– stochastic optimization does not require the use of sophisticated pseudo-random number generators;
– several criteria should be taken into consideration when evaluating the performance of an optimizer, and reasonable convergence should be obtained in relation to the number of tests.
The third element, as with any publication (scientific or non-scientific), is that readers should always attempt to read behind the lines, decoding information which is not explicitly set down on paper.
Contact the author
For comments, suggestions or to report errors, the author can be contacted:
– by e-mail:
– via the publisher.
Maurice CLERC
March 2015
Introduction
The part played by chance in solving optimization problems is essentially due to the use of metaheuristics. Metaheuristics, by definition, are used for solving “difficult” problems for which no definitive method exists, although, as we will see, this definition is not clear-cut. “Random” drawing is a natural choice when making certain choices or applying certain rules; to do this, metaheuristics use one or more random number generators (RNG).
The first part of this book includes a discussion of the risks inherent to the use of chance in the context of optimization; the rest of this part essentially deals with RNGs. A distinction is made between three classes: (1) truly random generators, based on physical phenomena; (2) coded generators, which attempt to simulate physical phenomena as closely as possible, resulting in highly complex algorithms; and (3) simple codes, used to generate lists of numbers which may be used by metaheuristics. A discussion of the way in which RNGs can be manipulated to produce specific distributions, for example multimodal distributions, will then follow. Finally, to conclude this part, different techniques for the use of guided randomness will be considered.
In the second part of the book, we will show how the performance of an algorithm is dependent on the selected RNG; consequently, an optimizer is made up of an algorithm/RNG pairing. The way in which optimizers may be compared will also be considered, using an effort/outcome approach; this approach can be used to derive all of the classic criteria (medians, means, etc.) alongside more sophisticated criteria, for example using the notion of result quality. The interpretation of criteria values highlights the notions of estimation convergence and significant difference. Consideration will also be given to test cases, notably the biases which may be inherent toward different types of optimizers.
The third and final part contains appendices, including source codes. It notably includes reflections on “unnecessary randomness”, with a brief explanation of why and how the stochastic aspects of optimization could be avoided in certain cases. This discussion may be developed at a later date into an additional volume on the subject of deterministic optimization.
PART 1Randomness in Optimization
1Necessary Risk
Il arrive souvent de ne rien obtenir parce que l’on ne tente rien (Often, nothing is gained because nothing is attempted)
Jacques Deval
