1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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  public IValueParameter<PercentValue> CandidateSizeFactorParameter {


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


49  }


50  public IValueLookupParameter<BoolValue> GreedyParameter {


51  get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }


52  }


53 


54  [StorableConstructor]


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


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


57  public GQAPPathRelinking()


58  : base() {


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


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


61  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)));


62  Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));


63  }


64 


65  public override IDeepCloneable Clone(Cloner cloner) {


66  return new GQAPPathRelinking(this, cloner);


67  }


68 


69  public static GQAPSolution Apply(IRandom random,


70  IntegerVector source, Evaluation sourceEval,


71  IntegerVector target, Evaluation targetEval,


72  GQAPInstance problemInstance, double candidateSizeFactor,


73  out int evaluatedSolutions, bool greedy = true) {


74  evaluatedSolutions = 0;


75  var demands = problemInstance.Demands;


76  var capacities = problemInstance.Capacities;


77  var cmp = new IntegerVectorEqualityComparer();


78 


79  var sFit = problemInstance.ToSingleObjective(sourceEval);


80  var tFit = problemInstance.ToSingleObjective(targetEval);


81  GQAPSolution pi_star = sFit < tFit


82  ? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone())


83  : new GQAPSolution((IntegerVector)target.Clone(), (Evaluation)targetEval.Clone()); // line 1 of Algorithm 4


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


85 


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


87  //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


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


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


90 


91  var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor));


92  var B_fit = new List<double>(B.Capacity);


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


94  B.Clear(); // line 6 of Algorithm 4


95  B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)


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


97  int oldLocation = pi_prime[v];


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


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


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


101 


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


103  var pi_dash_eval = problemInstance.Evaluate(pi_dash);


104  evaluatedSolutions++;


105  var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);


106 


107  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


108 


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


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


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


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


113  .ToArray();


114  if (replacement.Length > 0) {


115  var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;


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


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


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


119  }


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


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


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


123  }


124  }


125  }


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


127  GQAPSolution pi;


128  // line 22 of Algorithm 4


129  if (greedy) {


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


131  } else {


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


133  }


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


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


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


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


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


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


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


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


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


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


144  }


145  } else return pi_star;


146  phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));


147  }


148 


149  return pi_star;


150  }


151 


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


153  GQAPInstance problemInstance) {


154 


155  var qualities = QualityParameter.ActualValue;


156  var evaluations = EvaluationParameter.ActualValue;


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


158  var worseParent = 1  betterParent;


159  var source = parents[betterParent];


160  var target = parents[worseParent];


161 


162  int evaluatedSolution;


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


164  target, evaluations[worseParent], problemInstance,


165  CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,


166  GreedyParameter.ActualValue.Value).Assignment;


167  }


168 


169  /// <summary>


170  /// Relocates equipments in the same location as <paramref name="equipment"/> to other locations in case the location


171  /// is overutilized.


172  /// </summary>


173  /// <remarks>


174  /// This method is performance critical, called very often and should run as fast as possible.


175  /// </remarks>


176  /// <param name="random">The random number generator.</param>


177  /// <param name="pi">The current solution.</param>


178  /// <param name="equipment">The equipment that was just assigned to a new location.</param>


179  /// <param name="nonFix">The equipments that have not yet been fixed.</param>


180  /// <param name="demands">The demands for all equipments.</param>


181  /// <param name="capacities">The capacities of all locations.</param>


182  /// <param name="maximumTries">The number of tries that should be done in relocating the equipments.</param>


183  /// <returns>A feasible or infeasible solution</returns>


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


185  int l = pi[equipment];


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


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


188  return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5


189 


190  IntegerVector pi_prime = null;


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


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


193  var slack_prime = (double[])slack.Clone();


194  var maxSlack_prime = maxSlack;


195  // note that FTL can be computed only once for all tries as all tries restart with the same solution


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


197  var FTLweight = FTL.Select(x => demands[x]).ToList();


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


199  pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5


200  // set T can only shrink and not grow, thus it is created outside the loop and only updated inside


201  var T = new List<int>(FTL); // line 89 of Algorithm 5


202  var weightT = new List<double>(FTLweight);


203  do { // line 7 of Algorithm 5


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


205  var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5


206  int i = T[idx]; // line 11 of Algorithm 5


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


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


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


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


211  T.RemoveAt(idx);


212  weightT.RemoveAt(idx);


213  var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack


214  slack_prime[j] = demands[i]; // line 14 of Algorithm 5


215  slack_prime[l] += demands[i]; // line 14 of Algorithm 5


216  if (recomputeMaxSlack) {


217  maxSlack_prime = slack_prime.Max();


218  // T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes


219  for (var h = 0; h < T.Count; h++) {


220  var f = T[h];


221  if (demands[f] > maxSlack_prime) {


222  T.RemoveAt(h);


223  weightT.RemoveAt(h);


224  h;


225  }


226  }


227  }


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


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


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


231  if (slack_prime[l] < 0) {


232  // reset


233  Array.Copy(slack, slack_prime, slack.Length);


234  maxSlack_prime = maxSlack;


235  }


236  }


237  return pi_prime; // line 1923 of Algorithm 5


238  }


239 


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


241  var slack = capacities.ToArray();


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


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


244  }


245  return slack;


246  }


247  }


248  }

