Jeroen De Dauw
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)
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
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.
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.
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.
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 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.
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.
The underneath list contains the most important public properties of the Population class, which allow you to drastically change the working of the algorithm.
|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.|
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.
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.