1simulation::annealing(n) Tcl Simulation Tools simulation::annealing(n)
2______________________________________________________________________________
6
8 simulation::annealing - Simulated annealing
9
11 package require Tcl ?8.4?
12 package require simulation::annealing 0.2
14 ::simulation::annealing::getOption keyword
16 ::simulation::annealing::hasOption keyword
18 ::simulation::annealing::setOption keyword value
20 ::simulation::annealing::findMinimum args
22 ::simulation::annealing::findCombinatorialMinimum args
24______________________________________________________________________________
26
28 The technique of simulated annealing provides methods to estimate the
29 global optimum of a function. It is described in some detail on the
30 Wiki http://wiki.tcl.tk/.... The idea is simple:
31 • randomly select points within a given search space
33 • evaluate the function to be optimised for each of these points
35 and select the point that has the lowest (or highest) function
36 value or - sometimes - accept a point that has a less optimal
37 value. The chance by which such a non-optimal point is accepted
38 diminishes over time.
39 • Accepting less optimal points means the method does not neces‐
41 sarily get stuck in a local optimum and theoretically it is ca‐
42 pable of finding the global optimum within the search space.
43 The method resembles the cooling of material, hence the name.
45 The package simulation::annealing offers the command findMinimum:
47 puts [::simulation::annealing::findMinimum -trials 300 -parameters {x -5.0 5.0 y -5.0 5.0} -function {$x*$x+$y*$y+sin(10.0*$x)+4.0*cos(20.0*$y)}]
50 prints the estimated minimum value of the function f(x,y) =
52 x**2+y**2+sin(10*x)+4*cos(20*y) and the values of x and y where the
53 minimum was attained:
54 result -4.9112922923 x -0.181647676593 y 0.155743646974
57
60 The package defines the following auxiliary procedures:
61 ::simulation::annealing::getOption keyword
63 Get the value of an option given as part of the findMinimum com‐
64 mand.
65 string keyword
67 Given keyword (without leading minus)
68 ::simulation::annealing::hasOption keyword
71 Returns 1 if the option is available, 0 if not.
72 string keyword
74 Given keyword (without leading minus)
75 ::simulation::annealing::setOption keyword value
78 Set the value of the given option.
79 string keyword
81 Given keyword (without leading minus)
82 string value
84 (New) value for the option
85 The main procedures are findMinimum and findCombinatorialMinimum:
87 ::simulation::annealing::findMinimum args
89 Find the minimum of a function using simulated annealing. The
90 function and the method's parameters is given via a list of key‐
91 word-value pairs.
92 int n List of keyword-value pairs, all of which are available
94 during the execution via the getOption command.
95 ::simulation::annealing::findCombinatorialMinimum args
97 Find the minimum of a function of discrete variables using simu‐
98 lated annealing. The function and the method's parameters is
99 given via a list of keyword-value pairs.
100 int n List of keyword-value pairs, all of which are available
102 during the execution via the getOption command.
103 The findMinimum command predefines the following options:
105 • -parameters list: triples defining parameters and ranges
107 • -function expr: expression defining the function
109 • -code body: body of code to define the function (takes prece‐
111 dence over -function). The code should set the variable "result"
112 • -init code: code to be run at start up -final code: code to be
114 run at the end -trials n: number of trials before reducing the
115 temperature -reduce factor: reduce the temperature by this fac‐
116 tor (between 0 and 1) -initial-temp t: initial temperature
117 -scale s: scale of the function (order of magnitude of the val‐
118 ues) -estimate-scale y/n: estimate the scale (only if -scale is
119 not present) -verbose y/n: print detailed information on
120 progress to the report file (1) or not (0) -reportfile file:
121 opened file to print to (defaults to stdout)
122 Any other options can be used via the getOption procedure in the body.
124 The findCombinatorialMinimum command predefines the following options:
125 • -number-params n: number of binary parameters (the solution
127 space consists of lists of 1s and 0s). This is a required op‐
128 tion.
129 • -initial-values: list of 1s and 0s constituting the start of the
131 search.
132 The other predefined options are identical to those of findMinimum.
134
136 The procedure findMinimum works by constructing a temporary procedure
137 that does the actual work. It loops until the point representing the
138 estimated optimum does not change anymore within the given number of
139 trials. As the temperature gets lower and lower the chance of accepting
140 a point with a higher value becomes lower too, so the procedure will in
141 practice terminate.
142 It is possible to optimise over a non-rectangular region, but some care
144 must be taken:
145 • If the point is outside the region of interest, you can specify
147 a very high value.
148 • This does mean that the automatic determination of a scale fac‐
150 tor is out of the question - the high function values that force
151 the point inside the region would distort the estimation.
152 Here is an example of finding an optimum inside a circle:
154 puts [::simulation::annealing::findMinimum -trials 3000 -reduce 0.98 -parameters {x -5.0 5.0 y -5.0 5.0} -code {
157 if { hypot($x-5.0,$y-5.0) < 4.0 } {
158 set result [expr {$x*$x+$y*$y+sin(10.0*$x)+4.0*cos(20.0*$y)}]
159 } else {
160 set result 1.0e100
161 }
162 }]
163 The method is theoretically capable of determining the global optimum,
165 but often you need to use a large number of trials and a slow reduction
166 of temperature to get reliable and repeatable estimates.
167 You can use the -final option to use a deterministic optimization
169 method, once you are sure you are near the required optimum.
170 The findCombinatorialMinimum procedure is suited for situations where
172 the parameters have the values 0 or 1 (and there can be many of them).
173 Here is an example:
174 • We have a function that attains an absolute minimum if the first
176 ten numbers are 1 and the rest is 0:
177 proc cost {params} {
180 set cost 0
181 foreach p [lrange $params 0 9] {
182 if { $p == 0 } {
183 incr cost
184 }
185 }
186 foreach p [lrange $params 10 end] {
187 if { $p == 1 } {
188 incr cost
189 }
190 }
191 return $cost
192 }
193 • We want to find the solution that gives this minimum for various
196 lengths of the solution vector params:
197 foreach n {100 1000 10000} {
200 break
201 puts "Problem size: $n"
202 puts [::simulation::annealing::findCombinatorialMinimum -trials 300 -verbose 0 -number-params $n -code {set result [cost $params]}]
203 }
204 • As the vector grows, the computation time increases, but the
207 procedure will stop if some kind of equilibrium is reached. To
208 achieve a useful solution you may want to try different values
209 of the trials parameter for instance. Also ensure that the func‐
210 tion to be minimized depends on all or most parameters - see the
211 source code for a counter example and run that.
212
214 math, optimization, simulated annealing
215
217 Mathematics
218
220 Copyright (c) 2008 Arjen Markus <arjenmarkus@users.sourceforge.net>
221tcllib 0.2 simulation::annealing(n)