Simulated annealing (SA) is a recent technique for finding good solutions to a wide variety of combinatorial optimization problems. Given is a graph with an energy E assigned to each node. In simulated annealing parlance, the nodes are called `states', the arcs represent `moves' from one state to a neighboring state, and the energy is sometimes called `cost'. A typical application is a placement problem, say that of placing 100 circuits on a 10 x 10 grid. Here a state is a permutation of the numbers from 1 to lOO, representing a placement. A move could consist of interchanging any two circuits. Thus each state would have C100= 4950 neighbors. We will also define the 2 distance between any two states as the length of a shortest path connecting them. The simulated algorithm is as given in figure O. The temperature T is a parameter of the algorithm. It is always decreased gradually as the annealing proceeds, but the optimal control of T is not understood. It can easily be shown that this process is equivalent to that of a random walk on the graph, with self-loop edges, present, with random selection of an edge out of a node in proportion to the weight of that edge, and with the edge weights determined by the temperature T. While annealing works well on a wide variety of practical problems, it cannot work well on arbitrary graphs, nor on any graph with an arbitrary energy function. The goal of my research has been to characterize the energy landscape itself (the graph and energy function) and the behavior of the annealing algorithm. state = random initial state repeat (until done) { T = new temperature repeat (until inner-loop criterion) { new state = random neighbor(state) delta E = E(newstate) - E(state) If change in E < 0, state = newstate. Else state = newstate with probability e to the power of (- delta E/T) } } Figure 0: Annealing algorithm. Because the energy landscape itself is terrifically complex, we have focused on the energy trajectory, i.e. the sequence of energies following each move accepted.

Details

Title
Univariate Time Series Analysis of Simulated Annealing Data

Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).