This is a C# implementation of Genetic Algorithm based on the articles by The Nature Of Code . To understand the algorithm in more details, I would recommend you go read the article.
The implementation tries to evolve a random string into a string that makes sense. In our example, something random into the string "to be or not to be". The problem arises from a story of a monkey that is typing on the keyboard randomly. It is said, that at some point, the monkey would type the full works of Shakespeare, but the time it would take would be very very long, hence the need of genetic algorithms, to evolve that solution a bit faster.
The code can also be found on GitHub .
The implementation has been divided into a number of parts, as listed below
SETUP
- Initialize. Creating a population of N elements each with randomly generated DNA
LOOP
- Selection. Evaluating the fitness of each element of the population and building a mating pool.
- Reproduction, which is repeated N times, i.e.:
a) Picking two parent with probability according to relative fitness.
b) Crossover - where we create a child by combing the DNA of the two parents.
c) Mutation - we mutate the child's DNA based on a given probability
d) We add the new child to the population.
e) We replace the old population with the new population and return to step 1 of the loop
The Implementation Code
- Initializing the population.
In order to initialize the population we need an object to store the genetic information of an element in the population. In our situation we created a class and called it the DNA.
public class DNA
{
}
The population will be made up of an array of DNA objects each representing an element.
public class Population
{
private DNA[] population;
}
I also created a class called Population, which will be used to represent the functionality performed on the population.
Our genetic algorithm dictates that we create a population of N elements, each with randomly generated DNA. This will be accomplished in two steps. One the DNA will initialize itself with an array of random characters. This is accomplished on the constructor of the DNA class, so it's done automatically when the object is created. The constructor will also take a target string that will be used to evaluate the fitness of an object.
public class DNA
{
public char[] genes = new char[18];
private string target;
private static Random rnd = new Random();
const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ";
public DNA(string target)
{
this.target = target;
for (int i = 0; i < this.genes.Length; i++)
{
genes[i] = chars[rnd.Next(chars.Length)];
}
}
}
The Random class was used to generate a random character to fill the array, using a set of predefined strings. The character can be any alphanumeric character. We used an array of characters to represent the genes, i.e. the DNA because we will be performing operations on the characters, and strings won't be good to serve our purpose.
The next step, would be to implement the generation of the random population. And this is done on the constructor the Population class.
public class Population
{
private int totalPopulation;
private DNA[] population;
private Random rnd = new Random();
public Population(int totalPopulation)
{
this.totalPopulation = totalPopulation;
population = new DNA[this.totalPopulation];
for (int i = 0; i < this.population.Length; i++)
{
population[i] = new DNA(this.target);
}
}
}
Both of our classes are not complete, but we will complete them in a few.
The next step would be to deal with selection, which involves evaluating the fitness of each element of the population and building a mating pool. We calculated our fitness as follows:
Fitness = total # characters correct / total # characters
Our target character for this tutorial is the phrase "to be or not to be". And the code for implementing this is in the DNA class, the object will calculate it's fitness.
public class DNA
{
public float Fitness { get; set; }
public void EvaluateFitness()
{
int score = 0;
for (int i = 0; i < this.genes.Length; i++)
{
if (genes[i] == target[i])
{
score++;
}
}
Fitness = (float)score / target.Length;
}
}
After we have the fitness score, we can build the mating pool that we need for the reproduction step. The mating pool represents a data structure from which we continuously use to pick two parents. We pick our parents with properties calculated according to fitness. We used a list to represent our dynamic array list and we pick them according to the probabilities we used to fill them on the list.
public class Population
{
private List<DNA> matingPool;
private void CreateMatingPool()
{
matingPool = new List<DNA>();
for (int i = 0; i < this.population.Length; i++)
{
int n = (int)(population[i].Fitness * 100);
for (int j = 0; j < n; j++)
{
matingPool.Add(population[i]);
}
}
}
}
The next step would be to implement reproduction, which we accomplished by creating a child using half of the characters from parent A, and the other half of the characters from Parent B. The midpoint is determined randomly, hence it's not even really a midpoint. The code that implements that is listed below
public class Population
{
private void Reproduce()
{
for (int i = 0; i < this.population.Length; i++)
{
int a = rnd.Next(0, matingPool.Count);
int b = rnd.Next(0, matingPool.Count);
DNA parentA = matingPool[a];
DNA parentB = matingPool[b];
DNA child = Crossover(parentA, parentB);
child.Mutate(this.mutationRate);
population[i] = child;
}
}
private DNA Crossover(DNA parentA, DNA parentB)
{
DNA child = new DNA(this.target);
int midpoint = (int)rnd.Next(child.genes.Length);
for (int i = 0; i < child.genes.Length; i++)
{
if (i > midpoint)
{
child.genes[i] = parentA.genes[i];
}
else
{
child.genes[i] = parentB.genes[i];
}
}
return child;
}
}
Before we added, the new child to the population, we performed on critical action called mutation, which basically ensures that there is a variety in the population and that we do not stagnate at some point, but our solution continues to evolve from time to time. The code that implemented that is listed below:
public class DNA
{
public void Mutate(float mutationRate)
{
for (int i = 0; i < genes.Length; i++)
{
if (rnd.NextDouble() < mutationRate)
{
genes[i] = (char) rnd.Next(32, 128);
}
}
}
}
Finally, the last crucial step was putting all the above code together, to function as one and I did that using a method in the Population class called GenerateSolution();. The method creates a loop that will stop once the solution we needed has been found. The method assumes that at some point, all the members of the population will be the same, and picking a random element and comparing it to our intended solution will tell us just that.
public class Population
{
public void GenerateSolution()
{
int random = rnd.Next(population.Length);
while (population[random].ToString() != target)
{
Console.Write("Current Random String: ");
Console.WriteLine(population[random].ToString());
EvaluateElementsFitness();
CreateMatingPool();
Reproduce();
}
Console.WriteLine("\nPhrase: {0}", population[random].ToString());
}
private void EvaluateElementsFitness()
{
for (int i = 0; i < this.population.Length; i++)
{
population[i].EvaluateFitness();
}
}
}
The whole program, as I wrote in my computer is listed below. The program was made up of three classes, the DNA, Population and Program
DNA.cs
using System;
namespace GeneticAlgorithm
{
public class DNA
{
public char[] genes = new char[18];
private string target;
public float Fitness { get; set; }
private static Random rnd = new Random();
const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ";
public DNA(string target)
{
this.target = target;
for (int i = 0; i < this.genes.Length; i++)
{
genes[i] = chars[rnd.Next(chars.Length)];
}
}
public void EvaluateFitness()
{
int score = 0;
for (int i = 0; i < this.genes.Length; i++)
{
if (genes[i] == target[i])
{
score++;
}
}
Fitness = (float)score / target.Length;
}
public void Mutate(float mutationRate)
{
for (int i = 0; i < genes.Length; i++)
{
if (rnd.NextDouble() < mutationRate)
{
genes[i] = (char) rnd.Next(32, 128);
}
}
}
public override string ToString()
{
return new string(genes);
}
}
}
Population.cs
using System;
using System.Collections.Generic;
namespace GeneticAlgorithm
{
public class Population
{
private int totalPopulation;
private float mutationRate;
private string target;
private DNA[] population;
private List<DNA> matingPool;
private Random rnd = new Random();
public Population() : this(150) { }
public Population(int totalPopulation) : this(150, 0.01f) { }
public Population(int totalPopulation, float mutationRate) : this(150, 0.01f, "to be or not to be") { }
public Population(int totalPopulation, float mutationRate, string target)
{
this.totalPopulation = totalPopulation;
this.mutationRate = mutationRate;
this.target = target;
population = new DNA[this.totalPopulation];
for (int i = 0; i < this.population.Length; i++)
{
population[i] = new DNA(this.target);
}
}
public void GenerateSolution()
{
int random = rnd.Next(population.Length);
while (population[random].ToString() != target)
{
Console.Write("Current Random String: ");
Console.WriteLine(population[random].ToString());
EvaluateElementsFitness();
CreateMatingPool();
Reproduce();
}
Console.WriteLine("\nPhrase: {0}", population[random].ToString());
}
private void EvaluateElementsFitness()
{
for (int i = 0; i < this.population.Length; i++)
{
population[i].EvaluateFitness();
}
}
private void CreateMatingPool()
{
matingPool = new List<DNA>();
for (int i = 0; i < this.population.Length; i++)
{
int n = (int)(population[i].Fitness * 100);
for (int j = 0; j < n; j++)
{
matingPool.Add(population[i]);
}
}
}
private void Reproduce()
{
for (int i = 0; i < this.population.Length; i++)
{
int a = rnd.Next(0, matingPool.Count);
int b = rnd.Next(0, matingPool.Count);
DNA parentA = matingPool[a];
DNA parentB = matingPool[b];
DNA child = Crossover(parentA, parentB);
child.Mutate(this.mutationRate);
population[i] = child;
}
}
private DNA Crossover(DNA parentA, DNA parentB)
{
DNA child = new DNA(this.target);
int midpoint = (int)rnd.Next(child.genes.Length);
for (int i = 0; i < child.genes.Length; i++)
{
if (i > midpoint)
{
child.genes[i] = parentA.genes[i];
}
else
{
child.genes[i] = parentB.genes[i];
}
}
return child;
}
}
}
Program.cs
namespace GeneticAlgorithm
{
class Program
{
static void Main(string[] args)
{
Population problem1 = new Population(150, 0.01f, "to be or not to be");
problem1.GenerateSolution();
}
}
}
Thanks for reading this, I hope the solution works on your machine because it definitely did work on mine wink emojis