Changeset 7432 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment

Timestamp:

01/31/12 15:17:16 (13 years ago)

Author:

abeham

Message:

#1614

• updated gqap (finished path-relinking)
• fixed some bugs

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Analyzers/BestGQAPSolutionAnalyzer.cs (modified) (1 diff)
• GQAPAssignment.cs (modified) (1 diff)
• GQAPAssignmentArchive.cs (modified) (1 diff)
• GQAPIntegerVectorProximityCalculator.cs (deleted)
• GQAPSolutionStructuralEqualityComparer.cs (deleted)
• GeneralizedQuadraticAssignmentProblem.cs (modified) (3 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• Operators/DemandEquivalentSwapEquipmentManipluator.cs (modified) (1 diff)
• Operators/GQAPPathRelinking.cs (modified) (4 diffs)
• Operators/GreedyRandomizedSolutionCreator.cs (modified) (2 diffs)
• Operators/QualitySimilarityMerger.cs (modified) (1 diff)
• Operators/RelocateEquipmentManipluator.cs (modified) (1 diff)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Analyzers/BestGQAPSolutionAnalyzer.cs

@@ -155 +155 @@
       int bestIndex;
       var tmp = qualities.Select((x, index) => new { Index = index, Value = x.Value });
-      if (maximization) bestIndex = tmp.SelectMax(x => x.Value).Index;
-      else bestIndex = tmp.SelectMin(x => x.Value).Index;
+      if (maximization) bestIndex = tmp.ChooseMax(x => x.Value).Index;
+      else bestIndex = tmp.ChooseMin(x => x.Value).Index;
 
       if (bestKnownQuality == null || HasSolutionImproved(bestKnownQuality.Value, qualities[bestIndex].Value, maximization)) {

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPAssignment.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("Generalized QAP Assignment", "Represents a solution to the generalized QAP.")]
+  [Item("Generalized QAP Assignment", "Represents the solution as well as the problem parameters of a GQAP instance.")]
   [StorableClass]
   public sealed class GQAPAssignment : Item, INotifyPropertyChanged {

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPAssignmentArchive.cs

@@ -145 +145 @@
     private GQAPAssignmentArchive(GQAPAssignmentArchive original, Cloner cloner)
       : base(original, cloner) {
+      solutions = cloner.Clone(original.solutions);
       equipmentNames = cloner.Clone(original.equipmentNames);
       locationNames = cloner.Clone(original.locationNames);

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GeneralizedQuadraticAssignmentProblem.cs

@@ -142 +142 @@
     private GeneralizedQuadraticAssignmentProblem(GeneralizedQuadraticAssignmentProblem original, Cloner cloner)
       : base(original, cloner) {
-      AttachEventHandlers();
+      RegisterEventHandlers();
     }
     public GeneralizedQuadraticAssignmentProblem()
@@ -186 +186 @@
 
       InitializeOperators();
-      AttachEventHandlers();
+      RegisterEventHandlers();
     }
 
@@ -220 +220 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      AttachEventHandlers();
-    }
-
-    private void AttachEventHandlers() {
+      RegisterEventHandlers();
+    }
+
+    private void RegisterEventHandlers() {
       Evaluator.QualityParameter.ActualNameChanged += new System.EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       SolutionCreator.AssignmentParameter.ActualNameChanged += new EventHandler(SolutionCreator_IntegerVectorParameter_ActualNameChanged);

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

@@ -97 +97 @@
     <Compile Include="GeneralizedQuadraticAssignmentProblem.cs" />
     <Compile Include="GQAPAssignmentArchive.cs" />
-    <Compile Include="GQAPIntegerVectorProximityCalculator.cs" />
     <Compile Include="GQAPSolution.cs" />
     <Compile Include="Interfaces\IQualitiesAwareGQAPOperator.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/DemandEquivalentSwapEquipmentManipluator.cs

@@ -79 +79 @@
           assignment[equipment2] = location1;
           groupedLocations[location2].Remove(equipment2);
-          bool selected;
-          equipment2 = groupedLocations[location2].ChooseRandomOrDefault(random, out selected);
-          if (!selected) break;
+          if (!groupedLocations[location2].Any()) break;
+          equipment2 = groupedLocations[location2].ChooseUniformRandom(random);
         }
       }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GQAPPathRelinking.cs

@@ -73 +73 @@
     public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
       get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
+    }
+
+    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
+      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
     }
 
@@ -92 +96 @@
       Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
       Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
+      Parameters.Add(new ValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path-relinking 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)));
     }
 
@@ -98 +103 @@
     }
 
-    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, ItemArray<DoubleValue> qualities, DoubleArray demands,
-      DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleValue transportationCosts,
-      DoubleValue overbookedCapacityPenalty) {
+    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, BoolValue maximization, ItemArray<DoubleValue> qualities,
+      ItemArray<DoubleValue> flowDistanceQualities, ItemArray<DoubleValue> installationQualities, ItemArray<DoubleValue> overbookedCapacities,
+      DoubleArray demands, DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
+      DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty, DoubleValue candidateSizeFactor) {
       if (random == null) throw new ArgumentNullException("random", "No IRandom provider is given.");
       if (parents == null || !parents.Any()) throw new ArgumentException("No parents given for path relinking.", "parents");
@@ -110 +116 @@
       var source = parents[0];
       var target = parents[1];
-
-      var nu = 1.0;
+      IntegerVector result;
+      double resultQuality, resultFDQ, resultIQ, resultOC;
+
+      int betterParent = 1;
+      if ((maximization.Value && qualities[0].Value >= qualities[1].Value)
+        || (!maximization.Value && qualities[0].Value <= qualities[1].Value))
+        betterParent = 0;
+
+      result = (IntegerVector)parents[betterParent].Clone();
+      resultQuality = qualities[betterParent].Value;
+      resultFDQ = flowDistanceQualities[betterParent].Value;
+      resultIQ = installationQualities[betterParent].Value;
+      resultOC = overbookedCapacities[betterParent].Value;
+
       var pi_prime = (IntegerVector)source.Clone();
       var fix = new HashSet<int>();
       var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
-      var phi = new HashSet<int>(GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target));
+      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
 
       while (phi.Any()) {
-        var B = new HashSet<GQAPSolution>(new GQAPSolutionStructuralEqualityComparer());
+        var B = new List<GQAPSolution>();
         foreach (var v in phi) {
+          int oldLocation = pi_prime[v];
           pi_prime[v] = target[v];
-          var pi2 = makeFeasible(pi_prime, v);
-
-          double flowDistanceQuality, installationQuality, overbookedCapacity;
+          var pi2 = makeFeasible(random, pi_prime, v, nonFix, demands, capacities);
+          pi_prime[v] = oldLocation;
+
+          double currentFDQ, currentIQ, currentOC;
           GQAPEvaluator.Evaluate(pi2, weights, distances, installationCosts, demands, capacities,
-            out flowDistanceQuality, out installationQuality, out overbookedCapacity);
-
-          if (overbookedCapacity <= 0.0) {
-            var quality = GQAPEvaluator.GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity,
+            out currentFDQ, out currentIQ, out currentOC);
+
+          if (currentOC <= 0.0) {
+            var quality = GQAPEvaluator.GetCombinedQuality(currentFDQ, currentIQ, currentOC,
                 transportationCosts.Value, overbookedCapacityPenalty.Value);
-            var solution = new GQAPSolution(pi2, new DoubleValue(quality), new DoubleValue(flowDistanceQuality), new DoubleValue(installationQuality), new DoubleValue(overbookedCapacity));
-            if (B.Count >= nu * phi.Count) {
-              if (!B.Contains(solution) && quality <= B.Select(x => x.Quality.Value).Max()) {
-                // TODO: replace most similar element in B with worse cost
+            var solution = new GQAPSolution(pi2, new DoubleValue(quality), new DoubleValue(currentFDQ),
+              new DoubleValue(currentIQ), new DoubleValue(currentOC));
+            if (B.Count >= candidateSizeFactor.Value * phi.Count) {
+              int mostSimilarIndex = -1;
+              double mostSimilarValue = 1.0;
+              for (int i = 0; i < B.Count; i++) {
+                if (IsBetter(maximization.Value, solution.Quality.Value, B[i].Quality.Value)) {
+                  var similarity = IntegerVectorEqualityComparer.GetSimilarity(solution.Assignment, B[i].Assignment);
+                  if (similarity == 1.0) {
+                    mostSimilarIndex = -1;
+                    break;
+                  } else if (similarity < mostSimilarValue) {
+                    mostSimilarValue = similarity;
+                    mostSimilarIndex = i;
+                  }
+                }
               }
-            } else if (!B.Contains(solution)) {
-              B.Add(solution);
+              if (mostSimilarIndex >= 0)
+                B[mostSimilarIndex] = solution;
+            } else {
+              bool contains = false;
+              foreach (var b in B) {
+                if (!IntegerVectorEqualityComparer.GetDifferingIndices(solution.Assignment, b.Assignment).Any()) {
+                  contains = true;
+                  break;
+                }
+              }
+              if (!contains) B.Add(solution);
             }
           }
         }
         if (B.Any()) {
-          var pi = B.ChooseRandom(random);
-          var diff = GQAPIntegerVectorProximityCalculator.GetDifference(pi.Assignment, target);
-          var I = phi.Except(phi.Intersect(diff));
-          var i = I.ChooseRandom(random);
+          GQAPSolution pi;
+          if (maximization.Value) pi = B.ChooseProportionalRandom(random, 1, x => x.Quality.Value, false, true).First();
+          else pi = B.ChooseProportionalRandom(random, 1, x => 1.0 / x.Quality.Value, false, true).First();
+          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target);
+          var I = phi.Except(diff);
+          var i = I.ChooseUniformRandom(random);
           fix.Add(i);
           nonFix.Remove(i);
           pi_prime = pi.Assignment;
-          // TODO
-        }
+          if (IsBetter(maximization.Value, pi.Quality.Value, resultQuality)) {
+            result = pi.Assignment;
+            resultQuality = pi.Quality.Value;
+            resultFDQ = pi.FlowDistanceQuality.Value;
+            resultIQ = pi.InstallationQuality.Value;
+            resultOC = pi.OverbookedCapacity.Value;
+          }
+        } else return result;
+        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
       }
 
-      return pi_prime;
+      return result;
     }
 
     protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents) {
-      return Apply(random, parents, QualityParameter.ActualValue, DemandsParameter.ActualValue,
+      return Apply(random, parents, MaximizationParameter.ActualValue, QualityParameter.ActualValue, FlowDistanceQualityParameter.ActualValue,
+        InstallationQualityParameter.ActualValue, OverbookedCapacityParameter.ActualValue, DemandsParameter.ActualValue,
         CapacitiesParameter.ActualValue, WeightsParameter.ActualValue, DistancesParameter.ActualValue,
         InstallationCostsParameter.ActualValue, TransportationCostsParameter.ActualValue,
-        OverbookedCapacityPenaltyParameter.ActualValue);
-    }
-
-    private static IntegerVector makeFeasible(IntegerVector assignment, int equipment) {
-      // TODO: implement
-      return assignment;
+        OverbookedCapacityPenaltyParameter.ActualValue, CandidateSizeFactorParameter.Value);
+    }
+
+    private static IntegerVector makeFeasible(IRandom random, IntegerVector assignment, int equipment, HashSet<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
+      int l = assignment[equipment];
+      var slack = ComputeSlack(assignment, demands, capacities);
+      if (slack[l] >= 0) return (IntegerVector)assignment.Clone();
+
+      IntegerVector result = null;
+      int k = 0;
+      while (k < maximumTries && slack[l] < 0) {
+        result = (IntegerVector)assignment.Clone();
+        do {
+          var maxSlack = slack.Max();
+          var T = nonFix.Where(x => x != equipment && assignment[x] == l && demands[x] <= maxSlack);
+          if (T.Any()) {
+            int i = T.ChooseProportionalRandom(random, 1, x => demands[x], false, true).First();
+            var j = Enumerable.Range(0, capacities.Length).Where(x => slack[x] >= demands[i]).ChooseUniformRandom(random);
+            result[i] = j;
+            slack[j] -= demands[i];
+            slack[l] += demands[i];
+          } else break;
+        } while (slack[l] < 0);
+        k++;
+      }
+      return result;
+    }
+
+    private static DoubleArray ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
+      var slack = (DoubleArray)capacities.Clone();
+      for (int i = 0; i < assignment.Length; i++) {
+        slack[assignment[i]] -= demands[i];
+      }
+      return slack;
+    }
+
+    private static bool IsBetter(bool maximization, double quality, double otherQuality) {
+      return maximization && quality > otherQuality || !maximization && quality < otherQuality;
     }
   }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GreedyRandomizedSolutionCreator.cs

@@ -70 +70 @@
         do {
           if (L.Any() && random.NextDouble() < threshold) {
-            int l = L.ChooseRandom(random);
+            int l = L.ChooseUniformRandom(random);
             L.Remove(l);
             CL.Add(l);
@@ -76 +76 @@
           }
           if (T.Any()) {
-            int f = T.ChooseRandom(random);
+            int f = T.ChooseUniformRandom(random);
             T.Remove(f);
             F.Remove(f);
             CF.Add(f);
-            int l = WithSlackGreaterOrEqual(CL, demands[f], slack).ChooseRandom(random);
+            int l = WithSlackGreaterOrEqual(CL, demands[f], slack).ChooseUniformRandom(random);
             assignment.Add(f, l);
             slack[l] -= demands[f];

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/QualitySimilarityMerger.cs

@@ -94 +94 @@
 
       foreach (var candidate in candidates) {
-        double[] similarities = population.Select(x => GQAPIntegerVectorProximityCalculator.CalculateGenotypeSimilarity(x.Solution, candidate.Solution)).ToArray();
+        double[] similarities = population.Select(x => IntegerVectorEqualityComparer.GetSimilarity(x.Solution, candidate.Solution)).ToArray();
         if (!similarities.Any()) {
           population.Add(candidate);

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/RelocateEquipmentManipluator.cs

@@ -72 +72 @@
       }
 
-      bool selected;
-      var overstuffedLocation = usedCapacities.Where(x => capacities[x.Key] < x.Value).ChooseRandomOrDefault(random, out selected);
-      if (selected) {
-        int equipment = groupedLocations[overstuffedLocation.Key].ChooseRandomOrDefault(random, out selected);
-        var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value).ToList();
-        var location = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipment]).ChooseRandomOrDefault(random, out selected);
-        if (selected) {
-          assignment[equipment] = location.Key;
-        } else {
-          location = freeLocations.ChooseRandomOrDefault(random, out selected);
-          if (selected) assignment[equipment] = location.Key;
-          else assignment[equipment] = random.Next(locations);
-        }
-      } else {
+      var overbookedLocations = usedCapacities.Where(x => capacities[x.Key] < x.Value);
+      var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value);
+      if (!overbookedLocations.Any() || !freeLocations.Any()) { // perform a random relocation
         assignment[random.Next(assignment.Length)] = random.Next(locations);
+        return;
+      }
+
+      var sourceLocation = overbookedLocations.ChooseUniformRandom(random);
+      int equipmentToRelocate = groupedLocations[sourceLocation.Key].ChooseUniformRandom(random);
+      var bestFreeLocations = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipmentToRelocate]);
+
+      if (bestFreeLocations.Any()) { // a feasible solution will still be feasible, an infeasible solution might become feasible
+        var selected = bestFreeLocations.ChooseUniformRandom(random);
+        assignment[equipmentToRelocate] = sourceLocation.Key;
+      } else { // the solution will become infeasible
+        sourceLocation = freeLocations.ChooseUniformRandom(random);
+        assignment[equipmentToRelocate] = sourceLocation.Key;
       }
     }