About Chandra Archive Proposer Instruments & Calibration Newsletters Data Analysis HelpDesk Calibration Database NASA Archives & Centers Chandra Science Links

Skip the navigation links
Last modified: December 2006

URL: http://cxc.harvard.edu/ciao3.4/simul-ann-1.html
Hardcopy (PDF): A4 | Letter
AHELP for CIAO 3.4 simul-ann-1 Context: sherpa

Synopsis

A simulated annealing search, with one parameter varied at each step.

Syntax

simul-ann-1  [nloop] [tchn] [nsamp] [iseed] [tiny]

Description

The SIMUL-ANN-1 method is a simulated annealing method. Such a method is said to be useful when a desired global minimum is among many other local minima. It has been derived via an analogy to how metals cool and anneal; as the liquid metal is cooled slowly, the atoms are able to settle into their minimum energy state, i.e. form a crystal. In simulated annealing, the function to be optimized is held to be the analog of energy, and the system slowly ``cooled.'' At each temperature tried, the parameters are randomly varied; when there is no further improvement, the temperature is lowered, and again the parameters are varied some number of times. With sufficiently slow cooling, and sufficient random tries, the algorithm ``freezes'' near the global minimum. (At each randomization, only one parameter is varied.) This is quite different from the other techniques implemented here, which can be said to head downhill, fast, for a nearby minimum. The great advantage of simulated annealing is that it sometimes goes uphill, thus escaping undesirable local minima the other techniques tend to get stuck in. The great disadvantage, of course, is that it is a slow technique.

A simple view of simulated annealing is that a new guess at the location of the minimum of the objective function is acceptable if it causes the value of the function to decrease, and also with probability

P = exp[-(Delta)f/T]

where (Delta)f is the increase in the value of the objective function, and T is a ``temperature.'' After a large number of random points in parameter space have been sampled, and no improvement in the minimum value of the objective function has occurred, the temperature is decreased (increasing the probability penalty for positive (Delta)f), and the process is repeated. The expectation is that with a sufficient number of sampled points at each temperature, and a sufficiently slow ``cooling'' of the system, the result will ``freeze out'' at the true minimum. The analogy is supposed to be with a cooling gas, where the Boltzmann statistics of molecular motions causes the molecules of the gas to explore both the minimum energy state and adjacent energy states at any one temperature, and then freeze in a crystalline state of minimum energy as the temperature approaches zero.

SIMUL-ANN-1 starts with a temperature which is about twice the initial value of the objective function, and reduces it slowly towards zero, changing a single parameter value at each randomization.

Parameter tchn is a multiplying factor for the temperature variable between cooling steps. Its default value of 0.98 means that a large number of cooling steps is needed to reduce the temperature sufficiently that the function ``freezes out,'' but fast cooling is not recommended (as it inhibits the ergodic occupation of the search space). Parameter nloop specifies the maximum number of temperature values to try--but may be overridden if the code finds that the solution has ``frozen out'' early. Finally, parameter nsamp specifies the number of movements at each temperature--the number of random changes to the parameter values that will be tried.

SIMUL-ANN-1 tends to be slow, but is a possible way of making significant progress in traveling-salesman type problems. One of its strengths is that even if it doesn't find the absolutely best solution, it often converges to a solution that is close (in the (Delta)f sense) to the true minimum solution. Somewhat better results are often obtained by SIMUL-POW-1 and SIMUL-POW-2, where the simulated annealing method is combined with the Powell method.

Parameters

name type def min max
nloop integer 512 32 8192
tchn real 0.98 0.1 0.9999
nsamp integer 256 16 4096
iseed integer 14391 -1.e+20 1.e+20
tiny real 1.e-12 1.e-20 1.e-6

Detailed Parameter Descriptions

Parameter=nloop (integer default=512 min=32 max=8192)

Maximum number of temperatures.

Parameter=tchn (real default=0.98 min=0.1 max=0.9999)

Factor for temperature reduction.

Parameter=nsamp (integer default=256 min=16 max=4096)

Number of movements at each temperature.

Parameter=iseed (integer default=14391 min=-1.e+20 max=1.e+20)

Seed for random number generator.

Parameter=tiny (real default=1.e-12 min=1.e-20 max=1.e-6)

Smallest temperature allowed.

Bugs

See the Sherpa bug pages online for an up-to-date listing of known bugs.

Hardcopy (PDF): A4 | Letter
Last modified: December 2006



The Chandra X-Ray Center (CXC) is operated for NASA by the Smithsonian Astrophysical Observatory.
60 Garden Street, Cambridge, MA 02138 USA.    Email: cxcweb@head.cfa.harvard.edu
Smithsonian Institution, Copyright © 1998-2004. All rights reserved.