1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.IntegerVectorEncoding;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31  using HeuristicLab.Random;


32 


33  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


34  /// <summary>


35  /// 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/s1073201091440


36  /// </summary>


37  [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with pathrelinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527565.")]


38  [StorableClass]


39  public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator {


40 


41  public IScopeTreeLookupParameter<DoubleValue> QualityParameter {


42  get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }


43  }


44  public IScopeTreeLookupParameter<Evaluation> EvaluationParameter {


45  get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }


46  }


47 


48  public IValueParameter<PercentValue> CandidateSizeFactorParameter {


49  get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }


50  }


51 


52  [StorableConstructor]


53  protected GQAPPathRelinking(bool deserializing) : base(deserializing) { }


54  protected GQAPPathRelinking(GQAPPathRelinking original, Cloner cloner) : base(original, cloner) { }


55  public GQAPPathRelinking()


56  : base() {


57  Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", ""));


58  Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));


59  Parameters.Add(new ValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each pathrelinking 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)));


60  }


61 


62  public override IDeepCloneable Clone(Cloner cloner) {


63  return new GQAPPathRelinking(this, cloner);


64  }


65 


66  public static GQAPSolution Apply(IRandom random,


67  IntegerVector source, Evaluation sourceEval,


68  IntegerVector target, Evaluation targetEval,


69  GQAPInstance problemInstance, double candidateSizeFactor,


70  out int evaluatedSolutions) {


71  evaluatedSolutions = 0;


72  var demands = problemInstance.Demands;


73  var capacities = problemInstance.Capacities;


74  var cmp = new IntegerVectorEqualityComparer();


75 


76  var greedy = true; // greedy performed better according to the paper


77  var sFit = problemInstance.ToSingleObjective(sourceEval);


78  var tFit = problemInstance.ToSingleObjective(targetEval);


79  GQAPSolution pi_star = sFit < tFit ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4


80  double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4


81 


82  var pi_prime = (IntegerVector)source.Clone(); // line 3 of Algorithm 4


83  //var fix = new bool[demands.Length]; // line 3 of Algorithm 4, note that according to the description it is not necessary to track the fixed equipments


84  var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4


85  var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4


86 


87  while (phi.Count > 0) { // line 5 of Algorithm 4


88  var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4


89  var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)


90  foreach (var v in phi) { // line 7 of Algorithm 4


91  int oldLocation = pi_prime[v];


92  pi_prime[v] = target[v]; // line 8 of Algorithm 4


93  var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4


94  pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable


95  var pi_dash_eval = problemInstance.Evaluate(pi_dash);


96  evaluatedSolutions++;


97  var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);


98 


99  if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4


100  if (B.Any(x => cmp.Equals(x.Assignment, pi_dash))) continue; // cond. 2 of line 12 and cond. 1 of line 16 in Algorithm 4


101 


102  if (B.Count >= candidateSizeFactor * phi.Count) { // line 11 of Algorithm 4


103  var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })


104  .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4


105  .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })


106  .ToArray();


107  if (replacement.Length > 0) {


108  var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;


109  B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4


110  B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4


111  B_fit[mostSimilar] = pi_dash_fit; // line 13 of Algorithm 4


112  }


113  } else { // line 16, condition has been checked above already


114  B.Add(new GQAPSolution(pi_dash, pi_dash_eval)); // line 17 of Algorithm 4


115  B_fit.Add(pi_dash_fit); // line 17 of Algorithm 4


116  }


117  }


118  }


119  if (B.Count > 0) { // line 21 of Algorithm 4


120  GQAPSolution pi;


121  // line 22 of Algorithm 4


122  if (greedy) {


123  pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;


124  } else {


125  pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();


126  }


127  var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4


128  var I = phi.Except(diff); // line 24 of Algorithm 4


129  var i = I.SampleRandom(random); // line 25 of Algorithm 4


130  //fix[i] = true; // line 26 of Algorithm 4


131  nonFix.Remove(i); // line 26 of Algorithm 4


132  pi_prime = pi.Assignment; // line 27 of Algorithm 4


133  var fit = problemInstance.ToSingleObjective(pi.Evaluation);


134  if (fit < pi_star_Fit) { // line 28 of Algorithm 4


135  pi_star_Fit = fit; // line 29 of Algorithm 4


136  pi_star = pi; // line 30 of Algorithm 4


137  }


138  } else return pi_star;


139  phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));


140  }


141 


142  return pi_star;


143  }


144 


145  protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,


146  GQAPInstance problemInstance) {


147 


148  var qualities = QualityParameter.ActualValue;


149  var evaluations = EvaluationParameter.ActualValue;


150  var betterParent = qualities[0].Value <= qualities[1].Value ? 0 : 1;


151  var worseParent = 1  betterParent;


152  var source = parents[betterParent];


153  var target = parents[worseParent];


154 


155  int evaluatedSolution;


156  return Apply(random, source, evaluations[betterParent],


157  target, evaluations[worseParent], problemInstance,


158  CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;


159  }


160 


161  private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {


162  int l = pi[equipment];


163  var slack = ComputeSlack(pi, demands, capacities);


164  if (slack[l] >= 0) // line 1 of Algorithm 5


165  return new IntegerVector(pi); // line 2 of Algorithm 5


166 


167  IntegerVector pi_prime = null;


168  int k = 0; // line 4 of Algorithm 5


169  while (k < maximumTries && slack[l] < 0) { // line 5 of Algorithm 5


170  pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5


171  do { // line 7 of Algorithm 5


172  var maxSlack = slack.Max(); // line 89 of Algorithm 5


173  var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 89 of Algorithm 5


174  if (T.Count > 0) { // line 10 of Algorithm 5


175  int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5


176  var j = Enumerable.Range(0, capacities.Length)


177  .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5


178  .SampleRandom(random); // line 13 of Algorithm 5


179  pi_prime[i] = j; // line 14 of Algorithm 5


180  slack[j] = demands[i]; // line 14 of Algorithm 5


181  slack[l] += demands[i]; // line 14 of Algorithm 5


182  } else break; // cond. 1 in line 16 of Algorithm 5


183  } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5


184  k++; // line 17 of Algorithm 5


185  }


186  return pi_prime; // line 1923 of Algorithm 5


187  }


188 


189  private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {


190  var slack = new double[capacities.Length];


191  for (int i = 0; i < assignment.Length; i++) {


192  slack[assignment[i]] = demands[i];


193  }


194  return slack;


195  }


196  }


197  }

