Introduction
GALib is a small C# library that provides scaffolding for genetic algorithm based functionalities. It's completely Open Source, and is available under the GNU General Public License.
Background
I created this library while working on an application to solve 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 code
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, or one of the many awesome articles here on CP. This section will first introduce you to 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 is 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 number of generations in the evolution. Defaults to 100000.stagnationLimit - Optional. Int64. The maximum number of generations with no fitness improvement. Defaults to 10000.
Population will automatically populate itself with size amount of 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:
- 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, a rank selection that only holds into account the first n individuals, by calling the DoTruncatedRankSelection method, which accepts an Int32 parameter indicating n.
- 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.
- Tournament based selection
Tournament based selection consists of allocating reproduction slots to the best individuals of a randomly chosen subset. Population contains several overloaded DoTournamentBasedSelection methods, allowing you to hold tournaments of a fixed size, or a variable size between two bounds, both specified either as the amount of individuals, or as a 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 three 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 the 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 the overall fittest individual.
EvolutionComplete (Object sender, EvolutionCompleteEventArgs<IndividualType> e)
Properties
The list below contains the most important properties of the Population class, which allow you to drastically change the working of the algorithm.
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 an 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.
Individual class
Inheriting Individual forces you to implement some abstract methods:
void doBaseInitialization()void doRandomInitialization()void doMutation()void doCrossover(IIndividual mother, IIndividual father)Double determineFitness()
For details on other work done by Individual, see the source of the class itself.
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.
See also
History
- Version 0.1: 2010-01-24: Initial release.
