source: branches/1614_GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinkingMainLoop.cs @ 16009

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Optimization.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Selection;

namespace HeuristicLab.Algorithms.GRASP {
  [Item("GRASP+PR MainLoop", "The main loop that implements the behavior of the GRASP+PR algorithm.")]
  [StorableClass]
  public class GRASPWithPathRelinkingMainLoop : AlgorithmOperator {
    public IValueLookupParameter<IntValue> IterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
    }
    public IValueLookupParameter<IOperator> SolutionCreatorParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["SolutionCreator"]; }
    }
    public IValueLookupParameter<IOperator> EvaluatorParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["Evaluator"]; }
    }
    public IValueLookupParameter<IntValue> EvaluatedSolutionsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
    }
    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
    }
    public IValueLookupParameter<ResultCollection> ResultsParameter {
      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
    }
    public IValueLookupParameter<IntValue> EliteSetSizeParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["EliteSetSize"]; }
    }
    public IValueLookupParameter<IOperator> LocalImprovementParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["LocalImprovement"]; }
    }
    public IValueLookupParameter<IOperator> PathRelinkingParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["PathRelinking"]; }
    }
    public IValueLookupParameter<IOperator> EliteSetReducerParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["EliteSetReducer"]; }
    }
    public IValueLookupParameter<IOperator> AnalyzerParameter {
      get { return (IValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
    }

    [StorableConstructor]
    protected GRASPWithPathRelinkingMainLoop(bool deserializing) : base(deserializing) { }
    protected GRASPWithPathRelinkingMainLoop(GRASPWithPathRelinkingMainLoop original, Cloner cloner)
      : base(original, cloner) { }
    public GRASPWithPathRelinkingMainLoop()
      : base() {
      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations", "The algorithm's current iteration."));
      Parameters.Add(new ValueLookupParameter<IOperator>("SolutionCreator", "The solution creation procedure which ideally should be a greedy initialization heuristic."));
      Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The evaluator which calculates the fitness of a solutions."));
      Parameters.Add(new ValueLookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of maximum iterations that should be performed."));
      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "Specifies where the results are stored."));
      Parameters.Add(new ValueLookupParameter<IntValue>("EliteSetSize", "The size of the elite set."));
      Parameters.Add(new ValueLookupParameter<IOperator>("LocalImprovement", "The operator which performs the local improvement."));
      Parameters.Add(new ValueLookupParameter<IOperator>("PathRelinking", "The operator which performs the path relinking."));
      Parameters.Add(new ValueLookupParameter<IOperator>("EliteSetReducer", "The operator that reduces the existing elite set and the new solution to a new elite set."));
      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The analyzer that is to be applied."));

      var analyzer1 = new Placeholder() { Name = "(Analyzer)" };
      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;

      var selector1 = new RandomSelector();
      selector1.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
      selector1.CopySelected.Value = true;

      var ssp1 = new SubScopesProcessor();

      var eo1 = new EmptyOperator();

      var solutionsCreator = new SolutionsCreator();
      solutionsCreator.ParallelParameter.Value = new BoolValue(false);
      solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
      solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
      solutionsCreator.NumberOfSolutions = new IntValue(1);

      var ssp2 = new SubScopesProcessor();

      var eo2 = new EmptyOperator();

      var placeholder1 = new Placeholder() { Name = "(LocalImprovement)" };
      placeholder1.OperatorParameter.ActualName = LocalImprovementParameter.Name;

      var childrenCreator = new ChildrenCreator();
      childrenCreator.ParentsPerChild = new IntValue(2);

      var ssp3 = new SubScopesProcessor();

      var placeholder2 = new Placeholder() { Name = "(PathRelinking)" };
      placeholder2.OperatorParameter.ActualName = PathRelinkingParameter.Name;

      var placeholder3 = new Placeholder() { Name = "(Evaluator)" };
      placeholder3.OperatorParameter.ActualName = EvaluatorParameter.Name;

      var subScopesRemover = new SubScopesRemover();
      subScopesRemover.RemoveAllSubScopes = true;

      var ssp4 = new SubScopesProcessor();

      var placeholder4 = new Placeholder();
      placeholder4.Name = "(LocalImprovement)";
      placeholder4.OperatorParameter.ActualName = LocalImprovementParameter.Name;

      var placeholder5 = new Placeholder() { Name = "(EliteSetReplacer)" };
      placeholder5.OperatorParameter.ActualName = EliteSetReducerParameter.Name;

      var counter = new IntCounter() { Name = "Iterations++" };
      counter.ValueParameter.ActualName = IterationsParameter.Name;
      counter.Increment = new IntValue(1);

      var analyzer2 = new Placeholder() { Name = "(Analyzer)" };
      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;

      var comparator3 = new Comparator() { Name = "Iterations >= MaximumIterations" };
      comparator3.Comparison.Value = ComparisonType.GreaterOrEqual;
      comparator3.LeftSideParameter.ActualName = IterationsParameter.Name;
      comparator3.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
      comparator3.ResultParameter.ActualName = "TerminatedByIteration";

      var conditionalBranch3 = new ConditionalBranch() { Name = "Terminate by Iterations?" };
      conditionalBranch3.ConditionParameter.ActualName = "TerminatedByIteration";

      OperatorGraph.InitialOperator = analyzer1;
      analyzer1.Successor = selector1;
      selector1.Successor = ssp1;
      ssp1.Operators.Add(eo1);
      ssp1.Operators.Add(solutionsCreator);
      ssp1.Successor = placeholder5;
      eo1.Successor = null;
      solutionsCreator.Successor = ssp2;
      ssp2.Operators.Add(eo2);
      ssp2.Operators.Add(placeholder1);
      ssp2.Successor = childrenCreator;
      eo2.Successor = null;
      placeholder1.Successor = null;
      childrenCreator.Successor = ssp3;
      ssp3.Operators.Add(placeholder2);
      ssp3.Successor = null;
      placeholder2.Successor = placeholder3;
      placeholder3.Successor = subScopesRemover;
      subScopesRemover.Successor = placeholder4;
      placeholder4.Successor = null;
      placeholder5.Successor = counter;
      counter.Successor = analyzer2;
      analyzer2.Successor = comparator3;
      comparator3.Successor = conditionalBranch3;
      conditionalBranch3.TrueBranch = null;
      conditionalBranch3.FalseBranch = selector1;
      conditionalBranch3.Successor = null;
    }

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

    private void Parameterize() {
      var operators = Walk(OperatorGraph).ToArray();

      foreach (var solutionsCreator in operators.OfType<SolutionsCreator>()) {
        solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
        solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
      }
    }

    /// <summary>
    /// Walks an operator graph in that it jumps from one operator to all its operator parameters and yields each operator it touches.
    /// Cycles are detected and not walked twice.
    /// </summary>
    /// <param name="graph">The operator graph that should be walked.</param>
    /// <returns>An enumeration of all the operators that could be found.</returns>
    private IEnumerable<IOperator> Walk(OperatorGraph graph) {
      var open = new Stack<IOperator>();
      var visited = new HashSet<IOperator>();
      open.Push(graph.InitialOperator);

      while (open.Any()) {
        IOperator current = open.Pop();
        if (visited.Contains(current)) continue;
        visited.Add(current);
        yield return current;

        foreach (var parameter in current.Parameters.OfType<IValueParameter>()) {
          if (typeof(IOperator).IsAssignableFrom(parameter.DataType)) {
            if (parameter.Value != null)
              open.Push((IOperator)parameter.Value);
          }
        }
        var algOp = current as AlgorithmOperator;
        if (algOp != null && algOp.OperatorGraph.InitialOperator != null) {
          open.Push(algOp.OperatorGraph.InitialOperator);
        }
      }
    }

    public event EventHandler ProblemChanged;
    protected virtual void OnProblemChanged() {
      Parameterize();
      var handler = ProblemChanged;
      if (handler != null) handler(this, EventArgs.Empty);
    }
  }
}