Changes between Initial Version and Version 1 of Documentation/Howto/Implement Genetic Programming Problems

Timestamp:

04/06/12 18:18:53 (13 years ago)

Author:

gkronber

Comment:

first import of how-to for implementation of GP problems

Documentation/Howto/Implement Genetic Programming Problems

@@ +1 @@
+[[PageOutline]]
+= How-to Implement Custom Genetic Programming Problems =
+
+This how-to describes how you can implement your own plug-in to solve custom problems with genetic programming. GP is a very general evolutionary problem solving method and can be used to find solutions for a large number of different problems. The default installation of !HeuristicLab includes plug-ins for solving symbolic regression (and classification) problems and the artificial ant problems with genetic programming. However, if you want to use GP to solve other kinds of problems it is necessary to write a little bit of code for your own problem plug-in. This can be a little intriguing at first because the HeuristicLab source code is already very extensive and especially the implementation of the symbolic data analysis features includes so many extensions that it cannot be really used as a template for custom implementations. The source code for the artificial ant problem is much easier to understand and includes everything that is necessary for custom implementations of problems for genetic programming. 
+
+
+== The lawn mower problem ==
+This how-to describes the implementation of a very simple GP problem, namely the lawn mower problem [Koza 1994]. The goal is to find a program for a lawn mower that directs the mower over the whole lawn. 
+
+The mower can execute one of the following instructions:
+ * Forward: Move one step forward and mow.
+ * Left: Make a 90° left turn.
+ * Frog (Jump): Drive to a given point on the lawn without mowing.
+
+The lawn is a rectangular of size (n x m), which is 'connected' at the ends so that the mower appears on the left side if it drops off of the side (toroidal shape). This is  The mower should mow each cell of the lawn. The mower can mow a cell twice but this has no effect.
+
+[image(lawnmower.jpg)]
+
+== Design ==
+The first step for the implementation of a GP problem is the definition of the instruction set including function- and terminal symbols. In this example we will use the same symbols as used by Koza.
+* Terminals:
+ 1. Left: Turn the mower left
+ 2. Forward: Move one step forward while mowing
+ 3. Constant: Random constant that contains a vector of two integers
+* Functions:
+ 1. Sum: The vector sum of two integer vectors 
+ 2. Frog: Jump to a new position on the lawn, where the relative distance is specified by the single integer vector argument
+ 3. Prog: Executes two branches sequentially and returns the result of the last branch.
+
+Random constants and the vector sum function is necessary to provide input for the frog function. Without the frog function this example would be much easier as all instructions would only have side effects and no return values. Because of the frog function the closure property becomes relevant. This means that each terminal and function symbol must produce a integer vector output so that each combinations of functions and arguments represents a valid program. To satisfy the closure property The left, mow, and frog symbols return the integer vector {{{[0,0]}}}.
+
+
+== Implementation ==
+Next we implement the problem in a !HeuristicLab plug-in. There is a separate how-to on implementing custom plug-ins which explains this step in detail. 
+
+=== Project setup ===
+First create a new C# class library project called {{{HeuristicLab.Problems.LawnMower}}}. 
+
+In the properties of the project change the assembly name to {{{HeuristicLab.Problems.LawnMower-1.0}}}. This is not strictly necessary but in case we later want to add new features and release a new version of the problem we could potentially install both versions of the plug-in side by side if the version is included in the assembly name. 
+
+Next add references to the following assemblies in the !HeuristicLab installation folder:
+* `HeuristicLab.PluginInfrastructure-3.3.dll`
+* `HeuristicLab.Persistence-3.3.dll`
+* `HeuristicLab.Collections-3.3.dll`
+* `HeuristicLab.Common-3.3.dll`
+* `HeuristicLab.Core-3.3.dll`
+* `HeuristicLab.Data-3.3.dll`
+* `HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll`
+* `HeuristicLab.Operators-3.3.dll`
+* `HeuristicLab.Optimization-3.3.dll`
+* `HeuristicLab.Optimization.Operators-3.3.dll`
+* `HeuristicLab.Parameters-3.3.dll`
+
+These assemblies are necessary for genetic programming problem implementations.
+
+=== Plugin Class ===
+
+Every !HeuristicLab plug-in must contain a class which derives from {{{PluginBase}}} and contains properties declaring information about the plug-in and it's dependencies. We simple call this class {{{Plugin}}}
+
+{{{
+#!csharp
+using HeuristicLab.PluginInfrastructure;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [Plugin("HeuristicLab.Problems.LawnMower", "Lawn mower demo problem for genetic programming", "1.0.0")]
+  [PluginFile("HeuristicLab.Problems.LawnMower-1.0.dll", PluginFileType.Assembly)]
+  [PluginDependency("HeuristicLab.Data", "3.3")]
+  [PluginDependency("HeuristicLab.Core", "3.3")]
+  [PluginDependency("HeuristicLab.Common", "3.3")]
+  [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
+  [PluginDependency("HeuristicLab.Parameters", "3.3")]
+  [PluginDependency("HeuristicLab.Persistence", "3.3")]
+  public class Plugin : PluginBase {
+  }
+}
+}}}
+
+With the {{{Plugin}} attribute we can add a name an description for the plug-in that is shown in the !HeuristicLab plug-in manager. Next we declare which files belong to the plug-in. In our case the plug-in consists only of the assembly {{{HeuristicLab.Problems.LawnMower-1.0.dll}}}. The {{{PluginDependency}}} attributes declare dependencies for this plug-in which is necessary for plug-in management. Each !HeuristicLab assembly that is referenced in our project must also be included as a plug-in dependencies.
+
+  
+=== Symbol Classes ===
+The next step for implementing GP problems is the implementation of the symbol classes. Symbols include both function and terminal symbols that can be used in the evolved GP solutions.
+
+Left.cs:
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+
+namespace HeuristicLab.Problems.LawnMower {
+  // first version of left symbol (unfinished)
+  public class Left : Symbol {
+    public override int MinimumArity { get { return 0; } }
+    public override int MaximumArity { get { return 0; } }
+
+    public Left()
+      : base("Left", "Turns the lawn mower to the left.") {
+    }
+  }
+}
+}}}
+
+New symbol implementations must derive from the class {{{Symbol}}} defined in the {{{SymbolicExpressionTreeEncoding}}}. In each symbol the properties {{{MinimumArity}}} and {{{MaximumArity}}} must be overridden to declare how the symbol can be used in evolved programs. Here, the {{{Left}}} symbol is a terminal symbol and thus must not have any arguments. Therefore the arity of the symbol is set to zero (no arguments allowed).
+
+This first implementation of the {{{Left}}} symbol must be extended to support two essential functionalities, namely cloning and persistence.
+
+Since instances of symbols must be cloned it is necessary to implement the cloning functionality. In !HeuristicLab a common pattern is used for cloning in all clonable classes. The pattern involves overriding the {{{Clone()}}} method and implementing a cloning constructor.
+
+Cloning pattern for symbol {{{Left}}}
+{{{
+#!csharp
+    // cloning constructor
+    private Left(Left original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    // override for clone method
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Left(this, cloner);
+    }
+}}}
+
+To make it possible to store trees containing symbols to a file it is necessary to make two additional changes to the implementation of the {{{Left}}} symbol. In !HeuristicLab the classes of instances which are storable must be marked with the {{{[StorableClass]}}} attribute. Additionally, a storable constructor must be implemented which is marked with the {{{[StorableConstructor]}}} attribute. Any field or property that should be stored must be marked with a {{{[Storable]}}} attribute. However, in the left symbol there are no data that need to be stored.
+
+{{{Left.cs}}} including cloning pattern and storable pattern.
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  // final implementation of the left symbol
+  // with persistence and cloning patterns
+  [StorableClass] 
+  public class Left : Symbol {
+
+    public override int MinimumArity { get { return 0; } }
+    public override int MaximumArity { get { return 0; } }
+
+    // storable constructor for persistence
+    [StorableConstructor]
+    private Left(bool deserializing) : base(deserializing) { }
+    
+    // cloning constructor
+    private Left(Left original, Cloner cloner)
+      : base(original, cloner) {
+      // nothing needs to be cloned
+    }
+
+    public Left()
+      : base("Left", "Turns the lawn mower to the left.") {
+    }
+
+    // clone method override
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Left(this, cloner);
+    }
+  }
+}
+}}}
+
+ 
+In the same fashion we can implement the remaining symbols, where {{{MinimumArity}}} and {{{MaximumArity}}} properties must be adapted for each symbol.
+
+
+{{{Prog.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class Prog : Symbol {
+    public override int MinimumArity { get { return 2; } }
+    public override int MaximumArity { get { return 2; } }
+
+    [StorableConstructor]
+    private Prog(bool deserializing) : base(deserializing) { }
+    private Prog(Prog original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Prog()
+      : base("Prog", "Prog executes two branches sequentially and returns the result of the last branch.") {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Prog(this, cloner);
+    }
+  }
+}
+
+}}}
+
+{{{Sum.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class Sum : Symbol {
+    public override int MinimumArity { get { return 2; } }
+    public override int MaximumArity { get { return 2; } }
+
+    [StorableConstructor]
+    private Sum(bool deserializing) : base(deserializing) { }
+    private Sum(Sum original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Sum()
+      : base("Sum", "Sum of two integer vectors.") {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Sum(this, cloner);
+    }
+  }
+}
+}}}
+
+{{{Frog.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class Frog : Symbol {
+    public override int MinimumArity { get { return 1; } }
+    public override int MaximumArity { get { return 1; } }
+
+    [StorableConstructor]
+    private Frog(bool deserializing) : base(deserializing) { }
+    private Frog(Frog original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Frog()
+      : base("Frog", "Jumps to a relative position (determined by the argument).") {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Frog(this, cloner);
+    }
+  }
+}
+}}}
+
+{{{Forward.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class Forward : Symbol {
+    public override int MinimumArity { get { return 0; } }
+    public override int MaximumArity { get { return 0; } }
+
+    [StorableConstructor]
+    private Forward(bool deserializing) : base(deserializing) { }
+    private Forward(Forward original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Forward()
+      : base("Forward", "Moves the lawn mower one square forward.") {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Forward(this, cloner);
+    }
+  }
+}
+}}}
+
+{{{Constant.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class Constant : Symbol {
+    public override int MinimumArity { get { return 0; } }
+    public override int MaximumArity { get { return 0; } }
+
+    [StorableConstructor]
+    private Constant(bool deserializing) : base(deserializing) { }
+    private Constant(Constant original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Constant()
+      : base("Constant", "Vector of two random integers.") {
+    }
+
+    // override to create a specific tree node for constants
+    public override ISymbolicExpressionTreeNode CreateTreeNode() {
+      return new ConstantTreeNode();
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Constant(this, cloner);
+    }
+  }
+}
+}}}
+
+As you can see in the implementation of the class {{{Constant}}}, there is another override for the method {{{CreateTreeNode()}}}. This override is necessary because we want to create a specific kind of tree nodes ({{{ConstantTreeNode}}}), which will hold the random integer vector. This is the first class that holds data which must be marked with the {{{[Storable]}}} attribute and cloned in the cloning constructor.
+
+{{{ConstantTreeNode.cs}}}
+{{{
+#!csharp
+using System;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public class ConstantTreeNode : SymbolicExpressionTreeTerminalNode {
+    // the random integer vector is stored as a tuple of ints.
+    private Tuple<int, int> value;
+    [Storable] 
+    public Tuple<int, int> Value { 
+      get { return value; } 
+      private set { this.value = value; } 
+    }
+
+    [StorableConstructor]
+    private ConstantTreeNode(bool deserializing) : base(deserializing) { }
+    private ConstantTreeNode(ConstantTreeNode original, Cloner cloner)
+      : base(original, cloner) {
+      // important here we need to implement the cloning
+      // of the local data (integer vector)
+      this.value = 
+        new Tuple<int, int>(original.value.Item1, original.value.Item2);
+    }
+
+    // default constructor, the symbol of a ConstantTreeNode is always
+    // a Constant.
+    public ConstantTreeNode()
+      : base(new Constant()) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new ConstantTreeNode(this, cloner);
+    }
+
+    // This tree node holds data (integer vector).
+    // Thus, this property must be overridden to return true
+    // to indicate to the algorithm that the data in this node
+    // must be reset initially.
+    public override bool HasLocalParameters {
+      get { return true; }
+    }
+    // ResetLocalParameters is called by the algorithm to reset
+    // the data of the tree node when initializing the population.
+    // Here we want to create a random integer vector where both
+    // components are distributed uniformly.
+    public override void ResetLocalParameters(IRandom random) {
+      value = new Tuple<int, int>(random.Next(-20, 20), random.Next(-20, 20));
+    }
+  }
+}
+}}} 
+
+
+=== Grammar Class ===
+The {{{Grammar}}} class defines the set of valid trees. In this example the {{{Grammar}}} is very simple as it is allowed to use any function or terminal symbol as argument of any function symbol. In real-world application it is frequently necessary to restrict this relation which is possible by implementing these rules in the {{{Grammar}}}.
+
+{{{Grammar.cs}}}
+{{{
+#!csharp
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  [Item("Lawn Mower Grammar", "The grammar for the lawn mower demo GP problem.")]
+  public class Grammar : SymbolicExpressionGrammar {
+    [StorableConstructor]
+    private Grammar(bool deserializing) : base(deserializing) { }
+    private Grammar(Grammar original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public Grammar()
+      : base("Grammar", "The grammar for the lawn mower demo GP problem.") {
+      Initialize();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Grammar(this, cloner);
+    }
+
+    // initialize set of allowed symbols and define 
+    // the allowed combinations of symbols
+    private void Initialize() {
+      // create all symbols
+      var sum = new Sum();
+      var prog = new Prog();
+      var frog = new Frog();
+      var left = new Left();
+      var forward = new Forward();
+      var constant = new Constant();
+
+      var allSymbols = new List<ISymbol>() { 
+          sum, prog, frog, left, forward, constant };
+
+      // add all symbols to the grammar
+      foreach (var s in allSymbols)
+        AddSymbol(s);
+
+      // define grammar rules
+      // all symbols are allowed ...
+      foreach (var s in allSymbols) {
+        // ... as children of the sum function
+        AddAllowedChildSymbol(sum, s, 0);
+        AddAllowedChildSymbol(sum, s, 1);
+        // ... as children of the prog function
+        AddAllowedChildSymbol(prog, s, 0);
+        AddAllowedChildSymbol(prog, s, 1);
+        // ... as children of the frog function
+        AddAllowedChildSymbol(frog, s, 0);
+        // ... as root symbol 
+        AddAllowedChildSymbol(StartSymbol, s, 0);      
+      }
+    }
+  }
+}
+}}}
+
+
+=== Interpreter and Evaluator Classes ===
+Next we implement the necessary classes for evaluation of GP trees representing solution candidates for the lawn mower problem. We implement two classes, the {{{Interpreter}}} which simply executes a given tree, and the {{{Evaluator}}} which will be used as the fitness evaluation operator for the lawn mower problem and uses the {{{Interpreter}}} to execute trees.
+
+While it would be possible to implement the evaluation of symbols directly in the symbols themselves, we found it more convenient to extract the symbol semantics into a separate interpreter class. Due to this design it is for instance easily possible to implement different interpreters for lawn mower problems. 
+
+Additionally, the interpreter and evaluator are closely related classes, which could be combined into one class. However, we found that this design is more convenient because we can later also call the interpreter for other purposes than evaluation (e.g. for visualization).
+
+First let's look at the implementation of the {{{Interpreter}}}. The {{{Interpreter}}} is at the core of the lawn mower problem as it exactly describes how solution candidates are executed and which results they produce. The {{{Interpreter}}} should be implemented in an efficient way because it will be called repeatedly for solution evaluation and thus is at the critical point for performance optimization. The {{{Interpreter}}} is a simple class and not derived from any framework classes. It contains only static methods for the interpretation of trees. Thus, it is not necessary to mark it as a {{{[StorableClass]}}} and it is not necessary to implement the cloning pattern or the persistence pattern.
+
+{{{Interpreter.cs}}}
+{{{
+#!csharp
+using System;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+
+namespace HeuristicLab.Problems.LawnMower {
+  public class Interpreter {
+    // enumerable type for the possible headings of the mower
+    private enum Heading { South, East, North, West };
+
+    // internal class used to encapsulate the state of the mower
+    // at any time the mower has a certain heading
+    // has a position in the lawn
+    // and additionally has an energy to limit the number of steps
+    // a lawn mower can make
+    private class MowerState {
+      public Heading Heading { get; set; }
+      public Tuple<uint, uint> Position { get; set; }
+      public int Energy { get; set; }
+      public MowerState() {
+        Heading = Heading.South;
+        Position = new Tuple<uint, uint>(0, 0);
+        Energy = 0;
+      }
+    }
+
+
+    public static bool[,] EvaluateLawnMowerProgram(int length, int width, 
+      ISymbolicExpressionTree tree) {
+      // array to mark the fields that have been mowed
+      bool[,] lawn = new bool[length, width];
+      // initialize the mower state and position on the lawn
+      var mowerState = new MowerState();
+      mowerState.Heading = Heading.South;
+      mowerState.Energy = length * width * 2;
+      lawn[mowerState.Position.Item1, mowerState.Position.Item2] = true;
+      
+      // start program execution at the root node
+      EvaluateLawnMowerProgram(tree.Root, ref mowerState, lawn);
+
+      return lawn;
+    }
+
+    // evaluate a whole tree branch, each branch returns an integer vector
+    private static Tuple<int, int> EvaluateLawnMowerProgram(
+        ISymbolicExpressionTreeNode node, 
+        ref MowerState mowerState, bool[,] lawn) {
+      // if no energy is left then return immediately 
+      if (mowerState.Energy <= 0) return new Tuple<int, int>(0, 0);
+      
+      // The program-root and start symbols are predefined symbols 
+      // in each problem using the symbolic expression tree encoding.
+      // These symbols must be handled by the interpreter. Here we simply
+      // evaluate the whole sub-tree 
+      if (node.Symbol is ProgramRootSymbol) {
+        return EvaluateLawnMowerProgram(node.GetSubtree(0), 
+                                        ref mowerState, lawn);
+      } else if (node.Symbol is StartSymbol) {
+        return EvaluateLawnMowerProgram(node.GetSubtree(0), 
+                                        ref mowerState, lawn);
+      } else if (node.Symbol is Left) {
+        // turn left
+        switch (mowerState.Heading) {
+          case Heading.East: mowerState.Heading = Heading.North;
+            break;
+          case Heading.North: mowerState.Heading = Heading.West;
+            break;
+          case Heading.West: mowerState.Heading = Heading.South;
+            break;
+          case Heading.South:
+            mowerState.Heading = Heading.East;
+            break;
+        }
+        return new Tuple<int, int>(0, 0);
+      } else if (node.Symbol is Forward) {
+        int dRow = 0;
+        int dCol = 0;
+        // move forward
+        switch (mowerState.Heading) {
+          case Heading.East: dCol++; break;
+          case Heading.North: dRow--; break;
+          case Heading.West: dCol--; break;
+          case Heading.South: dRow++; break;
+        }
+        // make sure the mower does not move outside the lawn
+        int rows = lawn.GetLength(0);
+        int columns = lawn.GetLength(1);
+        uint newRow = 
+          (uint)((mowerState.Position.Item1 + rows + dRow) % rows);
+        uint newColumn = 
+          (uint)((mowerState.Position.Item2 + columns + dCol) % columns);
+        // set the new position
+        mowerState.Position = new Tuple<uint, uint>(newRow, newColumn);
+        // reduce the energy in each mowing step
+        mowerState.Energy = mowerState.Energy - 1;
+        lawn[newRow, newColumn] = true;
+        return new Tuple<int, int>(0, 0);
+      } else if (node.Symbol is Constant) {
+        // return the random constant value
+        var constNode = node as ConstantTreeNode;
+        return constNode.Value;
+      } else if (node.Symbol is Sum) {
+        // add the return values of the two argument branches
+        var p = EvaluateLawnMowerProgram(node.GetSubtree(0), 
+                                         ref mowerState, lawn);
+        var q = EvaluateLawnMowerProgram(node.GetSubtree(1), 
+                                         ref mowerState, lawn);
+        return new Tuple<int, int>(p.Item1 + q.Item1,
+          p.Item2 + q.Item2);
+      } else if (node.Symbol is Prog) {
+        // execute both argument branches sequentially
+        // and return the return value of the last one
+        EvaluateLawnMowerProgram(node.GetSubtree(0), ref mowerState, lawn);
+        return EvaluateLawnMowerProgram(node.GetSubtree(1), 
+                                        ref mowerState, lawn);
+      } else if (node.Symbol is Frog) {
+        // jump to a new position
+        // the relative position is the return value of the argument branch
+        var p = EvaluateLawnMowerProgram(node.GetSubtree(0), 
+                                         ref mowerState, lawn);
+
+        // make sure the mower does not move outside the lawn
+        int rows = lawn.GetLength(0);
+        int cols= lawn.GetLength(1);
+        uint newRow = 
+          (uint)((mowerState.Position.Item1 + rows + p.Item1 % rows) % rows);
+        uint newCol = 
+          (uint)((mowerState.Position.Item2 + cols + p.Item2 % cols) % cols);
+        // set new position
+        mowerState.Position = new Tuple<uint, uint>(newRow, newCol);
+        // set the cell at the new position to mowed
+        // and reduce the mower energy
+        lawn[newRow, newCol] = true;
+        mowerState.Energy = mowerState.Energy - 1;
+        return new Tuple<int, int>(0, 0);
+      } else {
+        throw 
+          new ArgumentException("Invalid symbol in the lawn mower program.");
+      }
+    }
+  }
+}
+}}}
+
+
+{{{Evaluator.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  [Item("Lawn Mower Evaluator", 
+        "Evaluator for the lawn mower demo GP problem.")]
+  public class Evaluator : SingleSuccessorOperator, 
+    ISingleObjectiveEvaluator {
+    #region parameter names
+    private const string QualityParameterName = "Quality";
+    private const string LawnMowerProgramParameterName = "LawnMowerProgram";
+    private const string LawnWidthParameterName = "LawnWidth";
+    private const string LawnLengthParameterName = "LawnLength";
+    #endregion
+
+
+    #region parameters
+    public ILookupParameter<DoubleValue> QualityParameter {
+      get { return (ILookupParameter<DoubleValue>)
+                     Parameters[QualityParameterName]; }
+    }
+    public ILookupParameter<ISymbolicExpressionTree> LawnMowerProgramParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)
+                     Parameters[LawnMowerProgramParameterName]; }
+    }
+    public ILookupParameter<IntValue> LawnWidthParameter {
+      get { return (ILookupParameter<IntValue>)
+                     Parameters[LawnWidthParameterName]; }
+    }
+    public ILookupParameter<IntValue> LawnLengthParameter {
+      get { return (ILookupParameter<IntValue>)
+                     Parameters[LawnLengthParameterName]; }
+    }
+    #endregion
+
+    [StorableConstructor]
+    protected Evaluator(bool deserializing) : base(deserializing) { }
+    protected Evaluator(Evaluator original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    // default constructor for the evaluator
+    public Evaluator() {
+      Parameters.Add(
+        new LookupParameter<DoubleValue>(
+          QualityParameterName, 
+          "The solution quality of the lawn mower program."));
+      Parameters.Add(
+        new LookupParameter<ISymbolicExpressionTree>(
+          LawnMowerProgramParameterName, 
+          "The lawn mower program to evaluate represented as " +
+          "symbolic expression tree."));
+      Parameters.Add(
+        new LookupParameter<IntValue>(LawnWidthParameterName, 
+                                      "The width of the lawn to mow."));
+      Parameters.Add(
+        new LookupParameter<IntValue>(LawnLengthParameterName, 
+                                      "The length of the lawn to mow."));
+    }
+
+    // override the apply method to change the behaviour of the operator
+    // here we take trees as inputs and calculate qualities 
+    // (fitness evaluation)
+    public override IOperation Apply() {
+      int length = LawnLengthParameter.ActualValue.Value;
+      int width = LawnWidthParameter.ActualValue.Value;
+      ISymbolicExpressionTree tree = LawnMowerProgramParameter.ActualValue;
+
+      // call the interpreter to execute the program represented as tree
+      bool[,] lawn = Interpreter.EvaluateLawnMowerProgram(length, width, tree);
+
+      // count number of cells that have been mowed
+      int numberOfMowedCells = 0;
+      for (int i = 0; i < length; i++)
+        for (int j = 0; j < width; j++)
+          if (lawn[i, j]) {
+            numberOfMowedCells++;
+          }
+
+      // the solution quality is the number of mowed cells
+      QualityParameter.ActualValue = new DoubleValue(numberOfMowedCells);
+      
+      // important: return base.Apply() to make sure that the
+      // next operator is queued for execution
+      return base.Apply();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Evaluator(this, cloner);
+    }
+  }
+}
+}}}
+
+=== Problem Class ===
+Finally, we implement the {Problem} class. 
+
+{{{Problem.cs}}}
+{{{
+#!csharp
+using System;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  [Creatable("Problems")]
+  [Item("Lawn Mower Problem", 
+        "The lawn mower demo problem for genetic programming.")]
+  public class Problem : SingleObjectiveHeuristicOptimizationProblem<Evaluator, 
+    ISymbolicExpressionTreeCreator> {
+    #region parameter names
+    private const string LawnWidthParameterName = "LawnWidth";
+    private const string LawnLengthParameterName = "LawnLength";
+    private const string LawnMowerProgramParameterName = "Program";
+    private const string MaxLawnMowerProgramLengthParameterName = 
+      "MaxProgramLength";
+    private const string MaxLawnMowerProgramDepthParameterName = 
+      "MaxProgramDepth";
+    private const string LawnMowerGrammarParameterName = "Grammar";
+    #endregion
+
+    #region parameters
+    public IFixedValueParameter<IntValue> LawnWidthParameter {
+      get { return (IFixedValueParameter<IntValue>)
+              Parameters[LawnWidthParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> LawnLengthParameter {
+      get { return (IFixedValueParameter<IntValue>)
+              Parameters[LawnLengthParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> MaxLawnMowerProgramLengthParameter {
+      get { return (IFixedValueParameter<IntValue>)
+              Parameters[MaxLawnMowerProgramLengthParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> MaxLawnMowerProgramDepthParameter {
+      get { return (IFixedValueParameter<IntValue>)
+              Parameters[MaxLawnMowerProgramDepthParameterName]; }
+    }
+    public IValueParameter<Grammar> GrammarParameter {
+      get { return (IValueParameter<Grammar>)
+              Parameters[LawnMowerGrammarParameterName]; }
+    }
+    #endregion
+
+    [StorableConstructor]
+    protected Problem(bool deserializing)
+      : base(deserializing) {
+    }
+    protected Problem(Problem original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    // default constructor for the problem
+    // also creates the fitness evaluation operator (Evaluator), 
+    // and the tree creation operator (RampedHalfAndHalfTreeCreator)
+    public Problem()
+      : base(new Evaluator(), new RampedHalfAndHalfTreeCreator()) {
+      Parameters.Add(
+        new FixedValueParameter<IntValue>(
+          LawnWidthParameterName, 
+          "Width of the lawn.", 
+          new IntValue(8)));
+      Parameters.Add(
+        new FixedValueParameter<IntValue>(
+          LawnLengthParameterName, 
+          "Length of the lawn.", 
+          new IntValue(8)));
+      Parameters.Add(
+        new FixedValueParameter<IntValue>(
+          MaxLawnMowerProgramDepthParameterName, 
+          "Maximal depth of the lawn mower program.", 
+          new IntValue(13)));
+      Parameters.Add(
+        new FixedValueParameter<IntValue>(
+          MaxLawnMowerProgramLengthParameterName, 
+          "Maximal length of the lawn mower program.", 
+          new IntValue(1000)));
+      Parameters.Add(
+        new ValueParameter<Grammar>(
+          LawnMowerGrammarParameterName, 
+          "Grammar for the lawn mower program.",
+          new Grammar()));
+      Maximization.Value = true;
+      InitializeOperators();
+
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Problem(this, cloner);
+    }
+
+    private void InitializeOperators() {
+      Operators.AddRange(
+        ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeOperator>());
+      Operators.Add(new MinAverageMaxSymbolicExpressionTreeLengthAnalyzer());
+      Operators.Add(new SymbolicExpressionSymbolFrequencyAnalyzer());
+      Operators.Add(new BestSolutionAnalyzer());
+      ParameterizeOperators();
+      ParameterizeAnalyzers();
+    }
+
+    protected override void OnEvaluatorChanged() {
+      base.OnEvaluatorChanged();
+      Evaluator.LawnMowerProgramParameter.ActualName = 
+        LawnMowerProgramParameterName;
+      Evaluator.LawnLengthParameter.ActualName = LawnLengthParameterName;
+      Evaluator.LawnWidthParameter.ActualName = LawnWidthParameterName;
+      ParameterizeAnalyzers();
+      ParameterizeOperators();
+    }
+
+    protected override void OnSolutionCreatorChanged() {
+      base.OnSolutionCreatorChanged();
+      SolutionCreator.SymbolicExpressionTreeParameter.ActualName = 
+        LawnMowerProgramParameterName;
+      ParameterizeAnalyzers();
+      ParameterizeOperators();
+    }
+
+    private void ParameterizeAnalyzers() {
+      var analyzers = Operators.OfType<IAnalyzer>();
+      foreach (var o in analyzers.OfType<ISymbolicExpressionTreeAnalyzer>()) {
+        o.SymbolicExpressionTreeParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+      }
+      foreach (var o in analyzers.OfType<BestSolutionAnalyzer>()) {
+        o.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
+      }
+    }
+
+    private void ParameterizeOperators() {
+      var operators = Parameters
+        .OfType<IValueParameter>()
+        .Select(p => p.Value)
+        .OfType<IOperator>()
+        .Union(Operators);
+      foreach (var o in operators.OfType<ISymbolicExpressionTreeGrammarBasedOperator>()) {
+        o.SymbolicExpressionTreeGrammarParameter.ActualName = 
+          LawnMowerGrammarParameterName;
+      }
+      foreach (var o in operators.OfType<ISymbolicExpressionTreeSizeConstraintOperator>()) {
+        o.MaximumSymbolicExpressionTreeDepthParameter.ActualName = 
+          MaxLawnMowerProgramDepthParameterName;
+        o.MaximumSymbolicExpressionTreeLengthParameter.ActualName = 
+          MaxLawnMowerProgramLengthParameterName;
+      }
+      foreach (var op in operators.OfType<Evaluator>()) {
+        op.LawnMowerProgramParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+        op.LawnLengthParameter.ActualName = LawnLengthParameterName;
+        op.LawnWidthParameter.ActualName = LawnWidthParameterName;
+      }
+      foreach (var op in operators.OfType<ISymbolicExpressionTreeCrossover>()) {
+        op.ParentsParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+        op.ChildParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+      }
+      foreach (var op in operators.OfType<ISymbolicExpressionTreeManipulator>()) {
+        op.SymbolicExpressionTreeParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+      }
+      foreach (var op in operators.OfType<ISymbolicExpressionTreeCreator>()) {
+        op.SymbolicExpressionTreeParameter.ActualName = 
+          SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
+      }
+    }
+  }
+}
+}}}
+
+== Extension of the Implementation == 
+
+=== Solution Class ===
+{{{Solution.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  public sealed class Solution : NamedItem {
+    private int width;
+    [Storable]
+    public int Width {
+      get { return width; }
+      private set { this.width = value; }
+    }
+    private int length;
+    [Storable]
+    public int Length {
+      get { return length; }
+      private set { this.length = value; }
+    }
+    private ISymbolicExpressionTree tree;
+    [Storable]
+    public ISymbolicExpressionTree Tree {
+      get { return tree; }
+      private set { this.tree = value; }
+    }
+    [StorableConstructor]
+    private Solution(bool deserializing) : base(deserializing) { }
+    private Solution(Solution original, Cloner cloner)
+      : base(original, cloner) {
+      this.length = original.length;
+      this.width = original.width;
+      this.tree = cloner.Clone(tree);
+    }
+
+    public Solution(ISymbolicExpressionTree tree, int length, int width)
+      : base("Solution", "A lawn mower solution.") {
+      this.tree = tree;
+      this.length = length;
+      this.width = width;
+    }
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Solution(this, cloner);
+    }
+  }
+}
+
+}}}
+
+=== Analyzer Class  ===
+{{{BestSolutionAnalyzer.cs}}}
+{{{
+#!csharp
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.LawnMower {
+  [StorableClass]
+  [Item("Best Lawn Mower Solution Analyzer", 
+        "Analyzer that stores the best lawn mower solution.")]
+  public class BestSolutionAnalyzer : SingleSuccessorOperator, 
+    ISymbolicExpressionTreeAnalyzer {
+    #region parameter names
+    private const string QualityParameterName = "Quality";
+    private const string SymbolicExpressionTreeParameterName = 
+      "LawnMowerProgram";
+    private const string LawnWidthParameterName = "LawnWidth";
+    private const string LawnLengthParameterName = "LawnLength";
+    private const string BestSolutionParameterName = "Best solution";
+    private const string ResultsParameterName = "Results";
+    #endregion
+
+
+    #region parameters
+    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)
+                      Parameters[QualityParameterName]; }
+    }
+    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)
+                      Parameters[SymbolicExpressionTreeParameterName]; }
+    }
+    public ILookupParameter<IntValue> LawnWidthParameter {
+      get { return (ILookupParameter<IntValue>)
+                      Parameters[LawnWidthParameterName]; }
+    }
+    public ILookupParameter<IntValue> LawnLengthParameter {
+      get { return (ILookupParameter<IntValue>)
+                      Parameters[LawnLengthParameterName]; }
+    }
+    public ILookupParameter<Solution> BestSolutionParameter {
+      get { return (ILookupParameter<Solution>)
+                      Parameters[BestSolutionParameterName]; }
+    }
+    public ILookupParameter<ResultCollection> ResultParameter {
+      get { return (ILookupParameter<ResultCollection>)
+                      Parameters[ResultsParameterName]; }
+    }
+    #endregion
+
+    [StorableConstructor]
+    protected BestSolutionAnalyzer(bool deserializing) : base(deserializing) { }
+    protected BestSolutionAnalyzer(BestSolutionAnalyzer original, 
+                                   Cloner cloner) : base(original, cloner) {
+    }
+
+    public BestSolutionAnalyzer() {
+      Parameters.Add(
+        new ScopeTreeLookupParameter<DoubleValue>(
+          QualityParameterName, 
+          "The solution quality of the lawn mower program."));
+      Parameters.Add(
+        new ScopeTreeLookupParameter<ISymbolicExpressionTree>(
+          SymbolicExpressionTreeParameterName, 
+          "The lawn mower program to evaluate represented " +
+          "as symbolic expression tree."));
+      Parameters.Add(
+        new LookupParameter<Solution>(
+          BestSolutionParameterName, "The best lawn mower solution."));
+      Parameters.Add(
+        new LookupParameter<IntValue>(
+          LawnWidthParameterName, "The width of the lawn to mow."));
+      Parameters.Add(
+        new LookupParameter<IntValue>(
+          LawnLengthParameterName, "The length of the lawn to mow."));
+      Parameters.Add(
+        new LookupParameter<ResultCollection>(
+          ResultsParameterName, "The result collection of the algorithm."));
+    }
+
+    public override IOperation Apply() {
+      // get an array of all trees
+      // and an array of all qualities
+      var trees = SymbolicExpressionTreeParameter.ActualValue;
+      var qualities = QualityParameter.ActualValue;
+
+      // find the tree with the best quality
+      double maxQuality = double.NegativeInfinity;
+      ISymbolicExpressionTree bestTree = null;
+      for (int i = 0; i < qualities.Length; i++) {
+        if (qualities[i].Value > maxQuality) {
+          maxQuality = qualities[i].Value;
+          bestTree = trees[i];
+        }
+      }
+      // create a solution instance
+      int length = LawnLengthParameter.ActualValue.Value;
+      int width = LawnWidthParameter.ActualValue.Value;
+      var bestSolution = new Solution(bestTree, length, width);
+      // store the new solution in the best solution parameter
+      BestSolutionParameter.ActualValue = bestSolution;
+
+      // also add the best solution as a result to the result collection
+      // or alternatively update the existing result
+      var resultCollection = ResultParameter.ActualValue;
+      if (!resultCollection.ContainsKey(BestSolutionParameterName)) {
+        resultCollection.Add(
+          new Result(BestSolutionParameterName, 
+                     "The best lawn mower solution", bestSolution));
+      } else {
+        resultCollection[BestSolutionParameterName].Value = bestSolution;
+      }
+
+      // important return base.Apply() to make sure the 
+      // next operator is queued for execution
+      return base.Apply();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BestSolutionAnalyzer(this, cloner);
+    }
+
+    // override this property to indicate that this analyzer
+    // should be enabled by default in the algorithm
+    public bool EnabledByDefault {
+      get { return true; }
+    }
+  }
+}
+}}}
+
+=== Solution View Classes ===
+{{{SolutionProgramView.cs}}}
+{{{
+#!csharp
+using System.Windows.Forms;
+using HeuristicLab.Core.Views;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
+using HeuristicLab.MainForm;
+using HeuristicLab.MainForm.WindowsForms;
+
+namespace HeuristicLab.Problems.LawnMower {
+  // This is a view called 'Lawn Mower Problem View',
+  // which can show instances of the class Solution,
+  // but it is not used as the default view for these instances.
+  [View("Lawn Mower Program View")]
+  [Content(typeof(Solution), IsDefaultView = false)]
+  public class SolutionProgramView : NamedItemView {
+    private Panel panel;
+    private GraphicalSymbolicExpressionTreeView graphTreeView;
+
+    public new Solution Content {
+      get { return (Solution)base.Content; }
+      set { base.Content = value; }
+    }
+
+    public SolutionProgramView() {
+      InitializeComponent();
+      // use an existing view from the symbolic expression tree encoding
+      // which visualizes symbolic expression trees
+      this.graphTreeView = new GraphicalSymbolicExpressionTreeView();
+      graphTreeView.Dock = DockStyle.Fill;
+      panel.Controls.Add(graphTreeView);
+    }
+
+    protected override void OnContentChanged() {
+      base.OnContentChanged();
+      if (Content == null) {
+        graphTreeView.Content = null;
+      } else {
+        graphTreeView.Content = Content.Tree;
+      }
+    }
+
+    private void InitializeComponent() {
+      #region designer code
+      [...]
+      #endregion
+    }
+  }
+}
+}}}
+
+{{{SolutionLawnView.cs}}}
+{{{
+#!csharp
+using System;
+using System.Drawing;
+using System.Windows.Forms;
+using HeuristicLab.Core.Views;
+using HeuristicLab.MainForm;
+using HeuristicLab.MainForm.WindowsForms;
+
+namespace HeuristicLab.Problems.LawnMower {
+  // This is a view called 'Lawn Mower Solution View',
+  // which can show instances of the class Solution,
+  // and it is used as the default view. 
+  [View("Lawn Mower Solution View")]
+  [Content(typeof(Solution), IsDefaultView = true)]
+  public class SolutionLawnView : NamedItemView {
+    private PictureBox pictureBox;
+    private System.Windows.Forms.GroupBox groupBox;
+
+    public new Solution Content {
+      get { return (Solution)base.Content; }
+      set { base.Content = value; }
+    }
+
+    public SolutionLawnView() {
+      InitializeComponent();
+      pictureBox.Image = new Bitmap(200, 200);
+    }
+
+    protected override void OnContentChanged() {
+      base.OnContentChanged();
+      if (Content == null) {
+        using (var g = Graphics.FromImage(pictureBox.Image))
+          g.Clear(DefaultBackColor);
+      } else {
+        bool[,] lawn = 
+          Interpreter.EvaluateLawnMowerProgram(Content.Length, 
+                                               Content.Width, 
+                                               Content.Tree);
+        PaintTiles(pictureBox.Image, lawn);
+      }
+    }
+
+    private void PaintTiles(Image lawnImage, bool[,] mowed) {
+      int w = lawnImage.Width;
+      int h = lawnImage.Height;
+
+      float tileHeight = h / (float)mowed.GetLength(0);
+      float tileWidth = w / (float)mowed.GetLength(1);
+
+      tileWidth = Math.Min(tileWidth, tileHeight);
+      tileHeight = tileWidth; // draw square tiles
+
+      using (var g = Graphics.FromImage(lawnImage)) {
+        g.Clear(DefaultBackColor);
+        for (int i = 0; i < Content.Length; i++)
+          for (int j = 0; j < Content.Width; j++)
+            if (mowed[i, j]) {
+              g.FillRectangle(Brushes.Chartreuse, 
+                              tileWidth * j, tileHeight * i, 
+                              tileWidth, tileHeight);
+            } else {
+              g.FillRectangle(Brushes.DarkGreen, 
+                              tileWidth * j, tileHeight * i, 
+                              tileWidth, tileHeight);
+            }
+      }
+    }
+
+    private void InitializeComponent() {
+      #region designer code
+      [...]
+      #endregion
+    }
+  }
+}
+}}}
+
+[Koza 1994] J. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, MA, The MIT Press. 1994