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 installCosts = problemInstance.InstallationCosts;


68  var demands = problemInstance.Demands;


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


70  var transportCosts = problemInstance.TransportationCosts;


71  var equipments = demands.Length;


72  var locations = capacities.Length;


73  int tries = 0;


74  var slack = new double[locations];


75  double minViolation = double.MaxValue;


76  int[] assignment = null;


77  int[] bestAssignment = null;


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


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


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


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


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


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


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


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


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


87 


88  for (var k = 0; k < equipments; k++) {


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


90  if (k == h) continue;


91  W[k] += weights[k, h];


92  }


93  W[k] *= demands[k];


94  }


95 


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


97  cancelToken.ThrowIfCancellationRequested();


98 


99  assignment = new int[equipments];


100 


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


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


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


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


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


106 


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


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


109 


110  Array.Clear(H, 0, H.Length);


111 


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


113  do { // line 4 of Algorithm 2


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


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


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


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


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


119  var HH = L.Select(x => H[x]);


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


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


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


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


124  // incrementally updating location weights


125  foreach (var k in L)


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


127 


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


129  }


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


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


132  var WW = T.Select(x => W[x]);


133  var f = T.SampleProportional(random, 1, WW, false, false) // line 11 of Algorithm 2


134  .Single();


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


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


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


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


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


140  var l = R[0];


141  if (R.Count > 1) { // optimization, calculate probabilistic weights only in case R > 1


142  Array.Clear(Z, 0, R.Count);


143  var zk = 0;


144  foreach (var k in R) {


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


146  var d = installCosts[f, k];


147  foreach (var i in CF) {


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


149  var j = assignment[i]  1;


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


151  }


152  foreach (var h in CL_list) {


153  if (k == h) continue;


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


155  }


156  zk++;


157  }


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


159  }


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


161  slack[l] = demands[f];


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


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


164  }


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


166 


167  if (maximumTries > 0) tries++;


168 


169  if (F.Count == 0) {


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


171  break;


172  } else if (createMostFeasibleSolution) {


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


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


175  CL_list.Add(l);


176  CL_selected[l] = true;


177  L.Remove(l);


178  }


179  while (F.Count > 0) {


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


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


182  F.RemoveAt(f.Index);


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


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


185  }


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


187  if (violation < minViolation) {


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


189  minViolation = violation;


190  }


191  }


192  }


193 


194  if (bestAssignment == null)


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


196 


197  return new IntegerVector(bestAssignment);


198  }


199 


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


201  return CreateSolution(random, problemInstance,


202  MaximumTriesParameter.ActualValue.Value,


203  CreateMostFeasibleSolutionParameter.ActualValue.Value,


204  CancellationToken);


205  }


206 


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


208  foreach (int f in facilities) {


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


210  }


211  }


212 


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


214  var max = double.MinValue;


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


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


217  }


218  return max;


219  }


220 


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


222  foreach (int l in locations) {


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


224  }


225  }


226  }


227  }

