Provided by: tcllib_1.14-dfsg-1_all

**NAME**

simulation::annealing - Simulated annealing

**SYNOPSIS**

package requireTcl?8.4?package requiresimulation::annealing0.2::simulation::annealing::getOptionkeyword::simulation::annealing::hasOptionkeyword::simulation::annealing::setOptionkeywordvalue::simulation::annealing::findMinimumargs::simulation::annealing::findCombinatorialMinimumargs_________________________________________________________________

**DESCRIPTION**

The technique ofsimulatedannealingprovides methods to estimate the global optimum of a function. It is described in some detail on the Wikihttp://wiki.tcl.tk/.... The idea is simple: · randomly select points within a given search space · evaluate the function to be optimised for each of these points and select the point that has the lowest (or highest) function value or - sometimes - accept a point that has a less optimal value. The chance by which such a non-optimal point is accepted diminishes over time. · Accepting less optimal points means the method does not necessarily get stuck in a local optimum and theoretically it is capable of finding the global optimum within the search space. The method resembles the cooling of material, hence the name. The packagesimulation::annealingoffers the commandfindMinimum: 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)}] prints the estimated minimum value of the function f(x,y) =x**2+y**2+sin(10*x)+4*cos(20*y)and the values of x and y where the minimum was attained: result -4.9112922923 x -0.181647676593 y 0.155743646974

**PROCEDURES**

The package defines the following auxiliary procedures:::simulation::annealing::getOptionkeywordGet the value of an option given as part of thefindMinimumcommand. stringkeywordGiven keyword (without leading minus)::simulation::annealing::hasOptionkeywordReturns 1 if the option is available, 0 if not. stringkeywordGiven keyword (without leading minus)::simulation::annealing::setOptionkeywordvalueSet the value of the given option. stringkeywordGiven keyword (without leading minus) stringvalue(New) value for the option The main procedures arefindMinimumandfindCombinatorialMinimum:::simulation::annealing::findMinimumargsFind the minimum of a function using simulated annealing. The function and the method's parameters is given via a list of keyword-value pairs. intnList of keyword-value pairs, all of which are available during the execution via thegetOptioncommand.::simulation::annealing::findCombinatorialMinimumargsFind the minimum of a function of discrete variables using simulated annealing. The function and the method's parameters is given via a list of keyword-value pairs. intnList of keyword-value pairs, all of which are available during the execution via thegetOptioncommand. ThefindMinimumcommand predefines the following options: ·-parameterslist: triples defining parameters and ranges ·-functionexpr: expression defining the function ·-codebody: body of code to define the function (takes precedence over-function). The code should set the variable "result" ·-initcode: code to be run at start up-finalcode: code to be run at the end-trialsn: number of trials before reducing the temperature-reducefactor: reduce the temperature by this factor (between 0 and 1)-initial-tempt: initial temperature-scales: scale of the function (order of magnitude of the values)-estimate-scaley/n: estimate the scale (only if-scaleis not present)-verbosey/n: print detailed information on progress to the report file (1) or not (0)-reportfilefile: opened file to print to (defaults to stdout) Any other options can be used via the getOption procedure in the body. ThefindCombinatorialMinimumcommand predefines the following options: ·-number-paramsn: number of binary parameters (the solution space consists of lists of 1s and 0s). This is a required option. ·-initial-values: list of 1s and 0s constituting the start of the search. The other predefined options are identical to those offindMinimum.

**TIPS**

The procedurefindMinimumworks by constructing a temporary procedure that does the actual work. It loops until the point representing the estimated optimum does not change anymore within the given number of trials. As the temperature gets lower and lower the chance of accepting a point with a higher value becomes lower too, so the procedure will in practice terminate. It is possible to optimise over a non-rectangular region, but some care must be taken: · If the point is outside the region of interest, you can specify a very high value. · This does mean that the automatic determination of a scale factor is out of the question - the high function values that force the point inside the region would distort the estimation. Here is an example of finding an optimum inside a circle: puts [::simulation::annealing::findMinimum -trials 3000 -reduce 0.98 -parameters {x -5.0 5.0 y -5.0 5.0} -code { if { hypot($x-5.0,$y-5.0) < 4.0 } { set result [expr {$x*$x+$y*$y+sin(10.0*$x)+4.0*cos(20.0*$y)}] } else { set result 1.0e100 } }] The method is theoretically capable of determining the global optimum, but often you need to use a large number of trials and a slow reduction of temperature to get reliable and repeatable estimates. You can use the-finaloption to use a deterministic optimization method, once you are sure you are near the required optimum. ThefindCombinatorialMinimumprocedure is suited for situations where the parameters have the values 0 or 1 (and there can be many of them). Here is an example: · We have a function that attains an absolute minimum if the first ten numbers are 1 and the rest is 0: proc cost {params} { set cost 0 foreach p [lrange $params 0 9] { if { $p == 0 } { incr cost } } foreach p [lrange $params 10 end] { if { $p == 1 } { incr cost } } return $cost } · We want to find the solution that gives this minimum for various lengths of the solution vectorparams: foreach n {100 1000 10000} { break puts "Problem size: $n" puts [::simulation::annealing::findCombinatorialMinimum -trials 300 -verbose 0 -number-params $n -code {set result [cost $params]}] } · As the vector grows, the computation time increases, but the procedure will stop if some kind of equilibrium is reached. To achieve a useful solution you may want to try different values of the trials parameter for instance. Also ensure that the function to be minimized depends on all or most parameters - see the source code for a counter example and run that.

**KEYWORDS**

math, optimization, simulated annealing

**CATEGORY**

Mathematics

**COPYRIGHT**

Copyright (c) 2008 Arjen Markus <arjenmarkus@users.sourceforge.net>