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 System.Threading;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.IntegerVectorEncoding;


30  using HeuristicLab.Parameters;


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


32  using HeuristicLab.Random;


33 


34  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


35  /// <summary>


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


37  /// </summary>


38  [Item("GreedyRandomizedSolutionCreator", "Creates a solution according to the procedure 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.")]


39  [StorableClass]


40  public class GreedyRandomizedSolutionCreator : GQAPStochasticSolutionCreator {


41 


42  public IValueLookupParameter<IntValue> MaximumTriesParameter {


43  get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTries"]; }


44  }


45  public IValueLookupParameter<BoolValue> CreateMostFeasibleSolutionParameter {


46  get { return (IValueLookupParameter<BoolValue>)Parameters["CreateMostFeasibleSolution"]; }


47  }


48 


49  [StorableConstructor]


50  protected GreedyRandomizedSolutionCreator(bool deserializing) : base(deserializing) { }


51  protected GreedyRandomizedSolutionCreator(GreedyRandomizedSolutionCreator original, Cloner cloner)


52  : base(original, cloner) { }


53  public GreedyRandomizedSolutionCreator()


54  : base() {


55  Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000)));


56  Parameters.Add(new ValueLookupParameter<BoolValue>("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false)));


57  }


58 


59  public override IDeepCloneable Clone(Cloner cloner) {


60  return new GreedyRandomizedSolutionCreator(this, cloner);


61  }


62 


63  public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance,


64  int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {


65  var weights = problemInstance.Weights;


66  var distances = problemInstance.Distances;


67  var demands = problemInstance.Demands;


68  var capacities = problemInstance.Capacities.ToArray();


69  var transportCosts = problemInstance.TransportationCosts;


70  var equipments = demands.Length;


71  var locations = capacities.Length;


72  int tries = 0;


73  var assignment = new int[equipments];


74  var slack = new double[locations];


75  double minViolation = double.MaxValue;


76  int[] bestAssignment = null;


77  var F = new List<int>(equipments); // set of (initially) all facilities / equipments


78  var CF = new List<int>(equipments); // set of chosen facilities / equipments


79  var L = new List<int>(locations); // set of (initially) all locations


80  var CL_list = new List<int>(locations); // list of chosen locations


81  var CL_selected = new bool[locations]; // bool decision if location is chosen


82  var T = new List<int>(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)


83  var H = new double[locations]; // proportions for choosing locations in stage 1


84  var W = new double[equipments]; // proportions for choosing facilities in stage 2


85  var Z = new double[locations]; // proportions for choosing locations in stage 2


86 


87  while (maximumTries <= 0  tries < maximumTries) {


88  cancelToken.ThrowIfCancellationRequested();


89 


90  Array.Copy(capacities, slack, locations); // line 2 of Algorihm 2


91  CF.Clear(); // line 2 of Algorihm 2


92  Array.Clear(CL_selected, 0, locations); // line 2 of Algorihm 2


93  CL_list.Clear(); // line 2 of Algorihm 2


94  T.Clear(); // line 2 of Algorihm 2


95 


96  F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); // line 2 of Algorihm 2


97  L.Clear(); L.AddRange(Enumerable.Range(0, locations)); // line 2 of Algorihm 2


98 


99  double threshold = 1.0; // line 3 of Algorithm 2


100  do { // line 4 of Algorithm 2


101  if (L.Count > 0 && random.NextDouble() < threshold) { // line 5 of Algorithm 2


102  // H is the proportion that a location is chosen


103  // The paper doesn't mention what happens if the candidate list CL


104  // does not contain an element in which case according to the formula


105  // all H_k elements would be 0 which would be equal to random selection


106  var HH = H.Select((v, i) => new { Index = i, Value = v })


107  .Where(x => !CL_selected[x.Index])


108  .Select(x => x.Value);


109  int l = L.SampleProportional(random, 1, HH, false, false).Single(); // line 6 of Algorithm 2


110  L.Remove(l); // line 7 of Algorithm 2


111  CL_list.Add(l); // line 7 of Algorithm 2


112  CL_selected[l] = true; // line 7 of Algorithm 2


113  for (var k = 0; k < locations; k++)


114  if (!CL_selected[k])


115  H[k] += capacities[k] * capacities[l] / distances[k, l];


116  T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 8 of Algorithm 2


117  }


118  if (T.Count > 0) { // line 10 of Algorithm 2


119  // W is the proportion that an equipment is chosen


120  Array.Clear(W, 0, W.Length);


121  var wk = 0;


122  foreach (var k in T) {


123  for (var h = 0; h < equipments; h++) {


124  if (k == h) continue;


125  W[wk] += weights[k, h];


126  }


127  W[wk] *= demands[k];


128  wk++;


129  }


130  var f = T.SampleProportional(random, 1, W.Take(T.Count), false, false) // line 11 of Algorithm 2


131  .Single();


132  T.Remove(f); // line 12 of Algorithm 2


133  F.Remove(f); // line 12 of Algorithm 2


134  CF.Add(f); // line 12 of Algorithm 2


135  var R = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).ToList(); // line 13 of Algorithm 2


136  // Z is the proportion that a location is chosen in stage 2


137  Array.Clear(Z, 0, Z.Length);


138  var zk = 0;


139  foreach (var k in R) {


140  // d is an increase in fitness if f would be assigned to location k


141  var d = problemInstance.InstallationCosts[f, k];


142  foreach (var i in CF) {


143  if (assignment[i] == 0) continue; // i is unassigned


144  var j = assignment[i]  1;


145  d += transportCosts * weights[f, i] * distances[k, j];


146  }


147  foreach (var h in CL_list) {


148  if (k == h) continue;


149  Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]);


150  }


151  zk++;


152  }


153  int l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2


154  assignment[f] = l + 1; // line 15 of Algorithm 2


155  slack[l] = demands[f];


156  T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 16 of Algorithm 2


157  threshold = 1.0  (double)T.Count / Math.Max(F.Count, 1.0); // line 17 of Algorithm 2


158  }


159  } while (T.Count > 0  L.Count > 0); // line 19 of Algorithm 2


160 


161  if (maximumTries > 0) tries++;


162 


163  if (F.Count == 0) {


164  bestAssignment = assignment.Select(x => x  1).ToArray();


165  break;


166  } else if (createMostFeasibleSolution) {


167  // complete the solution and remember the one with least violation


168  foreach (var l in L.ToArray()) {


169  CL_list.Add(l);


170  CL_selected[l] = true;


171  L.Remove(l);


172  }


173  while (F.Count > 0) {


174  var f = F.Select((v, i) => new { Index = i, Value = v }).MaxItems(x => demands[x.Value]).SampleRandom(random);


175  var l = CL_list.MaxItems(x => slack[x]).SampleRandom(random);


176  F.RemoveAt(f.Index);


177  assignment[f.Value] = l + 1;


178  slack[l] = demands[f.Value];


179  }


180  double violation = slack.Select(x => x < 0 ? x : 0).Sum();


181  if (violation < minViolation) {


182  bestAssignment = assignment.Select(x => x  1).ToArray();


183  minViolation = violation;


184  }


185  assignment = new int[equipments];


186  }


187  }


188 


189  if (bestAssignment == null)


190  throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));


191 


192  return new IntegerVector(bestAssignment);


193  }


194 


195  protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) {


196  return CreateSolution(random, problemInstance,


197  MaximumTriesParameter.ActualValue.Value,


198  CreateMostFeasibleSolutionParameter.ActualValue.Value,


199  CancellationToken);


200  }


201 


202  private static IEnumerable<int> WhereDemandEqualOrLess(IEnumerable<int> facilities, double maximum, DoubleArray demands) {


203  foreach (int f in facilities) {


204  if (demands[f] <= maximum) yield return f;


205  }


206  }


207 


208  private static double GetMaximumSlack(double[] slack, bool[] CL) {


209  var max = double.MinValue;


210  for (var i = 0; i < slack.Length; i++) {


211  if (CL[i] && max < slack[i]) max = slack[i];


212  }


213  return max;


214  }


215 


216  private static IEnumerable<int> WhereSlackGreaterOrEqual(IEnumerable<int> locations, double minimum, double[] slack) {


217  foreach (int l in locations) {


218  if (slack[l] >= minimum) yield return l;


219  }


220  }


221  }


222  }

