GeneticAlgorithmEngine

GeneticAlgorithmEngine provides an engine for running a Genetic Algorithm that can be easily configured to fit most search domains.

Download

You can find the GeneticAlgorithmEngine library on nuget.org via package name GeneticAlgorithm.

Table of Contents

• Usage

  • IChromosome
  • ICrossoverManager
  • IPopulationGenerator
  • Creating an Instance of GeneticSearchEngine

• Events

• Search Options

  • Mutations
  • CancellationToken
  • Include All History
  • Elitism
  • StopManagers
  • PopulationRenwalManagers
  • MutationProbabilityManager
  • PopulationConverters
  • SelectionStrategies

• Ready-Made Components

  • Chromosomes
  • MutationManagers
  • CrossoverManagers
  • PopulationGenerators
  • FitnessSharingChromosomeEvaluator
  • Example of Using Components

• Using An Environment

  • IEnvironment
  • ChromosomeEvaluator

Usage

GeneticAlgorithmEngine contains 3 interfaces that you'll need to implement.

IChromosome

Your chromosomes will need to implement the IChromosome interface.

public interface IChromosome
{
    /// <summary>
    /// Must return a value that is greater then zero.
    /// </summary>
    double Evaluate();

    void Mutate();
}

You can find a sample Chromosome here.

Please note that the Evaluate and Mutate methods will be called on deferent chromosomes in parallel, so they must be thread safe in that aspect.

ICrossoverManager

You'll need to implement the ICrossoverManager interface. This tells the engine how to perform crossovers for your chromosomes. Please note that your crossoverManager will be called on deferent chromosomes in parallel, so it must be thread safe in that aspect. You can read more about crossovers here.

public interface ICrossoverManager
{
    IChromosome Crossover(IChromosome chromosome1, IChromosome chromosome2);
}

You can find some sample CrossoverManagers here.

IPopulationGenerator

You'll also need to implement the IPopulationGenerator interface. The engine uses this class to create its initial population. The PopulationGenerator will also renew the population when needed (see IPopulationRenwalManagers). PopulationGenerator doesn't need to be thread safe.

public interface IPopulationGenerator
{
    /// <summary>
    /// size is the number of chromosomes we want to generate
    /// </summary>
    IEnumerable<IChromosome> GeneratePopulation(int size);
}

You can find some sample PopulationGenerators here.

Creating an Instance of GeneticSearchEngine

It's highly recommended that you use the GeneticSearchEngineBuilder class to create your GeneticSearchEngine.

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.SetMutationProbability(0.1).Build();
	
var result = searchEngine.Run();

Once you have an instance of an engine you can either use the Run method to run a complete search, or the Next method to run a single generation. You can also use the Pause method to pause the search, and then resume it anytime.

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.SetMutationProbability(0.1).Build();
	
GeneticSearchResult nextGeneration = searchEngine.Next(); // Run a single generation
Task.Run(() => searchEngine.Run()); // Do in a new thread, so that we don't need to wait for the engine to finish
Thread.Sleep(10); // Give the engine some time to run
searchEngine.Pause();
var task = Task.Run(() => searchEngine.Run()); // Resume the search from where it was paused
GeneticSearchResult result = task.Result;

searchEngine.Dispose();

Events

OnNewGeneration

This event is called once for every new generations. This is a good way for GUIs to visually show the changing population, or just show the search progress.

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator).Build();
searchEngine.OnNewGeneration += (Population population, IEnvironment e) =>
{
	/* Do some work here. For instance:
	IChromosome[] chromosomes = population.GetChromosomes();
	double[] evaluations = population.GetEvaluations();
	*/
};
var result = searchEngine.Run();

Search Options

Mutations

By default, the probability of a mutation is 0. You can change this by using the GeneticSearchEngineBuilder.SetMutationProbability method. Note that the mutation probability will be ignored if you set a IMutationProbabilityManager.

CancellationToken

You can use the GeneticSearchEngineBuilder.SetCancellationToken method to set a CencellationToken. The cancellation is checked once per generation, which means that if you're generations take a while to run, there may be a delay between your requesting of the cancellation and the engine actually stopping.

When the cancellation is requested, you'll get whatever result was found up till then (no exception is thrown).

IncludeAllHistory

If this option is turned on (by default it's off) the result will include the entire history of the population (and not only the last generation).

Elitism

Using elitism, you can set a percentage of the best chromosomes that will be passed "as is" to the next generation. You can read more about elitism here.

IStopManagers

StopManagers let you configure when the search is stopped. You can create your own managers by implementing the IStopManager interface, or use one of the existing managers. Note that there is no limit to the number of StopManagers that you can add to your search engine.

You can find a tutorial on creating a custom StopManager here. In addition, here are some examples of custom StopManagers.

Existing StopManagers:

• StopAtEvaluation: Will cause the search to stop when a chromosome reaches some predefined evaluation.
• StopAtConvergence: The search will stop when the difference between chromosomes in the population is too small.
• StopIfNoImprovment: Will stop if the improvement over 'X' generations isn't good enough.

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.AddStopManager(new StopAtConvergence(0.5)).Build();

var result = searchEngine.Run();

IPopulationRenwalManagers

PopulationRenwalManagers will tell the engine to renew a certain percentage of the population if some condition is met. This can fix premature convergence. You can create your own managers by implementing the IPopulationRenwalManager interface, or use one of the existing managers. Note that there is no limit to the number of PopulationRenwalManagers you can add to your search engine.

You can find a tutorial on creating a custom PopulationRenwalManager here. In addition, here are some examples of custom PopulationRenwalManagers.

Existing PopulationRenwalManagers:

• RenewAtConvergence: The search will renew some of the population if the difference between chromosomes in the population is too small.
• RenewIfNoImprovment: Will renew some of the population if the improvement over 'X' generations isn't good enough.
• RenewAtDifferenceBetweenAverageAndMaximumFitness: Will renew some of the population when the difference between the average and max evaluation is equal too small (available since 1.3.4).

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.AddPopulationRenwalManager(new RenewAtConvergence(0.5, 0.5)).Build();

var result = searchEngine.Run();

IMutationProbabilityManager

The IMutationProbabilityManager interface lets you dynamically determine the probability of a mutation based on the current population. For instance, you might want to set a high m