Changeset 15533 for branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs

Timestamp:

12/18/17 14:38:18 (7 years ago)

Author:

ddorfmei

Message:

#2747: Improved hard-coded genetic algorithm

• implemented restart strategy
• implemented 1-Opt algorithm
• added parameters to control restart strategy and optimal assignment strategy
• additional results: best solution found after number of generations, jobs/nests (for evaluation only)

File:

• branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs (modified) (12 diffs)

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs

@@ -35 +35 @@
 
 namespace HeuristicLab.Problems.Scheduling.CFSAP {
+  public enum OptimalAssignmentType { None, Polynomial, OneOpt, Both };
+
   [Item("Genetic Algorithm (CFSAP)", "")]
   [StorableClass]
@@ -79 +81 @@
       get { return pauseAfterGenerationParameter; }
     }
+    [Storable]
+    private IFixedValueParameter<EnumValue<OptimalAssignmentType>> optimalAssignmentParameter;
+    public IFixedValueParameter<EnumValue<OptimalAssignmentType>> OptimalAssignmentParameter {
+      get { return optimalAssignmentParameter; }
+    }
 
     public int PopulationSize {
@@ -103 +110 @@
       get { return pauseAfterGenerationParameter.Value.Value; }
       set { pauseAfterGenerationParameter.Value.Value = value; }
+    }
+    public OptimalAssignmentType OptimalAssignment {
+      get { return optimalAssignmentParameter.Value.Value; }
+      set { optimalAssignmentParameter.Value.Value = value; }
     }
 
@@ -115 +126 @@
       maximumEvaluatedSolutionsParameter = cloner.Clone(original.maximumEvaluatedSolutionsParameter);
       pauseAfterGenerationParameter = cloner.Clone(original.pauseAfterGenerationParameter);
+      optimalAssignmentParameter = cloner.Clone(original.optimalAssignmentParameter);
+
       generation = original.generation;
       evaluatedSolutions = original.evaluatedSolutions;
       bestQuality = original.bestQuality;
+
       if (original.population != null)
         population = original.population.Select(cloner.Clone).ToArray();
@@ -126 +140 @@
     }
     public GeneticAlgorithm() {
-      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("PopulationSize", "The size of the population, each individual of the population is a solution with a permutation and a binary vector.", new IntValue(100)));
+      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("PopulationSize", "The size of the population, each individual of the population is a solution with a permutation and a binary vector.", new IntValue(500)));
       Parameters.Add(elitesParameter = new FixedValueParameter<IntValue>("Elites", "The number of best individuals from the previous population that will continue to the next generation.", new IntValue(1)));
       Parameters.Add(mutationProbabilityParameter = new FixedValueParameter<PercentValue>("MutationProbability", "The probability that an individual should be mutated after it has been created through crossover.", new PercentValue(0.05)));
@@ -132 +146 @@
       Parameters.Add(maximumEvaluatedSolutionsParameter = new FixedValueParameter<IntValue>("MaximumEvaluatedSolutions", "The number of evaluated solutions before the algorithm terminates.", new IntValue(100000000)));
       Parameters.Add(pauseAfterGenerationParameter = new FixedValueParameter<BoolValue>("PauseAfterGeneration", "Whether the algorithm should pause after each generation.", new BoolValue(true)));
+      Parameters.Add(optimalAssignmentParameter = new FixedValueParameter<EnumValue<OptimalAssignmentType>>("OptimalAssignment", "Which optimal assignment strategy should be used.", new EnumValue<OptimalAssignmentType>(OptimalAssignmentType.Polynomial)));
     }
 
@@ -194 +209 @@
             Assignment = CrossAssignment(parent1.Assignment, parent2.Assignment)
           };
+
           var mutProb = random.NextDouble();
           if (mutProb < MutationProbability) {
@@ -199 +215 @@
             MutateAssignment(nextGeneration[p].Assignment);
           }
+
           nextGeneration[p].Quality = Problem.Evaluate(nextGeneration[p].Sequence, nextGeneration[p].Assignment);
           evaluatedSolutions++;
 
           if (nextGeneration[p].Quality <= bestQuality) {
-            if (!optimalSequences.Contains(nextGeneration[p].Sequence)) {
-              int cycleTime;
-              var assignment = OptimalAssignment.MakeAssignment(nextGeneration[p].Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out cycleTime);
-              evaluatedSolutions++;
-              nextGeneration[p].Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
-              nextGeneration[p].Quality = cycleTime;
-              optimalSequences.Add(nextGeneration[p].Sequence);
+            switch (OptimalAssignment) {
+              case OptimalAssignmentType.None:
+                break;
+              case OptimalAssignmentType.Polynomial:
+                OptimalPolynomialAssignment(nextGeneration[p]);
+                break;
+              case OptimalAssignmentType.OneOpt:
+                OneOptAssignment(nextGeneration[p]);
+                break;
+              case OptimalAssignmentType.Both:
+                HybridAssignment(nextGeneration[p]);
+                break;
+              default:
+                throw new InvalidOperationException("Optimal assignment strategy not defined.");
             }
-            if (nextGeneration[p].Quality < bestQuality) {
+
+          if (nextGeneration[p].Quality < bestQuality) {
               bestQuality = nextGeneration[p].Quality;
               ((DoubleValue)Results["BestQuality"].Value).Value = bestQuality;
@@ -232 +257 @@
           break;
         }
+      }
+    }
+
+    private void OptimalPolynomialAssignment(EncodedSolution generation) {
+      if (!optimalSequences.Contains(generation.Sequence)) {
+        var assignment = Scheduling.CFSAP.OptimalPolynomialAssignment.MakeAssignment(generation.Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
+        evaluatedSolutions++;
+        generation.Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
+        generation.Quality = cycleTime;
+        optimalSequences.Add(generation.Sequence);
+      }
+    }
+
+    private void OneOptAssignment(EncodedSolution generation) {
+      var assignment = Scheduling.CFSAP.OneOptAssignment.MakeAssignment(generation.Sequence, generation.Assignment, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
+      evaluatedSolutions++;
+      generation.Assignment = assignment;
+      generation.Quality = cycleTime;
+    }
+
+    private void HybridAssignment(EncodedSolution generation) {
+      var a = random.Next(2);
+      switch (a) {
+        case 0: OptimalPolynomialAssignment(generation); break;
+        case 1: OneOptAssignment(generation); break;
+        default: throw new InvalidOperationException("Assignment not defined.");
       }
     }
@@ -257 +308 @@
 
     private void MutateSequence(Permutation sequence) {
-      var cx = random.Next(7);
-      switch (cx) {
+      var m = random.Next(7);
+      switch (m) {
         case 0: InversionManipulator.Apply(random, sequence); break;
         case 1: InsertionManipulator.Apply(random, sequence); break;
@@ -266 +317 @@
         case 5: TranslocationInversionManipulator.Apply(random, sequence); break;
         case 6: ScrambleManipulator.Apply(random, sequence); break;
-        default: throw new InvalidOperationException("Crossover not defined.");
+        default: throw new InvalidOperationException("Manipulator not defined.");
       }
     }
@@ -284 +335 @@
     }
 
-    private class EncodedSolution : IDeepCloneable, IComparable<EncodedSolution> {
+    [StorableClass]
+    private class EncodedSolution : DeepCloneable, IComparable<EncodedSolution> {
+      [Storable]
       public Permutation Sequence { get; set; }
+      [Storable]
       public BinaryVector Assignment { get; set; }
+      [Storable]
       public double Quality { get; set; }
 
-      public IDeepCloneable Clone(Cloner cloner) {
-        return new EncodedSolution() {
-          Sequence = cloner.Clone(this.Sequence),
-          Assignment = cloner.Clone(this.Assignment),
-          Quality = this.Quality
-        };
-      }
-
-      public object Clone() {
-        return Clone(new Cloner());
+      [StorableConstructor]
+      private EncodedSolution(bool deserializing) { }
+
+      private EncodedSolution(EncodedSolution original, Cloner cloner) : base(original, cloner) {
+        Sequence = cloner.Clone(original.Sequence);
+        Assignment = cloner.Clone(original.Assignment);
+        Quality = original.Quality;
+      }
+
+      public EncodedSolution() { }
+
+      public override IDeepCloneable Clone(Cloner cloner) {
+        return new EncodedSolution(this, cloner);
       }