Where equations are born and mutants are buried

Question

I've read up on genetic programming yesterday so I figured I'd try to implement something myself. I would like the main focus to be on whether or not I've implemented the idea behind it correctly.

The thought behind it is simple: given a number and a few parameters, generate an equation that yields that number as solution. I have implemented the *, /, +, - and ^ operators.

The world gets populated with an equation of the form x + (y - z) where the values are randomly generated (I might generate the operators randomly as well later).

Some key remarks about the implementation:

• An equation whose result is not within the predetermined boundaries of the target solution, will be killed.

• A new generation consists of mutated equations and children. Parents are no longer in the new generation.

• When there's a single generation left, it will occassionally mutate until he is outside of the acceptable boundaries.

Which will raise the question: is this a good approach or should it be done differently?

Program

class Program
{
    static void Main(string[] args)
    {
        new Program();
        Console.Read();
    }

    private static void PrintTree(GeneticTree tree)
    {
        var output = string.Format("{0}: {1:0}{2, 15}[{3}]", tree.Name, tree.GetResult(), string.Empty, tree.GetDisplay());
        Console.WriteLine(output);
    }

    private static void PrintWorld(World world)
    {
        Console.WriteLine("================================");
        Console.WriteLine("Generation {0}", world.Generation);
        foreach (var algorithm in world.Population)
        {
            PrintTree(algorithm);
        }
    }

    public Program()
    {
        var world = new World(targetValue: 50, populationSize: 30, fitnessDelta: 100, mutationChance: 0.2d, minValue: -50, maxValue: 50);

        do
        {
           PrintWorld(world);
        } while (!world.AdvanceGeneration() && !world.Apocalypse);

        if (world.Apocalypse)
        {
            Console.WriteLine("No suitable solution has been found with the given parameters");
        }
        else
        {
            PrintWorld(world);
            Console.WriteLine("Possible solutions after {0} generation(s):", world.Generation);
            foreach (var solution in world.WorkingAlgorithms)
            {
                Console.WriteLine("{0}: {1}", solution.Name, solution.GetDisplay());
            }
        }
    }
}

World

public class World
{
    private static readonly Random Random = new Random();
    private readonly int _populationSize;
    private readonly int _targetValue; 
    private readonly int _fitnessDelta;
    private readonly double _mutationChance;
    private readonly int _minValue;
    private readonly int _maxValue;

    public List<GeneticTree> Population { get; private set; }

    public List<GeneticTree> WorkingAlgorithms { get; private set; }

    public bool Apocalypse { get; private set; }

    public int Generation { get; private set; }

    public World(int targetValue, int populationSize, int fitnessDelta, double mutationChance, int minValue, int maxValue)
    {
        Population = new List<GeneticTree>();
        WorkingAlgorithms = new List<GeneticTree>();
        _targetValue = targetValue;
        _populationSize = populationSize;
        _fitnessDelta = fitnessDelta;
        _mutationChance = mutationChance;
        _minValue = minValue;
        _maxValue = maxValue;
        Initialize();
        Generation = 1;
    }

    private void Initialize()
    {
        for (var i = 0; i < _populationSize; i++)
        {
            var tree = new GeneticTree( _minValue, _maxValue)
            {
                Name = "Algorithm " + i
            };

            Element ops = new AdditionOperator
            {
                LeftElement = new ValueElement(Random.Next(_minValue, _maxValue)),
                RightElement = new SubtractionOperator
                {
                    LeftElement = new ValueElement(Random.Next(_minValue, _maxValue)),
                    RightElement = new ValueElement(Random.Next(_minValue, _maxValue))
                }
            }; // x + (y - z)
            tree.AddOperations(ops);
            Population.Add(tree);
        }
    }

    /// <summary>
    /// Returns true when a solution has been found
    /// </summary>
    public bool AdvanceGeneration()
    {
        var newGeneration = new List<GeneticTree>(Population.Count);

        // Add random roll to determine whether it should mutate or combine with another algorithm
        for (int index = 0; index < Population.Count; index++)
        {
            var algorithm = Population[index];
            if (Random.NextDouble() < _mutationChance)
            {
                algorithm.Mutate();
                newGeneration.Add(algorithm);
            }
            else
            {
                var randomParent = Population.ElementAt(Random.Next(0, Population.Count));
                var child = algorithm.Combine(randomParent);
                newGeneration.Add(child);
            }
        }

        Population = newGeneration;
        ++Generation;
        return CheckFitness();
    }

    private bool CheckFitness()
    {
        var foundSolution = false;

        for (int index = 0; index < Population.Count; index++)
        {
            var algorithm = Population[index];
            var result = algorithm.GetResult();
            if ((Math.Abs(result - _targetValue) < 0.1))
            {
                WorkingAlgorithms.Add(algorithm);
                foundSolution = true;
            }
            else
            {
                if (Math.Max(result, _targetValue) - Math.Min(result, _targetValue) > _fitnessDelta)
                {
                    Population.RemoveAt(index);
                }
            }
        }

        if (Population.Count == 0)
        {
            Apocalypse = true;
        }

        return foundSolution;
    }
}

Element

public abstract class Element
{
    public abstract double GetValue();

    public abstract string GetDisplay();

    public abstract List<Element> Children { get; }
}

Operators

public abstract class Operator : Element
{

}

public abstract class BinaryOperator : Operator
{
    public Element LeftElement { get; set; }

    public Element RightElement { get; set; }

    protected abstract string GetBinarySpecificDisplay();

    protected abstract double GetBinarySpecificValue(double leftValue, double rightValue);

    public override double GetValue()
    {
        var left = LeftElement as ValueElement;
        var leftValue = left != null ? left.Value : LeftElement.GetValue();

        var right = RightElement as ValueElement;
        var rightValue = right != null ? right.Value : RightElement.GetValue();

        return GetBinarySpecificValue(leftValue, rightValue);
    }

    public override List<Element> Children
    {
        get { return new List<Element> { LeftElement, RightElement }; }
    }

    public override string GetDisplay()
    {
        return LeftElement.GetDisplay() + " " + GetBinarySpecificDisplay() + " " + RightElement.GetDisplay();
    }
}

public class AdditionOperator : BinaryOperator
{

    protected override string GetBinarySpecificDisplay()
    {
        return "+";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue + rightValue;
    }
}

public class SubtractionOperator : BinaryOperator
{
    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue - rightValue;
    }

    protected override string GetBinarySpecificDisplay()
    {
        return "-";
    }
}

public class DivisionOperator : BinaryOperator
{
    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue / rightValue;
    }

    protected override string GetBinarySpecificDisplay()
    {
        return "/";
    }
}

public class MultiplicationOperator : BinaryOperator
{
    protected override string GetBinarySpecificDisplay()
    {
        return "*";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue * rightValue;
    }
}

public class ExclusiveOrOperator : BinaryOperator
{
    protected override string GetBinarySpecificDisplay()
    {
        return "^";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return (int) leftValue ^ (int) rightValue;
    }
}

ValueElement

public class ValueElement : Element
{
    public double Value { get; set; }

    public ValueElement(double value)
    {
        Value = value;
    }

    public override double GetValue()
    {
        return Value;
    }

    public override string GetDisplay()
    {
        return Value.ToString(CultureInfo.InvariantCulture);
    }

    public override List<Element> Children { get { return null; } }
}

GeneticTree

public class GeneticTree
{
    private const double MutationChance = 0.2d;
    private readonly int _upperBoundary;
    private readonly int _lowerBoundary;
    private readonly static Random Random = new Random();
    private readonly static Type[] BinaryOperations =
    {
        typeof(AdditionOperator), 
        typeof(SubtractionOperator), 
        typeof(DivisionOperator),
        typeof(MultiplicationOperator),
        typeof(ExclusiveOrOperator)
    };
    private bool _canStillSwap;
    private Element _nodes;

    public string Name { get; set; }

    public int Depth { get; private set; }

    public GeneticTree(int minValue, int maxValue)
    {
        _lowerBoundary = minValue;
        _upperBoundary = maxValue;
    }

    public void AddOperations(Element element)
    {
        _nodes = element;
        GetTreeDepth();
    }

    private void GetTreeDepth()
    {
        if (_nodes == null)
        {
            return;;
        }

        Depth = 1;

        if (_nodes.Children != null)
        {
            GetTreeDepth(_nodes.Children);
        }
    }

    private void GetTreeDepth(List<Element> children)
    {
        foreach(var child in children)
        {
            Depth++;
            if (child.Children != null)
            {
                GetTreeDepth(child.Children);
            }
        }
    }

    public double GetResult()
    {
        return _nodes.GetValue();
    }

    public string GetDisplay()
    {
        return _nodes.GetDisplay();
    }

    public void Mutate()
    {
        _canStillSwap = true;
        _nodes = InternalMutate(_nodes);
    }

    private Element InternalMutate(Element element)
    {
        if (!_canStillSwap)
        {
            return element;
        }

        if (MustMutate())
        {
            var valueElement = element as ValueElement;
            if (valueElement != null)
            {
                return MutateValueElement();
            }

            var binaryElement = element as BinaryOperator;
            if (binaryElement != null)
            {
                return MutateBinaryElement(binaryElement);
            }
        }
        else
        {
            if (element.Children != null)
            {
                var binaryOperator = element as BinaryOperator;
                if (binaryOperator != null)
                {
                    var leftChild = binaryOperator.LeftElement;
                    var rightChild = binaryOperator.RightElement;

                    leftChild = InternalMutate(leftChild);
                    rightChild = InternalMutate(rightChild);

                    binaryOperator.LeftElement = leftChild;
                    binaryOperator.RightElement = rightChild;
                }
            }
        }
        return element;
    }

    private Element MutateValueElement()
    {
        _canStillSwap = false;
        return new ValueElement(Random.Next(_lowerBoundary, _upperBoundary));
    }

    private Element MutateBinaryElement(BinaryOperator element)
    {
        var currentType = element.GetType();
        var newType = BinaryOperations.Except(new[] { currentType }).OrderBy(x => Guid.NewGuid()).First();
        var newElement = (BinaryOperator) Activator.CreateInstance(newType);
        newElement.LeftElement = element.LeftElement;
        newElement.RightElement = element.RightElement;
        _canStillSwap = false;
        return newElement;
    }

    private bool MustMutate()
    {
        return Random.NextDouble() < MutationChance;
    }

    public GeneticTree Combine(GeneticTree otherParent)
    {
        // We will assume both trees have the same layout and depth.
        // For example:
        //     +                          *
        //  5     -                   3       ^
        //      6   2                       4    2

        if (Depth != otherParent.Depth)
        {
            throw new ApplicationException("Trees are not similarly constructed");
        }

        var pivot = Depth / 2;
        if (pivot <= 1)
        {
            return this;
        }

        if (_nodes.Children != null)
        {
            var binaryNodeMom = _nodes as BinaryOperator;
            var binaryNodeDad = otherParent._nodes as BinaryOperator;
            if (binaryNodeMom != null && binaryNodeDad != null)
            {
                var momLeftElement = binaryNodeMom.LeftElement;
                var dadRightElement = binaryNodeDad.RightElement;

                var tree = new GeneticTree(_lowerBoundary, _upperBoundary)
                {
                    Name = "Nameless child"
                };

                var child = binaryNodeMom;
                child.LeftElement = momLeftElement;
                child.RightElement = dadRightElement;

                tree.AddOperations(child);
                return tree;
            }
        }

        return this;
    }
}

Sample output:

GitHub

Those who want to play around with it or prefer a more comfortable way of viewing, you can get the code from my GitHub.

Answer 1

You are organizing your algorithms into two categories: working algorithms and non-working algorithms; this is rather Manichean. You should try to design something where an algorithm is not "working" but "approaching the expected result better than the other ones". In other words, don't try to find "who works", but "who works better". The best thing you could do IMO is to get all the results for a generation, compare them to see which ones are closer to the expected result and which ones are farther. In other terms, you should give to your algorithms what I would call a "relative fitness" to know which solution is "relatively better" than the other ones.

This relative fitness will help you to generate a new generation with the following steps:

• Attach a survival percentage to every algorithm, relative to its relative fitness (the closer it is approching the expected result, the higher the survival percentage).
• For every algorithm in your population, get a random number between 0 and 1.
• Remove the algorithms for whom the random number is greater than its survival percentage.
• Keep the surviving algorithms for the next generation.
• Complete the new generation by creating algorithms that are mutations and combinations of the surviving algorithms.

If you do this, then you should be able to almost always keep the best algorithms between generations, but you will also keep some other ones whose mutations and/or combinations may unexpectedly produce agorithms that are better than your current best ones. This process of "you may have an unexpected talent" is useful to avoid local extrema.

Answer 2

Code smells

Don't do all the work in constructor

This piece of code is as useful as it seems:

static void Main(string[] args)
{
    new Program();
    Console.Read();
}

All the code in the constructor could be put in Main. The reason we move code from Main to instance classes is so that we can run them with multiple configurations. For example here there isn't a way to run the Program with another World. It could be changed so instead, you can figure out attendant changes to be made in Program.cs easily:

static void Main(string[] args)
{
    var world = new World(
        targetValue: 50, 
        populationSize: 30, 
        fitnessDelta: 100, 
        mutationChance: 0.2d, 
        minValue: -50, 
        maxValue: 50);
    new Program(world).Run(); // I can reuse `Run` method elsewhere now
    Console.Read();
}

Prefer interfaces over abstract classes

The following could be interfaces instead:

public abstract class Element
{
    public abstract double GetValue();

    public abstract string GetDisplay();

    public abstract List<Element> Children { get; }
}

public abstract class Operator : Element
{

}

Do not impose unnecessary limitations on the code usability. Incidentally, this is how you define interfaces in C++; if this a bit of habit hanging on from C++ use, you should try to get rid of it while coding C#.

Do not return null if return type is a collection or enumerable.

This is bad news:

    List<Element> Children { get { return null; } }

only place it is actually used is here:

    private void GetTreeDepth()
    {
        // ... SNIP

        if (_nodes.Children != null)
        {
            GetTreeDepth(_nodes.Children);
        }
    }

    private void GetTreeDepth(List<Element> children)
    {
        foreach(var child in children)
        {
            Depth++;
            if (child.Children != null)
            {
                GetTreeDepth(child.Children);
            }
        }
    }

If you return an empty list instead neither of the above null-checks would be necessary.

Do not null check unused variable

I said "[Element.Children] is actually used" above, because in the other to cases it is referenced it is null-checked and then not used! Here:

if (element.Children != null)
{
    var binaryOperator = element as BinaryOperator;

and here:

if (_nodes.Children != null)
{
    var binaryNodeMom = _nodes as BinaryOperator;

This seems like a left-over pseudo-runtime-type-checking. These null-checks at one time were probably standing in for checking whether a variable was a binary operator, but when normal type-checking was added they've become useless.

Separation of concerns in GeneticTree

GeneticTree does two things: It generates mutated individuals for the population, It also is those individuals.

You can see this in the way the fields are organized:

private const double MutationChance = 0.2d;
private readonly int _upperBoundary;
private readonly int _lowerBoundary;
private readonly static Random Random = new Random();
private readonly static Type[] BinaryOperations= ...;

vs. private bool _canStillSwap;

private Element _nodes;

public string Name { get; set; }

public int Depth { get; private set; }

Just like when you see a chunk of lines that go together in a method means you should extract a method, when you see a chunk of fields in a class you should extract a class. Another indication is that MutationChance is const, Random and BinaryOperations are static and _upperBoundary and _lowerBoundary are not static but they don't change while the algorithm is running, they need to be passed around unmodified, just because they couldn't be easily made static. First group of fields should be extracted to a GeneticTreeFactory, if you can find a meaninful name like MutationGenerator from the domain all the more better.