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  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 ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4


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


83 


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


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


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


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


88 


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


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


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


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


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


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


95  int oldLocation = pi_prime[v];


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


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


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


99 


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


101  var pi_dash_eval = problemInstance.Evaluate(pi_dash);


102  evaluatedSolutions++;


103  var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);


104 


105  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


106 


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


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


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


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


111  .ToArray();


112  if (replacement.Length > 0) {


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


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


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


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


117  }


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


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


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


121  }


122  }


123  }


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


125  GQAPSolution pi;


126  // line 22 of Algorithm 4


127  if (greedy) {


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


129  } else {


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


131  }


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


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


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


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


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


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


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


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


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


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


142  }


143  } else return pi_star;


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


145  }


146 


147  return pi_star;


148  }


149 


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


151  GQAPInstance problemInstance) {


152 


153  var qualities = QualityParameter.ActualValue;


154  var evaluations = EvaluationParameter.ActualValue;


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


156  var worseParent = 1  betterParent;


157  var source = parents[betterParent];


158  var target = parents[worseParent];


159 


160  int evaluatedSolution;


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


162  target, evaluations[worseParent], problemInstance,


163  CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,


164  GreedyParameter.ActualValue.Value).Assignment;


165  }


166 


167  /// <summary>


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


169  /// is overutilized.


170  /// </summary>


171  /// <remarks>


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


173  /// </remarks>


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


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


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


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


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


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


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


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


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


183  int l = pi[equipment];


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


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


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


187 


188  IntegerVector pi_prime = null;


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


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


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


192  var maxSlack_prime = maxSlack;


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


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


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


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


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


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


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


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


201  do { // line 7 of Algorithm 5


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


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


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


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


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


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


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


209  T.RemoveAt(idx);


210  weightT.RemoveAt(idx);


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


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


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


214  if (recomputeMaxSlack) {


215  maxSlack_prime = slack_prime.Max();


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


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


218  var f = T[h];


219  if (demands[f] > maxSlack_prime) {


220  T.RemoveAt(h);


221  weightT.RemoveAt(h);


222  h;


223  }


224  }


225  }


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


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


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


229  if (slack_prime[l] < 0) {


230  // reset


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


232  maxSlack_prime = maxSlack;


233  }


234  }


235  return pi_prime; // line 1923 of Algorithm 5


236  }


237 


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


239  var slack = capacities.ToArray();


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


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


242  }


243  return slack;


244  }


245  }


246  }

