Package: tcllib, Version: CVS HEAD

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:

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.
TypeNameMode
stringkeyword
  Given keyword (without leading minus)

::simulation::annealing::hasOption keyword
Returns 1 if the option is available, 0 if not.
TypeNameMode
stringkeyword
  Given keyword (without leading minus)

::simulation::annealing::setOption keyword value
Set the value of the given option.
TypeNameMode
stringkeyword
  Given keyword (without leading minus)
stringvalue
  (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.
TypeNameMode
intn
  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.
TypeNameMode
intn
  List of keyword-value pairs, all of which are available during the execution via the getOption command.
The findMinimum command predefines the following options: Any other options can be used via the getOption procedure in the body. The findCombinatorialMinimum command predefines the following options: 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:

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:

KEYWORDS

math, optimization, simulated annealing