Changeset 15564 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms

Timestamp:

01/01/18 23:52:39 (7 years ago)

Author:

abeham

Message:

#1614:

• Fixed some bugs
• Added OSGA
• Updated ES (added recombination)
• Reusing operators among algorihtms (RelocateEquipmentManipluator)
• Rewrote DiscreteLocationCrossover

Location:

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

Files:

• Evolutionary/ESContext.cs (modified) (2 diffs)
• Evolutionary/EvolutionStrategy.cs (modified) (10 diffs)
• Evolutionary/OSGA.cs (added)
• Evolutionary/OSGAContext.cs (copied) (copied from branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASPContext.cs) (3 diffs)
• GRASP/GRASP.cs (modified) (2 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj (modified) (1 diff)
• Infrastructure/Contexts/PopulationContext.cs (modified) (1 diff)
• LAHC/LAHC.cs (modified) (1 diff)
• LAHC/pLAHC.cs (modified) (1 diff)
• LocalSearch/IteratedLS.cs (modified) (6 diffs)
• LocalSearch/MultistartLS.cs (modified) (1 diff)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/ESContext.cs

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -50 +49 @@
       get { return normalRand.Value; }
       set { normalRand.Value = value; }
-    }
-
-    public void ReplacePopulation(IEnumerable<ISingleObjectiveSolutionScope<ESGQAPSolution>> replacement) {
-      Scope.SubScopes.Replace(replacement);
     }
     

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs

@@ -69 +69 @@
       get { return selectionParameter; }
     }
+    [Storable]
+    private FixedValueParameter<BoolValue> useRecombinationParameter;
+    public IFixedValueParameter<BoolValue> UseRecombinationParameter {
+      get { return useRecombinationParameter; }
+    }
 
     public int Lambda {
@@ -81 +86 @@
       get { return selectionParameter.Value.Value; }
       set { selectionParameter.Value.Value = value; }
+    }
+    public bool UseRecombination {
+      get { return useRecombinationParameter.Value.Value; }
+      set { useRecombinationParameter.Value.Value = value; }
     }
 
@@ -90 +99 @@
       muParameter = cloner.Clone(original.muParameter);
       selectionParameter = cloner.Clone(original.selectionParameter);
+      useRecombinationParameter = cloner.Clone(original.useRecombinationParameter);
     }
     public EvolutionStrategy() {
@@ -95 +105 @@
       Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
       Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
-      
+      Parameters.Add(useRecombinationParameter = new FixedValueParameter<BoolValue>("Use Recombination", "Whether to create an \"intermediate\" solution to perform the mutation from.", new BoolValue(false)));
+
       Problem = new GQAP();
     }
@@ -116 +127 @@
         Context.EvaluatedSolutions++;
 
-        var ind = new ESGQAPSolution(assign, eval, Context.Random.NextDouble() * 2 - 1);
+        var min = (1.0 / assign.Length) * 2 - 1; // desired min prob
+        var max = (4.0 / assign.Length) * 2 - 1; // desired max prob
+        min = 0.5 * (Math.Log(1 + min) - Math.Log(1 - min)); // arctanh
+        max = 0.5 * (Math.Log(1 + max) - Math.Log(1 - max));
+        var ind = new ESGQAPSolution(assign, eval, min + Context.Random.NextDouble() * (max - min));
         var fit = Problem.ProblemInstance.ToSingleObjective(eval);
         Context.AddToPopulation(Context.ToScope(ind, fit));
@@ -135 +150 @@
     protected override void Run(CancellationToken cancellationToken) {
       var lastUpdate = ExecutionTime;
+      var eq = new IntegerVectorEqualityComparer();
 
       while (!StoppingCriterion()) {
@@ -140 +156 @@
 
         for (var l = 0; l < Lambda; l++) {
-          var m = Context.AtRandomPopulation();
-
-          var offspring = (ESGQAPSolution)m.Solution.Clone();
-          var count = Mutate(m, offspring);
-          offspring.SParam += 0.7071 * Context.NormalRand.NextDouble(); //((1.0 / count) - offspring.SParam) / 10.0;
-
-          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
+          IntegerVector child = null;
+          var sParam = 0.0;
+          if (UseRecombination) {
+            child = DiscreteLocationCrossover.Apply(Context.Random, new ItemArray<IntegerVector>(Context.Population.Select(x => x.Solution.Assignment)), Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities);
+            sParam = Context.Population.Select(x => x.Solution.SParam).Average();
+          } else {
+            var m = Context.AtRandomPopulation();
+            child = (IntegerVector)m.Solution.Assignment.Clone();
+            sParam = m.Solution.SParam;
+          }
+          sParam += 0.7071 * Context.NormalRand.NextDouble();
+          RelocateEquipmentManipluator.Apply(Context.Random, child,
+            Problem.ProblemInstance.Capacities.Length, (Math.Tanh(sParam) + 1) / 2.0);
+          var eval = Problem.ProblemInstance.Evaluate(child);
           Context.EvaluatedSolutions++;
+
+          var offspring = new ESGQAPSolution(child, eval, sParam);
+
           var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
-          nextGen.Add(Context.ToScope(offspring, fit));
+          if (Selection == ESSelection.Comma || Context.Population.Select(x => x.Solution.Assignment).All(x => !eq.Equals(child, x)))
+            nextGen.Add(Context.ToScope(offspring, fit));
 
           if (fit < Context.BestQuality) {
@@ -160 +187 @@
           Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
         } else if (Selection == ESSelection.Plus) {
-          var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList();
+          var best = Context.Population.Concat(nextGen).OrderBy(x => x.Fitness).Take(Mu).ToList();
           Context.ReplacePopulation(best);
         } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
@@ -181 +208 @@
         else Results.Add(new Result("BestSolution", Context.BestSolution));
 
-        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        try {
+          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        } catch (OperationCanceledException) { }
 
         Context.Iterations++;
@@ -194 +223 @@
       else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     }
-
-    private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
-      var stopProb = (Math.Tanh(m.Solution.SParam) + 1) / 2.0; // squash strategy parameter to ]0;1[
-      var offspringFeasible = offspring.Evaluation.IsFeasible;
-      double[] slack = null;
-      if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
-      var count = 1;
-      foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
-        var currentLoc = offspring.Assignment[equip];
-        if (offspringFeasible) {
-          var demand = Problem.ProblemInstance.Demands[equip];
-          var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
-            .Where(x => x.Index != currentLoc
-            && x.Value >= demand).ToList();
-          int newLoc = -1;
-          if (feasibleLoc.Count == 0) {
-            newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
-            if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
-            offspringFeasible = false;
-          } else {
-            newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
-          }
-          offspring.Assignment[equip] = newLoc;
-          slack[currentLoc] += demand;
-          slack[newLoc] -= demand;
-        } else {
-          var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
-          if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
-          offspring.Assignment[equip] = newLoc;
-        }
-        if (Context.Random.NextDouble() < stopProb) break;
-        count++;
-      }
-
-      return count;
-    }
   }
 }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGAContext.cs

@@ -23 +23 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
-namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
-  [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")]
+namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
+  [Item("OSGA (GQAP) Context", "Context for OSGA (GQAP).")]
   [StorableClass]
-  public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
+  public sealed class OSGAContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     
     [Storable]
@@ -44 +45 @@
       set { bestSolution.Value = value; }
     }
-    
+
+    [Storable]
+    private IValueParameter<ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>> nextGeneration;
+    public ItemList<ISingleObjectiveSolutionScope<GQAPSolution>> NextGeneration {
+      get { return nextGeneration.Value; }
+      set { nextGeneration.Value = value; }
+    }
+
+    [Storable]
+    private IValueParameter<DoubleValue> selectionPressure;
+    public double SelectionPressure {
+      get { return selectionPressure.Value.Value; }
+      set { selectionPressure.Value.Value = value; }
+    }
+
+    [Storable]
+    private IValueParameter<IntValue> attempts;
+    public int Attempts {
+      get { return attempts.Value.Value; }
+      set { attempts.Value.Value = value; }
+    }
+
     public void SortPopulation() {
       Scope.SubScopes.Replace(Scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Problem.Maximization ? -x.Fitness : x.Fitness).ToList());
@@ -50 +72 @@
     
     [StorableConstructor]
-    private GRASPContext(bool deserializing) : base(deserializing) { }
-    private GRASPContext(GRASPContext original, Cloner cloner)
+    private OSGAContext(bool deserializing) : base(deserializing) { }
+    private OSGAContext(OSGAContext original, Cloner cloner)
       : base(original, cloner) {
       problem = cloner.Clone(original.problem);
       bestSolution = cloner.Clone(original.bestSolution);
+      nextGeneration = cloner.Clone(original.nextGeneration);
+      selectionPressure = cloner.Clone(original.selectionPressure);
+      attempts = cloner.Clone(original.attempts);
     }
-    public GRASPContext() : this("GRASP+PR (GQAP) Context") { }
-    public GRASPContext(string name) : base(name) {
+    public OSGAContext() : this("OSGA (GQAP) Context") { }
+    public OSGAContext(string name) : base(name) {
       Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
       Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
+      Parameters.Add(nextGeneration = new ValueParameter<ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>>("NextGeneration"));
+      Parameters.Add(selectionPressure = new ValueParameter<DoubleValue>("SelectionPressure", new DoubleValue(0)));
+      Parameters.Add(attempts = new ValueParameter<IntValue>("Attempts", new IntValue(0)));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new GRASPContext(this, cloner);
+      return new OSGAContext(this, cloner);
     }
 

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

@@ -167 +167 @@
       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);
+        IntegerVector pi_prime_vec = null;
+        try {
+          pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
+        } catch (OperationCanceledException) { break; }
+
         if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
           GQAPSolution pi_prime;
@@ -234 +238 @@
         else Results.Add(new Result("BestSolution", Context.BestSolution));
 
-        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        try {
+          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        } catch (OperationCanceledException) { }
 
         Context.Iterations++;

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

@@ -102 +102 @@
     <Compile Include="Evolutionary\ESGQAPSolution.cs" />
     <Compile Include="Evolutionary\EvolutionStrategy.cs" />
+    <Compile Include="Evolutionary\OSGAContext.cs" />
+    <Compile Include="Evolutionary\OSGA.cs" />
     <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" />
     <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Contexts/PopulationContext.cs

@@ -40 +40 @@
       Scope.SubScopes[index] = solScope;
     }
+    public void ReplacePopulation(IEnumerable<TSolutionScope> replacement) {
+      Scope.SubScopes.Replace(replacement);
+    }
     public TSolutionScope AtPopulation(int index) {
       return Scope.SubScopes[index] as TSolutionScope;

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

@@ -156 +156 @@
         else Results.Add(new Result("BestSolution", Context.BestSolution));
 
-        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
-        
+        try {
+          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        } catch (OperationCanceledException) { }
+
         if (cancellationToken.IsCancellationRequested) break;
       }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHC.cs

@@ -187 +187 @@
             result.Value = Context.BestSolution;
           else Results.Add(new Result("BestSolution", Context.BestSolution));
-          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+
+          try {
+            Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+          } catch (OperationCanceledException) { }
 
           if (cancellationToken.IsCancellationRequested) break;

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/IteratedLS.cs

@@ -25 +25 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -48 +48 @@
     }
 
+    [Storable]
+    private IFixedValueParameter<PercentValue> perturbationStrengthParameter;
+    public IFixedValueParameter<PercentValue> PerturbationStrengthParameter {
+      get { return perturbationStrengthParameter; }
+    }
+
+    public double PerturbationStrength {
+      get { return perturbationStrengthParameter.Value.Value; }
+      set { perturbationStrengthParameter.Value.Value = value; }
+    }
+
     [StorableConstructor]
     private IteratedLS(bool deserializing) : base(deserializing) { }
@@ -54 +65 @@
     }
     public IteratedLS() {
+      Parameters.Add(perturbationStrengthParameter = new FixedValueParameter<PercentValue>("PerturbationStrength", "The expected length of the random walk relative to the size of the solution vector.", new PercentValue(0.5)));
 
       Problem = new GQAP();
@@ -97 +109 @@
         var lsevaluations = 0;
         var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();
-        RandomWalk(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, candidate.Assignment.Length);
+        RelocateEquipmentManipluator.Apply(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, 1.0 / (PerturbationStrength * candidate.Assignment.Length));
         candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);
         Context.EvaluatedSolutions++;
@@ -127 +139 @@
         else Results.Add(new Result("BestSolution", Context.BestSolution));
 
-        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        try {
+          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        } catch (OperationCanceledException) { }
 
         Context.Iterations++;
@@ -140 +154 @@
       else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     }
-
-    private static void RandomWalk(IRandom random, IntegerVector assignment, int locations, int walkLength) {
-      for (int i = 0; i < walkLength; i++) {
-        var equipment = random.Next(assignment.Length);
-        assignment[equipment] = random.Next(locations);
-        if (random.NextDouble() < 1.0 / walkLength) break;
-      }
-    }
   }
 }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/MultistartLS.cs

@@ -107 +107 @@
         else Results.Add(new Result("BestSolution", Context.BestSolution));
 
-        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        try {
+          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
+        } catch (OperationCanceledException) { }
 
         Context.Iterations++;