Click here to Skip to main content
15,867,308 members
Articles / Artificial Intelligence

GALib

Rate me:
Please Sign up or sign in to vote.
5.00/5 (10 votes)
24 Jan 2010GPL35 min read 61.8K   1.3K   40   18
A small C# library that provides scaffolding for genetic algorithm based functionality.

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

Image 1

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.

Image 2

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.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)


Written By
Software Developer
Belgium Belgium
I am a free and open source software enthusiast and freelance software developer with multiple years of experience in both web and desktop development. Currently my primarily focus is on MediaWiki and Semantic MediaWiki work. I'm in the all time top 10 MediaWiki comitters and am one of the WikiWorks consultants. You can contact me at jeroendedauw at gmail for development jobs and questions related to my work.

More info can be found on my website [0] and my blog [1]. You can also follow me on twitter [2] and identi.ca [3].

[0] http://www.jeroendedauw.com/
[1] http://blog.bn2vs.com/
[2] https://twitter.com/#!/JeroenDeDauw
[3] http://identi.ca/jeroendedauw

Comments and Discussions

 
QuestionExample Code Pin
Peter Hawke4-Feb-13 14:43
Peter Hawke4-Feb-13 14:43 
GeneralMy vote of 5 Pin
Filip D'haene26-May-11 9:27
Filip D'haene26-May-11 9:27 
GeneralRoulette Wheel selection Pin
gentianam12-May-11 3:27
gentianam12-May-11 3:27 
GeneralRe: Roulette Wheel selection Pin
hussein_moh29-Mar-12 11:25
hussein_moh29-Mar-12 11:25 
GeneralFitness for first generation members Pin
gentianam7-Apr-11 4:33
gentianam7-Apr-11 4:33 
GeneralRe: Fitness for first generation members Pin
Jeroen De Dauw7-Apr-11 4:41
Jeroen De Dauw7-Apr-11 4:41 
GeneralRe: Fitness for first generation members [modified] Pin
gentianam7-Apr-11 4:46
gentianam7-Apr-11 4:46 
GeneralRe: Fitness for first generation members Pin
Jeroen De Dauw7-Apr-11 5:05
Jeroen De Dauw7-Apr-11 5:05 
GeneralRe: Fitness for first generation members Pin
gentianam7-Apr-11 5:45
gentianam7-Apr-11 5:45 
Generalsorting in genetic algorithm Pin
rohalax15-Mar-10 20:50
rohalax15-Mar-10 20:50 
GeneralRe: sorting in genetic algorithm Pin
Jeroen De Dauw16-Mar-10 5:28
Jeroen De Dauw16-Mar-10 5:28 
GeneralCrossover-Reg Pin
pandeeswari murugesan5-Feb-10 22:30
pandeeswari murugesan5-Feb-10 22:30 
GeneralCrossover-Reg Pin
pandeeswari murugesan5-Feb-10 22:29
pandeeswari murugesan5-Feb-10 22:29 
QuestionDynamic implementation Pin
rohalax24-Jan-10 23:56
rohalax24-Jan-10 23:56 
GeneralNice Pin
krn_2k24-Jan-10 21:57
krn_2k24-Jan-10 21:57 
GeneralRe: Nice Pin
Jeroen De Dauw24-Jan-10 22:02
Jeroen De Dauw24-Jan-10 22:02 
Questionplz help us...... Pin
rohalax24-Jan-10 21:51
rohalax24-Jan-10 21:51 
AnswerRe: plz help us...... Pin
Jeroen De Dauw24-Jan-10 22:04
Jeroen De Dauw24-Jan-10 22:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.