Simulated Annealing and Its Application to NN designs
by
Austina S S Clark
Department of Mathematics and Statistics University of Otago, Dunedin

Annealing is the physical process of heating up a solid until it melts, followed by cooling it down until it crystallizes into a state with a perfect lattice. During this process, the free energy of the solid is minimized. Practice shows that the cooling must be done carefully in order not to get trapped in locally optimal lattice structures with crystal imperfections.

There is some similarity between a solid and a combinatorial optimization problem. In both cases there are many degrees of freedom and in both cases some global quantity has to be optimized.

Simulated annealing is a generally applicable algorithm that can be used to find near-optimal solutions to a wide variety of combinatorial optimization problems. It was proposed by Metropolis et al (1953) and Kirkpatrick et al (1983). Cerny (1985) introduced these ideas into mathematics, statistics and computing. Since many combinatorial problems are NP-hard, i.e., no algorithm has been found that can derive global optima for these problems in a running time bounded by a polynomial function, it is practical to consider only approximation algorithms for all but small problems.

In design construction the primary requirement for an optimal design is simply high efficiency for all contrasts of interest. Here we will briefly describe the simulated annealing algorithm and then illustrate its application to construct some optimal designs for both one-dimensional and two-dimensional nearest neighbour designs using the A-optimality criterion.

Date received: August 23, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadt-36.