Changeset 15533 for branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.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/MultiNestCFSAPSolvingStrategy.cs (modified) (10 diffs)

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

@@ -12 +12 @@
 
 namespace HeuristicLab.Problems.Scheduling.CFSAP {
-  [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instace to the worst nest.")]
+  [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instance to the worst nest.")]
   [StorableClass]
   [Creatable(CreatableAttribute.Categories.Algorithms)]
@@ -33 +33 @@
     }
 
-
     public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
       get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
+    }
+
+    public IValueParameter<BoolValue> RestartParameter {
+      get { return (IValueParameter<BoolValue>)Parameters["Restart"]; }
+    }
+
+    public IValueParameter<IntValue> MinTriesParameter {
+      get { return (IValueParameter<IntValue>)Parameters["Restart.MinTries"]; }
+    }
+
+    public IValueParameter<DoubleValue> LastSuccessPercentageParameter {
+      get { return (IValueParameter<DoubleValue>)Parameters["Restart.LastSuccessPercentage"]; }
     }
 
@@ -53 +64 @@
     }
 
+    public bool Restart {
+      get => RestartParameter.Value.Value;
+      set => RestartParameter.Value.Value = value;
+    }
+
+    public int MinTries {
+      get => MinTriesParameter.Value.Value;
+      set => MinTriesParameter.Value.Value = value;
+    }
+
+    public double LastSuccessPercentage {
+      get => LastSuccessPercentageParameter.Value.Value;
+      set => LastSuccessPercentageParameter.Value.Value = value;
+    }
+
     [StorableConstructor]
     protected MultiNestCFSAPSolvingStrategy(bool deserializing) : base(deserializing) { }
+
     protected MultiNestCFSAPSolvingStrategy(MultiNestCFSAPSolvingStrategy original, Cloner cloner)
       : base(original, cloner) {
@@ -67 +94 @@
       if (original.qualityPerEvaluations != null)
         qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
-    }
+
+      restart = original.restart;
+      minTries = original.minTries;
+      lastSuccessPercentage = original.lastSuccessPercentage;
+    }
+
     public MultiNestCFSAPSolvingStrategy() {
       Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
       Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
       Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
-    }
-    
+      Parameters.Add(new ValueParameter<BoolValue>("Restart", "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
+      Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
+      Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
+    }
+
     public override IDeepCloneable Clone(Cloner cloner) {
       return new MultiNestCFSAPSolvingStrategy(this, cloner);
     }
-
 
     [StorableHook(HookType.AfterDeserialization)]
@@ -83 +117 @@
       if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
         Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
+      if (!Parameters.ContainsKey("Restart"))
+        Parameters.Add(new ValueParameter<BoolValue>(nameof(Restart), "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
+      if (!Parameters.ContainsKey("Restart.MinTries"))
+        Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
+      if (!Parameters.ContainsKey("Restart.LastSuccessPercentage"))
+        Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
     }
 
@@ -95 +135 @@
     [Storable]
     private IndexedDataTable<double> qualityPerEvaluations;
+    [Storable]
+    private bool restart = true;
+    [Storable]
+    private int minTries = 10000;
+    [Storable]
+    private double lastSuccessPercentage = 0.1;
 
     protected override void OnPrepared() {
@@ -117 +163 @@
         cfsap.UpdateEncoding();
         algorithms.Add(clone);
-        algorithmsResults.Add(new Result("Nest " + (n + 1), clone.Results));
+        algorithmsResults.Add(new Result($"Nest {n + 1}", clone.Results));
         clone.Start();
       }
@@ -133 +179 @@
       qualityPerEvaluations.Rows.Add(qpeRow);
       double evaluations = GetEvaluatedSolutions();
-      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
-      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
+      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
+      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
 
       Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
       Results.Add(new Result("Maximum T", new IntValue(min)));
       Results.Add(new Result("BestQuality", new DoubleValue(min)));
+      Results.Add(new Result("Best Solution Found After Evaluated Solutions", new DoubleValue(evaluations)));
       Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
       Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
@@ -144 +191 @@
       Results.Add(new Result("QualityPerClock", qualityPerClock));
       Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
+      Results.Add(new Result("Tries", new IntValue(nests)));
+      Results.Add(new Result("Nests", new IntValue(nests)));
+      Results.Add(new Result("Jobs", new IntValue(Problem.ProcessingTimes.First().Count() / Problem.SetupTimes.First().Count())));
 
       base.Initialize(cancellationToken);
@@ -149 +199 @@
 
     private double GetEvaluatedSolutions() {
-      if (algorithmsResults == null) throw new InvalidOperationException("Strategy has not been started yet.");
+      if (algorithmsResults == null)
+        throw new InvalidOperationException("Strategy has not been started yet.");
       return algorithmsResults.Select(x => {
-        IResult res;
-        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out res)) {
+        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out var res)) {
           var itm = res.Value;
-          if (itm is IntValue) return ((IntValue)itm).Value;
-          else if (itm is DoubleValue) return ((DoubleValue)itm).Value;
+          if (itm is IntValue)
+            return ((IntValue)itm).Value;
+          else if (itm is DoubleValue)
+            return ((DoubleValue)itm).Value;
         }
-        throw new InvalidOperationException("No result " + EvaluatedSolutionsName + " in the collection of " + x.Name);
+        throw new InvalidOperationException($"No result {EvaluatedSolutionsName} in the collection of {x.Name}");
       }).Sum();
     }
 
     protected override void Run(CancellationToken cancellationToken) {
+      var evaluationsPrevTries = 0.0;
       var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
       var min = worst.Quality;
 
-      while (ExecutionTime < MaximumRuntime) {
-        algorithms[worst.Index].Start(cancellationToken);
-        qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
-        worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
-
-        var evaluations = GetEvaluatedSolutions();
-        var time = ExecutionTime.TotalSeconds;
-        var qpcRow = qualityPerClock.Rows.First();
-        var qpeRow = qualityPerEvaluations.Rows.First();
-        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)min);
-        qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)min);
-
-        if (worst.Quality < min) {
-          min = worst.Quality;
-          ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
-          ((IntValue)Results["Maximum T"].Value).Value = min;
-          ((DoubleValue)Results["BestQuality"].Value).Value = min;
-          ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
-          ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
-          qpcRow.Values.Add(Tuple.Create(time, (double)min));
-          qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
+      var overallBestQualities = algorithms.Select(a => ((DoubleValue)a.Results["BestQuality"].Value).Value).ToArray();
+
+      do {
+        var tries = 0;
+        var lastSuccess = 0;
+
+        while (ExecutionTime < MaximumRuntime && !cancellationToken.IsCancellationRequested &&
+            (!Restart || (tries < MinTries || (tries - lastSuccess) < tries * LastSuccessPercentage))) {
+          ++tries;
+          ++((IntValue)Results["Tries"].Value).Value;
+
+          algorithms[worst.Index].Start(cancellationToken);
+          qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
+          worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
+
+          var evaluations = evaluationsPrevTries + GetEvaluatedSolutions();
+          var time = ExecutionTime.TotalSeconds;
+          var qpcRow = qualityPerClock.Rows.First();
+          var qpeRow = qualityPerEvaluations.Rows.First();
+          qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)Math.Min(worst.Quality, min));
+          qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)Math.Min(worst.Quality, min));
+
+          if (worst.Quality < min) {
+            min = worst.Quality;
+            overallBestQualities[worst.Index] = min;
+            ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
+            ((IntValue)Results["Maximum T"].Value).Value = min;
+            ((DoubleValue)Results["BestQuality"].Value).Value = min;
+            ((DoubleValue)Results["Best Solution Found After Evaluated Solutions"].Value).Value = evaluations;
+            ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
+            ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
+            qpcRow.Values.Add(Tuple.Create(time, (double)min));
+            qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
+            lastSuccess = tries;
+          }
         }
 
-        if (cancellationToken.IsCancellationRequested) return;
+        if (cancellationToken.IsCancellationRequested || ExecutionTime >= MaximumRuntime || !Restart)
+          break;
+
+        evaluationsPrevTries += GetEvaluatedSolutions();
+
+        // restart worst algorithm
+        var worstAlgorithm = algorithms[worst.Index];
+        var prevGenerations = ((IntValue)worstAlgorithm.Results["Generation"].Value).Value;
+        var prevEvaluatedSolutions = ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value;
+
+        worstAlgorithm.Prepare();
+        worstAlgorithm.Start(cancellationToken);
+        ++((IntValue)Results["Tries"].Value).Value;
+
+        ((IntValue)worstAlgorithm.Results["Generation"].Value).Value += prevGenerations;
+        ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value += prevEvaluatedSolutions;
+      } while (Restart);
+
+      for (var i = 0; i < algorithms.Count(); ++i) {
+        if (overallBestQualities[i] < ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value) {
+          ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value = overallBestQualities[i];
+        }
       }
     }