English English

Evolutionary Algorithms on Ising-Models

The applet below demonstrates the behaviour of Evolutionary Algorithms on Ising models. The applet requires at least a Java 1.2 plug-in, which you can download, e.g., from Sun.

Fitness function and algorithm can be selected using the combo boxes in the upper right corner of the applet. Parameter settings can be made in the lower right corner. The "Delay" slider below the display can be used to set the delay between two steps (in ms). The "Go" button starts the algorithm. The display area in the north west corner of the applet gives a visualisation of the coloured graph and a plot of the fitness.


© 2004 Simon Fischer

The Ising model

While it was initially introduced by Ising as a model of ferromagnetism in 1924, Nauds and Nauds introduced the Ising model as fitness functions for Genetic and Evolutionary Algorithms into computer science. For a colouring of the vertices of a graph, the value of the fitness function is defined as the number of monochromatic edges. For graphs that consist of clusters, vertices are rendered as circles and edges are rendered as lines connecting the circles. For the ring and the torus, the vertices are rendered as boxes while the edges are omitted.

The one- and even more the two-dimensional Ising Model were considered archetypical functions that are difficult to optimise for mutation based search heuristics like the (1+1)EA and randomised local search (RLS), whereas the genetic crossover operator can help to combine building blocks (in this case monochromatic blocks) and find a solution quickly.

New results

Fischer (2003) and Fischer and Wegener (2004) gave rigorous proofs for surprisingly small upper bounds of Evolutionary and Genetic Algorithms on the one-dimensional Ising model, the ring. These upper bounds are asymptotically tight under a reasonable hypothesis. Both (1+1)EA and RLS can optimise the ring within an expected number of O(n³) steps, where n is the dimension of the ring. Furthermore, the constants hidden in the O are small. Even smaller upper bounds hold for the (1+lambda)EA for which the expected number of generations is bounded above by O(n²log n) for a value of lambda=n/log n. This also leads to an expected number of O(n³) fitness evaluations.

Fischer (2004) gives a polynomial upper bound for the Metropolis algorithm on the two-dimensional Ising model. The analysis of this fitness function is slightly more involved but based on similar principles.

The algorithms

The applet above demonstrates the behaviour of some simple algorithms on these fitness functions. All except the GIGA are mutation-based algorithms. The (1+1)EA performs a mutation step by flipping all bits independently with probability 1/n where n is the dimension of the search space. RLS and the Metropolis algorithm flip exactly one bit, which is chosen at random. While (1+1)EA and RLS replace the current individual by its offspring only, if its fitness is at least the fitness of the old individual, the Metropolis algorithm also accepts it with probability exp((f'-f)/T) if its fitness is less than the fitness of the old individual.

The Gene Invariant Genetic Algorithm (GIGA) uses a population of size two, which always contains two complementary individuals. It does not use mutation, but only two-point-crossover.

Observations

The ring

Setting the delay slider to a value greater than 0, one can easily observe the random walk of "borders" (or "domain walls") for the mutation-based algorithms. Whenever two borders collide, the fitness increases by 2. For an initial block length of l, this takes an expected number of O(l²) steps. Using GIGA, one can see that monochromatic blocks are combined.

The torus

The optimisation of the torus is similar to the optimisation of the ring. However, there exist local optima from which plus-strategies, i.e. strategies replacing the old individual by the new iff its fitness is not less then the fitness of the old, cannot escape. Starting a few runs one should sooner or later encounter such a colouring which consists of a white and a black ring running around the torus. We can prove, that the Metropolis algorithm, which also accepts offspring with lesser fitness with a small probability, can escape from such situations. Here, we can observe, that it cannot only escape from them, but also has a tendency to avoid them entirely. Starting a few runs of the Metropolis algorithm, one will hardly ever observe a situation with two rings.

Publications

References

  • B. Naudts and J. Naudts: The effect of spin-flip symmetry on the performance of the simple GA. In: E. Eiben, Th. Bäck, M. Schoenauer, and H.-P. Schwefel (editors): Proceedings of the 5th Conference on Parallel Problem Solving from Nature, volume 1498 of LNCS, pages 67–76, Berlin Heidelberg New York, 1998. Springer-Verlag.
  • E. Ising: Beitrag zur Theorie des Ferromagnetismus. In: Z. Physik, 31, pages 235–258, 1925.

© Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.