source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs @ 16724

#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 System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {

  /// <summary>
  /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
  /// </summary>
  /// <remarks>
  /// A fine distinction to the described algorithm is that newly found best solutions are always accepted into the elite set. This is reasonable, but not mentioned in the paper by Mateus et al.
  /// </remarks>
  [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as 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)]
  [StorableClass]
  public sealed class GRASP : StochasticAlgorithm<GRASPContext, IntegerVectorEncoding> {

    public override bool SupportsPause {
      get { return true; }
    }

    public override Type ProblemType {
      get { return typeof(GQAP); }
    }

    public new GQAP Problem {
      get { return (GQAP)base.Problem; }
      set { base.Problem = value; }
    }

    [Storable]
    private FixedValueParameter<IntValue> eliteSetSizeParameter;
    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
      get { return eliteSetSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter;
    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
      get { return minimiumEliteSetSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
    public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
      get { return maximumLocalSearchIterationsParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> candidateSizeFactorParameter;
    public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter {
      get { return candidateSizeFactorParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> maximumCandidateListSizeParameter;
    public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter {
      get { return maximumCandidateListSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> oneMoveProbabilityParameter;
    public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter {
      get { return oneMoveProbabilityParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> minimumDifferenceParameter;
    public IFixedValueParameter<IntValue> MinimumDifferenceParameter {
      get { return minimumDifferenceParameter; }
    }
    
    public int EliteSetSize {
      get { return eliteSetSizeParameter.Value.Value; }
      set { eliteSetSizeParameter.Value.Value = value; }
    }
    public int MinimumEliteSetSize {
      get { return minimiumEliteSetSizeParameter.Value.Value; }
      set { minimiumEliteSetSizeParameter.Value.Value = value; }
    }
    public int MaximumLocalSearchIterations {
      get { return maximumLocalSearchIterationsParameter.Value.Value; }
      set { maximumLocalSearchIterationsParameter.Value.Value = value; }
    }
    public double CandidateSizeFactor {
      get { return candidateSizeFactorParameter.Value.Value; }
      set { candidateSizeFactorParameter.Value.Value = value; }
    }
    public int MaximumCandidateListSize {
      get { return maximumCandidateListSizeParameter.Value.Value; }
      set { maximumCandidateListSizeParameter.Value.Value = value; }
    }
    public double OneMoveProbability {
      get { return oneMoveProbabilityParameter.Value.Value; }
      set { oneMoveProbabilityParameter.Value.Value = value; }
    }
    public int MinimumDifference {
      get { return minimumDifferenceParameter.Value.Value; }
      set { minimumDifferenceParameter.Value.Value = value; }
    }

    [StorableConstructor]
    private GRASP(bool deserializing) : base(deserializing) { }
    private GRASP(GRASP original, Cloner cloner)
      : base(original, cloner) {
      eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
      minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
      maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
      candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
      maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
      oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
      minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
    }
    public GRASP() {
      Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
      Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
      Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
      Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
      Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
      Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));

      Problem = new GQAP();
    }

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

    protected override void Initialize(CancellationToken cancellationToken) {
      base.Initialize(cancellationToken);

      Context.Problem = Problem;
      Context.BestSolution = null;

      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
    }

    protected override void Run(CancellationToken cancellationToken) {
      base.Run(cancellationToken);
      var eq = new IntegerVectorEqualityComparer();
      var lastUpdate = ExecutionTime;
      while (!StoppingCriterion()) { // line 2 in Algorithm 1
        // next: line 3 in Algorithm 1
        IntegerVector pi_prime_vec = null;
        try {
          pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 10, true, cancellationToken);
        } catch (OperationCanceledException) { break; }

        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
          GQAPSolution pi_prime;
          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
            pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1
          else {
            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
            Context.EvaluatedSolutions++;
          }

          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
          // Book-keeping
          var newBest = Context.BestQuality > fitness;
          if (newBest) {
            Context.BestQuality = fitness;
            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
          }

          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
            // in this implementation a new best solution is always accepted into the elite set
            if (newBest || similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
              var replacement = Context.Population.Select((v, i) => new { Scope = v, Index = i })
                                          .Where(x => x.Scope.Fitness >= fitness) // cond. 1 of line 13 in Algorithm 1
                                          .OrderByDescending(x => similarities[x.Index]) // line 14 in Algorithm 1
                                          .FirstOrDefault();
              if (replacement != null) {
                Context.ReplaceAtPopulation(replacement.Index, Context.ToScope(pi_prime, fitness)); // line 14 in Algorithm 1
              }
            }
            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
            // in this implementation a new best solution is always accepted into the elite set
          } else if (newBest || IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
          }
        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
          Context.EvaluatedSolutions++;
          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
          // Book-keeping
          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
            Context.BestQuality = fitness;
            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
          }
        } else if (Context.PopulationCount == 0) {
          // Book-keeping
          // pi_prime_vec is not feasible, but no other feasible solution has been found so far
          var eval = Problem.ProblemInstance.Evaluate(pi_prime_vec);
          Context.EvaluatedSolutions++;
          var fit = Problem.ProblemInstance.ToSingleObjective(eval);
          if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
            Context.BestQuality = fit;
            Context.BestSolution = new GQAPSolution(pi_prime_vec, eval);
          }
        }

        IResult result;
        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
          if (Results.TryGetValue("Iterations", out result))
            ((IntValue)result.Value).Value = Context.Iterations;
          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
          if (Results.TryGetValue("EvaluatedSolutions", out result))
            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
          lastUpdate = ExecutionTime;
        }
        if (Results.TryGetValue("BestQuality", out result))
          ((DoubleValue)result.Value).Value = Context.BestQuality;
        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
        if (Results.TryGetValue("BestSolution", out result))
          result.Value = Context.BestSolution;
        else Results.Add(new Result("BestSolution", Context.BestSolution));

        try {
          Context.RunOperator(Analyzer, cancellationToken);
        } catch (OperationCanceledException) { }

        Context.Iterations++;
        if (cancellationToken.IsCancellationRequested) break;
      }
      IResult result2;
      if (Results.TryGetValue("Iterations", out result2))
        ((IntValue)result2.Value).Value = Context.Iterations;
      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
      if (Results.TryGetValue("EvaluatedSolutions", out result2))
        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    }

    private bool IsSufficientlyDifferent(IntegerVector vec) {
      return Context.Population.All(x =>
        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
      );
    }

    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
      // Following code represents line 1 of Algorithm 4
      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
      if (targetFit < sourceFit) {
        var h = source;
        source = target;
        target = h;
        var hh = sourceEval;
        sourceEval = targetEval;
        targetEval = hh;
      }
      int evaluatedSolutions;
      // lines 2-36 of Algorithm 4 are implemented in the following call
      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
        out evaluatedSolutions);
      Context.EvaluatedSolutions += evaluatedSolutions;
      return pi_star;
    }

    private void ApproxLocalSearch(GQAPSolution pi_prime) {
      var localSearchEvaluations = 0;
      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
      Context.EvaluatedSolutions += localSearchEvaluations;
    }
  }
}