Symmetry in the representation of an optimization problem

A genetic algorithm (GA) is an iterative and stochastic search method inspired by natural biological evolution. In this thesis, we study the dynamics of a GA on problems with symmetry in the representation. A simple example of symmetry is spin-flip symmetry; a problem has spin-flip symmetry in its representation if each pair of bit-complementary strings has identical fitness values. The one-dimensional Ising model is such a problem.; The main reason why unspecialized GAs encounter difficulties when solving symmetrical problems is the loss of diversity in the population. We try six different methods to remove the effect of symmetry on an optimization algorithm: a naive approach, adapting the genetic operators to the symmetry, adapting the fitness function, using a niching technique, using a distributed GA, and adding a highly redundant genotype-phenotype mapping. The best results on the Ising model are obtained using the niching technique.; In real-world problems, we do not often find exact spin-flip symmetry. The multimodality in the problem, together with the interaction structure of the problem, however, can cause the same GA behavior as spin-flip symmetry does. To get a better idea of how our results on exemplar problems obtained can be generalized, we construct a load balancing problem on a scale-free network. An unspecialized GA running on this problem rapidly looses its diversity and gets stuck in a local optimum. A distributed GA, however, maintains diversity in the population, and crossover produces an optimum by combining highly fit candidate solutions.; We distinguish two classes of symmetrical problems: problems for which all equally good partial solutions have to be preserved to obtain an optimum, and problems for which the GA benefits from the fact that genetic drift chooses between equally good partial solutions. By analyzing in detail the GA dynamics on a twomax and comparing this to the dynamics on an Ising model, we investigate the difference between these two types of symmetrical problems.; The Ising model and the H-IFF problem are two ‘crossover-friendly’ problems. They can be solved quickly by a crossover-based algorithm that ensures diversity in the population. To show this, we investigate in depth the dynamics of a recombinative hill-climber on the H-IFF problem. (Abstract shortened by UMI.)...