source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs @ 15562

#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>
  [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> {

    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.BestQuality = double.NaN;
      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)));

      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    }

    protected override void Run(CancellationToken cancellationToken) {
      var eq = new IntegerVectorEqualityComparer();
      while (!StoppingCriterion()) { // line 2 in Algorithm 1
        // next: line 3 in Algorithm 1
        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
        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 = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // 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
          if (Context.BestQuality > fitness) {
            Context.BestQuality = fitness;
            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
          }

          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
            if (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 { V = v, Index = i })
                                          .Where(x => x.V.Fitness >= fit).ToArray();
              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
                // next two lines: line 14 in Algorithm 1
                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
                Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
              }
            }
          } else if (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();
          }
        }

        IResult result;
        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)));
        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));

        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);

        Context.Iterations++;
        if (cancellationToken.IsCancellationRequested) break;
      }
    }

    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;
    }
  }
}