Open HeuristicLab-Trac-Bot opened 8 years ago
I implemented half-way through a proof of concept. I divide an algorithm into two classes:
A. The class that defines the parameters and the logic (i.e. AlgorithmA) B. 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:
#!csharp [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.#!csharp public interface IContext : IExecutionContext { new IExecutionContext Parent { get; set; } int Iterations { get; set; } int EvaluatedSolutions { get; set; } }
A BasicContext implementation could look like this:
#!csharp 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:
#!csharp [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.
#!csharp [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.
It was decided 4.0 won't contain a new algorithm model
HL architects: this ticket should get a more appropriate name
Issue migrated from trac ticket # 2645
milestone: HeuristicLab 4.x Backlog | component: Optimization | priority: medium
2016-07-24 01:52:55: @abeham created the issue