Genetic Programming in C#, LambdaGp

I’ve been a fan of Artificial Intelligence for a long time and I’ve been worked both with Neural Networks and Genetic Programming. Since I’ve migrated to C# I’ve lost access to all my old tools, so I decided to start work on a C# based Genetic Programming engine. I call it LambdaGp, because it makes extensive use of Lambda expressions.

After about four hours of coding (this is my fourth GP engine, so I do have some ideas about the design from the start) I have an engine that can solve my first demo problems.

I hope to publish my LambdaGp engine on CodePlex sometime in the future, but here are my two first test problems.

Symbolic regression of a constant

Applying symbolic regression to find a function that evolves to a constant may seem like overkill, but it’s a time-honored “Hello World” test-application in GP circles. Well, I always use it anyway. I’ve stated the problem as; find an expression that evaluates to a specific value, using the functions +,-,/,- and the constant terminals 1, 3 and 5

        private static Population SetupFindConstantTest(double targetValue)
        {
            Population population = new Population();
            population.GenomeDefinition.AddFunctions(
                new Add(),
                new Mul(),
                new Div(),
                new Sub(),
                new Constant(1),
                new Constant(3),
                new Constant(5));
            population.GenomeDefinition.MaxDepth = 3;
            population.PopulationSize = 750;

            population.FitnessFunction =
                ind =>
                Math.Abs(targetValue - ind.Evaluate());
            return population;
        }

Note how the fitness function simply returns the absolute distance between what the expression evaluates to, and the sought value. A perfect hit would return zero.

Below I’ll show how I use the population generated above, but when I ask it to find an expression that evaluates to 13,5 it goes through these iterations;

Generation=1,
New champion:
(-
  (/
    (* 5 3)
    (/ 3 3))
  (+
    (/ 5 5)
    (/ 3 5))),
Fitness=0,25
.
.
.
Generation=43,
New champion:
(-
  (* 3 5)
  (/ 3
    (- 5 3))),
Fitness=0,09
Reached target fitness!
Done

In other words, 3*5-3/(5-3). The reason that the fitness isn’t zero (lower fitness is better) is because of “parsimony pressure”; larger expressions have lower fitness. Fitness is punished depending on the size of the found expression.

Symbolic regression of an actual function

My second demo problem is finding an expression that matches a lambda function, for instance (5 * x^2) + (x * 3) + 5.

You’ll notice how I’ve used lambda for the fitness function instead of using a delegate. I think it’s readable enough, but not everyone would agree. But I could easily use a method delegate instead.

The fitness function iterates from –2 * pi to + 2 * pi in steps of 0.3, and calculates the expected value and the value that the expression suggests. If then keeps a running sum of squared errors. Again, a perfect solution would return zero. Anyway, this method struggled like crazy – to find my equation. Turns out I forgot to add multiplication, a fairly useful function…

The Ephemeral function is like a constant, only it randomizes new constants every time it’s used, in the range –5 to +5.

With multiplication, the new C# code looks like this;

private static Population SetupFindFunctionTest(Func<double, double> func)
        {
            Population population = new Population();
            population.GenomeDefinition.MaxSize = 30;
            population.GenomeDefinition.MaxDepth = 5;
            population.GenomeDefinition.AddFunctions(
                new Add(),
                new Div(),
                new Sub(),
                new Mul(),
                new Pow(),
                new Ephemeral(-5, +5));

            Variable x = population.GenomeDefinition.AddFunction(new Variable("x", 0.1));
            population.GenomeDefinition.MaxDepth = 5;
            population.PopulationSize = 2000;
            population.MaxGenerations = 500;

            population.FitnessFunction =
                ind =>
                {
                    x.Value = -2 * Math.PI;
                    double errorSum = 0;

                    while (x.Value < 2 * Math.PI)
                    {
                        double targetValue = func(x.Value);
                        double error = targetValue - ind.Evaluate();
                        errorSum += error * error;

                        x.Value += 0.3;
                    }

                    return errorSum;
                };

            return population;
        }

And it comes up with this code;

Generation=309,
New champion:
(+ x
  (+ 0,019
    (+
      (+
        (+ x x)
        (+ 4,977
          (*
            (+ x x)
            (+ x x))))
      (* x x)))),
Fitness=0,210671999999998

Again, the solution is actually “perfect”, it’s only parsimony pressure that gives it a non-zero fitness.

Symbolic regression of Sinus

To give it a trickier problem, I’m going have it try find sinus. This a complicated function to solve by symbolic regression – the Taylor expansion is infinite and the first iterations are quite significant.

sin(x) = X - X3/ 3! + X5/ 5! - ... + (-1)(n+1) * X(2*n-1)/ (2n-1)!

This proves to be much harder, as expected. I re-wrote the fitness function to report average squared error instead of the summed squared error, this gives a better feel for the actual result. I found the Taylor expansion for sinus here, and on that page you can also find the information that the fifth power expansion is accurate between –pi/2 to +pi/2 – and since we’re testing from –pi*2 to +pi*2, we need a solution of a higher power than five!

After a while, it closes in and finally finds this solution

Generation=516,
New champion:
(/
  (+ -10,02609
    (* x x))
  (-
    (-
      (/ x -4,28915)
      (*
        (/ -4,64585 x)
        (+ 1,84747 -4,15677)))
    (/
      (/
        (*
          (* x x)
          (/ x -6,95817))
        (/ -4,73401 x))
      (+
        (/ x -4,54048)
        (*
          (/ -3,55989 x)
          (* 1,65336 -1,95395)))))),
Fitness=0,00918493349840388 (before parsimony 0,00918493349840388)

This can of course be further reduced, but I’ll leave that as an exercise for the reader…

For completeness, the code to execute population run looks like this;

public static void Main(string[] args)
        {
            Population pop =
                //SetupFindConstantTest(13.5);
                //SetupFindFunctionTest(x => (x * x * 5) + (x * 3) + 5);
                SetupFindFunctionTest(Math.Sin);

            pop.AfterGeneration +=
                (sender, e) =>
                {
                    if (e.DifferentFromPreviousGeneration)
                    {
                        Console.WriteLine(
                            "Generation={0}, \n\rNew champion: \n\r{1}, \n\rFitness={2} (before parsimony {3})",
                            e.GenerationCount,
                            e.Champion.ToPrettyString(),
                            e.Champion.Fitness,
                            e.Champion.FitnessBeforeParsimony);
                    }
                    if (e.TargetFitnessReached)
                    {
                        Console.WriteLine("Reached target fitness!");
                    }
                };

            while (pop.GenerationCount < pop.MaxGenerations && pop.TargetFitnessReached == false)
            {
                pop.RunGeneration();
                if (Console.KeyAvailable)
                {
                    ConsoleKeyInfo key = Console.ReadKey();
                    if (key.KeyChar == 'R' || key.KeyChar == 'r')
                    {
                        pop.ResetPopulation();
                    }
                }
            }

            Console.WriteLine("Done");
            Console.ReadKey();
        }

About mfagerlund
Writes code in my sleep - and sometimes it even compiles!

5 Responses to Genetic Programming in C#, LambdaGp

  1. Pingback: Genetic Programming in C#

  2. James says:

    Dude. Very awesome. Can’t find it on CodePlex though😦

  3. Ben Stabile says:

    Feel free to borrow from this Codeplex project:

    I’ve forked ECJ to C# .NET 4.0 if you are interested in a full-featured Evolutionary Computation framework. The package includes everything from the original ECJ Java project, including all of the working samples.

    I also wrote 500 unit tests to verify many aspects of the conversion. But many more tests are needed. In particular, the distributed computation aspects are not fully tested. That’s because I plan on converting from ECJ’s simple use of sockets to a more robust strategy using WCF and WF. I’ll also be reworking the framework to utilize TPL (Task Parallel Library).

    Anyway, you can download the initial conversion here:

    http://branecloud.codeplex.com

    I am also in the process of converting several other frameworks from Java to .NET that relate to “synthetic intelligence” research (when I can find the time).

    Ben

    PS: is a very powerful and flexible framework for Evolutionary Computation in Java. But there are a lot of cool .NET features that could make it even better for those of us who prefer C#.

  4. Ben Stabile says:

    In my previous “PS” I tried to give the link for Sean Luke’s ECJ site at George Mason University:

    http://cs.gmu.edu/~eclab/projects/ecj/

    “BraneCloud Evolution” (my independently converted fork) does not include documentation. But you can find everything you need to get started on Sean Luke’s project pages.

    \’-)

    Ben

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: