Complex Systems

A Two-Dimensional Genetic Algorithm for the Ising Problem Download PDF

Charles A. Anderson
Kathryn F. Jones
Jennifer Ryan
University of Colorado at Denver,
Denver, CO 80217-3364, USA


The genetic algorithm is a powerful heuristic for the solution of hard combinatorial problems and has been investigated by numerous authors. Many problems, arising for example in communication networks, possess strong two-dimensional characteristics. We describe a genetic algorithm with a new crossover operator called block-uniform crossover, which exploits the two-dimensional character of a problem. The concept was tested on a version of the Ising model, which is important in physics. This new algorithm outperforms genetic algorithms with traditional crossover operators in all trials.