path: root/tcllib/idoc/man/files/modules/simulation/annealing.n

'\"
'\" Generated from file 'annealing\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2008 Arjen Markus <arjenmarkus@users\&.sourceforge\&.net>
'\"
.TH "simulation::annealing" n 0\&.2 tcllib "Tcl Simulation Tools"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
simulation::annealing \- Simulated annealing
.SH SYNOPSIS
package require \fBTcl  ?8\&.4?\fR
.sp
package require \fBsimulation::annealing  0\&.2\fR
.sp
\fB::simulation::annealing::getOption\fR \fIkeyword\fR
.sp
\fB::simulation::annealing::hasOption\fR \fIkeyword\fR
.sp
\fB::simulation::annealing::setOption\fR \fIkeyword\fR \fIvalue\fR
.sp
\fB::simulation::annealing::findMinimum\fR \fIargs\fR
.sp
\fB::simulation::annealing::findCombinatorialMinimum\fR \fIargs\fR
.sp
.BE
.SH DESCRIPTION
.PP
The technique of \fIsimulated annealing\fR provides methods to
estimate the global optimum of a function\&. It is described in some
detail on the Wiki \fIhttp://wiki\&.tcl\&.tk/\&.\&.\&.\fR\&. The idea is simple:
.IP \(bu
randomly select points within a given search space
.IP \(bu
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\&.
.IP \(bu
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\&.
.PP
The method resembles the cooling of material, hence the name\&.
.PP
The package \fIsimulation::annealing\fR offers the command \fIfindMinimum\fR:
.CS


    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)}]

.CE
prints the estimated minimum value of the function f(x,y) =
\fIx**2+y**2+sin(10*x)+4*cos(20*y)\fR and the values of x and y where
the minimum was attained:
.CS


result -4\&.9112922923 x -0\&.181647676593 y 0\&.155743646974

.CE
.SH PROCEDURES
The package defines the following auxiliary procedures:
.TP
\fB::simulation::annealing::getOption\fR \fIkeyword\fR
Get the value of an option given as part of the \fIfindMinimum\fR
command\&.
.RS
.TP
string \fIkeyword\fR
Given keyword (without leading minus)
.RE
.sp
.TP
\fB::simulation::annealing::hasOption\fR \fIkeyword\fR
Returns 1 if the option is available, 0 if not\&.
.RS
.TP
string \fIkeyword\fR
Given keyword (without leading minus)
.RE
.sp
.TP
\fB::simulation::annealing::setOption\fR \fIkeyword\fR \fIvalue\fR
Set the value of the given option\&.
.RS
.TP
string \fIkeyword\fR
Given keyword (without leading minus)
.TP
string \fIvalue\fR
(New) value for the option
.RE
.PP
The main procedures are \fIfindMinimum\fR and \fIfindCombinatorialMinimum\fR:
.TP
\fB::simulation::annealing::findMinimum\fR \fIargs\fR
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\&.
.RS
.TP
int \fIn\fR
List of keyword-value pairs, all of which are available
during the execution via the \fIgetOption\fR command\&.
.RE
.TP
\fB::simulation::annealing::findCombinatorialMinimum\fR \fIargs\fR
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\&.
.RS
.TP
int \fIn\fR
List of keyword-value pairs, all of which are available
during the execution via the \fIgetOption\fR command\&.
.RE
.PP
The \fIfindMinimum\fR command predefines the following options:
.IP \(bu
\fI-parameters list\fR: triples defining parameters and ranges
.IP \(bu
\fI-function expr\fR: expression defining the function
.IP \(bu
\fI-code body\fR: body of code to define the function (takes
precedence over \fI-function\fR)\&. The code should set the variable
"result"
.IP \(bu
\fI-init code\fR: code to be run at start up
\fI-final code\fR: code to be run at the end
\fI-trials n\fR: number of trials before reducing the temperature
\fI-reduce factor\fR: reduce the temperature by this factor (between 0 and 1)
\fI-initial-temp t\fR: initial temperature
\fI-scale s\fR: scale of the function (order of magnitude of the values)
\fI-estimate-scale y/n\fR: estimate the scale (only if \fI-scale\fR
is not present)
\fI-verbose y/n\fR: print detailed information on progress to the
report file (1) or not (0)
\fI-reportfile file\fR: opened file to print to (defaults to stdout)
.PP
Any other options can be used via the getOption procedure
in the body\&.
The \fIfindCombinatorialMinimum\fR command predefines the following
options:
.IP \(bu
\fI-number-params n\fR: number of binary parameters (the solution
space consists of lists of 1s and 0s)\&. This is a required option\&.
.IP \(bu
\fI-initial-values\fR: list of 1s and 0s constituting the start of
the search\&.
.PP
The other predefined options are identical to those of \fIfindMinimum\fR\&.
.SH TIPS
The procedure \fIfindMinimum\fR 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\&.
.PP
It is possible to optimise over a non-rectangular region, but some care
must be taken:
.IP \(bu
If the point is outside the region of interest, you can specify a very
high value\&.
.IP \(bu
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\&.
.PP
Here is an example of finding an optimum inside a circle:
.CS


    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
            }
        }]

.CE
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\&.
.PP
You can use the \fI-final\fR option to use a deterministic optimization
method, once you are sure you are near the required optimum\&.
.PP
The \fIfindCombinatorialMinimum\fR 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:
.IP \(bu
We have a function that attains an absolute minimum if the first ten
numbers are 1 and the rest is 0:
.CS


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
}

.CE
.IP \(bu
We want to find the solution that gives this minimum for various lengths
of the solution vector \fIparams\fR:
.CS


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]}]
}

.CE
.IP \(bu
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\&.
.PP
.SH KEYWORDS
math, optimization, simulated annealing
.SH CATEGORY
Mathematics
.SH COPYRIGHT
.nf
Copyright (c) 2008 Arjen Markus <arjenmarkus@users\&.sourceforge\&.net>

.fi