Changeset 7425

Timestamp:

01/27/12 18:41:01 (12 years ago)

Author:

abeham

Message:

#1614

• worked on path relinking

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• GQAPSolutionStructuralEqualityComparer.cs (added)
• Operators/GQAPPathRelinking.cs (modified) (3 diffs)

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

@@ -29 +29 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
 
-namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
+namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
   [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
   [StorableClass]
@@ -110 +111 @@
       var target = parents[1];
 
+      var nu = 1.0;
       var pi_prime = (IntegerVector)source.Clone();
       var fix = new HashSet<int>();
       var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
-      var phi = GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target);
+      var phi = new HashSet<int>(GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target));
 
       while (phi.Any()) {
-        var B = new HashSet<IntegerVector>();
+        var B = new HashSet<GQAPSolution>(new GQAPSolutionStructuralEqualityComparer());
         foreach (var v in phi) {
           pi_prime[v] = target[v];
@@ -124 +126 @@
           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,
+                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
+              }
+            } else if (!B.Contains(solution)) {
+              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);
+          fix.Add(i);
+          nonFix.Remove(i);
+          pi_prime = pi.Assignment;
+          // TODO
         }
       }