Analysis of BasicAlgorithms

[abeham]

Stefan and I were talking about making BasicAlgorithms analyzable. We came up with the idea that implementors of such an algorithm must provide an IEnumerable of solutions and their respective quality. As we already have ideas on how to separate the monolithic run method into iterations and allow pausable behavior we would then be able to run most analyzers in between those iterations.

Implementation details are not yet finished and a proof of concept has yet to be created.

[abeham]

I implemented half-way through a proof of concept. I divide an algorithm into two classes:

1. The class that defines the parameters and the logic (i.e. AlgorithmA)
2. The class that defines the state (i.e. Context of AlgorithmA)

Classes in B should not contain any logic, just the data and data manipulation methods. Classes in A should perform all the initialization and manipulation.

An example of an algorithm that derives from BasicAlgorithm:

  [Item("Context-based Algorithm", "Algorithms that make use of contexts to facilitate applying operators.")]
  [StorableClass]
  public abstract class ContextAlgorithm<TContext> : BasicAlgorithm
    where TContext : class, IContext, new() {

    [Storable]
    private TContext context;
    protected TContext Context {
      get { return context; }
    }

    ...

    protected override void Initialize(CancellationToken cancellationToken) {
      base.Initialize(cancellationToken);
      context = new TContext();
      context.Scope.Variables.Add(new Variable("Results", Results));

      IExecutionContext ctxt = null;
      foreach (var item in Problem.ExecutionContextItems)
        ctxt = new Core.ExecutionContext(ctxt, item, Context.Scope);
      ctxt = new Core.ExecutionContext(ctxt, this, Context.Scope);
      context.Parent = ctxt;

      context.Iterations = 0;
      context.EvaluatedSolutions = 0;
    }
  }

IContext is a generic context that holds basic elements common to all algorithms. The new on Parent is required because I require a setter in the Initialize method above.

  public interface IContext : IExecutionContext {
    new IExecutionContext Parent { get; set; }
    int Iterations { get; set; }
    int EvaluatedSolutions { get; set; }
  }

A BasicContext implementation could look like this:

  public class BasicContext : ParameterizedNamedItem, IContext {

    private IExecutionContext parent;
    public IExecutionContext Parent {
      get { return parent; }
      set { parent = value; }
    }

    [Storable]
    private IScope scope;
    public IScope Scope {
      get { return scope; }
      private set { scope = value; }
    }

    IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {
      get { return Parameters; }
    }

    [Storable]
    private IValueParameter<IntValue> iterations;
    public int Iterations {
      get { return iterations.Value.Value; }
      set { iterations.Value.Value = value; }
    }

    [Storable]
    private IValueParameter<IntValue> evaluatedSolutions;
    public int EvaluatedSolutions {
      get { return evaluatedSolutions.Value.Value; }
      set { evaluatedSolutions.Value.Value = value; }
    }

    [StorableConstructor]
    protected BasicContext(bool deserializing) : base(deserializing) { }
    protected BasicContext(BasicContext original, Cloner cloner)
    : base(original, cloner) {
      scope = cloner.Clone(original.scope);
      iterations = cloner.Clone(original.iterations);
      evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
    }
    protected BasicContext() : base() {
      scope = new Scope("Global");
      Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));
      Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
    }
    // more constructors

    public override IDeepCloneable Clone(Cloner cloner) {
      return new BasicContext(this, cloner);
    }

    // applies an operator to the global scope
    public void RunOperator(IOperator op, CancellationToken cancellationToken) {
      var stack = new Stack<IOperation>();
      stack.Push(((IExecutionContext)this).CreateChildOperation(op, scope));

      while (stack.Count > 0) {
        cancellationToken.ThrowIfCancellationRequested();

        var next = stack.Pop();
        if (next is OperationCollection) {
          var coll = (OperationCollection)next;
          for (int i = coll.Count - 1; i >= 0; i--)
            if (coll[i] != null) stack.Push(coll[i]);
        } else if (next is IAtomicOperation) {
          var operation = (IAtomicOperation)next;
          try {
            next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
          } catch (Exception ex) {
            stack.Push(operation);
            if (ex is OperationCanceledException) throw ex;
            else throw new OperatorExecutionException(operation.Operator, ex);
          }
          if (next != null) stack.Push(next);
        }
      }
    }

    ...
  }

A context for population-based algorithms could look as follows:

  [Item("Population Context", "A context for population-based algorithms.")]
  public abstract class PopulationContext<TSolutionScope> : StochasticContext
    where TSolutionScope: class, IScope {

    public IEnumerable<TSolutionScope> Population {
      get { return Scope.SubScopes.OfType<TSolutionScope>(); }
    }
    public void AddToPopulation(TSolutionScope solScope) {
      Scope.SubScopes.Add(solScope);
    }
    public void ReplaceAtPopulation(int index, TSolutionScope solScope) {
      Scope.SubScopes[index] = solScope;
    }
    public void ReplacePopulation(IEnumerable<TSolutionScope> replacement) {
      Scope.SubScopes.Replace(replacement);
    }
    public TSolutionScope AtPopulation(int index) {
      return Scope.SubScopes[index] as TSolutionScope;
    }
    public TSolutionScope AtRandomPopulation() {
      return Scope.SubScopes[Random.Next(PopulationCount)] as TSolutionScope;
    }
    public int PopulationCount {
      get { return Scope.SubScopes.Count; }
    }


    [StorableConstructor]
    protected PopulationContext(bool deserializing) : base(deserializing) { }
    protected PopulationContext(PopulationContext<TSolutionScope> original, Cloner cloner)
      : base(original, cloner) {
    }
    protected PopulationContext() : base() { }
    // more constructors
  }

I would also propose to provide more specific scopes so that variable access becomes easier and doesn't always require a dictionary lookup. Here is a very basic scope for solutions of single-objective problems.

  [Item("Solution Scope", "Scope for an individual/solution of a single-objective single-encoded problem.")]
  [StorableClass]
  public sealed class SingleObjectiveSolutionScope<T> : NamedItem, ISingleObjectiveSolutionScope<T> where T : class, IItem {
    public new static Image StaticItemImage {
      get { return HeuristicLab.Common.Resources.VSImageLibrary.OrgChart; }
    }

    [Storable]
    private IScope parent;
    public IScope Parent {
      get { return parent; }
      set {
        if (parent != value) {
          parent = value;
        }
      }
    }

    [Storable]
    private VariableCollection variables;
    public VariableCollection Variables {
      get { return variables; }
    }

    [Storable]
    private ScopeList subScopes;
    public ScopeList SubScopes {
      get { return subScopes; }
    }

    [Storable]
    private Variable solution;
    public T Solution {
      get { return (T)solution.Value; }
      set { solution.Value = value; }
    }

    [Storable]
    private Variable fitness;
    public double Fitness {
      get { return ((DoubleValue)fitness.Value).Value; }
      set { ((DoubleValue)fitness.Value).Value = value; }
    }

    [StorableConstructor]
    private SingleObjectiveSolutionScope(bool deserializing) : base(deserializing) { }
    private SingleObjectiveSolutionScope(SingleObjectiveSolutionScope<T> original, Cloner cloner)
      : base(original, cloner) {
      // the parent will not be deep-cloned
      parent = original.parent;
      variables = cloner.Clone(original.variables);
      subScopes = cloner.Clone(original.subScopes);
      foreach (var child in SubScopes)
        child.Parent = this;
      solution = cloner.Clone(original.solution);
      fitness = cloner.Clone(original.fitness);

      RegisterSubScopesEvents();
    }
    public SingleObjectiveSolutionScope(T code, string codeName, double fitness, string fitnessName) {
      this.solution = new Variable(codeName, code);
      this.fitness = new Variable(fitnessName, new DoubleValue(fitness));
      variables = new VariableCollection(2) { this.solution, this.fitness };
      subScopes = new ScopeList(2);

      RegisterSubScopesEvents();
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SingleObjectiveSolutionScope<T>(this, cloner);
    }

    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      RegisterSubScopesEvents();
    }

    public void Clear() {
      variables.Clear();
      subScopes.Clear();
    }

    ...
  }

Using this infrastructure we could build algorithms that only execute e.g. Mutation and Crossover in form of operators and have ordinary C# code for counting and branching. Still, further research is required.

[abeham]

r15624: created branch

[abeham]

r15625: implemented generic context-based genetic algorithm

[abeham]

r15695: renamed branch according to guidelines

[abeham]

r15696: ignore items by name

[abeham]

It was decided 4.0 won't contain a new algorithm model

[jkarder]

HL architects: this ticket should get a more appropriate name