shaunhey/program.cs

## program.cs
using System;
using System.Collections.Generic;
using System.Text;

namespace ml
{
    public class Citizen
    {
        private static int _nextId = 0;

        public int Id { get; private set; }
        public int Fitness { get; private set; }
        public string Value { get; set; }

        // Not necessary, but fun...
        public Citizen Mother { get; set; }
        public Citizen Father { get; set; }

        public Citizen()
        {
            Id = _nextId;
            _nextId++;

            Fitness = int.MaxValue;
            Value = "";

            Mother = null;
            Father = null;
        }

        public override string ToString()
        {
            return string.Format("Id: {0:D6}, Value: {1}, Fitness: {2:D4}, Mother: {3:D6}, Father: {4:D6}",
                Id, Value, Fitness, (Mother == null) ? 0 : Mother.Id, (Father == null) ? 0 : Father.Id);
        }

        public void SetFitnessToTarget(string target)
        {
            int fitness = 0;

            for (int i = 0; i < target.Length; i++)
            {
                int difference = target[i] - Value[i];
                fitness += Math.Abs(difference);
            }

            Fitness = fitness;
        }
    }

    public class Simulation
    {
        private readonly string POSSIBLE_CHARACTERS = " `1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>?";

        private List<Citizen> m_population;
        private Random m_random = new Random();
        private string m_target = "";
        private int m_populationSize = 0;
        private double m_mutationRate = 0.0;
        DateTime m_startTime;
        DateTime m_endTime;

        public Simulation(string target, int populationSize, double mutationRate)
        {
            m_target = target;
            m_populationSize = populationSize;
            m_mutationRate = mutationRate;
            m_population = new List<Citizen>(populationSize);

            Console.WriteLine("Target: {0}, Population Size: {1}, Mutation Rate: {2}", target, populationSize, mutationRate);

            // The first generation. About the same intelligence as most politicians...
            for (int i = 0; i < populationSize; i++)
            {
                Citizen c = new Citizen();
                c.Value = GenerateRandomString(target.Length);
                m_population.Add(c);
            }
        }

        void CalculateTheFitnessOfTheCitizens()
        {
            m_population.ForEach((c) => { c.SetFitnessToTarget(m_target); });
        }

        void SortThePopulationByFitness()
        {
            m_population.Sort((left, right) => left.Fitness.CompareTo(right.Fitness));
        }

        void RemoveTheWeakestCitizens()
        {
            m_population.RemoveRange(m_populationSize / 2, m_populationSize / 2);
        }

        string GenerateRandomString(int length)
        {
            StringBuilder sb = new StringBuilder(length);

            for (int i = 0; i < length; i++)
            {
                sb.Append(POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)]);
            }

            return sb.ToString();
        }

        void ApplyRandomMutation(ref StringBuilder value)
        {
            value[m_random.Next(value.Length)] = POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)];
        }

        void GetRandomParents(out Citizen mother, out Citizen father)
        {
            int a = m_random.Next(m_population.Count);
            int b = m_random.Next(m_population.Count);

            while (b == a) //Don't allow the same parent for both
            {
                b = m_random.Next(m_population.Count);
            }

            mother = m_population[a];
            father = m_population[b];
        }

        Citizen Mate(Citizen mother, Citizen father)
        {
            StringBuilder newValue = new StringBuilder();
            Citizen child = new Citizen();

            child.Mother = mother;
            child.Father = father;

            for (int i = 0; i < mother.Value.Length; i++)
            {
                // Determine dominant features randomly
                bool fatherIsDominant = m_random.NextDouble() < .5;

                if (fatherIsDominant)
                    newValue.Append(father.Value[i]);
                else
                    newValue.Append(mother.Value[i]);
            }

            double chanceOfMutation = m_random.NextDouble();
            if (chanceOfMutation < m_mutationRate)
                ApplyRandomMutation(ref newValue);

            child.Value = newValue.ToString();

            return child;
        }

        void MateThePopulation()
        {
            var parents = m_population;
            var children = new List<Citizen>(m_populationSize);

            for (int i = 0; i < m_populationSize; i++)
            {
                Citizen mother = null;
                Citizen father = null;

                GetRandomParents(out mother, out father);

                var child = Mate(mother, father);

                children.Add(child);
            }

            m_population = children; //Children are the future...
        }

        void PrintPaternalLineage(Citizen c)
        {
            Citizen father = c.Father;
            Console.Write("{0} ", c.Id);
            while (father != null)
            {
                Console.Write("=> {0} ", father.Id);
                father = father.Father;
            }
            Console.WriteLine();
        }

        public void Run(int maxGenerations)
        {
            Console.WriteLine("Starting simulation");
            m_startTime = DateTime.Now;

            for (int i = 0; i < maxGenerations; i++)
            {
                CalculateTheFitnessOfTheCitizens();
                SortThePopulationByFitness();

                var fittest = m_population[0];

                Console.WriteLine("[Gen {0:D5}] {1}", i, fittest);

                // Game over...
                if (fittest.Fitness == 0)
                {
                    m_endTime = DateTime.Now;
                    Console.WriteLine();
                    Console.WriteLine("Perfection reached after {0} generations. Time elapsed: {1}", i, (m_endTime - m_startTime).ToString());
                    Console.WriteLine();
                    PrintPaternalLineage(fittest);
                    break;
                }

                RemoveTheWeakestCitizens();
                MateThePopulation();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Simulation s = new Simulation(
                target: "Genetic algorithms are cool!",
                populationSize: 2048,
                mutationRate: 0.25);

            s.Run(maxGenerations: 100);

            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }
}
	using System;
	using System.Collections.Generic;
	using System.Text;

	namespace ml
	{
	public class Citizen
	{
	private static int _nextId = 0;

	public int Id { get; private set; }
	public int Fitness { get; private set; }
	public string Value { get; set; }

	// Not necessary, but fun...
	public Citizen Mother { get; set; }
	public Citizen Father { get; set; }

	public Citizen()
	{
	Id = _nextId;
	_nextId++;

	Fitness = int.MaxValue;
	Value = "";

	Mother = null;
	Father = null;
	}

	public override string ToString()
	{
	return string.Format("Id: {0:D6}, Value: {1}, Fitness: {2:D4}, Mother: {3:D6}, Father: {4:D6}",
	Id, Value, Fitness, (Mother == null) ? 0 : Mother.Id, (Father == null) ? 0 : Father.Id);
	}

	public void SetFitnessToTarget(string target)
	{
	int fitness = 0;

	for (int i = 0; i < target.Length; i++)
	{
	int difference = target[i] - Value[i];
	fitness += Math.Abs(difference);
	}

	Fitness = fitness;
	}
	}

	public class Simulation
	{
	private readonly string POSSIBLE_CHARACTERS = " `1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}\|ASDFGHJKL:\"ZXCVBNM<>?";

	private List<Citizen> m_population;
	private Random m_random = new Random();
	private string m_target = "";
	private int m_populationSize = 0;
	private double m_mutationRate = 0.0;
	DateTime m_startTime;
	DateTime m_endTime;

	public Simulation(string target, int populationSize, double mutationRate)
	{
	m_target = target;
	m_populationSize = populationSize;
	m_mutationRate = mutationRate;
	m_population = new List<Citizen>(populationSize);

	Console.WriteLine("Target: {0}, Population Size: {1}, Mutation Rate: {2}", target, populationSize, mutationRate);

	// The first generation. About the same intelligence as most politicians...
	for (int i = 0; i < populationSize; i++)
	{
	Citizen c = new Citizen();
	c.Value = GenerateRandomString(target.Length);
	m_population.Add(c);
	}
	}

	void CalculateTheFitnessOfTheCitizens()
	{
	m_population.ForEach((c) => { c.SetFitnessToTarget(m_target); });
	}

	void SortThePopulationByFitness()
	{
	m_population.Sort((left, right) => left.Fitness.CompareTo(right.Fitness));
	}

	void RemoveTheWeakestCitizens()
	{
	m_population.RemoveRange(m_populationSize / 2, m_populationSize / 2);
	}

	string GenerateRandomString(int length)
	{
	StringBuilder sb = new StringBuilder(length);

	for (int i = 0; i < length; i++)
	{
	sb.Append(POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)]);
	}

	return sb.ToString();
	}

	void ApplyRandomMutation(ref StringBuilder value)
	{
	value[m_random.Next(value.Length)] = POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)];
	}

	void GetRandomParents(out Citizen mother, out Citizen father)
	{
	int a = m_random.Next(m_population.Count);
	int b = m_random.Next(m_population.Count);

	while (b == a) //Don't allow the same parent for both
	{
	b = m_random.Next(m_population.Count);
	}

	mother = m_population[a];
	father = m_population[b];
	}

	Citizen Mate(Citizen mother, Citizen father)
	{
	StringBuilder newValue = new StringBuilder();
	Citizen child = new Citizen();

	child.Mother = mother;
	child.Father = father;

	for (int i = 0; i < mother.Value.Length; i++)
	{
	// Determine dominant features randomly
	bool fatherIsDominant = m_random.NextDouble() < .5;

	if (fatherIsDominant)
	newValue.Append(father.Value[i]);
	else
	newValue.Append(mother.Value[i]);
	}

	double chanceOfMutation = m_random.NextDouble();
	if (chanceOfMutation < m_mutationRate)
	ApplyRandomMutation(ref newValue);

	child.Value = newValue.ToString();

	return child;
	}

	void MateThePopulation()
	{
	var parents = m_population;
	var children = new List<Citizen>(m_populationSize);

	for (int i = 0; i < m_populationSize; i++)
	{
	Citizen mother = null;
	Citizen father = null;

	GetRandomParents(out mother, out father);

	var child = Mate(mother, father);

	children.Add(child);
	}

	m_population = children; //Children are the future...
	}

	void PrintPaternalLineage(Citizen c)
	{
	Citizen father = c.Father;
	Console.Write("{0} ", c.Id);
	while (father != null)
	{
	Console.Write("=> {0} ", father.Id);
	father = father.Father;
	}
	Console.WriteLine();
	}

	public void Run(int maxGenerations)
	{
	Console.WriteLine("Starting simulation");
	m_startTime = DateTime.Now;

	for (int i = 0; i < maxGenerations; i++)
	{
	CalculateTheFitnessOfTheCitizens();
	SortThePopulationByFitness();

	var fittest = m_population[0];

	Console.WriteLine("[Gen {0:D5}] {1}", i, fittest);

	// Game over...
	if (fittest.Fitness == 0)
	{
	m_endTime = DateTime.Now;
	Console.WriteLine();
	Console.WriteLine("Perfection reached after {0} generations. Time elapsed: {1}", i, (m_endTime - m_startTime).ToString());
	Console.WriteLine();
	PrintPaternalLineage(fittest);
	break;
	}

	RemoveTheWeakestCitizens();
	MateThePopulation();
	}
	}
	}

	class Program
	{
	static void Main(string[] args)
	{
	Simulation s = new Simulation(
	target: "Genetic algorithms are cool!",
	populationSize: 2048,
	mutationRate: 0.25);

	s.Run(maxGenerations: 100);

	Console.WriteLine("Press any key...");
	Console.ReadKey();
	}
	}
	}