simulated annealing

Mathematics is not a deductive science ... what you do is trial and error, experimentation, guesswork - Paul Halmos

General optimisation/AI resources

Special topics

Selected articles | Software | Links

The fields of tabu search and simulated annealing are relatively sparse in comparison with genetic algorithms.

Selected articles

As a starting point I have prepared a brief overview of simulated annealing, using some of the sources further on.

A name which crops up frequently in simulated annealing is that of Lester Ingber. His site is a comprehensive resource of papers and simulated annealing software.

More tweaks by Ingber: Adaptive Simulated Annealing (ASA) is a global optimisation algorithm based on an associated proof that the parameter space can be sampled much more efficiently than by using other previous simulated annealing algorithms, while in Very Fast Simulated Re-Annealing, the introduction of re-annealing permits adaptation to changing sensitivities in the multi-dimensional parameter-space and speeds things up.

While his paper Simulated annealing: Practice versus theory is ostensibly on demonstrating how simulated quenching can be much faster than simulated annealing without sacrificing accuracy, it is an extremely wide-ranging and comprehensive paper which covers a variety of techniques and applications and also provides almost a hundred references. Recommended.

A paper by Frost and Heineman provides an insight into a heuristic for parallel stochastic optimisation

to the top

.... more specialised and advanced:

(May take a while to download these PDFs)

Applications to investment problems are addressed in A simple options training model, which reveals some simple but relevant probabilistic insights into the nature of options trading often not discussed in most texts, and Trading Markets With Canonical Momenta and Adaptive Simulated Annealing a short but interesting article on intuition versus analysis.

The paper Mortgage Pool Allocation by Simulated Annealing shows a successful application of simulated annealing to the problem of mortgage pool allocation: it finds good (highly profitable) solutions very quickly. This result is significant both for the complexity of the problem solved and because demonstrates the feasibility of simulated annealing for solving a real-world financial problems.

to the top

Software

The University of East Anglia KDD site has used heuristics (GA,SA,TS) as their main approach to solving data mining problems; so far they have been most successful with SA. One of the areas they first found success with was the financial services sector. Links and papers related to this work are on this site.

The only commercial source of simulated annealing software I've found is Exatech's XSolver, an Excel add-in. Haven't tried it; can't vouch for it. Their home page has a Java applet demonstrating the process of simulated annealing and the user manual can be browsed.

Lester Ingber's ASA code can be downloaded from his site. Read the read-me here first.

The following Fortran code (Word for easy cutting and pasting) implementation of simulated annealing was used in "Global Optimization of Statistical Functions with Simulated Annealing," Goffe, Ferrier and Rogers, Journal of Econometrics, vol. 60, no. 1/2, Jan./Feb. 1994, pp. 65-100. It was found competitive, if not superior, to multiple restarts of conventional optimisation routines for difficult optimisation problems.

Another non-commercial software site is Taygeta Scientific Inc

to the top

Links

The ParSA or Parallel Simulated Annealing Library has some useful publications, while the COSA (Cooperative Simulated Annealing) site has an excellent Java applet which solves various practical problems. Great fun.

to the top