Skip to content

Latest commit

 

History

History
425 lines (311 loc) · 31.7 KB

README.md

File metadata and controls

425 lines (311 loc) · 31.7 KB
Raw

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

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 mutation probability for a few generations if the population is homogeneous, and lower it while the population is diversified.

You can find an exsample of a custom MutationManager here.

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.SetCustomMutationProbabilityManager(new MyMutationProbabilityManager()).Build();

var result = searchEngine.Run();

IPopulationConverter

The IPopulationConverter interface provides you with a very powerful tool for customizing your search. The IPopulationConverter method ConvertPopulation is called every generation after the population is created. In this method you can change the population in any way you want. This allows you to add Lamarckian evolution to your algorithm - that is, let the chromosomes improve themselves before generating the children.

There is no limit to the number of PopulationConverters you can add to your search. If you add more than one, they will be called in the order in which they were added.

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.AddPopulationConverter(new MyPopulationConverter()).Build();

var result = searchEngine.Run();

You can find an example of a custom PopulationConverter here.

ISelectionStrategy

The ISelectionStrategy tells the engine how to choose the chromosomes that will create the next generation. You can create your own SelectionStrategy by implementing the ISelectionStrategy interface, or use one of the existing strategies. By default, the engine will use the RouletteWheelSelection, but you can changed that with the GeneticSearchEngineBuilder's SetSelectionStrategy method.

Existing SelectionStrategies:

  • RouletteWheelSelection: With RouletteWheelSelection, the chance of choosing a chromosome is equal to the chromosome's fitness divided by the total fitness. In other words, if we have two chromosomes, A and B, where A.Evaluation == 6 and B.Evaluation == 4, there's a 60% change of choosing A, and a 40% change of choosing B.
  • TournamentSelection: With TournamentSelection, we choose a random n chromosomes from the population, and of then select the chromosome with the highest evaluation. In TournamentSelection, selection pressure will grow as the tournament size grows. See this link for more information.
  • StochasticUniversalSampling: StochasticUniversalSampling (SUS) is very similar to RouletteWheelSelection. For more information look here.
  • RankSelection: RankSelection firsts ranks the chromosomes based on their evaluation. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population). RankSelection is very similar to RouletteWheelSelection, but can lead to slower convergence, because the best chromosomes do not differ so much from other ones. (Available since 1.3.6.)

You can find examples of ISelectionStrategies here.

Example:

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.SetSelectionStrategy(new TournamentSelection(5)).Build();

var result = searchEngine.Run();

Ready-Made Components

GeneticAlgorithmEngine includes a library of ready-made implementations of commonly used genetic components (such as CrossoverManagers, MutationManagers and chromosomes).

Chromosomes

The VectorChromosome<T> is an implementation of the IChromosome interface. It holds a generic vector, which is set in its constructor and can be retrieved via its GetVector method.

VectorChromosome expects an IMutationManager<T> and IEvaluator in its constructor, which tell it how to preform mutations and evaluate itself.

// A very simple implementation of IEvaluator for VectorChromosome of type int
class BasicEvaluator : IEvaluator
{
    public double Evaluate(IChromosome chromosome) =>
        ((VectorChromosome<int>) chromosome).GetVector().Sum();
}
	
class UseVectorChromosome
{
    IMutationManager mutationManager = new UniformMutationManager(0, 10); // UniformMutationManager is a ready-made in component
    IEvaluator evaluator = new BasicEvaluator();
    int[] vector = new int[] {1, 3, 2, 8};
    VectorChromosome<int> vectorChromosome = new VectorChromosome<int>(vector, mutationManager, evaluator);
}

MutationManagers

IMutationManager<T> tells the VectorChromosome<T> how to preform mutations. You can create your own MutationManager by implementing the IMutationManager<T> interface, or use an existing managers.

Existing managers:

  • BitStringMutationManager: This mutation only works on binary chromosomes (represented as type VectorChromosome<bool>). It flips bits at random (that is replaces 1 with 0 and 0 with 1). The probability of a bit being flipped is 1 / <vector-length>.
  • IntBoundaryMutationManager: This mutation operator replaces the genome with either lower or upper bound randomly (works only on integer-vector chromosomes). The probability of a bit being replaced is 1 / <vector-length>.
  • DoubleBoundaryMutationManager: This mutation operator replaces the genome with either lower or upper bound randomly (works only on double-vector chromosomes). The probability of a bit being replaced is 1 / <vector-length>.
  • IntUniformMutationManager: This mutation operator replaces the genome with a random value between the lower and upper bound (works only on integer-vector chromosomes). The probability of a bit being replaced is 1 / <vector-length>.
  • DoubleUniformMutationManager: This mutation operator replaces the genome with a random value between the lower and upper bound (works only on double-vector chromosomes). The probability of a bit being replaced is 1 / <vector-length>.
  • IntGaussianMutationManager: This operator adds a unit Gaussian distributed random value to the chosen gene (works only on integer-vector chromosomes). If it falls outside of the user-specified lower or upper bounds for that gene, the new gene value is clipped.
  • DoubleGaussianMutationManager: This operator adds a unit Gaussian distributed random value to the chosen gene (works only on double-vector chromosomes). If it falls outside of the user-specified lower or upper bounds for that gene, the new gene value is clipped.
  • IntShrinkMutationManager: This operator adds a random number taken from a Gaussian distribution with mean equal to the original genome (works only on integer-vector chromosomes). If it falls outside of the user-specified lower or upper bounds for that gene, the new gene value is clipped.
  • DoubleShrinkMutationManager: This operator adds a random number taken from a Gaussian distribution with mean equal to the original genome (works only on double-vector chromosomes). If it falls outside of the user-specified lower or upper bounds for that gene, the new gene value is clipped.

In some problems, it's impotent to insure that all chromosomes contain each genome exactly once. The following list contains mutation managers with the guarantee that if the original chromosome contained each genome exactly once, so will the mutated chromosome.

CrossoverManagers

The CrossoverManagers are implementations of the ICrossoverManager interface.

  • SinglePointCrossoverManager<T>: A point on both parents' chromosomes is picked randomly, and designated a 'crossover point'. Bits to the right of that point are swapped between the two parent chromosomes. Works on chromosomes of type VectorChromosome<T>. See this for more information.
  • K_PointCrossoverManager<T>: Similar to SinglePointCrossoverManager, only that K points are chosen instead of one. Works on chromosomes of type VectorChromosome<T>. See this for more information.
  • UniformCrossoverManager<T>: In uniform crossover, each bit is chosen from either parent with equal probability. Works on chromosomes of type VectorChromosome<T>.
  • GeneralEdgeRecombinationCrossover<T>: For a genome at location i, the genomes at locations (i - 1) and (i + 1) are it's neighbors. In GeneralEdgeRecombinationCrossover we start with a random geone in one of the pantns. From there, we randomlly select one of the element's neigbors in either the first or second parant. We repeat this process will we reach the length of the first parent. Works on chromosomes of type VectorChromosome<T>. (Available since 3.3.3).

In some problems, it's impotent to insure that all chromosomes contain each genome exactly once. The following list contains crossover managers that must be used on chromosomes of the same length that contain each genome exactly once. There managers will ensure that the children also contain each genome exactly once. Note that for these crossover managers to work, the Equals method must be implemented for type T.

  • OrderCrossover<T> (OX1): See this. Ordered crossover Works on chromosomes of type VectorChromosome<T>. In ordered crossover, we randomly select a subset of the first parent string and then fill the remainder of the route with the genes from the second parent in the order in which they appear. This insures that if no genome was repeated in the parents, no genome will be repeated in the child either. (Available since 1.3.1)
  • OrderBasedCrossover<T> (OX2): In OrderBasedCrossover, several positions are selected at random from the second parent. Let A be the list of elements at the selected indexes in parent2. All elements that aren't in A are copied as is from parent1. The missing elements are added in the order in which they appear in parent2. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.2)
  • PartiallyMappedCrossover<T> (PMX): See this. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.1)
  • CycleCrossoverManager<T> (CX): See this. The Cycle Crossover operator identifies a number of so-called cycles between two parent chromosomes. Then, to form the child, cycle one is copied from parent 1, cycle 2 from parent 2, cycle 3 from parent 1, and so on. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.1)
  • PositionBasedCrossoverManager<T> (POS): In PositionBasedCrossover, several positions are selected at random from the first parent. The genomes in those positions are copied as-is from the first parent. The rest of the genomes are coped from the second parent in order as long as the genome hasn't already been copied from parent1. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.2)
  • AlternatingPositionCrossover<T> (AP): In AlternatingPositionCrossover, we alternately select the next element of the first parent and the next element of the second parent, omitting the elements already present in the offspring. This guarantees that the child contains each genome exactly once. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.2)
  • EdgeRecombinationCrossover<T> (ERO): Every genome has two neighborers in each chromosome - or between 2 to 4 neighbors between both its parents. In EdgeRecombinationCrossover we randomly chose a neighbor with the lease neighbors from one of these and continue with it. See this for mote details. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.3)
  • HeuristicCrossover<T> (HX): HeuristicCrossover is almost the same as EdgeRecombinationCrossover. The only difference is that in HeuristicCrossover we select the next neighbor at random from the neighbors of the current element. In EdgeRecombinationCrossover we take the current element's neighbor with the least neighbors. Works on chromosomes of type VectorChromosome<T>. (Available since 1.3.3)

PopulationGenerators

PopulationGenerators are implementations of the IPopulationGenerator interface.

FitnessSharingChromosomeEvaluator

FitnessSharingChromosomeEvaluator is an implementation of the IChromosomeEvaluators interface that implements fitness sharing (a technique to prevent premature conversion in which part of a chromosome's fitness depends on it's similarity to the rest of the population).

The class expects three parameters

  • minDistance: Only distances smaller than minDistance will be considered when calculating the distance.
  • distanceScale: A parameter that defines how much influence sharing has. Higher = more sharing.
  • distanceCalculator: A function that calculates the distance between 2 chromosomes. Note that the distance must be between 0 to 1 (not including).

Please note that FitnessSharingChromosomeEvaluator expects to get an environment of type DefaultEnvironment, so don't set a different environment when using it.

FitnessSharingChromosomeEvaluator is available since version 1.3.5.

Example of Using Components

Following is an example of using components:

class BasicEvaluator : IEvaluator
{
    public double Evaluate(IChromosome chromosome) =>
        ((VectorChromosome<int>) chromosome).GetVector().Sum();
}
	
class UseComponents
{
    IMutationManager mutationManager = new UniformMutationManager(0, 10);
    IEvaluator evaluator = new BasicEvaluator();
    IPopulationGenerator populationGenerator =
            new IntVectorChromosomePopulationGenerator(VECTOR_SIZE, 0, 10, mutationManager, evaluator);
    ICrossoverManager crossoverManager = new SinglePointCrossoverManager<int>(mutationManager, evaluator);
    GeneticSearchEngine engine =
        new GeneticSearchEngineBuilder(POPULATION_SIZE, GENERATION, crossoverManager, populationGenerator).Build();
    SearchReasult result = engine.Run();
}

Using an Environment

Sometimes, it's impossible to evaluate a chromosome without knowing information about it's surroundings, such as the rest of the population. (This, by the way, in the case in nature - where the fitness an individual depends on its environment and the way it interacts with the other individuals). Also, you can use the environment to implement fitness sharing (a technique to prevent premature conversion in which part of a chromosome's fitness depends on it's similarity to the rest of the population).

GeneticAlgorithmEngine provides two classes to deal with this.

IEnvironment

The IEnvironment represents the "environment". You can create your own environment by implementing the IEnvironment interface. If you don't, we will use the DefaultEnvironment class, which contains the other chromosomes, and the generation number.

The environment's UpdateEnvierment is called before the evaluation of a generation begins, which lets you configure your environment based on the current population. UpdateEnvierment is guaranteed to be called once per generation.

You can find an example of a custom Environment here.

IChromosomeEvaluator

If you set the IChromosomeEvaluator, the engine will use your ChromosomeEvaluator's evaluate method (and not the chromosome's default evaluate method). Since the IChromosomeEvaluator's SetEnvierment is called before the evaluation begins, your ChromosomeEvaluator can use the information in the environment to evaluate the chromosomes.

You can find an example of a custom ChromosomeEvaluator here.

Example of Using an Environment

var searchEngine = new GeneticSearchEngineBuilder(POPULATION_SIZE, MAX_GENERATIONS, crossoverManager, populationGenerator)
	.SetEnvironment(new MyEnvironment) // If you don't set an environment, we'll use the DefaultEnvironment class
	.SetCustomChromosomeEvaluator(new MyChromosomeEvaluator()).Build();

var result = searchEngine.Run();

Tutorial

You can find a tutorial on using an environment here. The tutorial's full source code (alongside a poorly designed GUI) is located here.