annealing man page on MacOSX

Man page or keyword search:  
man Server   23457 pages
apropos Keyword Search (all sections)
Output format
MacOSX logo
[printable version]

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 neces‐
	      sarily 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 com‐
	      mand.

	      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 key‐
	      word-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 simu‐
	      lated 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	prece‐
	      dence 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 fac‐
	      tor (between 0  and  1)  -initial-temp  t:  initial  temperature
	      -scale  s: scale of the function (order of magnitude of the val‐
	      ues) -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  fac‐
	      tor 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 func‐
	      tion 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)
[top]

List of man pages available for MacOSX

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
...................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net