Genetic Algorithm Visualization and INterataction (GAVIN)

DEMO Home Gregory S. Hornby
hornby@cs.brandeis.edu
Dynamic & Evolutionary Machine Organization Lab

First I should mention what my thesis is. It is not uncommon for people to implement a GA on a parallel machine. Usually the performance of these parallel implementations are comparable with a simple, sequential GA. Sometimes the parallel GA will achieve super-linear speedup. I am investigating whether imposing a structure on the population can improve the performance of a GA on some classes of functions.

A tool for understanding Genetic/Evolutionary Algorithms

In studying evolutionary algorithms it is difficult to understand how the different phases (initialization, selection, variation and replacement) of the algorithm interact and how different population structures affect the search. The standard statistical and convergence methods for under standing how the population is moving do not provide enough informa tion. Through computer visualization the search process can be graphically displayed so that the user can see exactly how the population is moving on the fitness landscape and how individuals from different sub-populations are interacting.

G.A.V.IN. is a research tool I built with some assistance from my friend Paul. It stands for Genetic Algorithm Visualization and INteraction. There are two parts to the program, the genetic algorithm library and the graphics library. I wrote the GA part and Paul wrote most of the graphics part.

For those who are interested there is a chapter and an appendix on GAVIN in my MSc thesis.

I am studying the search properties of parallel genetic algorithms. The two main models I am looking at are the Island Model and the Neighbourhood Model. The first has a number of subpopulations, each containing a number of individuals. Each subpopulation runs like a canonical GA with some communication (exchange of individuals) between subpopulations. The second model has each individual located on some topography (eg a grid) with the restriction that it is only allowed to communicate (reproduce) with its immediate neighbours.

Here are some pictures from a sample run. The first picture shows the population (red cubes) at an early generation, the second picture shows the population near the end of the run.

A Sample Run

In the following series of images GAVIN verifies that using multiple sub- populations results in each sub-population converging to its own local optima on the fitness landscape. The fitness landscape is described by the shaded green surface - with higher/more fit parts of the landscape col ored by lighter shades of green. Individuals on the landscape are repre sented by small, colored cubes. The colors of the cubes show which sub- population the individual is a member of. It can be seen that over time individuals in the same sub-population cluster together at the top of a lo cal optima. The population structure consists of nine sub-populations (with individuals in each given a different color) of fifteen individuals and no migration between the different sub-populations.


The initial population.

The population after 9 generations.

The population after 19 generations.

The population after 30 generations.
The significance of this finding is that it shows that a population's conver gence properties can be controlled by the structure of the population. One problem that plagues EAs is premature convergence, the conver gence of the population to a sub-optimal part of the fitness landscape. Using multiple sub-populations is a promising direction to go to alleviate this problem.

Findings

My research on EAs has focused on the recombination operator, one of the main variation methods, and on the population structure.

When individuals are paired up to produce offspring the offspring are created by applying the recombination operator with two parent individ uals as input and one or two offspring individuals as output. The find ings of studying recombination were that information about the fitness landscape must be incorporated into the operator for better than random search performance to be achieved.

In a 1932 paper, Sewall Wright proposed a theory for why semi-isolated sub-populations search a landscape better than one large population. Ac cording to his theory each sub-population drifts to different parts of the local landscape. Eventually one sub-population moves, by chance, onto a higher local optima. Through migration this more fit sub-population draws the other sub-populations to this part of the landscape and then the process repeats. Semi-isolated sub-populations are a diverse, mobile population. In contrast a single, large population converges to one peak and is hard to move. Results from studying EAs with different popula tion structures have shown that it does cause the EA to search in different ways.

Thanks and Acknowledgements

Thanks to,

Publications

  • Hornby, G.S. (1996). The Recombination Operator, its Correlation to the Fitness Landscape and Search Performance.
    Master's Dissertation, University of Alberta, Department of Computing Science, 1996.


    Homepage. Research Projects. Publications.

    hornby@cs.brandeis.edu - Last modified: March 20, 2003
    Images & Animations Copyright © Gregory Hornby