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

Last change on this file since 15472 was 15472, checked in by abeham, 5 years ago

#2747: worked on the CFSAP

  • merged HeuristicLab.Problems.Instances from trunk
  • updated best known qualities
  • reduced memory footprint of run
  • added convergence graph result to solving strategy
File size: 8.9 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 instace 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
36    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
37      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
38    }
39
40    public IAlgorithm Solver {
41      get { return SolverParameter.Value; }
42      set { SolverParameter.Value = value; }
43    }
44
45    public TimeSpan MaximumRuntime {
46      get { return MaximumRuntimeParameter.Value.Value; }
47      set { MaximumRuntimeParameter.Value.Value = value; }
48    }
49
50    public string EvaluatedSolutionsName {
51      get { return EvaluatedSolutionsNameParameter.Value.Value; }
52      set { EvaluatedSolutionsNameParameter.Value.Value = value; }
53    }
54
55    [StorableConstructor]
56    protected MultiNestCFSAPSolvingStrategy(bool deserializing) : base(deserializing) { }
57    protected MultiNestCFSAPSolvingStrategy(MultiNestCFSAPSolvingStrategy original, Cloner cloner)
58      : base(original, cloner) {
59      if (original.algorithms != null)
60        algorithms = original.algorithms.Select(x => cloner.Clone(x)).ToList();
61      if (original.qualities != null)
62        qualities = original.qualities.ToArray();
63      if (original.algorithmsResults != null)
64        algorithmsResults = cloner.Clone(original.algorithmsResults);
65      if (original.qualityPerClock != null)
66        qualityPerClock = cloner.Clone(original.qualityPerClock);
67      if (original.qualityPerEvaluations != null)
68        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
69    }
70    public MultiNestCFSAPSolvingStrategy() {
71      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
72      Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
73      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")));
74    }
75   
76    public override IDeepCloneable Clone(Cloner cloner) {
77      return new MultiNestCFSAPSolvingStrategy(this, cloner);
78    }
79
80
81    [StorableHook(HookType.AfterDeserialization)]
82    private void AfterDeserialization() {
83      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
84        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")));
85    }
86
87    [Storable]
88    private List<IAlgorithm> algorithms;
89    [Storable]
90    private int[] qualities;
91    [Storable]
92    private ResultCollection algorithmsResults;
93    [Storable]
94    private IndexedDataTable<double> qualityPerClock;
95    [Storable]
96    private IndexedDataTable<double> qualityPerEvaluations;
97
98    protected override void OnPrepared() {
99      base.OnPrepared();
100      algorithms = null;
101      qualities = null;
102      algorithmsResults = null;
103      qualityPerClock = null;
104      qualityPerEvaluations = null;
105    }
106
107    protected override void Initialize(CancellationToken cancellationToken) {
108      var nests = Problem.ProcessingTimesParameter.Value.Count;
109      algorithms = new List<IAlgorithm>(nests);
110      algorithmsResults = new ResultCollection();
111      for (var n = 0; n < nests; n++) {
112        var clone = (IAlgorithm)SolverParameter.Value.Clone();
113        clone.Prepare();
114        var cfsap = (ICFSAP)clone.Problem;
115        cfsap.ProcessingTimes = Problem.ProcessingTimes[n];
116        cfsap.SetupTimes = Problem.SetupTimes[n];
117        cfsap.UpdateEncoding();
118        algorithms.Add(clone);
119        algorithmsResults.Add(new Result("Nest " + (n + 1), clone.Results));
120        clone.Start();
121      }
122      qualities = algorithms.Select(x => (int)((DoubleValue)x.Results["BestQuality"].Value).Value).ToArray();
123      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
124      var min = worst.Quality;
125
126      qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
127      var qpcRow = new IndexedDataRow<double>("First-hit Graph");
128      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
129      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
130      qualityPerClock.Rows.Add(qpcRow);
131      qualityPerEvaluations = new IndexedDataTable<double>("Quality per Evaluations");
132      var qpeRow = new IndexedDataRow<double>("First-hit Graph");
133      qualityPerEvaluations.Rows.Add(qpeRow);
134      double evaluations = GetEvaluatedSolutions();
135      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
136      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
137
138      Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
139      Results.Add(new Result("Maximum T", new IntValue(min)));
140      Results.Add(new Result("BestQuality", new DoubleValue(min)));
141      Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
142      Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
143      Results.Add(new Result("Nest Results", algorithmsResults));
144      Results.Add(new Result("QualityPerClock", qualityPerClock));
145      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
146
147      base.Initialize(cancellationToken);
148    }
149
150    private double GetEvaluatedSolutions() {
151      if (algorithmsResults == null) throw new InvalidOperationException("Strategy has not been started yet.");
152      return algorithmsResults.Select(x => {
153        IResult res;
154        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out res)) {
155          var itm = res.Value;
156          if (itm is IntValue) return ((IntValue)itm).Value;
157          else if (itm is DoubleValue) return ((DoubleValue)itm).Value;
158        }
159        throw new InvalidOperationException("No result " + EvaluatedSolutionsName + " in the collection of " + x.Name);
160      }).Sum();
161    }
162
163    protected override void Run(CancellationToken cancellationToken) {
164      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
165      var min = worst.Quality;
166
167      while (ExecutionTime < MaximumRuntime) {
168        algorithms[worst.Index].Start(cancellationToken);
169        qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
170        worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
171
172        var evaluations = GetEvaluatedSolutions();
173        var time = ExecutionTime.TotalSeconds;
174        var qpcRow = qualityPerClock.Rows.First();
175        var qpeRow = qualityPerEvaluations.Rows.First();
176        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)min);
177        qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)min);
178
179        if (worst.Quality < min) {
180          min = worst.Quality;
181          ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
182          ((IntValue)Results["Maximum T"].Value).Value = min;
183          ((DoubleValue)Results["BestQuality"].Value).Value = min;
184          ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
185          ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
186          qpcRow.Values.Add(Tuple.Create(time, (double)min));
187          qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
188        }
189
190        if (cancellationToken.IsCancellationRequested) return;
191      }
192    }
193  }
194}
Note: See TracBrowser for help on using the repository browser.