Chapter 8: Extensions of this Work*8.1 Development of the Simulation Software
The software could be extended in several ways:
(a) It could be made to ascertain the site and bond percolation thresholds for various lattice geometries.1 Actually it does this already, generating clusters of occupied sites at a given concentration of sites or bonds and testing for the presence of a spanning cluster, looking for the smallest concentration at which a spanning cluster first appears (for further details see Appendix 6, "Site and Bond Percolation Thresholds"). This gives results consistent with those already known, e.g., 0.34729 for the bond percolation threshold on the triangular lattice (Sykes and Essam, 1963 and 1964), but the method used does not (with the numbers of trials which were used) provide a precision of more than three decimal places.2
(b) The software could be extended to measure thermal and percolation correlation lengths in pure and dilute spin systems. Appendix 7, "Determination of Correlation Lengths", discusses the conceptual framework in which this might be done and presents some algorithms for this purpose.(c) The software could be extended to measure relaxation times in pure and dilute spin systems, thus allowing a study of "singular dynamic scaling" (for further details see Appendix 8, "Relaxation Time and Singular Dynamic Scaling").
(d) The software could be used to study non-ferromagnetic systems, such as anti-ferromagnetic systems (where the interaction energy J is negative) and spin glasses (in which the J's are randomly +1 or -1 or in which they have some other random distribution).
8.2 Simulated Annealing
Simulated Annealing, based on ideas drawn from statistical physics, is a method of optimizing a quantity which involves the generation of random numbers; in other words it is a stochastic optimization algorithm.
Suppose we have a system and a function E(), called a "cost function", which assigns a positive real number to any state of that system, and that we wish to find a state which minimizes E().
For example (the classical "travelling salesman problem") consider a set of cities and distances between them (or some other quantity such as time taken to travel from one to another, or the cost of doing so). A state of the system is a permutation of the cities, defining a path which starts from one city and traverses all of them to arrive back at the first city. The cost function is the sum of the distances (or other quantities) associated with each segment of the path. We wish to find a path which minimizes the cost function.
To use the Simulated Annealing algorithm we consider ways of changing one state Si to another state Sj. Then, beginning with some (perhaps randomly chosen) state, we construct a trajectory through the phase space as follows: For any state Si in the trajectory, consider a change to Sj. Let δEji = E(Sj) - E(Si). If δEji < 0 then the change is accepted and the new state is adopted. If δEji ≥ 0 then the change is accepted with probability e-ΔEji/T where T is a positive real number interpreted as a "temperature" value. This generation of states continues until E() becomes constant. Then the temperature is decreased slightly and the process is repeated. This continues until decreasing the temperature does not result in a decrease in the cost function.
Clearly this outline requires specification of such matters as what temperature value should be chosen at the start and how it should be lowered (this is called the "cooling schedule"). Also the ways in which one state may change to another obviously depends on the system under consideration. E.g., in the travelling salesman problem, a change might consist in swapping the positions of two cities in the path.
The Simulated Annealing algorithm finds a state S which is either a global minimum for the cost function or is close to the global minimum. It does this by not allowing itself to be trapped in a local minimum. For a given T, for any ΔEji < T.ln2 the chance of accepting the transition is greater than ½. Thus with a high temperature there is a significant chance of jumping out of a local minimum into some state from which a descent to a lower value is possible. As the temperature is lowered, such jumps occur less frequently, and finally the system comes to rest in some local minimum which hopefully is (or is close to) the global minimum.
Clearly the Simulated Annealing algorithm is similar to the Metropolis algorithm used to produce an equilibrium state in a spin system at a constant temperature.3 In this case changes consist of single spin flips. Instead of the Metropolis algorithm we could also use the Glauber algorithm or perhaps even something analogous to a cluster algorithm such as the Swendsen-Wang algorithm.
It would be worth considering whether the simulation software could be adapted to implement the Simulated Annealing algorithm in such a way as to be applicable to various kinds of optimization problem. Clearly it would not be difficult to implement some cooling schedule. But the simulation software deals with spin systems (either Ising systems, where the spins have a value of +1 or -1, or q-state Potts systems, where spins have a value 1, ..., q) and the connection between a spin system and some other system in which a quantity is to be optimized may not be immediately evident, and is likely to be different in different cases.
In the case of the travelling salesman problem of n cities we might represent the problem by means of an Ising model on a square lattice of linear size n, and such that the spin Sij has spin value +1 if there is a path-segment from city i to city j, and is -1 otherwise. Here the phase space is not the set of all permutations of cities, but that of all graphs on a set of n points (the graphs need not connect all points). Using a table of distances between cities we might define a cost function as follows:
Consider the spin system as a 2d array. For each column and for each row count the number of +1 spins in that row or column. Associate with each count a value which is a minimum for counts of 1. The cost function is then the sum of these values plus the sum of the distances between pairs of cities associated with spins with value +1.4 Applying the Simulated Annealing algorithm (using spin flips as the means to change state) and minimizing the cost function produces (or may be expected to produce) an array such that there is one and only one segment starting from each city and one and only one segment ending at each city, with a minimum total path distance. It is possible, however, that a solution might be such that instead of one path connecting all cities there are several paths connecting subsets of cities. To produce a solution guaranteeing a single path connecting all cities the cost function must be modified to give a higher value to states of the spin system which do not correspond to a connected path.
Clearly the basic uncertainty in adapting the simulation software to implement the Simulated Annealing algorithm is that of the ability to interpret a spin system in such a way as to correspond to the parameters of a system in which some quantity is to be optimized, and this matter can be decided only by the consideration of various cases where the Simulated Annealing algorithm is applicable.
Title page Contents Next: Appendix 1 References