Skip to content

Instantly share code, notes, and snippets.

@yetanotherchris
Created February 19, 2013 10:37
Show Gist options
  • Save yetanotherchris/4984748 to your computer and use it in GitHub Desktop.
Save yetanotherchris/4984748 to your computer and use it in GitHub Desktop.
GA1: GA class
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment