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.

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

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.

Basic implementation of Left

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 Left

    // 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.

Full implementation of Left

The following source code is the full implemenation of the symbol Left including the cloning pattern and the persistence pattern.

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

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

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

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

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

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

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

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

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.");
      }
    }
  }
}

In HeuristicLab each problem must supply a fitness evaluation operator. This operator must derive from ISingleObjectiveEvaluator and we can use the base class SingleSuccessorOperator for all operators that can have a successor. The Item attribute can be used to set a name and description for the operator that is shown in the GUI. All operators must have the StorableClass attribute.

An operator can have multiple input and output parameters and to implement the ISingleObjectiveEvaluator interface at least a QualityParameter must be implemented. The evaluator also needs the tree representing the lawn moower program that it should evaluate and the length and width of the lawn to calculate the quality of the tree.

All of these parameters must have the type LookupParameter<T> because the values of these parameters are looked up in the scope on which the parameter is applied.

Evaluator

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

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;
      }
    }
  }
}

First test run

Extension of the Implementation

Solution Class

Solution.cs

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

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

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
    }
  }
}

Lawn mower program screenshot

SolutionLawnView

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
    }
  }
}

Lawn mower solution screenshot

[Koza 1994] J. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, MA, The MIT Press. 1994