The Ising Model on the Ring: Mutation Versus Recombination

Simon Fischer and Ingo Wegener^*

Abstract. The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight how these algorithms work as adaptation schemes. The Ising model on the ring has been considered as a typical example with a clear building block structure suited well for two-point crossover. It has been claimed that GAs based on recombination and appropriate diversity-preserving methods outperform by far EAs based only on mutation. Here, a rigorous analysis of the expected optimization time proves that mutation-based EAs are surprisingly effective. The (1+) EA with an appropriate -value is almost as efficient as usual GAs. Moreover, it is proved that specialized GAs do even better and this holds for two-point crossover as well as for one-point crossover.

Keywords: Ising model, mutation vs. recombination, expected optimization time, fitness sharing

^*Supported in part by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Center “Computational Intelligence” (SFB 531) and by the German Israeli Foundation (GIF) in the project “Robustness Aspects of Algorithms.”

LNCS 3102, p. 1113 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004