source: branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs @ 15533

Last change on this file since 15533 was 15533, checked in by ddorfmei, 5 years ago

#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 size: 13.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Threading;
5using HeuristicLab.Analysis;
6using HeuristicLab.Common;
7using HeuristicLab.Core;
8using HeuristicLab.Data;
9using HeuristicLab.Optimization;
10using HeuristicLab.Parameters;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12
13namespace HeuristicLab.Problems.Scheduling.CFSAP {
14  [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instance to the worst nest.")]
15  [StorableClass]
16  [Creatable(CreatableAttribute.Categories.Algorithms)]
17  public class MultiNestCFSAPSolvingStrategy : BasicAlgorithm {
18    public override bool SupportsPause => true;
19
20    public override Type ProblemType => typeof(MultiNestCFSAP);
21
22    public new MultiNestCFSAP Problem {
23      get { return (MultiNestCFSAP)base.Problem; }
24      set { base.Problem = value; }
25    }
26
27    public IValueParameter<IAlgorithm> SolverParameter {
28      get { return (IValueParameter<IAlgorithm>)Parameters["Solver"]; }
29    }
30
31    public IFixedValueParameter<TimeSpanValue> MaximumRuntimeParameter {
32      get { return (IFixedValueParameter<TimeSpanValue>)Parameters["MaximumRuntime"]; }
33    }
34
35    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
36      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
37    }
38
39    public IValueParameter<BoolValue> RestartParameter {
40      get { return (IValueParameter<BoolValue>)Parameters["Restart"]; }
41    }
42
43    public IValueParameter<IntValue> MinTriesParameter {
44      get { return (IValueParameter<IntValue>)Parameters["Restart.MinTries"]; }
45    }
46
47    public IValueParameter<DoubleValue> LastSuccessPercentageParameter {
48      get { return (IValueParameter<DoubleValue>)Parameters["Restart.LastSuccessPercentage"]; }
49    }
50
51    public IAlgorithm Solver {
52      get { return SolverParameter.Value; }
53      set { SolverParameter.Value = value; }
54    }
55
56    public TimeSpan MaximumRuntime {
57      get { return MaximumRuntimeParameter.Value.Value; }
58      set { MaximumRuntimeParameter.Value.Value = value; }
59    }
60
61    public string EvaluatedSolutionsName {
62      get { return EvaluatedSolutionsNameParameter.Value.Value; }
63      set { EvaluatedSolutionsNameParameter.Value.Value = value; }
64    }
65
66    public bool Restart {
67      get => RestartParameter.Value.Value;
68      set => RestartParameter.Value.Value = value;
69    }
70
71    public int MinTries {
72      get => MinTriesParameter.Value.Value;
73      set => MinTriesParameter.Value.Value = value;
74    }
75
76    public double LastSuccessPercentage {
77      get => LastSuccessPercentageParameter.Value.Value;
78      set => LastSuccessPercentageParameter.Value.Value = value;
79    }
80
81    [StorableConstructor]
82    protected MultiNestCFSAPSolvingStrategy(bool deserializing) : base(deserializing) { }
83
84    protected MultiNestCFSAPSolvingStrategy(MultiNestCFSAPSolvingStrategy original, Cloner cloner)
85      : base(original, cloner) {
86      if (original.algorithms != null)
87        algorithms = original.algorithms.Select(x => cloner.Clone(x)).ToList();
88      if (original.qualities != null)
89        qualities = original.qualities.ToArray();
90      if (original.algorithmsResults != null)
91        algorithmsResults = cloner.Clone(original.algorithmsResults);
92      if (original.qualityPerClock != null)
93        qualityPerClock = cloner.Clone(original.qualityPerClock);
94      if (original.qualityPerEvaluations != null)
95        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
96
97      restart = original.restart;
98      minTries = original.minTries;
99      lastSuccessPercentage = original.lastSuccessPercentage;
100    }
101
102    public MultiNestCFSAPSolvingStrategy() {
103      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
104      Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
105      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")));
106      Parameters.Add(new ValueParameter<BoolValue>("Restart", "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
107      Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
108      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)));
109    }
110
111    public override IDeepCloneable Clone(Cloner cloner) {
112      return new MultiNestCFSAPSolvingStrategy(this, cloner);
113    }
114
115    [StorableHook(HookType.AfterDeserialization)]
116    private void AfterDeserialization() {
117      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
118        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")));
119      if (!Parameters.ContainsKey("Restart"))
120        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)));
121      if (!Parameters.ContainsKey("Restart.MinTries"))
122        Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
123      if (!Parameters.ContainsKey("Restart.LastSuccessPercentage"))
124        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)));
125    }
126
127    [Storable]
128    private List<IAlgorithm> algorithms;
129    [Storable]
130    private int[] qualities;
131    [Storable]
132    private ResultCollection algorithmsResults;
133    [Storable]
134    private IndexedDataTable<double> qualityPerClock;
135    [Storable]
136    private IndexedDataTable<double> qualityPerEvaluations;
137    [Storable]
138    private bool restart = true;
139    [Storable]
140    private int minTries = 10000;
141    [Storable]
142    private double lastSuccessPercentage = 0.1;
143
144    protected override void OnPrepared() {
145      base.OnPrepared();
146      algorithms = null;
147      qualities = null;
148      algorithmsResults = null;
149      qualityPerClock = null;
150      qualityPerEvaluations = null;
151    }
152
153    protected override void Initialize(CancellationToken cancellationToken) {
154      var nests = Problem.ProcessingTimesParameter.Value.Count;
155      algorithms = new List<IAlgorithm>(nests);
156      algorithmsResults = new ResultCollection();
157      for (var n = 0; n < nests; n++) {
158        var clone = (IAlgorithm)SolverParameter.Value.Clone();
159        clone.Prepare();
160        var cfsap = (ICFSAP)clone.Problem;
161        cfsap.ProcessingTimes = Problem.ProcessingTimes[n];
162        cfsap.SetupTimes = Problem.SetupTimes[n];
163        cfsap.UpdateEncoding();
164        algorithms.Add(clone);
165        algorithmsResults.Add(new Result($"Nest {n + 1}", clone.Results));
166        clone.Start();
167      }
168      qualities = algorithms.Select(x => (int)((DoubleValue)x.Results["BestQuality"].Value).Value).ToArray();
169      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
170      var min = worst.Quality;
171
172      qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
173      var qpcRow = new IndexedDataRow<double>("First-hit Graph");
174      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
175      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
176      qualityPerClock.Rows.Add(qpcRow);
177      qualityPerEvaluations = new IndexedDataTable<double>("Quality per Evaluations");
178      var qpeRow = new IndexedDataRow<double>("First-hit Graph");
179      qualityPerEvaluations.Rows.Add(qpeRow);
180      double evaluations = GetEvaluatedSolutions();
181      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
182      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
183
184      Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
185      Results.Add(new Result("Maximum T", new IntValue(min)));
186      Results.Add(new Result("BestQuality", new DoubleValue(min)));
187      Results.Add(new Result("Best Solution Found After Evaluated Solutions", new DoubleValue(evaluations)));
188      Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
189      Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
190      Results.Add(new Result("Nest Results", algorithmsResults));
191      Results.Add(new Result("QualityPerClock", qualityPerClock));
192      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
193      Results.Add(new Result("Tries", new IntValue(nests)));
194      Results.Add(new Result("Nests", new IntValue(nests)));
195      Results.Add(new Result("Jobs", new IntValue(Problem.ProcessingTimes.First().Count() / Problem.SetupTimes.First().Count())));
196
197      base.Initialize(cancellationToken);
198    }
199
200    private double GetEvaluatedSolutions() {
201      if (algorithmsResults == null)
202        throw new InvalidOperationException("Strategy has not been started yet.");
203      return algorithmsResults.Select(x => {
204        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out var res)) {
205          var itm = res.Value;
206          if (itm is IntValue)
207            return ((IntValue)itm).Value;
208          else if (itm is DoubleValue)
209            return ((DoubleValue)itm).Value;
210        }
211        throw new InvalidOperationException($"No result {EvaluatedSolutionsName} in the collection of {x.Name}");
212      }).Sum();
213    }
214
215    protected override void Run(CancellationToken cancellationToken) {
216      var evaluationsPrevTries = 0.0;
217      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
218      var min = worst.Quality;
219
220      var overallBestQualities = algorithms.Select(a => ((DoubleValue)a.Results["BestQuality"].Value).Value).ToArray();
221
222      do {
223        var tries = 0;
224        var lastSuccess = 0;
225
226        while (ExecutionTime < MaximumRuntime && !cancellationToken.IsCancellationRequested &&
227            (!Restart || (tries < MinTries || (tries - lastSuccess) < tries * LastSuccessPercentage))) {
228          ++tries;
229          ++((IntValue)Results["Tries"].Value).Value;
230
231          algorithms[worst.Index].Start(cancellationToken);
232          qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
233          worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
234
235          var evaluations = evaluationsPrevTries + GetEvaluatedSolutions();
236          var time = ExecutionTime.TotalSeconds;
237          var qpcRow = qualityPerClock.Rows.First();
238          var qpeRow = qualityPerEvaluations.Rows.First();
239          qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)Math.Min(worst.Quality, min));
240          qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)Math.Min(worst.Quality, min));
241
242          if (worst.Quality < min) {
243            min = worst.Quality;
244            overallBestQualities[worst.Index] = min;
245            ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
246            ((IntValue)Results["Maximum T"].Value).Value = min;
247            ((DoubleValue)Results["BestQuality"].Value).Value = min;
248            ((DoubleValue)Results["Best Solution Found After Evaluated Solutions"].Value).Value = evaluations;
249            ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
250            ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
251            qpcRow.Values.Add(Tuple.Create(time, (double)min));
252            qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
253            lastSuccess = tries;
254          }
255        }
256
257        if (cancellationToken.IsCancellationRequested || ExecutionTime >= MaximumRuntime || !Restart)
258          break;
259
260        evaluationsPrevTries += GetEvaluatedSolutions();
261
262        // restart worst algorithm
263        var worstAlgorithm = algorithms[worst.Index];
264        var prevGenerations = ((IntValue)worstAlgorithm.Results["Generation"].Value).Value;
265        var prevEvaluatedSolutions = ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value;
266
267        worstAlgorithm.Prepare();
268        worstAlgorithm.Start(cancellationToken);
269        ++((IntValue)Results["Tries"].Value).Value;
270
271        ((IntValue)worstAlgorithm.Results["Generation"].Value).Value += prevGenerations;
272        ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value += prevEvaluatedSolutions;
273      } while (Restart);
274
275      for (var i = 0; i < algorithms.Count(); ++i) {
276        if (overallBestQualities[i] < ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value) {
277          ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value = overallBestQualities[i];
278        }
279      }
280    }
281  }
282}
Note: See TracBrowser for help on using the repository browser.