Jeroen De Dauw
Software Craftsman

GALib

GALib is an arterial intelligence hobby project I created in 2010. It provides a foundation for genetic algorithm driven algorithms. It is written in C#, completely open source and available under the GNU General Public License.

Latest version: 0.1 (2010-01-22)

Download

You can also download the code directly via SVN from the SourceForge source code repository, at https://csgalib.svn.sourceforge.net/svnroot/csgalib. From a command line, you can call the following:

svn checkout https://csgalib.svn.sourceforge.net/svnroot/csgalib

Background

I created this library while working on Skynet, an application that solves the Travelling Salesman Problem. The idea for creating that application came to me after reading the first part of Bio-Inspired Artificial Intelligence by Dario Floreano and Claudio Mattiussi. I figured I needed to do an implementation of what I've read to test myself. All work was done in my free time.

Using the library

This section explains how to create your own GA implementations using GALib. If you are not familiar with how genetic algorithms work, you are advised to first have a good look at this Wikipedia article and related pages. This section will first introduce you how the actual evolution is done, and then how to create your own specific implementation by specifying an individual type.

Class diagram

Population class

The Population class is the core of GALib. It is a collection of individuals of a type you specify, on which evolution (selection and reproduction) can be done. The evolution of the population is done on a background thread, and can be done with rank based selection, truncated rank based selection, roulette wheel selection and tournament selection. Events are fired every time a new generation has been created, a new fittest individual has been found or the evolution is complete.

Constructor

The constructor allows you to specify some general properties that are likely to be different in multiple use cases. These are:

size - Optional. Int32. The size of the population (# of individuals). Defaults to 100.
generations - Optional. Int64. The maximum amount of generations in the evolution. Defaults to 100000.
stagnationLimit - Optional. Int64. The maximum amount of generations with no fitness improvement. Defaults to 10000.

Population will automatically populate itself with size amount new individuals. Since Population is a list of individuals, you can add, remove, and manipulate members yourself. This is however highly discouraged once the evolution is running.

Evolution methods

You can choose between several selection algorithms.

1. Rank based selection

Rank based selection allocates reproduction slots to individuals based on their fitness rank. You can initiate rank based selection with the DoRankBasedSelection method. Similarly you can do truncated rank selection, rank selection that only holds into account the n first individuals, by calling the DoTruncatedRankSelection method, which accepts an Int32 parameter indicating n.

2. Roulette wheel based selection

Roulette wheel selection allocates reproduction slots to individuals proportional to their fitness. You can initiate roulette wheel selection with the DoRouletteWheelSelection method.

3. Tournament based selection

Tournament based selection consists of allocating reproduction slots to the best individuals of a randomly chosen subsets. Population contains several overloaded DoTournamentBasedSelection methods, allowing you holds tournaments of a fixed size, or a variable size between two bounds, both specified either as amount of individuals, or percentage of the population size.

You can stop the evolution by calling the CancelEvolution method. The worker thread on which evolution is done will finish after the current generation has been completed.

After every generation, the individuals will be sorted according to their fitness, fittest first. This means that populationInstance[0] will yield you the fittest individual for that generation, and populationInstance[populationInstance.Count - 1] will get you the least fit member. You can also use GetFittest to get a range of fittest individuals. It accepts an Int32 indicating the size of the range, and a Boolean indicating whether elites should be included.

Events

The Population class contains 3 events that will be fired at various points through the evolutionary process.

GenerationComplete (Object sender, GenerationCompleteEventArgs<IndividualType> e)

Occurs every time a generation is complete. This means selection, reproduction and fitness determination have happened, in that order. GenerationCompleteEventArgs contains the current generation number and fittest individual of the generation.

NewFittest (Object sender, NewFittestEventArgs<IndividualType> e)

Occurs when a new overall fittest individual is found. NewFittestEventArgs contains the current generation number and overall fittest individual.

EvolutionComplete (Object sender, EvolutionCompleteEventArgs<IndividualType> e)

Occurs when the evolution stops, either by reaching the maximum amount of generations, the stagnation limit, or user cancellation. EvolutionCompleteEventArgs contains the current generation number, the overall fittest individual and a boolean indicating whether the evolution was cancelled by the user.

Properties

The underneath list contains the most important public properties of the Population class, which allow you to drastically change the working of the algorithm.

Property name	Type	Summary	Requirements
Size	Int32	Gets or sets the size of the population (# of individuals).	>0
MaximunGenerations	Int64	Gets or sets the maximum amount of generations in the evolution.	>0
StagnationLimit	Int64	Gets or sets the maximum amount of generations with no fitness improvement.	>0
MutationRatio	Int32	Gets or sets the percentage of mutation applied to the genotype of every individual during every generation.	[0,100[
ElitismPercentage	Int32	Gets or sets the percentage of elites in the population. Elites are the best individuals in a population, and are granted survival into the next generation.	[0,100]
ElitistsAmount	Int32	Gets or sets the amount of elites in the population. Elites are the best individuals in a population, and are granted survival into the next generation.	[0, pop size]
RemoveDuplicates	Boolean	Gets or sets if duplicates (identical individuals) should be prevented during the evolution.
RemoveTwins	Boolean	Gets or sets if duplicate twins (identical individuals from the same parents) should be prevented during crossover.
OverallFittest	IndividualType	Gets or sets if overall fittest individual.

Individuals

For your own implementation, you need to specify your own individual type(s). The definitions for these types contain initialization, mutation and crossover methods, as well as the genotype specification and fitness function. GALib provides scaffolding in the form of an IIndividual interface and Individual abstract class. You MUST implement the interface in your individual type definition to be able to create a population of your type. You CAN (most likely should) inherit from Individual, which will spare you some basic work, and implement IIndividual for you.

Islands

I started creating an IslandGroup class to enable simultaneous but separated evolution on multiple 'islands'. However, I did not finish this class

Points of Interest

Since my main motivation for creating this library was exercise, I learned a lot from building it. This is the first C# library I've ever written, as well as the first time I've done any GA programming (or AI in general). Abstracting the library in a way so that it can be used for GA in general was very interesting, and required me to expanded my knowledge of how to use interfaces and inheritance and use generics in a non-basic way for the first time.

Jeroen De Dauw Software Craftsman