1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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  [Item("SlackMinimizationSolutionCreator", "A heuristic that creates a solution to the Generalized Quadratic Assignment Problem by minimizing the amount of slack.")]


36  [StorableClass]


37  public class SlackMinimizationSolutionCreator : GQAPStochasticSolutionCreator {


38 


39  public IValueLookupParameter<IntValue> MaximumTriesParameter {


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


41  }


42  public IValueLookupParameter<BoolValue> CreateMostFeasibleSolutionParameter {


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


44  }


45  public IValueLookupParameter<IntValue> DepthParameter {


46  get { return (IValueLookupParameter<IntValue>)Parameters["Depth"]; }


47  }


48  public IValueLookupParameter<IntValue> RandomWalkLengthParameter {


49  get { return (IValueLookupParameter<IntValue>)Parameters["RandomWalkLength"]; }


50  }


51 


52  [StorableConstructor]


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


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


55  public SlackMinimizationSolutionCreator()


56  : base() {


57  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 to create a feasible solution.", new IntValue(100000)));


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


59  Parameters.Add(new ValueLookupParameter<IntValue>("Depth", "How deep the algorithm should look forward.", new IntValue(3)));


60  Parameters.Add(new ValueLookupParameter<IntValue>("RandomWalkLength", "The length of the random walk in the feasible region that is used to diversify the found assignments.", new IntValue(10)));


61  }


62 


63  public override IDeepCloneable Clone(Cloner cloner) {


64  return new SlackMinimizationSolutionCreator(this, cloner);


65  }


66 


67  [StorableHook(HookType.AfterDeserialization)]


68  private void AfterDeserialization() {


69  if (!Parameters.ContainsKey("Depth")) {


70  Parameters.Add(new ValueLookupParameter<IntValue>("Depth", "How deep the algorithm should look forward.", new IntValue(3)));


71  }


72  if (!Parameters.ContainsKey("RandomWalkLength")) {


73  Parameters.Add(new ValueLookupParameter<IntValue>("RandomWalkLength", "The length of the random walk in the feasible region that is used to diversify the found assignments.", new IntValue(10)));


74  }


75  }


76 


77  public static IntegerVector CreateSolution(IRandom random, DoubleArray demands, DoubleArray capacities, int depth, int maximumTries, bool createMostFeasibleSolution, int randomWalkLength, CancellationToken cancel) {


78  IntegerVector result = null;


79  bool isFeasible = false;


80  int counter = 0;


81  double minViolation = double.MaxValue;


82  var slack = new DoubleArray(capacities.Length);


83  var assignment = new Dictionary<int, int>(demands.Length);


84 


85  while (!isFeasible) {


86  cancel.ThrowIfCancellationRequested();


87  if (maximumTries > 0) {


88  counter++;


89  if (counter > maximumTries) {


90  if (createMostFeasibleSolution) break;


91  else throw new InvalidOperationException("A feasible solution could not be obtained after " + maximumTries + " attempts.");


92  }


93  }


94  assignment.Clear();


95  for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i];


96  var remainingEquipment = new HashSet<int>(Enumerable.Range(0, demands.Length));


97  while (remainingEquipment.Any()) {


98  var minimumDemand = remainingEquipment.Min(x => demands[x]);


99  var possibleLocations = Enumerable.Range(0, capacities.Length).Where(x => slack[x] >= minimumDemand);


100  if (!possibleLocations.Any()) break;


101  foreach (var location in possibleLocations.Shuffle(random)) {


102  var group = FindBestGroup(location, slack[location], remainingEquipment, demands, depth);


103  foreach (var eq in group) {


104  remainingEquipment.Remove(eq);


105  assignment[eq] = location;


106  slack[location] = demands[eq];


107  }


108  }


109  }


110  if (assignment.Count != demands.Length) {


111  // complete the solution


112  while (remainingEquipment.Any()) {


113  var f = remainingEquipment.MaxItems(x => demands[x]).SampleRandom(random);


114  var l = Enumerable.Range(0, capacities.Length).MaxItems(x => slack[x]).SampleRandom(random);


115  remainingEquipment.Remove(f);


116  assignment.Add(f, l);


117  slack[l] = demands[f];


118  }


119  } else RandomFeasibleWalk(random, assignment, demands, slack, randomWalkLength);


120  double violation = GQAPEvaluator.EvaluateOverbooking(slack, capacities);


121  isFeasible = violation == 0;


122  if (isFeasible  violation < minViolation) {


123  result = new IntegerVector(assignment.OrderBy(x => x.Key).Select(x => x.Value).ToArray());


124  minViolation = violation;


125  }


126  }


127  return result;


128  }


129 


130  private static IEnumerable<int> FindBestGroup(int location, double slack, HashSet<int> remainingEquipment, DoubleArray demands, int depth = 3) {


131  var feasibleEquipment = remainingEquipment.Where(x => demands[x] <= slack).ToArray();


132 


133  if (!feasibleEquipment.Any()) yield break;


134  if (depth == 0) {


135  var e = feasibleEquipment.MaxItems(x => demands[x]).First();


136  yield return e;


137  yield break;


138  }


139 


140  double bestSlack = slack;


141  int bestEquipment = 1;


142  int[] bestColleagues = new int[0];


143  foreach (var e in feasibleEquipment) {


144  remainingEquipment.Remove(e);


145  var colleagues = FindBestGroup(location, slack  demands[e], remainingEquipment, demands, depth  1).ToArray();


146  var slackWithColleagues = slack  demands[e]  colleagues.Sum(x => demands[x]);


147  if (bestSlack > slackWithColleagues  (bestSlack == slackWithColleagues && colleagues.Length < bestColleagues.Length)) {


148  bestSlack = slackWithColleagues;


149  bestEquipment = e;


150  bestColleagues = colleagues;


151  }


152  remainingEquipment.Add(e);


153  }


154  yield return bestEquipment;


155  foreach (var a in bestColleagues) yield return a;


156  }


157 


158  private static void RandomFeasibleWalk(IRandom random, Dictionary<int, int> assignment, DoubleArray demands, DoubleArray slack, int walkLength) {


159  for (int i = 0; i < walkLength; i++) {


160  var equipments = Enumerable.Range(0, demands.Length).Shuffle(random);


161  foreach (var e in equipments) {


162  var partners = Enumerable.Range(0, demands.Length)


163  .Where(x => slack[assignment[x]] + demands[x]  demands[e] >= 0


164  && slack[assignment[e]] + demands[e]  demands[x] >= 0);


165  if (!partners.Any()) continue;


166  var f = partners.SampleRandom(random);


167  int h = assignment[e];


168  assignment[e] = assignment[f];


169  assignment[f] = h;


170  slack[assignment[e]] += demands[f]  demands[e];


171  slack[assignment[f]] += demands[e]  demands[f];


172  break;


173  }


174  }


175  }


176 


177  protected override IntegerVector CreateRandomSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {


178  return CreateSolution(random, demands, capacities,


179  DepthParameter.ActualValue.Value,


180  MaximumTriesParameter.ActualValue.Value,


181  CreateMostFeasibleSolutionParameter.ActualValue.Value,


182  RandomWalkLengthParameter.ActualValue.Value,


183  CancellationToken);


184  }


185  }


186  }

