Changeset 7595 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Timestamp:

03/11/12 20:17:07 (13 years ago)

Author:

abeham

Message:

#1614: updated SlackMinimizationSolutionCreator

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/SlackMinimizationSolutionCreator.cs (modified) (7 diffs)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/SlackMinimizationSolutionCreator.cs

@@ -46 +46 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["Depth"]; }
     }
+    public IValueLookupParameter<IntValue> RandomWalkLengthParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["RandomWalkLength"]; }
+    }
 
     [StorableConstructor]
@@ -55 +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)));
       Parameters.Add(new ValueLookupParameter<IntValue>("Depth", "How deep the algorithm should look forward.", new IntValue(3)));
+      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)));
     }
 
@@ -66 +70 @@
         Parameters.Add(new ValueLookupParameter<IntValue>("Depth", "How deep the algorithm should look forward.", new IntValue(3)));
       }
+      if (!Parameters.ContainsKey("RandomWalkLength")) {
+        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)));
+      }
     }
 
-    public static IntegerVector CreateSolution(IRandom random, DoubleArray demands, DoubleArray capacities, int depth, int maximumTries, bool createMostFeasibleSolution, CancellationToken cancel) {
+    public static IntegerVector CreateSolution(IRandom random, DoubleArray demands, DoubleArray capacities, int depth, int maximumTries, bool createMostFeasibleSolution, int randomWalkLength, CancellationToken cancel) {
       IntegerVector result = null;
       bool isFeasible = false;
@@ -89 +96 @@
         var remainingEquipment = new HashSet<int>(Enumerable.Range(0, demands.Length));
         while (remainingEquipment.Any()) {
-          var equipment = remainingEquipment.ChooseProportionalRandom(random, 1, x => demands[x], true, true).Single();
-          remainingEquipment.Remove(equipment);
-
-          var freeLocations = GetLocationsByFillLevel(equipment, demands[equipment], slack);
-          if (!freeLocations.Any()) break;
-          double bestSlack = double.MaxValue;
-          int bestLocation = -1;
-          int[] additionalEquipment = new int[0];
-          foreach (var location in freeLocations.Shuffle(random)) {
-            HashSet<int> newEquipment;
-            var estimatedSlack = EstimatePotentialSlack(location.Key, location.Value, remainingEquipment, demands, out newEquipment, depth);
-            if (estimatedSlack < bestSlack || (estimatedSlack == bestSlack && newEquipment.Count < additionalEquipment.Length)) {
-              bestSlack = estimatedSlack;
-              bestLocation = location.Key;
-              additionalEquipment = newEquipment.ToArray();
+          var minimumDemand = remainingEquipment.Min(x => demands[x]);
+          var possibleLocations = Enumerable.Range(0, capacities.Length).Where(x => slack[x] >= minimumDemand);
+          if (!possibleLocations.Any()) break;
+          foreach (var location in possibleLocations.Shuffle(random)) {
+            var group = FindBestGroup(location, slack[location], remainingEquipment, demands, depth);
+            foreach (var eq in group) {
+              remainingEquipment.Remove(eq);
+              assignment[eq] = location;
+              slack[location] -= demands[eq];
             }
-          }
-          assignment[equipment] = bestLocation;
-          slack[bestLocation] -= demands[equipment];
-          foreach (var eq in additionalEquipment) {
-            remainingEquipment.Remove(eq);
-            assignment[eq] = bestLocation;
-            slack[bestLocation] -= demands[eq];
           }
         }
@@ -124 +118 @@
           }
         }
+        RandomFeasibleWalk(random, assignment, demands, slack, randomWalkLength);
         double violation = GQAPEvaluator.EvaluateOverbooking(slack, capacities);
         isFeasible = violation == 0;
@@ -134 +129 @@
     }
 
-    private static double EstimatePotentialSlack(int location, double slack, HashSet<int> remainingEquipment, DoubleArray demands, out HashSet<int> addedEquipment, int depth = 3) {
-      var feasibleEquipment = remainingEquipment.Where(x => demands[x] < slack).ToArray();
-      addedEquipment = new HashSet<int>();
+    private static IEnumerable<int> FindBestGroup(int location, double slack, HashSet<int> remainingEquipment, DoubleArray demands, int depth = 3) {
+      var feasibleEquipment = remainingEquipment.Where(x => demands[x] <= slack).ToArray();
 
-      if (!feasibleEquipment.Any()) return slack;
+      if (!feasibleEquipment.Any()) yield break;
       if (depth == 0) {
         var e = feasibleEquipment.ChooseMax(x => demands[x]);
-        addedEquipment.Add(e);
-        return slack - demands[e];
+        yield return e;
+        yield break;
       }
 
       double bestSlack = slack;
-      int minSlackEquipment = -1;
+      int bestEquipment = -1;
+      int[] bestColleagues = new int[0];
       foreach (var e in feasibleEquipment) {
         remainingEquipment.Remove(e);
-        HashSet<int> childEquipment;
-        var potentialSlack = EstimatePotentialSlack(location, slack - demands[e], remainingEquipment, demands, out childEquipment, depth - 1);
-        if (bestSlack > potentialSlack || (bestSlack == potentialSlack && childEquipment.Count < addedEquipment.Count)) {
-          bestSlack = potentialSlack;
-          minSlackEquipment = e;
-          addedEquipment.Clear();
-          foreach (var child in childEquipment) addedEquipment.Add(child);
+        var colleagues = FindBestGroup(location, slack - demands[e], remainingEquipment, demands, depth - 1).ToArray();
+        var slackWithColleagues = slack - demands[e] - colleagues.Sum(x => demands[x]);
+        if (bestSlack > slackWithColleagues || (bestSlack == slackWithColleagues && colleagues.Length < bestColleagues.Length)) {
+          bestSlack = slackWithColleagues;
+          bestEquipment = e;
+          bestColleagues = colleagues;
         }
         remainingEquipment.Add(e);
       }
-      if (minSlackEquipment > -1)
-        addedEquipment.Add(minSlackEquipment);
-      return bestSlack;
+      yield return bestEquipment;
+      foreach (var a in bestColleagues) yield return a;
+    }
+
+    private static void RandomFeasibleWalk(IRandom random, Dictionary<int, int> assignment, DoubleArray demands, DoubleArray slack, int walkLength) {
+      for (int i = 0; i < walkLength; i++) {
+        var equipments = Enumerable.Range(0, demands.Length).Shuffle(random);
+        foreach (var e in equipments) {
+          var partners = Enumerable.Range(0, demands.Length)
+            .Where(x => slack[assignment[x]] + demands[x] - demands[e] >= 0
+                && slack[assignment[e]] + demands[e] - demands[x] >= 0);
+          if (!partners.Any()) continue;
+          var f = partners.ChooseUniformRandom(random);
+          int h = assignment[e];
+          assignment[e] = assignment[f];
+          assignment[f] = h;
+          slack[assignment[e]] += demands[f] - demands[e];
+          slack[assignment[f]] += demands[e] - demands[f];
+          break;
+        }
+      }
     }
 
@@ -169 +181 @@
         MaximumTriesParameter.ActualValue.Value,
         CreateMostFeasibleSolutionParameter.ActualValue.Value,
+        RandomWalkLengthParameter.ActualValue.Value,
         CancellationToken);
-    }
-
-    private static IEnumerable<KeyValuePair<int, double>> GetLocationsByFillLevel(int equipment, double demand, DoubleArray slack) {
-      var freeLocations = slack
-        .Select((v, idx) => new KeyValuePair<int, double>(idx, v))
-        .Where(x => x.Value >= demand);
-      if (!freeLocations.Any()) {
-        return Enumerable.Empty<KeyValuePair<int, double>>();
-      }
-      return freeLocations.Select(x => new KeyValuePair<int, double>(x.Key, slack[x.Key] - demand)).OrderBy(x => x.Value);
     }
   }