1math::probopt(n) Tcl Math Library math::probopt(n)
2______________________________________________________________________________
6
8 math::probopt - Probabilistic optimisation methods
9
11 package require Tcl 8.6
12 package require TclOO
14 package require math::probopt 1
16 ::math::probopt::pso function bounds args
18 ::math::probopt::sce function bounds args
20 ::math::probopt::diffev function bounds args
22 ::math::probopt::lipoMax function bounds args
24 ::math::probopt::adaLipoMax function bounds args
26______________________________________________________________________________
28
30 The purpose of the math::probopt package is to provide various optimi‐
31 sation algorithms that are based on probabilistic techniques. The re‐
32 sults of these algorithms may therefore vary from one run to the next.
33 The algorithms are all well-known and well described and proponents
34 generally claim they are efficient and reliable.
35 As most of these algorithms have one or more tunable parameters or even
37 variations, the interface to each accepts options to set these parame‐
38 ters or the select the variation. These take the form of key-value
39 pairs, for instance, -iterations 100.
40 This manual does not offer any recommendations with regards to these
42 algorithms, nor does it provide much in the way of guidelines for the
43 parameters. For this we refer to online articles on the algorithms in
44 question.
45 A few notes, however:
47 • With the exception of LIPO, the algorithms are capable of deal‐
49 ing with irregular (non-smooth) and even discontinuous func‐
50 tions.
51 • The results depend on the random number seeding and are likely
53 not to be very accurate, especially if the function varies
54 slowly in the vicinty of the optimum. They do give a good start‐
55 ing point for a deterministic algorithm.
56 The collection consists of the following algorithms:
58 • PSO - particle swarm optimisation
60 • SCE - shuffled complexes evolution
62 • DE - differential evolution
64 • LIPO - Lipschitz optimisation
66 The various procedures have a uniform interface:
68 set result [::math::probopt::algorithm function bounds args]
71 The arguments have the following meaning:
73 • The argument function is the name of the procedure that evalu‐
75 ates the function. Its interface is:
76 set value [function coords]
79 where coords is a list of coordinates at which to evaluate the
82 function. It is supposed to return the function value.
83 • The argument bounds is a list of pairs of minimum and maximum
85 for each coordinate. This list implicitly determines the dimen‐
86 sion of the coordinate space in which the optimum is to be
87 sought, for instance for a function like x**2 + (y-1)**4, you
88 may specify the bounds as {{-1 1} {-1 1}}, that is, two pairs
89 for the two coordinates.
90 • The rest (args) consists of zero or more key-value pairs to
92 specify the options. Which options are supported by which algo‐
93 rithm, is documented below.
94 The result of the various optimisation procedures is a dictionary con‐
96 taining at least the following elements:
97 • optimum-coordinates is a list containing the coordinates of the
99 optimum that was found.
100 • optimum-value is the function value at those coordinates.
102 • evaluations is the number of function evaluations.
104 • best-values is a list of successive best values, obtained as
106 part of the iterations.
107
109 The algorithms in the package are the following:
110 ::math::probopt::pso function bounds args
112 The "particle swarm optimisation" algorithm uses the idea that
113 the candidate optimum points should swarm around the best point
114 found so far, with variations to allow for improvements.
115 It recognises the following options:
117 • -swarmsize number: Number of particles to consider (de‐
119 fault: 50)
120 • -vweight value: Weight for the current "velocity"
122 (0-1, default: 0.5)
123 • -pweight value: Weight for the individual particle's
125 best position (0-1, default: 0.3)
126 • -gweight value: Weight for the "best" overall position
128 as per particle (0-1, default: 0.3)
129 • -type local/global: Type of optimisation
131 • -neighbours number: Size of the neighbourhood (default:
133 5, used if "local")
134 • -iterations number: Maximum number of iterations
136 • -tolerance value: Absolute minimal improvement for mini‐
138 mum value
139 ::math::probopt::sce function bounds args
141 The "shuffled complex evolution" algorithm is an extension of
142 the Nelder-Mead algorithm that uses multiple complexes and reor‐
143 ganises these complexes to find the "global" optimum.
144 It recognises the following options:
146 • -complexes number: Number of particles to con‐
148 sider (default: 2)
149 • -mincomplexes number: Minimum number of complexes
151 (default: 2; not currently used)
152 • -newpoints number: Number of new points to be
154 generated (default: 1)
155 • -shuffle number: Number of iterations after
157 which to reshuffle the complexes (if set to 0, the de‐
158 fault, a number will be calculated from the number of di‐
159 mensions)
160 • -pointspercomplex number: Number of points per complex
162 (if set to 0, the default, a number will be calculated
163 from the number of dimensions)
164 • -pointspersubcomplex number: Number of points per subcom‐
166 plex (used to select the best points in each complex; if
167 set to 0, the default, a number will be calculated from
168 the number of dimensions)
169 • -iterations number: Maximum number of iterations
171 (default: 100)
172 • -maxevaluations number: Maximum number of function
174 evaluations (when this number is reached the iteration is
175 broken off. Default: 1000 million)
176 • -abstolerance value: Absolute minimal improvement
178 for minimum value (default: 0.0)
179 • -reltolerance value: Relative minimal improvement
181 for minimum value (default: 0.001)
182 ::math::probopt::diffev function bounds args
184 The "differential evolution" algorithm uses a number of initial
185 points that are then updated using randomly selected points. It
186 is more or less akin to genetic algorithms. It is controlled by
187 two parameters, factor and lambda, where the first determines
188 the update via random points and the second the update with the
189 best point found sofar.
190 It recognises the following options:
192 • -iterations number: Maximum number of iterations
194 (default: 100)
195 • -number number: Number of point to work with
197 (if set to 0, the default, it is calculated from the num‐
198 ber of dimensions)
199 • -factor value: Weight of randomly selected
201 points in the updating (0-1, default: 0.6)
202 • -lambda value: Weight of the best point
204 found so far in the updating (0-1, default: 0.0)
205 • -crossover value: Fraction of new points to be
207 considered for replacing the old ones (0-1, default: 0.5)
208 • -maxevaluations number: Maximum number of function
210 evaluations (when this number is reached the iteration is
211 broken off. Default: 1000 million)
212 • -abstolerance value: Absolute minimal improvement
214 for minimum value (default: 0.0)
215 • -reltolerance value: Relative minimal improvement
217 for minimum value (default: 0.001)
218 ::math::probopt::lipoMax function bounds args
220 The "Lipschitz optimisation" algorithm uses the "Lipschitz"
221 property of the given function to find a maximum in the given
222 bounding box. There are two variants, lipoMax assumes a fixed
223 estimate for the Lipschitz parameter.
224 It recognises the following options:
226 • -iterations number: Number of iterations (equals
228 the actual number of function evaluations, default: 100)
229 • -lipschitz value: Estimate of the Lipschitz pa‐
231 rameter (default: 10.0)
232 ::math::probopt::adaLipoMax function bounds args
234 The "adaptive Lipschitz optimisation" algorithm uses the "Lip‐
235 schitz" property of the given function to find a maximum in the
236 given bounding box. The adaptive variant actually uses two
237 phases to find a suitable estimate for the Lipschitz parameter.
238 This is controlled by the "Bernoulli" parameter.
239 When you specify a large number of iterations, the algorithm may
241 take a very long time to complete as it is trying to improve on
242 the Lipschitz parameter and the chances of hitting a better es‐
243 timate diminish fast.
244 It recognises the following options:
246 • -iterations number: Number of iterations (equals
248 the actual number of function evaluations, default: 100)
249 • -bernoulli value: Parameter for random deci‐
251 sions (exploration versus exploitation, default: 0.1)
252
254 The various algorithms have been described in on-line publications.
255 Here are a few:
256 • PSO: Maurice Clerc, Standard Particle Swarm Optimisation (2012)
258 https://hal.archives-ouvertes.fr/file/index/docid/764996/file‐
259 name/SPSO_descriptions.pdf
260 Alternatively: https://en.wikipedia.org/wiki/Particle_swarm_op‐
262 timization
263 • SCE: Qingyuan Duan, Soroosh Sorooshian, Vijai K. Gupta, Optimal
265 use offo the SCE-UA global optimization method for calibrating
266 watershed models (1994), Journal of Hydrology 158, pp 265-284
267 https://www.researchgate.net/publication/223408756_Opti‐
269 mal_Use_of_the_SCE-UA_Global_Optimization_Method_for_Calibrat‐
270 ing_Watershed_Models
271 • DE: Rainer Storn and Kenneth Price, Differential Evolution - A
273 simple and efficient adaptivescheme for globaloptimization over
274 continuous spaces (1996)
275 http://www1.icsi.berkeley.edu/~storn/TR-95-012.pdf
277 • LIPO: Cedric Malherbe and Nicolas Vayatis, Global optimization
279 of Lipschitz functions, (june 2017)
280 https://arxiv.org/pdf/1703.02628.pdf
282
284 mathematics, optimisation, probabilistic calculations
285
287 Mathematics
288tcllib 1 math::probopt(n)