source: branches/1614_GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinking.cs @ 17607

#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.Linq;
using HeuristicLab.Analysis;
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.PluginInfrastructure;
using HeuristicLab.Random;
using HEAL.Attic;

namespace HeuristicLab.Algorithms.GRASP {
  /// <summary>
  /// The algorithm combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking and is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.
  /// </summary>
  [Item("GRASP+PR", "The algorithm combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking and is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
  [StorableType("AA509A09-10A7-48B9-AEF1-50997F01A0B0")]
  public sealed class GRASPWithPathRelinking : HeuristicOptimizationEngineAlgorithm, IStorableContent {
    public string Filename { get; set; }

    #region Problem Properties
    public override Type ProblemType {
      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
    }
    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
      set { base.Problem = value; }
    }
    #endregion

    #region Parameter Properties
    private IValueParameter<BoolValue> SetSeedRandomlyParameter {
      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
    }
    private IValueParameter<IntValue> SeedParameter {
      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
    }
    private IValueParameter<MultiAnalyzer> AnalyzerParameter {
      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
    }
    public IValueParameter<IntValue> MaximumIterationsParameter {
      get { return (IValueParameter<IntValue>)Parameters["MaximumIterations"]; }
    }
    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters["EliteSetSize"]; }
    }
    private IFixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
    }
    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
    }
    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters["MinimumEliteSetSize"]; }
    }
    public ConstrainedValueParameter<ICrossover> PathRelinkingParameter {
      get { return (ConstrainedValueParameter<ICrossover>)Parameters["PathRelinking"]; }
    }
    public ConstrainedValueParameter<IPopulationReducer> EliteSetReducerParameter {
      get { return (ConstrainedValueParameter<IPopulationReducer>)Parameters["EliteSetReducer"]; }
    }
    #endregion

    #region Properties
    public BoolValue SetSeedRandomly {
      get { return SetSeedRandomlyParameter.Value; }
      set { SetSeedRandomlyParameter.Value = value; }
    }
    public IntValue Seed {
      get { return SeedParameter.Value; }
      set { SeedParameter.Value = value; }
    }
    public MultiAnalyzer Analyzer {
      get { return AnalyzerParameter.Value; }
      set { AnalyzerParameter.Value = value; }
    }
    public IntValue EliteSetSize {
      get { return EliteSetSizeParameter.Value; }
      set { EliteSetSizeParameter.Value.Value = value.Value; }
    }
    public IntValue LocalImprovementMaximumIterations {
      get { return LocalImprovementMaximumIterationsParameter.Value; }
      set { LocalImprovementMaximumIterationsParameter.Value.Value = value.Value; }
    }

    private RandomCreator RandomCreator {
      get { return (RandomCreator)OperatorGraph.InitialOperator; }
    }
    private VariableCreator VariableCreator {
      get { return (VariableCreator)RandomCreator.Successor; }
    }
    private SolutionsCreator SolutionsCreator {
      get { return (SolutionsCreator)VariableCreator.Successor; }
    }
    private SubScopesCounter SubScopesCounter {
      get { return (SubScopesCounter)SolutionsCreator.Successor; }
    }
    private ResultsCollector ResultsCollector {
      get { return (ResultsCollector)SubScopesCounter.Successor; }
    }
    private GRASPWithPathRelinkingMainLoop MainLoop {
      get { return (GRASPWithPathRelinkingMainLoop)ResultsCollector.Successor; }
    }
    #endregion

    [Storable]
    private BestAverageWorstQualityAnalyzer analyzer;

    [StorableConstructor]
    private GRASPWithPathRelinking(StorableConstructorFlag _) : base(_) { }
    private GRASPWithPathRelinking(GRASPWithPathRelinking original, Cloner cloner)
      : base(original, cloner) {
      analyzer = cloner.Clone(original.analyzer);
      RegisterEventHandlers();
    }
    public GRASPWithPathRelinking()
      : base() {
      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator."));
      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer()));
      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations that the algorithm should run.", new IntValue(1000)));
      Parameters.Add(new FixedValueParameter<IntValue>("EliteSetSize", "The elite set stores the best found solutions.", new IntValue(10)));
      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations performed by the local improvement operator.", new IntValue(1000)));
      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "Performs a local search on the solution."));
      Parameters.Add(new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimum amount of elites for performing path relinking.", new IntValue(2)));
      Parameters.Add(new ConstrainedValueParameter<ICrossover>("PathRelinking", "The operator that performs the path relinking."));
      Parameters.Add(new ConstrainedValueParameter<IPopulationReducer>("EliteSetReducer", "The operator that reduces the old elite set and the new solution(s) to a new elite set."));

      analyzer = new BestAverageWorstQualityAnalyzer();
      Analyzer.Operators.Add(analyzer);

      var randomCreator = new RandomCreator();
      OperatorGraph.InitialOperator = randomCreator;

      randomCreator.RandomParameter.ActualName = "Random";
      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
      randomCreator.SeedParameter.Value = null;
      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
      randomCreator.SetSeedRandomlyParameter.Value = null;
      
      var variableCreator = new VariableCreator();
      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
      randomCreator.Successor = variableCreator;
      
      var solutionsCreator = new SolutionsCreator();
      solutionsCreator.NumberOfSolutionsParameter.ActualName = MinimumEliteSetSizeParameter.Name;
      solutionsCreator.ParallelParameter.Value = new BoolValue(true);
      variableCreator.Successor = solutionsCreator;

      var subscopesCounter = new SubScopesCounter();
      subscopesCounter.Name = "EvaluatedSolutions++";
      subscopesCounter.AccumulateParameter.Value.Value = true;
      subscopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
      solutionsCreator.Successor = subscopesCounter;

      var resultsCollector = new ResultsCollector();
      resultsCollector.CopyValue.Value = false;
      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "Counter for the number of times the evaluation function is called."));
      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The algorithm's current iteration"));
      subscopesCounter.Successor = resultsCollector;

      var mainLoop = new GRASPWithPathRelinkingMainLoop();
      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
      mainLoop.EliteSetReducerParameter.ActualName = EliteSetReducerParameter.Name;
      mainLoop.EliteSetSizeParameter.ActualName = EliteSetSizeParameter.Name;
      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
      mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
      mainLoop.ResultsParameter.ActualName = "Results";
      resultsCollector.Successor = mainLoop;

      InitializeOperators();
      RegisterEventHandlers();
    }

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

    public override void Prepare() {
      if (Problem != null) base.Prepare();
    }

    #region Events
    protected override void OnProblemChanged() {
      InitializeOperators();
      base.OnProblemChanged();
    }

    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
      Parameterize();
      base.Problem_SolutionCreatorChanged(sender, e);
    }
    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
      Parameterize();
      base.Problem_EvaluatorChanged(sender, e);
    }
    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
      InitializeOperators();
      base.Problem_OperatorsChanged(sender, e);
    }

    private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
      Parameterize();
    }
    #endregion

    #region Helpers
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (Problem != null) {
      }
      RegisterEventHandlers();
    }

    private void RegisterEventHandlers() {
      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
    }

    private void InitializeOperators() {
      Analyzer.Operators.Clear();
      if (Problem != null) {
        foreach (IAnalyzer a in Problem.Operators.OfType<IAnalyzer>()) {
          foreach (var param in a.Parameters.OfType<IScopeTreeLookupParameter>())
            param.Depth = 1;
          Analyzer.Operators.Add(a);
          Analyzer.Operators.SetItemCheckedState(a, a.EnabledByDefault);
        }
        InitializeFromInstallation(LocalImprovementParameter, x => x is ILocalImprovementAlgorithmOperator
          && ((ILocalImprovementAlgorithmOperator)x).ProblemType.IsInstanceOfType(Problem));
        InitializeFromProblem(PathRelinkingParameter);
        InitializeFromProblem(EliteSetReducerParameter);
      } else {
        LocalImprovementParameter.ValidValues.Clear();
        PathRelinkingParameter.ValidValues.Clear();
        EliteSetReducerParameter.ValidValues.Clear();
      }
      Analyzer.Operators.Add(analyzer);

      Parameterize();
    }

    private void Parameterize() {
      if (Problem != null) {
        SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
        SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;

        MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
        MainLoop.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;

        analyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;

        if (LocalImprovementParameter.Value != null) {
          if (LocalImprovementParameter.Value is ILocalImprovementAlgorithmOperator)
            ((ILocalImprovementAlgorithmOperator)LocalImprovementParameter.Value).Problem = Problem;
        }
      }
      foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
        localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
        localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
        localImprovement.ResultsParameter.ActualName = "Results";
      }
      foreach (var reducer in EliteSetReducerParameter.ValidValues) {
        reducer.MinimumPopulationSizeParameter.ActualName = MinimumEliteSetSizeParameter.Name;
        reducer.MaximumPopulationSizeParameter.ActualName = EliteSetSizeParameter.Name;
      }
    }

    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
      InitializeFromProblem<T>(parameter, x => true);
    }
    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
      if (parameter == null) throw new ArgumentNullException("parameter");
      if (condition == null) throw new ArgumentNullException("condition");
      string oldName = String.Empty;
      if (parameter.Value != null) oldName = parameter.Value.Name;
      parameter.ValidValues.Clear();
      foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
        parameter.ValidValues.Add(item);
      }
      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
      if (newItem != null) parameter.Value = newItem;
    }
    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
      InitializeFromInstallation<T>(parameter, x => true);
    }
    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
      if (parameter == null) throw new ArgumentNullException("parameter");
      if (condition == null) throw new ArgumentNullException("condition");
      string oldName = String.Empty;
      if (parameter.Value != null) oldName = parameter.Value.Name;
      parameter.ValidValues.Clear();
      foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
        parameter.ValidValues.Add(item);
      }
      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
      if (newItem != null) parameter.Value = newItem;
    }
    #endregion
  }
}