Genetic Algorithms in C#

February 21, 2011

The code below is a 3.5 upgrade to Barry Lapthorn’s original C# example found on codeproject. I’ve .NET’ised it a bit more (inline with the Framework Guidelines book) and given it a facelift using a Func for the fitness function and autogenerated properties. It should also run a lot faster without the boxing and unboxing required by ArrayList, as it now employs List for its generations.

I’m in the middle of writing my own version of a C# Genetic Algorithm example, however unlike Barry’s example mine uses bit strings to represent the genes in the genomes. I’m also planning on giving a bit background information to GAs in the article, based on my knowledge from a recent university course - compressing an explanation into several paragraphs will be an interesting test of the completeness of my knowledge.

Example usage

As with Barry’s original example you use it like so (with the delegate fluff now removed thanks to the v3 compiler):

	public static void Main()
	{
	// Crossover = 80%
	// Mutation = 5%
	// Population size = 100
	// Generations = 2000
	// Genome size = 2
	GA ga = new GA(0.8, 0.05, 100, 2000, 2);
	ga.FitnessFunction = FitnessFunction;
	ga.Elitism = true;
	ga.Go();

	double[] values;
	double fitness;

	ga.GetBest(out values, out fitness);
	System.Console.WriteLine("Best ({0}):", fitness);

	for (int i = 0; i < values.Length; i++)
	System.Console.WriteLine("{0} ", values[i]);

	ga.GetWorst(out values, out fitness);
	System.Console.WriteLine("\nWorst ({0}):", fitness);

	for (int i = 0; i < values.Length; i++)
	System.Console.WriteLine("{0} ", values[i]);

	Console.Read();
	}

	// optimal solution for this is (0.5,0.5)
	public static double FitnessFunction(double[] values)
	{
	if (values.GetLength(0) != 2)
	throw new ArgumentOutOfRangeException("should only have 2 args");

	double x = values[0];
	double y = values[1];
	double n = 9; // should be an int, but I don't want to waste time casting.
	double f1 = Math.Pow(15 * x * y * (1 - x) * (1 - y) * Math.Sin(n * Math.PI * x) * Math.Sin(n * Math.PI * y), 2);

	return f1;
	}

view raw gistfile1.cs hosted with ❤ by GitHub

And the 3 classes needed are GA, Genome and GenomeComparer:

GA

	using System;

	namespace GeneticAlgorithm
	{
	/// <summary>
	/// Genetic Algorithm class
	/// </summary>
	public class GA
	{
	private double _totalFitness;
	private List<Genome> _thisGeneration;
	private List<Genome> _nextGeneration;
	private List<double> _fitnessTable;
	private static Random _random = new Random();
	public Func<double[], double> FitnessFunction { get; set; }
	public int PopulationSize { get; set; }
	public int GenerationSize { get; set; }
	public int GenomeSize { get; set; }
	public double MutationRate { get; set; }
	public string FitnessFile { get; set; }
	public double CrossoverRate { get; set; }
	public bool Elitism { get; set; }

	/// <summary>
	/// Default constructor sets mutation rate to 5%, crossover to 80%, population to 100, and generations to 2000.
	/// </summary>
	public GA()
	: this(0.8, 0.05, 100, 2000, 2)
	{
	}

	public GA(int genomeSize)
	: this(0.8, 0.05, 100, 2000, genomeSize)
	{
	}

	public GA(double crossoverRate, double mutationRate, int populationSize, int generationSize, int genomeSize)
	{
	Elitism = false;
	MutationRate = mutationRate;
	CrossoverRate = crossoverRate;
	PopulationSize = populationSize;
	GenerationSize = generationSize;
	GenomeSize = genomeSize;
	FitnessFile = "";
	}

	/// <summary>
	/// Method which starts the GA executing.
	/// </summary>
	public void Go()
	{
	if (FitnessFunction == null)
	throw new ArgumentNullException("Need to supply fitness function");
	if (GenomeSize == 0)
	throw new IndexOutOfRangeException("Genome size not set");

	// Create the fitness table.
	_fitnessTable = new List<double>();
	_thisGeneration = new List<Genome>(GenerationSize);
	_nextGeneration = new List<Genome>(GenerationSize);

	Genome.MutationRate = MutationRate;
	CreateGenomes();
	RankPopulation();
	StreamWriter outputFitness = null;
	bool write = false;

	if (FitnessFile != "")
	{
	write = true;
	outputFitness = new StreamWriter(FitnessFile);
	}

	for (int i = 0; i < GenerationSize; i++)
	{
	CreateNextGeneration();
	RankPopulation();
	if (write)
	{
	if (outputFitness != null)
	{
	double d = (double)((Genome)_thisGeneration[PopulationSize - 1]).Fitness;
	outputFitness.WriteLine("{0},{1}", i, d);
	}
	}
	}

	if (outputFitness != null)
	outputFitness.Close();
	}

	/// <summary>
	/// After ranking all the genomes by fitness, use a 'roulette wheel' selection
	/// method. This allocates a large probability of selection to those with the
	/// highest fitness.
	/// </summary>
	/// <returns>Random individual biased towards highest fitness</returns>
	private int RouletteSelection()
	{
	double randomFitness = _random.NextDouble() * _totalFitness;
	int idx = -1;
	int mid;
	int first = 0;
	int last = PopulationSize - 1;
	mid = (last - first) / 2;

	// ArrayList's BinarySearch is for exact values only
	// so do this by hand.
	while (idx == -1 && first <= last)
	{
	if (randomFitness < _fitnessTable[mid])
	{
	last = mid;
	}
	else if (randomFitness > _fitnessTable[mid])
	{
	first = mid;
	}
	mid = (first + last) / 2;

	// lies between i and i+1
	if ((last - first) == 1)
	idx = last;
	}
	return idx;
	}

	/// <summary>
	/// Rank population and sort in order of fitness.
	/// </summary>
	private void RankPopulation()
	{
	_totalFitness = 0;
	for (int i = 0; i < PopulationSize; i++)
	{
	Genome g = ((Genome)_thisGeneration[i]);
	g.Fitness = FitnessFunction(g.Genes);
	_totalFitness += g.Fitness;
	}

	_thisGeneration.Sort(new GenomeComparer());

	// now sorted in order of fitness.
	double fitness = 0.0;
	_fitnessTable.Clear();

	for (int i = 0; i < PopulationSize; i++)
	{
	fitness += ((Genome)_thisGeneration[i]).Fitness;
	_fitnessTable.Add((double)fitness);
	}
	}

	/// <summary>
	/// Create the initial genomes by repeated calling the supplied fitness function
	/// </summary>
	private void CreateGenomes()
	{
	for (int i = 0; i < PopulationSize; i++)
	{
	Genome genome = new Genome(GenomeSize);
	_thisGeneration.Add(genome);
	}
	}

	private void CreateNextGeneration()
	{
	_nextGeneration.Clear();
	Genome genome = null;

	if (Elitism)
	genome = _thisGeneration[PopulationSize - 1];

	for (int i = 0; i < PopulationSize; i += 2)
	{
	int pidx1 = RouletteSelection();
	int pidx2 = RouletteSelection();

	Genome parent1, parent2, child1, child2;
	parent1 = _thisGeneration[pidx1];
	parent2 = _thisGeneration[pidx2];

	if (_random.NextDouble() < CrossoverRate)
	{
	parent1.Crossover(ref parent2, out child1, out child2);
	}
	else
	{
	child1 = parent1;
	child2 = parent2;
	}

	child1.Mutate();
	child2.Mutate();

	_nextGeneration.Add(child1);
	_nextGeneration.Add(child2);
	}

	if (Elitism && genome != null)
	_nextGeneration[0] = genome;

	_thisGeneration.Clear();

	for (int i = 0; i < PopulationSize; i++)
	_thisGeneration.Add(_nextGeneration[i]);
	}

	public void GetBest(out double[] values, out double fitness)
	{
	Genome genome = _thisGeneration[PopulationSize - 1];
	values = new double[genome.Length];
	genome.GetValues(ref values);
	fitness = (double)genome.Fitness;
	}

	public void GetWorst(out double[] values, out double fitness)
	{
	GetNthGenome(0, out values, out fitness);
	}

	public void GetNthGenome(int n, out double[] values, out double fitness)
	{
	if (n < 0 \|\| n > PopulationSize - 1)
	throw new ArgumentOutOfRangeException("n too large, or too small");

	Genome genome = _thisGeneration[n];
	values = new double[genome.Length];
	genome.GetValues(ref values);
	fitness = (double)genome.Fitness;
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Genome

	namespace GeneticAlgorithm
	{
	public class Genome
	{
	static Random _random = new Random();
	public static double MutationRate { get; set; }
	public double Fitness { get; set; }
	public int Length { get; private set; }
	public double[] Genes { get; private set; }

	public Genome(int length)
	{
	Length = length;
	Genes = new double[length];
	CreateGenes();
	}

	public Genome(int length, bool createGenes)
	{
	Length = length;
	Genes = new double[length];
	if (createGenes)
	CreateGenes();
	}

	public Genome(ref double[] genes)
	{
	Length = genes.GetLength(0);
	Genes = new double[Length];
	for (int i = 0; i < Length; i++)
	Genes[i] = genes[i];
	}

	private void CreateGenes()
	{
	// DateTime d = DateTime.UtcNow;
	for (int i = 0; i < Length; i++)
	Genes[i] = _random.NextDouble();
	}

	public void Crossover(ref Genome genome2, out Genome child1, out Genome child2)
	{
	int pos = (int)(_random.NextDouble() * (double)Length);
	child1 = new Genome(Length, false);
	child2 = new Genome(Length, false);
	for (int i = 0; i < Length; i++)
	{
	if (i < pos)
	{
	child1.Genes[i] = Genes[i];
	child2.Genes[i] = genome2.Genes[i];
	}
	else
	{
	child1.Genes[i] = genome2.Genes[i];
	child2.Genes[i] = Genes[i];
	}
	}
	}

	public void Mutate()
	{
	for (int pos = 0; pos < Length; pos++)
	{
	if (_random.NextDouble() < MutationRate)
	Genes[pos] = (Genes[pos] + _random.NextDouble()) / 2.0;
	}
	}

	public void GetValues(ref double[] values)
	{
	for (int i = 0; i < Length; i++)
	values[i] = Genes[i];
	}

	public override string ToString()
	{
	string result = "";
	for (int i = 0; i < Length; i++)
	{
	result += string.Format("{0:F4}", Genes[i]);
	}

	return result;
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

GenomeComparer

	namespace GeneticAlgorithm
	{
	/// <summary>
	/// Compares genomes by fitness
	/// </summary>
	public sealed class GenomeComparer : IComparer<Genome>
	{
	public int Compare(Genome x, Genome y)
	{
	if (x.Fitness > y.Fitness)
	return 1;
	else if (x.Fitness == y.Fitness)
	return 0;
	else
	return -1;
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

artificial-intelligencecsharp

I'm Chris Small, a software engineer working in London. This is my tech blog. Find out more about me via Github, Stackoverflow, Resume