Parallel Genetic Algorithms

Introduction

A genetic algorithm (GA) is a search procedure that optimizes some objective function f by maintaining a population P of candidate solutions and employing operations inspired by genetics (called crossover and mutation) to generate a new population from the previous one. Generally, the candidate solutions are encoded as bit strings.

Crossover

provides a method of combining two candidates from the population to form a new candidate. For two n-bit strings A and B, it may be as simple as taking the first k (< n) bits from candidate A and merging them with the last n-k bits from candidate B.

Mutation

consists of flipping one or more bits of a candidate.

The most important part of a GA is the fitness function which gives an evaluation for each candidate as to how good a soultion it is. When candidates are chosen for crossover they are picked in proportion to their relative fitness to the entire population.

There are many efficiency issues in the parallel implementation of GA's. See section 4 of this document for more ideas.

1. The computation of relative fitness may require global communication so data layout becomes important.
2. SIMD implementations may be inefficient if the fitness function is not well parallelizable.
3. MIMD implementation:
   1. Do you divide the population over multiple processors and have some interaction or do you treat them as multiple runs of the problem?
   2. How much synchronization is required?

Project idea

Some references:

1. John Holland, "Genetic Algorithms", Scientific American, July 1992. Easy introduction by the father of the field.
2. John Koza, "Genetic Programming: on the programming of computers by means of natural selection", MIT Press, 1992 Chapter 3 is a good introduction. See me if you want to copy my copy - Bob
3. Carter and Park, "How good are genetic algorithms at finding large cliques" (BU-CS-TR 93-015) Section 4 discusses implementation on CM-5