# ga.py

A minimal genetic algorithm in Python.

This was an entry in the prestigious Murphy Cup.

## Installation

Requires Numpy. Try easy_install numpy.

## Usage

Run the program as follows: $./ga.py. If you want to set the seed to 17, use $ ./ga.py 17.

## Parameters

The fitness function is called FITNESS. It’s set to just sum the ones in the genome, ie OneMax. It’s easy to change. At the same time also change FITNESS_THRESHOLD to the appropriate maximum value.

The parameters LEN (genome length), POPSIZE (population size), GENERATIONS (number of generations to run for), CROSSOVER_PROB (probability of using crossover as opposed to reproduction) and PMUT (probability of mutating an individual created by crossover or reproduction) are available.

Bonus: SELECTION (selection method, either tournament or roulette (fitness-proportionate)) is also available. Tournament performs much much better on large OneMax problems.

## Minimal?

The number of lines of code (non-comment, non-blank) can be found using this command, which reports 71 lines:

$cat ga.py | grep -v "^#" | grep -v "^[[:space:]]*$" | wc

## Performance

Genomes are stored as Numpy boolean arrays to save space and make copying fast.

You can time it using this command:

$time ./ga.py which gives 1.2s for 100 generations, 100 popsize, 100 genome length on my iMac. You can profile it using this command: $ python -m cProfile ga.py

which prints out a long list of function names and the total time spent in each. Interesting: change FITNESS to sum (instead of numpy.sum), and sum now dominates running time.