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.