139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Almost every month, a new optimization algorithm is proposed, often accompanied by the claim that it is superior to all those that came before it. However, this claim is generally based on the algorithm's performance on a specific set of test cases, which are not necessarily representative of the types of problems the algorithm will face in real life. This book presents the theoretical analysis and practical methods (along with source codes) necessary to estimate the difficulty of problems in a test set, as well as to build bespoke test sets consisting of problems with varied difficulties. The book formally establishes a typology of optimization problems, from which a reliable test set can be deduced. At the same time, it highlights how classic test sets are skewed in favor of different classes of problems, and how, as a result, optimizers that have performed well on test problems may perform poorly in real life scenarios.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 182
Veröffentlichungsjahr: 2019
Ähnliche
Table of Contents
Cover
Preface
The Essentials
Introduction
Reading guide
1 Some Definitions
1.1. Continuous case vs discrete case: when a theorem no longer holds
1.2. Landscape
2 Difficulty of the Difficulty
2.1. Effort and budgets
2.2. Acceptable solution
2.3. Difficulty vs complexity
2.4. Normalized roughness
2.5. Measure
δ
r,ε
2.6. Measure
δ
0
2.7. Measures non-NisB
2.8. Perceived difficulty
3 Landscape Typology
3.1. Reliable functions, misleading and neutral
3.2. Plateaus
3.3. Multimodal functions
3.4. Unimodal functions
4 LandGener
4.1. Examples
4.2. Generated files
4.3. Regular landscape
5 Test Cases
5.1. Structure of a representative test case
5.2. CEC 2005
5.3. CEC 2011
6 Difficulty vs Dimension
6.1. Rosenbrock function
6.2. Griewank function
6.3. Example of the normalized paraboloid
6.4. Normalized bi-paraboloid
6.5. Difficulty
δ
0
and dimension
7 Exploitation and Exploration vs Difficulty
7.1. Exploitation, an incomplete definition
7.2. Rigorous definitions
7.3. Balance profile
8 The Explo2 Algorithm
8.1. The algorithm
8.2. Subjective numerical summary of a distribution of results
9 Balance and Perceived Difficulty
9.1. Constant profile-based experiments
9.2. Calculated difficulty vs perceived difficulty
Appendix
A.1. Pigeonhole principle and monotonicity
A.2. Similarities between optimizers
A.3. Optimizer signature
A.4. Non-NisB difficulties of a unimodal function
A.5. A few test functions
A.6. Equivalent functions
A.7. Examples of deceptive functions
A.8. Empirical rules for a measure of difficulty
A.9. Optimizer effectiveness
A.10. Explo2+
A.11. Greedy
A.12. Source codes
A.13. LandGener landscapes
References
Index
End User License Agreement
Guide
Cover
Table of Contents
Begin Reading
Pages
ii
iii
iv
v
ix
x
xi
xii
xiii
xiv
1
2
3
4
5
6
7
8
9
10
11
12
13
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
65
66
67
68
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
125
126
127
128
129
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
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
197
Difficulties increase the nearer we get to the goal.
- Johann Wolfgang von Goethe
There are much less difficulties in solving a problem than in defining it.
- Joseph de Maistre
Iterative Optimizers
Difficulty Measures and Benchmarks
Maurice Clerc
First published 2019 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 Ltd27-37 St George’s RoadLondon SW19 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2019
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: 2019930133
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-78630-409-4
Preface
The Essentials
– Problems in a set of test cases can be classified according to several difficulty measures consistent with one another, in other words approximately giving the same ordering relation;
– these measures are valid for optimizers that explicitly or implicitly assume that “nearer is better”, in probability;
– some can be estimated using the Monte Carlo method, when the structure of the landscapes of the problems of the test case is unknown (basins of attraction, plateaus, local minima). Computations, however, can take a very long time;
– one of the measures presented requires an acceptable error threshold to be assumed, but its coding only takes a few lines. The other measure, somewhat more complex because it is based on position triplets, does not require an error threshold to be
a priori
defined, but is less reliable in the presence of plateaus;
– another difficulty indicator,
δ
0
, is proposed based on the structure of the landscape of the problem. It is consistent with previous ones and can be quickly calculated, but it requires the basins of attraction and plateaus of the problem landscape to be known;
– since this information is rarely given and difficult to find in conventional test cases, the LandGener program is specifically designed to create known structure landscapes, upon which
δ
0
is easily computable;
– a typology of all possible landscapes is established, essentially in terms of modality and plateau ratio, with the estimate of the relative significance of each class;
– some conventional test cases are analyzed based on this typology. It is shown that they are biased in favor of certain types of problems, for example, unimodal ones or ones without plateaus. However, the application of a difficulty measure makes it possible to classify their problems, from the easiest to the more selective;
– rigorous definitions of the concepts of usage and exploration are given, making them measurable. The main types of evolution of their ratio (balance profiles) are studied.
Maurice CLERC
January 2019
Introduction
Every year, not to say every month, a new optimization algorithm is proposed, accompanied by the creator’s claim that it is superior to the previous ones. This type of assertion is based on test results achieved with test cases, more specifically a selection of problems to which the algorithm is applied.
In Guided Randomness in Optimization (Clerc 2015), I show that it is easy to choose a set of test cases and the way the results are addressed to seemingly “justify” this superiority.
For example, consider the test case of Table I.1, which was actually used in an article1. With such a set of problems, an algorithm has to be defined whose signature (see section A.3) is biased in favor of the center of the search space to obtain good results. At the extreme, if the algorithm is to be seen as a black box inside of which the test case is introduced and that offers a solution, there is a “magical” box that finds the perfect solution of each of the functions in a time almost equal to zero2.
Table I.1.A biased test case in a published article (see footnote 1). The names of the functions have been kept
Name
Equation
Sphere
Rosenbrock
Ellipsoid
Rastrigin
Ackley
Obviously, if users, impressed by the optimistic conclusions of the presentation of the algorithm, try to apply it to their own problems, they will almost surely get very bad results.
This lack of reliability is due to the fact that the test set is not representative of the problems that the user will have to solve.
Moreover, in practice, it is interesting that a test case contains problems of different levels of difficulty. In fact, this allows a better hierarchization of the algorithms tested with this test case, knowing that users will not necessarily prefer the algorithm capable of solving most difficult problems if theirs are not so much and that in addition, this algorithm is very expensive in terms of computing resources. A precise definition of the term “difficulty” is therefore necessary. This is far from being trivial, because, as shown in the small example above, the difficulty of an optimization depends on the optimizer being used.
Therefore, after reading this book, you should be able, in principle:
– to analyze the structure of a set of test cases and to deduce therefrom which types of optimizers it promotes;
– to build your own set of test cases, with given characteristics (class of optimizers under consideration, levels of difficulty);
– to perform a well-based critical assessment on optimizers presented in the literature.
Reading guide
This book, short but dense (beware!), is actually a collection of studies related to the question “How can optimizers be reliably compared?”. As such, chapters can be read almost independently of each other. It is, however, advisable to start with the chapter of definitions, some not being completely conventional.
Based on your knowledge of the subject and your areas of interest, it is thus possible, for example, to directly consult Chapter 6, even if, for the very last section, it is necessary to have previously studied a difficulty measure presented in Chapter 2.
Similarly, if you are a practitioner especially curious to see how “customized” landscapes can be created, Chapter 4 on the LandGener program is right for you. On the contrary, the chapter on the typology of landscapes (Chapter 3), full of mathematical formulas, may appear to be rather boring and one could just browse the conclusions, or even ignore it completely.
And, of course, the various sections of the appendix are even more independent and non-essential, despite the fact that they can provide useful information, such as examples of deceptive functions and small codes sources. Regarding the latter, in fact, it should be noted that the main ones are not given here but may be downloaded (see www.iste.co.uk/clerc/iterative.zip).
More comprehensively, here are some observations on each chapter (Excluding the Appendix):
–
Chapter 1
: “Some definitions”. The most important ones are those concerning basins, plateaus and structures, but if readers intend to avoid
Chapter 3
, it is alternatively possible, as a first step, to skip this chapter and to merely consider intuitive notions.
–
Chapter 2
: “Difficulty of the difficulty”. The difficulty measures that will then be used almost everywhere are defined here. This is therefore a chapter to be almost necessarily read.
–
Chapter 3
: Landscape typology”. One to be skipped if the reader is allergic to combinatorial computations. Nonetheless, it might prove useful to take a look at the findings.
–
Chapter 4
: “LandGener”. It is essentially the presentation of principles allowing for the “customized” creation of landscapes – and, therefore, of test cases – with a few examples.
–
Chapter 5
: “Test cases”. Critical analysis of two sets of conventional test cases. It is made according to the typology seen in
Chapter 3
, but it is not really necessary to have read the latter if the reader trusts its conclusions!
–
Chapter 6
: “Difficulty vs dimension”. A small study around the notion, not always correct, that the difficulty increases with the dimension (the number of variables) of the problem.
–
Chapter 7
: “Exploitation and exploration vs difficulty”. In fact, this chapter and the next one form a whole. Exploitation and exploration concepts, often merely qualitative, are formally defined and measurable. The possible evolutions of their ratios (balance profiles) are studied.
–
Chapter 8
: “The Explo2 algorithm”. As an example, it is shown that it is possible to write a small optimizer explicitly using a predefined balance profile and that it is relatively effective despite being greedy in computational time. This is probably the chapter most likely to incur successful developments.
–
Chapter 9
: “Balance and perceived difficulty”. Slightly heterogeneous, but the two experimental studies that it contains are too short to justify specific chapters. One concerns the impact of the profile balance on performance, and the other makes it possible to insist on the fact that a difficulty measure only gives an ordering relation on a set of problems, without prejudice to quantitative differences between the difficulties actually collected by a given optimizer.
1
I do not provide the reference because it does not seem useful to increase the number of citations. Note though that some very similar ones have also been published.
2
The algorithm contained in the box is simply:
– evaluate the point (0, 0,…, 0);
– evaluate the point (1, 1,…, 1);
– propose the best of both as a solution.
