Simple genetic algorithm on C#

I'm reading the book and introduction to genetic algorithms by MIt Press and I really like the topic. I have not read any implementation online of the many implementations that they are for this type of algorithms and i'm going to implement them from scratch. Then after i finish the book compare to the ones online. So the first thing that needs to be explained before we go into the code is what is a genetic algorithm and what are their uses. According to wikipedia "A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems." That sums it up pretty well they help us find better candidate solutions to a problem that has no optimal solution. They help you search for solutions. What involves a genetic algorithm.

  1. Define a starting population.
  2. Use a method of probability to decide who breeds with who (fitness function).
  3. Breed the next generation.
  4. Mutate the next generation.
  5. Iterate trough the process a given number of times.

After reading the first chapter of the book and seeing and example of the steps that take to create a genetic algorithm is the code at the bottom is what I came up with. There is a few things at the moment i still need to clean it up a bit and make a more generic implementation but if someone wants to give me feedback or participate on this it will be more than welcome:

 
 

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; namespace SimpleGeneticAlgorithm { public delegate int FitnessDelegate(object chromosomeRepresentation); public delegate ChromosomePair SelectionDelegate(); public struct ChromosomePair { public Chromosome parent1; public Chromosome parent2; }
public class Chromosome { public string ChromosomeString { set; get; }
public int CalculateFitness(FitnessDelegate fitnessFunction) { return fitnessFunction(ChromosomeString); }
public static int SumStringCharacter(object chromosomestring) { int sum = 0; foreach (char c in (string)chromosomestring) { if (c == '1') { sum++; } else if (c == '0') { } else { //tODO:AddErrorCondition } } return sum; }
public Chromosome() { Random r = new Random(Convert.ToInt32(DateTime.Now.Ticks % Int16.MaxValue)); this.ChromosomeString = String.Empty; for (int i = 0; i < 8; i++) { this.ChromosomeString += "" + r.Next() % 2; } Thread.Sleep(1); } }
public class GenerationManager { public Chromosome[] CurrentGen; public List PastGenerations = new List(); public SelectionDelegate SelectionAlgorithm; public int CrossoverProbability = 50; //This is a percentage public int MutationProbability = 25; public GenerationManager() { CurrentGen = new Chromosome[4]; for (int i = 0; i < 4; i++) { CurrentGen[i] = new Chromosome(); } }
public ChromosomePair BasicSelection() {
ChromosomePair pair = new ChromosomePair(); int currentHighest=-1; int secondHighest=-1; for (int i = 0; i < 4; i++) { Random r = new Random(Convert.ToInt32(DateTime.Now.Ticks % Int16.MaxValue));
 int val = 
(CurrentGen[i].CalculateFitness(Chromosome.SumStringCharacter)
 + (r.Next() % 
14)); if (val >= currentHighest)
{
pair.parent2 = 
pair.parent1;
pair.parent1 = CurrentGen[i];
secondHighest = 
currentHighest;
currentHighest = val;
}
Thread.Sleep(1);
}
if 
(secondHighest == -1)
{
return BasicSelection();
}
return 
pair;
}

public ChromosomePair Crossover(ChromosomePair pair) { ChromosomePair par = new ChromosomePair(); Random r = new Random(Convert.ToInt32(DateTime.Now.Ticks % Int16.MaxValue)); bool doCrossover = (((r.Next() % 100) + 1) < CrossoverProbability); if (doCrossover) { par.parent1 = GenerateChild(pair); } else { par.parent1 = pair.parent1; par.parent2 = pair.parent2; } return par;
}
private Chromosome GenerateChild(ChromosomePair pair) { Byte[] parentOneArray = getByteArrayFromString(pair.parent1.ChromosomeString); Byte[] parentTwoArray = getByteArrayFromString(pair.parent2.ChromosomeString); Chromosome ret = new Chromosome(); for(int i =0 ; i< parentOneArray.Length; i++) { parentOneArray[i] = (byte)(parentOneArray[i] | parentTwoArray[i]); } ret.ChromosomeString = getStringFromByteArray(parentOneArray); return ret; }
private byte[] getByteArrayFromString(string p) { List ret = new List(); foreach (Char c in p) { if (c == '1') { ret.Add(1); } else { ret.Add(0); } } return ret.ToArray(); } private string getStringFromByteArray(byte[] p) { string a = string.Empty; foreach (byte c in p) { a += c; } return a; }
public Chromosome Mutate(Chromosome entry) { Random r = new Random(Convert.ToInt32(DateTime.Now.Ticks % Int16.MaxValue)); bool doMutation = (((r.Next() % 100))< MutationProbability);Chromosome ret = new Chromosome(); ret.ChromosomeString = entry.ChromosomeString;
 if (doMutation) { 
if (entry.ChromosomeString.IndexOf('0') >= 0)
{
byte[] tmp = 
getByteArrayFromString(entry.ChromosomeString);
tmp[entry.ChromosomeString.IndexOf('0')] 
= 1;
ret.ChromosomeString = getStringFromByteArray(tmp);
}

} return ret; } }
}
using System; using System.Collections.Generic; using System.Linq; using System.Text; using SimpleGeneticAlgorithm;
namespace GeneticAlgorithmTestConsole { class Program { public static void Main(string[] args) { GenerationManager manager = new GenerationManager(); Console.WriteLine("First gen:"); Chromosome[] Gen = manager.CurrentGen; foreach (Chromosome c in Gen) { Console.WriteLine(c.ChromosomeString +" " + c.CalculateFitness(Chromosome.SumStringCharacter)); } Console.WriteLine("Pair Matches"); List pairs = new List(); foreach (Chromosome c in Gen) { ChromosomePair pair = manager.BasicSelection(); pairs.Add(pair); Console.WriteLine(pair.parent1.ChromosomeString + " " + pair.parent2.ChromosomeString); } Console.WriteLine("First Generation Before mutation Childrens"); List nextgen = new List(); foreach (ChromosomePair p in pairs) { ChromosomePair pair = manager.Crossover(p); if (pair.parent2== null) { Console.WriteLine(pair.parent1.ChromosomeString); nextgen.Add(pair.parent1); } else { Console.WriteLine(pair.parent1.ChromosomeString + " " + pair.parent2.ChromosomeString); nextgen.Add(pair.parent1); nextgen.Add(pair.parent2); } } if (nextgen.Count > 4) { nextgen.RemoveRange(3, nextgen.Count - 1 - 3); } //Run mutations Console.WriteLine("First Generation After Mutation Childrens"); for(int i =0; i< nextgen.Count; i++) { nextgen[i] = manager.Mutate(nextgen[i]); Console.WriteLine(nextgen[i].ChromosomeString); } manager.PastGenerations.Add(manager.CurrentGen);
manager.CurrentGen = nextgen.ToArray();
Console.WriteLine("How many more generations would you like to iterate"); int iterations = Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < iterations; i++) { IterateGeneration(manager); } Console.ReadLine(); }
public static void IterateGeneration(GenerationManager manager) { Chromosome[] Gen = manager.CurrentGen; foreach (Chromosome c in Gen) { Console.WriteLine(c.ChromosomeString + " " + c.CalculateFitness(Chromosome.SumStringCharacter)); } Console.WriteLine("Pair Matches"); List pairs = new List(); foreach (Chromosome c in Gen) { ChromosomePair pair = manager.BasicSelection(); pairs.Add(pair); Console.WriteLine(pair.parent1.ChromosomeString + " " + pair.parent2.ChromosomeString); } Console.WriteLine("First Generation Before mutation Childrens"); List nextgen = new List(); foreach (ChromosomePair p in pairs) { ChromosomePair pair = manager.Crossover(p); if (pair.parent2 == null) { Console.WriteLine(pair.parent1.ChromosomeString); nextgen.Add(pair.parent1); } else { Console.WriteLine(pair.parent1.ChromosomeString + " " + pair.parent2.ChromosomeString); nextgen.Add(pair.parent1); nextgen.Add(pair.parent2); } } if (nextgen.Count > 4) { nextgen.RemoveRange(3, nextgen.Count - 1 - 3); } //Run mutations Console.WriteLine("First Generation After Mutation Childrens"); for (int i = 0; i < nextgen.Count; i++) { nextgen[i] = manager.Mutate(nextgen[i]); Console.WriteLine(nextgen[i].ChromosomeString); } manager.PastGenerations.Add(manager.CurrentGen);
manager.CurrentGen = nextgen.ToArray();
} } }


Similar Articles