Changeset 15572 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs

Timestamp:

01/03/18 00:28:51 (7 years ago)

Author:

abeham

Message:

#1614:

• fixed a bug in GRASP where solutions in the elite set would be mutated
• introduced termination criteria when reaching best-known quality
• tweaked generating random numbers in StochasticNMoveSingleMoveGenerator
• changed DiscreteLocationCrossover to use an allele from one of the parents instead of introducing a mutation in case no feasible insert location is found
• changed OSGA maxselpress to 500
• slight change to contexts, introduced single-objectiveness much earlier in the class hierachy
  • limited ContextAlgorithm to SingleObjectiveBasicProblems (doesn't matter here)

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs (modified) (4 diffs)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs

@@ -36 +36 @@
   /// 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>
+  /// <remarks>
+  /// A fine distinction to the described algorithm is that newly found best solutions are always accepted into the elite set. This is reasonable, but not mentioned in the paper by Mateus et al.
+  /// </remarks>
   [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as 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.")]
   [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
   [StorableClass]
-  public sealed class GRASP : StochasticAlgorithm<GRASPContext> {
+  public sealed class GRASP : StochasticAlgorithm<GRASPContext, IntegerVectorEncoding> {
 
     public override bool SupportsPause {
@@ -175 +178 @@
           GQAPSolution pi_prime;
           if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
-            pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1
+            pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1
           else {
             // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
@@ -188 +191 @@
           var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
           // Book-keeping
-          if (Context.BestQuality > fitness) {
+          var newBest = Context.BestQuality > fitness;
+          if (newBest) {
             Context.BestQuality = fitness;
             Context.BestSolution = (GQAPSolution)pi_prime.Clone();
@@ -194 +198 @@
 
           if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
-            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
             double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
-            if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
-              var replacement = Context.Population.Select((v, i) => new { V = v, Index = i })
-                                          .Where(x => x.V.Fitness >= fit).ToArray();
-              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
-                // next two lines: line 14 in Algorithm 1
-                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
-                Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
+            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
+            // in this implementation a new best solution is always accepted into the elite set
+            if (newBest || similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
+              var replacement = Context.Population.Select((v, i) => new { Scope = v, Index = i })
+                                          .Where(x => x.Scope.Fitness >= fitness) // cond. 1 of line 13 in Algorithm 1
+                                          .OrderByDescending(x => similarities[x.Index]) // line 14 in Algorithm 1
+                                          .FirstOrDefault();
+              if (replacement != null) { 
+                Context.ReplaceAtPopulation(replacement.Index, Context.ToScope(pi_prime, fitness)); // line 14 in Algorithm 1
               }
             }
-          } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
+            // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference
+            // in this implementation a new best solution is always accepted into the elite set
+          } else if (newBest || IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
             Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
           }