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

Timestamp:

12/29/17 23:56:43 (6 years ago)

Author:

abeham

Message:

#1614: added additional algorithms

Location:

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

Files:

• . (added)
• GRASP.cs (moved) (moved from branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP.cs) (15 diffs)

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

@@ -23 +23 @@
 using System.Linq;
 using System.Threading;
-using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -31 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
@@ -41 +39 @@
   [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
   [StorableClass]
-  public class GRASP : BasicAlgorithm {
+  public sealed class GRASP : StochasticAlgorithm<GRASPContext> {
 
     public override bool SupportsPause {
@@ -57 +55 @@
 
     [Storable]
-    private ValueParameter<IAnalyzer> analyzerParameter;
-    public IValueParameter<IAnalyzer> AnalyzerParameter {
-      get { return analyzerParameter; }
-    }
-
-    [Storable]
-    private FixedValueParameter<BoolValue> setSeedRandomlyParameter;
-    private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
-      get { return setSeedRandomlyParameter; }
-    }
-    [Storable]
-    private FixedValueParameter<IntValue> seedParameter;
-    private IFixedValueParameter<IntValue> SeedParameter {
-      get { return seedParameter; }
-    }
-    [Storable]
     private FixedValueParameter<IntValue> eliteSetSizeParameter;
     private IFixedValueParameter<IntValue> EliteSetSizeParameter {
@@ -83 +65 @@
     }
     [Storable]
-    private FixedValueParameter<IntValue> maximumIterationsParameter;
-    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
-      get { return maximumIterationsParameter; }
-    }
-    [Storable]
     private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
     public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
-      get { return maximumIterationsParameter; }
+      get { return maximumLocalSearchIterationsParameter; }
     }
     [Storable]
@@ -113 +90 @@
     }
     
-    public bool SetSeedRandomly {
-      get { return setSeedRandomlyParameter.Value.Value; }
-      set { setSeedRandomlyParameter.Value.Value = value; }
-    }
-    public int Seed {
-      get { return seedParameter.Value.Value; }
-      set { seedParameter.Value.Value = value; }
-    }
     public int EliteSetSize {
       get { return eliteSetSizeParameter.Value.Value; }
@@ -129 +98 @@
       set { minimiumEliteSetSizeParameter.Value.Value = value; }
     }
-    public int MaximumIterations {
-      get { return maximumIterationsParameter.Value.Value; }
-      set { maximumIterationsParameter.Value.Value = value; }
-    }
     public int MaximumLocalSearchIterations {
       get { return maximumLocalSearchIterationsParameter.Value.Value; }
@@ -155 +120 @@
 
     [StorableConstructor]
-    protected GRASP(bool deserializing) : base(deserializing) { }
-    protected GRASP(GRASP original, Cloner cloner)
+    private GRASP(bool deserializing) : base(deserializing) { }
+    private GRASP(GRASP original, Cloner cloner)
       : base(original, cloner) {
-      setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);
-      seedParameter = cloner.Clone(original.seedParameter);
-      analyzerParameter = cloner.Clone(original.analyzerParameter);
       eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
       minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
-      maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
       maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
       candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
@@ -169 +130 @@
       oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
       minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
-      context = cloner.Clone(original.context);
     }
     public GRASP() {
-      Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));
-      Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));
-      Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
       Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
       Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
-      Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));
       Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
       Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<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)));
@@ -183 +139 @@
       Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
       Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
+
       Problem = new GQAP();
     }
@@ -190 +147 @@
     }
 
-    public override void Prepare() {
-      base.Prepare();
-      Results.Clear();
-      context = null;
-    }
-
-    [Storable]
-    private GRASPContext context;
-
     protected override void Initialize(CancellationToken cancellationToken) {
       base.Initialize(cancellationToken);
-      context = new GRASPContext();
-      context.Problem = Problem;
-      context.Scope.Variables.Add(new Variable("Results", Results));
-
-      IExecutionContext ctxt = null;
-      foreach (var item in Problem.ExecutionContextItems)
-        ctxt = new Core.ExecutionContext(ctxt, item, context.Scope);
-      ctxt = new Core.ExecutionContext(ctxt, this, context.Scope);
-      context.Parent = ctxt;
-
-      if (SetSeedRandomly) {
-        var rnd = new System.Random();
-        Seed = rnd.Next();
-      }
-      context.Random = new MersenneTwister((uint)Seed);
-      context.Iterations = 0;
-      context.EvaluatedSolutions = 0;
-      context.BestQuality = double.NaN;
-      context.BestSolution = null;
-
-      context.Initialized = true;
-
-      Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
-      Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
-      Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
+
+      Context.Problem = Problem;      
+      Context.BestQuality = double.NaN;
+      Context.BestSolution = null;
+
+      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
+      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
+      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
       Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
 
-      context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
+      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     }
 
@@ -235 +166 @@
       while (!StoppingCriterion()) { // line 2 in Algorithm 1
         // next: line 3 in Algorithm 1
-        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
-        if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
+        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
+        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
           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 = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // 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
             pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
-            context.EvaluatedSolutions++;
+            Context.EvaluatedSolutions++;
           }
 
           ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
-          var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1
+          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
           pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
           ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
           var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
           // Book-keeping
-          if (context.BestQuality > fitness) {
-            context.BestQuality = fitness;
-            context.BestSolution = (GQAPSolution)pi_prime.Clone();
-          }
-
-          if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
+          if (Context.BestQuality > fitness) {
+            Context.BestQuality = fitness;
+            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
+          }
+
+          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();
+            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 })
+              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));
+                Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
               }
             }
           } else if (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
+            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
           }
         } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
           && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
           var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
-          context.EvaluatedSolutions++;
+          Context.EvaluatedSolutions++;
           var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
-          context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
+          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
           // Book-keeping
-          if (context.PopulationCount == 1 || context.BestQuality > fitness) {
-            context.BestQuality = fitness;
-            context.BestSolution = (GQAPSolution)pi_prime.Clone();
+          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
+            Context.BestQuality = fitness;
+            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
           }
         }
@@ -287 +218 @@
         IResult result;
         if (Results.TryGetValue("Iterations", out result))
-          ((IntValue)result.Value).Value = context.Iterations;
-        else Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
+          ((IntValue)result.Value).Value = Context.Iterations;
+        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
         if (Results.TryGetValue("EvaluatedSolutions", out result))
-          ((IntValue)result.Value).Value = context.EvaluatedSolutions;
-        else Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
+          ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
+        else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
         if (Results.TryGetValue("BestQuality", out result))
-          ((DoubleValue)result.Value).Value = context.BestQuality;
-        else Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
+          ((DoubleValue)result.Value).Value = Context.BestQuality;
+        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
         if (Results.TryGetValue("BestSolution", out result))
-          result.Value = context.BestSolution;
-        else Results.Add(new Result("BestSolution", context.BestSolution));
-
-        context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
-
-        context.Iterations++;
+          result.Value = Context.BestSolution;
+        else Results.Add(new Result("BestSolution", Context.BestSolution));
+
+        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+
+        Context.Iterations++;
+        if (cancellationToken.IsCancellationRequested) break;
       }
     }
 
     private bool IsSufficientlyDifferent(IntegerVector vec) {
-      return context.Population.All(x =>
+      return Context.Population.All(x =>
         HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
       );
@@ -327 +259 @@
       int evaluatedSolutions;
       // lines 2-36 of Algorithm 4 are implemented in the following call
-      var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval,
+      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
         target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
         out evaluatedSolutions);
-      context.EvaluatedSolutions += evaluatedSolutions;
+      Context.EvaluatedSolutions += evaluatedSolutions;
       return pi_star;
     }
@@ -336 +268 @@
     private void ApproxLocalSearch(GQAPSolution pi_prime) {
       var localSearchEvaluations = 0;
-      ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
+      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
         OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
-      context.EvaluatedSolutions += localSearchEvaluations;
-    }
-
-    private bool StoppingCriterion() {
-      return context.Iterations > MaximumIterations;
+      Context.EvaluatedSolutions += localSearchEvaluations;
     }
   }