NAME¶
simulation::annealing - Simulated annealing
SYNOPSIS¶
package require
Tcl ?8.4?
package require
simulation::annealing 0.2
::simulation::annealing::getOption keyword
::simulation::annealing::hasOption keyword
::simulation::annealing::setOption keyword value
::simulation::annealing::findMinimum args
::simulation::annealing::findCombinatorialMinimum args
DESCRIPTION¶
The technique of
simulated annealing provides methods to estimate the
global optimum of a function. It is described in some detail on the Wiki
http://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 package
simulation::annealing offers the command
findMinimum:
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::getOption keyword
- Get the value of an option given as part of the findMinimum
command.
- string keyword
- Given keyword (without leading minus)
- ::simulation::annealing::hasOption keyword
- Returns 1 if the option is available, 0 if not.
- string keyword
- Given keyword (without leading minus)
- ::simulation::annealing::setOption keyword value
- Set the value of the given option.
- string keyword
- Given keyword (without leading minus)
- string value
- (New) value for the option
The main procedures are
findMinimum and
findCombinatorialMinimum:
- ::simulation::annealing::findMinimum args
- Find the minimum of a function using simulated annealing. The function and
the method's parameters is given via a list of keyword-value pairs.
- int n
- List of keyword-value pairs, all of which are available during the
execution via the getOption command.
- ::simulation::annealing::findCombinatorialMinimum args
- Find 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.
- int n
- List of keyword-value pairs, all of which are available during the
execution via the getOption command.
The
findMinimum command predefines the following options:
- •
- -parameters list: triples defining parameters and ranges
- •
- -function expr: expression defining the function
- •
- -code body: body of code to define the function (takes precedence
over -function). The code should set the variable
"result"
- •
- -init code: code to be run at start up -final code: code to
be run at the end -trials n: number of trials before reducing the
temperature -reduce factor: reduce the temperature by this factor
(between 0 and 1) -initial-temp t: initial temperature -scale
s: scale of the function (order of magnitude of the values)
-estimate-scale y/n: estimate the scale (only if -scale is
not present) -verbose y/n: print detailed information on progress
to the report file (1) or not (0) -reportfile file: opened file to
print to (defaults to stdout)
Any other options can be used via the getOption procedure in the body. The
findCombinatorialMinimum command predefines the following options:
- •
- -number-params n: 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 of
findMinimum.
TIPS¶
The procedure
findMinimum works 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
-final option to use a deterministic optimization method,
once you are sure you are near the required optimum.
The
findCombinatorialMinimum procedure 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 vector params:
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>