About sga

Abstract

sga is a simple genetic algorithm (GA) program that demonstrates the dynamic behaviour of standard genetic algorithms. sga is written in C and is released under the GNU General Public License (GPL) 3.0.

What are Genetic Algorithms?

The Wikipedia definition...

A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination). More...

Overview of features

sga allows the user to define a number of different variables and functions prior to running the program. Each individual in the system is treated as a fixed-length binary string and all generations have a static population size. This allows users to quickly get an idea of how each generation has changed from the last. The program has options for one-point crossover and/or mutation. This means that individuals can be sliced in two and recombined to make new individuals or some bits in each individual can be randomly flipped to simulate mutation. The program offers a number of fitness functions which can affect which individuals are allowed to pass to the next generation. Each generation is summarised on-screen with various statistics including best, worst, mean, and standard deviation per generation. Also a one-line summary of the number of ones in each locus is shown below each displayed generation.

Fitness functions

The fitness functions are the tests we put in place to determine how likely it is that an individual will be killed off or moved into the next generation. The fitness functions in sga include:

  1. Constant (all fitnesses the same)
  2. Random (fitness() returns a random value)
  3. Onemax (maximise the number of ones)
  4. Diffmax (maximise the difference between number of ones and zeros)
  5. Integer (fitness equals integer equivalent of bitstring).

Program Output

sga Output

  1. The generation we are summarising.
  2. A snap-shot of the generation summarised below by the percentage of ones, A '-' means all ones or no ones, and a digit: 0=less than 10%, 1=10%+, 2=20%+ etc.
  3. The number of individuals where all bits are ones.
  4. The number of individuals where there are no ones.
  5. The mean number of individuals with all ones.
  6. The standard deviation for this generation.

The Team

The majority of people working on the sga project are students of De Montfort University. The godfather? That's Tim Watson, the person who created the sga project firstly to demonstate how genetic algorithms work to his students, and secondly to give his students a flavour of an open source project.