The aim of this research is to try to identify problem classes for which multiple population GAs are superior to a single population GA, and why. The search space induced by an algorithm can be represented by a graph with vertices representing state and edges representing possible shifts in state. In GAs using finite strings over finite discrete alphabets, these graphs can be simplified so that nodes represent strings, or populations of strings, and edges join strings that can be created one from the other through some genetic operation. The structure of the graphs will depend on the types of operations and on the size of the alphabet. This research identifies isomorphisms between mutation and crossover on arbitrary alphabets, higher order crossover operators that follow naturally, and other extensions of the usual notion of crossover in ordinary GAs.
Preliminary results show in some respects superior properties under certain benign assumptions.
This research is primarily concerned with the design and analysis of algorithms for special classes of graphs. Some specific topics in this area are described below. There is more work to be done on fundamental characterizations, and there are several algorithmic problems yet to be tackled - most notably, the Hamiltonian problems on these graphs. AT-free graphs are interesting from a theoretical point of view because they generalize several families of graphs that have elegant theoretical characterizations. This work is important from a practical point of view because the graphs which arise as models in many practical problems are AT-free.