Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

simulation::annealing(n)                    Tcl Simulation Tools                    simulation::annealing(n)



____________________________________________________________________________________________________________

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 opti-mum optimum
              mum 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(1_*x)+4*cos(2_*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 param-eters parameters
              eters 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: num-ber number
              ber 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 vec-
              tor 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>




simulation                                           0.2                            simulation::annealing(n)