The one-dimensional Ising model: Mutation versus recombination

The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight into how these algorithms work as adaptation schemes. The one-dimensional Ising model with periodic boundary conditions 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 by far outperform EAs based on mutation only. 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 typical 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.