Changeset 15555 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs

Timestamp:

12/20/17 23:35:23 (6 years ago)

Author:

abeham

Message:

#1614: finished checking the implementation against the paper

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs (modified) (4 diffs)

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

@@ -32 +32 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
+  /// <summary>
+  /// 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/s10732-010-9144-0
+  /// </summary>
   [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]
@@ -71 +74 @@
       var cmp = new IntegerVectorEqualityComparer();
 
+      var greedy = true; // greedy performed better according to the paper
       var sFit = problemInstance.ToSingleObjective(sourceEval);
       var tFit = problemInstance.ToSingleObjective(targetEval);
@@ -114 +118 @@
         }
         if (B.Count > 0) { // line 21 of Algorithm 4
-          var pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First(); // line 22 of Algorithm 4
+          GQAPSolution pi;
+          // line 22 of Algorithm 4
+          if (greedy) {
+            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;
+          } else {
+            pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
+          }
           var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
           var I = phi.Except(diff); // line 24 of Algorithm 4
@@ -126 +136 @@
             pi_star = pi; // line 30 of Algorithm 4
           }
-        } else return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
+        } else return pi_star;
         phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
       }
 
-      return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
+      return pi_star;
     }