Changeset 15558 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3

Timestamp:

12/22/17 01:32:13 (6 years ago)

Author:

abeham

Message:

#1614: fixed bugs

Location:

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

Files:

• GRASP.cs (modified) (9 diffs)
• GRASPContext.cs (modified) (2 diffs)

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

@@ -108 +108 @@
     }
     [Storable]
-    private FixedValueParameter<PercentValue> minimumDifferenceParameter;
-    public IFixedValueParameter<PercentValue> MinimumDifferenceParameter {
+    private FixedValueParameter<IntValue> minimumDifferenceParameter;
+    public IFixedValueParameter<IntValue> MinimumDifferenceParameter {
       get { return minimumDifferenceParameter; }
     }
@@ -121 +121 @@
       set { seedParameter.Value.Value = value; }
     }
+    public int EliteSetSize {
+      get { return eliteSetSizeParameter.Value.Value; }
+      set { eliteSetSizeParameter.Value.Value = value; }
+    }
     public int MinimumEliteSetSize {
       get { return minimiumEliteSetSizeParameter.Value.Value; }
       set { minimiumEliteSetSizeParameter.Value.Value = value; }
     }
-    public int EliteSetSize {
-      get { return eliteSetSizeParameter.Value.Value; }
-      set { eliteSetSizeParameter.Value.Value = value; }
+    public int MaximumIterations {
+      get { return maximumIterationsParameter.Value.Value; }
+      set { maximumIterationsParameter.Value.Value = value; }
+    }
+    public int MaximumLocalSearchIterations {
+      get { return maximumLocalSearchIterationsParameter.Value.Value; }
+      set { maximumLocalSearchIterationsParameter.Value.Value = value; }
     }
     public double CandidateSizeFactor {
@@ -141 +149 @@
       set { oneMoveProbabilityParameter.Value.Value = value; }
     }
-    public double MinimumDifference {
+    public int MinimumDifference {
       get { return minimumDifferenceParameter.Value.Value; }
       set { minimumDifferenceParameter.Value.Value = value; }
@@ -174 +182 @@
       Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
       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<PercentValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new PercentValue(1e-7)));
+      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();
     }
@@ -252 +260 @@
             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) { // cond. 2 of line 13 in Algorithm 1
+            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();
@@ -277 +285 @@
         }
 
-        context.Iterations++;
-
         IResult result;
         if (Results.TryGetValue("Iterations", out result))
@@ -294 +300 @@
 
         context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
+
+        context.Iterations++;
       }
     }
@@ -299 +307 @@
     private bool IsSufficientlyDifferent(IntegerVector vec) {
       return context.Population.All(x =>
-        HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, vec) <= 1.0 - MinimumDifference
+        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
       );
     }
@@ -329 +337 @@
       var localSearchEvaluations = 0;
       ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
-        OneMoveProbability, 1000, Problem.ProblemInstance, out localSearchEvaluations);
+        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
       context.EvaluatedSolutions += localSearchEvaluations;
     }
 
     private bool StoppingCriterion() {
-      return context.Iterations > MaximumIterationsParameter.Value.Value;
+      return context.Iterations > MaximumIterations;
     }
   }

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

@@ -174 +174 @@
       scope.Variables.Add(new Variable("Evaluation", code.Evaluation));
       return scope;
-    }
-
-    public double Evaluate(GQAPSolution solution, CancellationToken token) {
-      var solScope = ToScope(solution);
-      Evaluate(solScope, token);
-      return solScope.Fitness;
-    }
-
-    public void Evaluate(ISingleObjectiveSolutionScope<GQAPSolution> solScope, CancellationToken token) {
-      var pdef = Problem as ISingleObjectiveProblemDefinition;
-      if (pdef != null) {
-        var ind = new SingleEncodingIndividual(pdef.Encoding, solScope);
-        solScope.Fitness = pdef.Evaluate(ind, Random);
-      } else {
-        RunOperator(Problem.Evaluator, solScope, token);
-      }
-    }
-
-    public GRASPSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<GQAPSolution> solution) {
-      return new GRASPSolutionContext(this, solution);
     }
 
@@ -274 +254 @@
     #endregion
   }
-
-  [Item("GRASP+PR (GQAP) SolutionContext", "SolutionContext for GRASP+PR (GQAP).")]
-  [StorableClass]
-  public sealed class GRASPSolutionContext : ParameterizedNamedItem, IExecutionContext {
-
-    private GRASPContext parent;
-    public IExecutionContext Parent {
-      get { return parent; }
-      set { throw new InvalidOperationException("Cannot set the parent of a single-solution context."); }
-    }
-
-    [Storable]
-    private ISingleObjectiveSolutionScope<GQAPSolution> scope;
-    public IScope Scope {
-      get { return scope; }
-    }
-
-    IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {
-      get { return Parameters; }
-    }
-
-    public GQAP Problem {
-      get { return parent.Problem; }
-    }
-    public bool Maximization {
-      get { return parent.Maximization; }
-    }
-
-    public double BestQuality {
-      get { return parent.BestQuality; }
-      set { parent.BestQuality = value; }
-    }
-
-    public GQAPSolution BestSolution {
-      get { return parent.BestSolution; }
-      set { parent.BestSolution = value; }
-    }
-
-    public IRandom Random {
-      get { return parent.Random; }
-    }
-
-    [Storable]
-    private IValueParameter<IntValue> evaluatedSolutions;
-    public int EvaluatedSolutions {
-      get { return evaluatedSolutions.Value.Value; }
-      set { evaluatedSolutions.Value.Value = value; }
-    }
-
-    [Storable]
-    private IValueParameter<IntValue> iterations;
-    public int Iterations {
-      get { return iterations.Value.Value; }
-      set { iterations.Value.Value = value; }
-    }
-
-    [StorableConstructor]
-    private GRASPSolutionContext(bool deserializing) : base(deserializing) { }
-    private GRASPSolutionContext(GRASPSolutionContext original, Cloner cloner)
-      : base(original, cloner) {
-      scope = cloner.Clone(original.scope);
-      evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
-      iterations = cloner.Clone(original.iterations);
-    }
-    public GRASPSolutionContext(GRASPContext baseContext, ISingleObjectiveSolutionScope<GQAPSolution> solution) {
-      parent = baseContext;
-      scope = solution;
-
-      Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
-      Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));
-    }
-
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new GRASPSolutionContext(this, cloner);
-    }
-
-    public void IncrementEvaluatedSolutions(int byEvaluations) {
-      if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");
-      EvaluatedSolutions += byEvaluations;
-    }
-    public double Evaluate(GQAPSolution solution, CancellationToken token) {
-      return parent.Evaluate(solution, token);
-    }
-
-    public void Evaluate(ISingleObjectiveSolutionScope<GQAPSolution> solScope, CancellationToken token) {
-      parent.Evaluate(solScope, token);
-    }
-
-    #region IExecutionContext members
-    public IAtomicOperation CreateOperation(IOperator op) {
-      return new Core.ExecutionContext(this, op, Scope);
-    }
-
-    public IAtomicOperation CreateOperation(IOperator op, IScope s) {
-      return new Core.ExecutionContext(this, op, s);
-    }
-
-    public IAtomicOperation CreateChildOperation(IOperator op) {
-      return new Core.ExecutionContext(this, op, Scope);
-    }
-
-    public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {
-      return new Core.ExecutionContext(this, op, s);
-    }
-    #endregion
-  }
 }