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

Timestamp:

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

Author:

abeham

Message:

#1614: finished checking the implementation against the paper

Location:

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

Files:

• Crossovers/GQAPPathRelinking.cs (modified) (4 diffs)
• LocalImprovers/ApproximateLocalSearch.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;
     }
 

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

@@ -31 +31 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 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("ApproximateLocalSearch", "The approximate local search 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]
@@ -105 +109 @@
 
       /// <summary>
-      /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
-      /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
-      /// the maxItr parameter defined by Mateus et al.
       /// </summary>
       /// <param name="random">The random number generator to use.</param>
@@ -127 +128 @@
       var evaluations = 0.0;
       var deltaEvaluationFactor = 1.0 / assignment.Length;
-      while (true) {
-        int count = 0;
-        var CLS = new List<Tuple<NMove, double, Evaluation>>();
-        double sum = 0.0;
+      var greedy = true; // greedy selection performed better in 5 of 8 instances according to the paper
+      while (true) { // line 1 of Algorithm 3
+        var count = 0; // line 2 of Algorithm 3
+        var CLS = new List<Tuple<NMove, double, Evaluation>>(); // line 3 of Algorithm 3
         do {
-          NMove move;
-          if (random.NextDouble() < oneMoveProbability)
-            move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(random, assignment, capacities);
-          else move = StochasticNMoveSingleMoveGenerator.GenerateTwoMove(random, assignment, capacities);
-          
+          var move = Move(random, assignment, oneMoveProbability, capacities); // line 4 of Algorithm 3
+
           var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
           evaluations += move.Indices.Count * deltaEvaluationFactor;
           double moveQuality = problemInstance.ToSingleObjective(moveEval);
 
-          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) {
-            CLS.Add(Tuple.Create(move, moveQuality, moveEval));
-            sum += 1.0 / moveQuality;
+          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) { // line 5 of Algorithm 3
+            CLS.Add(Tuple.Create(move, moveQuality, moveEval)); // line 6 of Algorithm 3
           }
-          count++;
-        } while (CLS.Count < maxCLS && count < maximumIterations);
+          count++; // line 8 of Algorithm 3
+        } while (CLS.Count < maxCLS && count < maximumIterations); // line 9 of Algorithm 3
 
-        if (CLS.Count == 0) {
+        if (CLS.Count == 0) { // line 10 of Algorithm 3
           evaluatedSolutions += (int)Math.Ceiling(evaluations);
           return; // END
         } else {
-          var ball = random.NextDouble() * sum;
-          var selected = CLS.Last();
-          foreach (var candidate in CLS) {
-            ball -= 1.0 / candidate.Item2;
-            if (ball <= 0.0) {
-              selected = candidate;
-              break;
-            }
+          // line 11 of Algorithm 3
+          Tuple<NMove, double, Evaluation> selected;
+          if (greedy) {
+            selected = CLS.MinItems(x => x.Item2).Shuffle(random).First();
+          } else {
+            selected = CLS.SampleProportional(random, 1, CLS.Select(x => 1.0 / x.Item2), false, false).Single();
           }
           NMoveMaker.Apply(assignment, selected.Item1);
@@ -166 +161 @@
         }
       }
+    }
+
+    private static NMove Move(IRandom random, IntegerVector assignment, double oneMoveProbability, DoubleArray capacities) {
+      if (random.NextDouble() < oneMoveProbability)
+        return StochasticNMoveSingleMoveGenerator.GenerateOneMove(random, assignment, capacities);
+      return StochasticNMoveSingleMoveGenerator.GenerateTwoMove(random, assignment, capacities);
     }