Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

Evolutionary Computation

Winter 2002, Vol. 10, No. 4, Pages 317-344
(doi: 10.1162/106365602760972749)
© 2002 Massachusetts Institute of Technology
Spin-Flip Symmetry and Synchronization
Article PDF (871.59 KB)

In the context of optimization by evolutionary algorithms (EAs), epistasis, deception, and scaling are well-known examples of problem difficulty characteristics. The presence of one such characteristic in the representation of a search problem indicates a certain type of difficulty the EA is to encounter during its search for globally optimal configurations. In this paper, we claim that the occurrence of symmetry in the representation is another problem difficulty characteristic and discuss one particular form, spin-flip symmetry, characterized by fitness invariant permutations on the alphabet. Its usual effect on unspecialized EAs, premature convergence due to synchronization problems, is discussed in detail. We discuss five different ways to specialize EAs to cope with the symmetry: adapting the genetic operators, changing the fitness function, using a niching technique, using a distributed EA, and attaching a highly redundant genotype-phenotype mapping.