source: branches/ScopedAlgorithms/HeuristicLab.Optimization/3.3/Algorithms/SingleObjective/HeuristicAlgorithm.cs @ 14429

Last change on this file since 14429 was 14429, checked in by abeham, 4 years ago

#2701, #2708: Made a new branch from ProblemRefactoring and removed ScopedBasicAlgorithm branch (which becomes MemPR branch)

File size: 13.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26using System.Threading.Tasks;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Optimization.Algorithms.SingleObjective {
34  public abstract class HeuristicAlgorithm<TContext, TProblem, TEncoding, TSolution> : Algorithm
35      where TContext : HeuristicAlgorithmContext<TProblem, TEncoding, TSolution>,
36                       IStochasticContext, IEvaluatedSolutionsContext, IBestQualityContext,
37                       IBestSolutionContext<TSolution>, new()
38      where TProblem : class, ISingleObjectiveProblem<TEncoding, TSolution>, ISingleObjectiveProblemDefinition<TEncoding, TSolution>
39      where TEncoding : class, IEncoding<TSolution>
40      where TSolution : class, ISolution {
41    private Type problemType;
42
43    public override Type ProblemType {
44      get { return typeof(SingleObjectiveProblem<TEncoding, TSolution>); }
45    }
46
47    public new TProblem Problem {
48      get { return (TProblem)base.Problem; }
49      set { base.Problem = value; }
50    }
51
52    private CancellationTokenSource cancellationTokenSource;
53    protected CancellationTokenSource CancellationTokenSource {
54      get { return cancellationTokenSource; }
55      private set { cancellationTokenSource = value; }
56    }
57
58
59    public int? MaximumEvaluations {
60      get {
61        var val = ((OptionalValueParameter<IntValue>)Parameters["MaximumEvaluations"]).Value;
62        return val != null ? val.Value : (int?)null;
63      }
64      set {
65        var param = (OptionalValueParameter<IntValue>)Parameters["MaximumEvaluations"];
66        param.Value = value.HasValue ? new IntValue(value.Value) : null;
67      }
68    }
69
70    public TimeSpan? MaximumExecutionTime {
71      get {
72        var val = ((OptionalValueParameter<TimeSpanValue>)Parameters["MaximumExecutionTime"]).Value;
73        return val != null ? val.Value : (TimeSpan?)null;
74      }
75      set {
76        var param = (OptionalValueParameter<TimeSpanValue>)Parameters["MaximumExecutionTime"];
77        param.Value = value.HasValue ? new TimeSpanValue(value.Value) : null;
78      }
79    }
80
81    public double? TargetQuality {
82      get {
83        var val = ((OptionalValueParameter<DoubleValue>)Parameters["TargetQuality"]).Value;
84        return val != null ? val.Value : (double?)null;
85      }
86      set {
87        var param = (OptionalValueParameter<DoubleValue>)Parameters["TargetQuality"];
88        param.Value = value.HasValue ? new DoubleValue(value.Value) : null;
89      }
90    }
91
92    public bool SetSeedRandomly {
93      get { return ((FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]).Value.Value; }
94      set { ((FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]).Value.Value = value; }
95    }
96
97    public int Seed {
98      get { return ((FixedValueParameter<IntValue>)Parameters["Seed"]).Value.Value; }
99      set { ((FixedValueParameter<IntValue>)Parameters["Seed"]).Value.Value = value; }
100    }
101
102    public IMultiAnalyzer AlgorithmAnalyzer {
103      get { return ((ValueParameter<IMultiAnalyzer>)Parameters["Analyzer.Algorithm"]).Value; }
104      set { ((ValueParameter<IMultiAnalyzer>)Parameters["Analyzer.Algorithm"]).Value = value; }
105    }
106
107    public IMultiAnalyzer ProblemAnalyzer {
108      get { return ((ValueParameter<IMultiAnalyzer>)Parameters["Analyzer.Problem"]).Value; }
109      set { ((ValueParameter<IMultiAnalyzer>)Parameters["Analyzer.Problem"]).Value = value; }
110    }
111
112    [Storable]
113    private ResultCollection results;
114    public override ResultCollection Results {
115      get { return results; }
116    }
117
118    [Storable]
119    private TContext context;
120    public TContext Context {
121      get { return context; }
122      protected set {
123        if (context == value) return;
124        context = value;
125      }
126    }
127
128    [StorableConstructor]
129    protected HeuristicAlgorithm(bool deserializing) : base(deserializing) { }
130    protected HeuristicAlgorithm(HeuristicAlgorithm<TContext, TProblem, TEncoding, TSolution> original, Cloner cloner)
131      : base(original, cloner) { }
132    protected HeuristicAlgorithm() {
133      results = new ResultCollection();
134
135      Parameters.Add(new ValueParameter<IMultiAnalyzer>("Analyzer.Algorithm", "The algorithm's analyzers to apply to the solution(s) (independent of the problem)."));
136      Parameters.Add(new ValueParameter<IMultiAnalyzer>("Analyzer.Problem", "The problem's analyzer to apply to the solution(s)."));
137      Parameters.Add(new OptionalValueParameter<IntValue>("MaximumEvaluations", "The maximum number of solution evaluations."));
138      Parameters.Add(new OptionalValueParameter<TimeSpanValue>("MaximumExecutionTime", "The maximum runtime.", new TimeSpanValue(TimeSpan.FromMinutes(1))));
139      Parameters.Add(new OptionalValueParameter<DoubleValue>("TargetQuality", "The target quality at which the algorithm terminates."));
140      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether each run of the algorithm should be conducted with a new random seed.", new BoolValue(true)));
141      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The random number seed that is used in case SetSeedRandomly is false.", new IntValue(0)));
142
143    }
144
145    protected override void OnProblemChanged() {
146      base.OnProblemChanged();
147      if (ProblemAnalyzer != null) {
148        ProblemAnalyzer.Operators.Clear();
149        if (Problem != null) {
150          foreach (var analyzer in Problem.Operators.OfType<IAnalyzer>()) {
151            foreach (var param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
152              param.Depth = 1;
153            ProblemAnalyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
154          }
155        }
156      }
157    }
158
159    public override void Prepare() {
160      if (Problem == null) return;
161      base.Prepare();
162      results.Clear();
163      Context = null;
164      stopRequested = false;
165      OnPrepared();
166    }
167
168    private bool stopRequested = false;
169    public override void Start() {
170      base.Start();
171      CancellationTokenSource = new CancellationTokenSource();
172
173      OnStarted();
174      var task = Task.Run((Action)Run, cancellationTokenSource.Token);
175      var continuation = new Task[3];
176      continuation[0] = task.ContinueWith(t => {
177        if (t.Exception != null) {
178          OnExceptionOccurred(t.Exception.InnerExceptions.Count == 1 ? t.Exception.InnerExceptions[0] : t.Exception);
179        }
180        OnPaused();
181      }, TaskContinuationOptions.OnlyOnFaulted);
182      continuation[1] = task.ContinueWith(t => {
183        OnStopped();
184      }, TaskContinuationOptions.OnlyOnRanToCompletion);
185      continuation[2] = task.ContinueWith(t => {
186        if (stopRequested) OnStopped();
187        else OnPaused();
188      }, TaskContinuationOptions.OnlyOnCanceled);
189      Task.WhenAny(continuation).ContinueWith(_ => {
190        CancellationTokenSource.Dispose();
191        CancellationTokenSource = null;
192      });
193    }
194
195    public override void Pause() {
196      base.Pause();
197      CancellationTokenSource.Cancel();
198    }
199
200    public override void Stop() {
201      // CancellationToken.ThrowIfCancellationRequested() must be called from within the Run method, otherwise stop does nothing
202      // alternatively check the IsCancellationRequested property of the cancellation token
203      base.Stop();
204      stopRequested = true;
205      if (CancellationTokenSource != null) {
206        try {
207          CancellationTokenSource.Cancel();
208        } catch {
209          OnStopped();
210        }
211      } else OnStopped();
212    }
213
214    private DateTime lastUpdateTime;
215    private void Run() {
216      var token = CancellationTokenSource.Token;
217      lastUpdateTime = DateTime.UtcNow;
218      System.Timers.Timer timer = new System.Timers.Timer(250);
219      timer.AutoReset = true;
220      timer.Elapsed += timer_Elapsed;
221      timer.Start();
222      try {
223        if (context == null) {
224          context = CreateContext();
225
226          IExecutionContext ctxt = null;
227          foreach (var item in Problem.ExecutionContextItems)
228            ctxt = new Core.ExecutionContext(ctxt, item, Context.Scope);
229          ctxt = new Core.ExecutionContext(ctxt, this, Context.Scope);
230
231          context.Parent = ctxt;
232
233          if (SetSeedRandomly) Seed = new System.Random().Next();
234          Context.Random.Reset(Seed);
235          Context.Scope.Variables.Add(new Variable("Results", Results));
236        } else context.CancellationToken = token;
237
238        if (!Context.Initialized) {
239          try {
240            PerformInitialize(token);
241          } catch {
242            context = null;
243            return;
244          }
245          Context.Initialized = true;
246        }
247
248        while (!CheckTerminate(token)) {
249          PerformIterate(token);
250          PerformAnalyze(token);
251          token.ThrowIfCancellationRequested();
252        }
253      } finally {
254        timer.Elapsed -= timer_Elapsed;
255        timer.Stop();
256        ExecutionTime += DateTime.UtcNow - lastUpdateTime;
257      }
258    }
259
260    protected virtual TContext CreateContext() {
261      return new TContext() { Problem = Problem, CancellationToken = CancellationTokenSource.Token };
262    }
263
264    protected virtual ISingleObjectiveSolutionScope<TSolution> CreateEmptySolutionScope() {
265      return new SingleObjectiveSolutionScope<TSolution>(null, Problem.Encoding.Name, double.NaN, Problem.Evaluator.QualityParameter.ActualName);
266    }
267
268    protected static bool IsBetter(bool maximization, double a, double b) {
269      return !double.IsNaN(a) && double.IsNaN(b) || maximization && a > b || !maximization && a < b;
270    }
271
272    protected virtual void Evaluate(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token) {
273      scope.Fitness = Problem.Evaluate(scope.Solution, Context.Random);
274    }
275
276    protected abstract void PerformInitialize(CancellationToken token);
277    protected abstract void PerformIterate(CancellationToken token);
278    protected virtual void PerformAnalyze(CancellationToken token) {
279      IResult res;
280      if (!Results.TryGetValue("EvaluatedSolutions", out res)) {
281        res = new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions));
282        Results.Add(res);
283      } else ((IntValue)res.Value).Value = Context.EvaluatedSolutions;
284      if (!Results.TryGetValue("BestQuality", out res)) {
285        res = new Result("BestQuality", new DoubleValue(Context.BestQuality));
286        Results.Add(res);
287      } else ((DoubleValue)res.Value).Value = Context.BestQuality;
288
289      RunOperator(ProblemAnalyzer, Context.Scope, token);
290      RunOperator(AlgorithmAnalyzer, Context.Scope, token);
291    }
292
293    protected virtual bool CheckTerminate(CancellationToken token) {
294      return MaximumEvaluations.HasValue && Context.EvaluatedSolutions >= MaximumEvaluations.Value
295        || MaximumExecutionTime.HasValue && ExecutionTime >= MaximumExecutionTime.Value
296        || TargetQuality.HasValue && (Problem.Maximization && Context.BestQuality >= TargetQuality.Value
297                                  || !Problem.Maximization && Context.BestQuality <= TargetQuality.Value);
298    }
299
300    #region Engine Helper
301    protected void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {
302      var stack = new Stack<IOperation>();
303      stack.Push(Context.CreateChildOperation(op, scope));
304
305      while (stack.Count > 0) {
306        cancellationToken.ThrowIfCancellationRequested();
307
308        var next = stack.Pop();
309        if (next is OperationCollection) {
310          var coll = (OperationCollection)next;
311          for (int i = coll.Count - 1; i >= 0; i--)
312            if (coll[i] != null) stack.Push(coll[i]);
313        } else if (next is IAtomicOperation) {
314          var operation = (IAtomicOperation)next;
315          try {
316            next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
317          } catch (Exception ex) {
318            stack.Push(operation);
319            if (ex is OperationCanceledException) throw ex;
320            else throw new OperatorExecutionException(operation.Operator, ex);
321          }
322          if (next != null) stack.Push(next);
323        }
324      }
325    }
326    #endregion
327
328    #region Events
329    private void timer_Elapsed(object sender, System.Timers.ElapsedEventArgs e) {
330      System.Timers.Timer timer = (System.Timers.Timer)sender;
331      timer.Enabled = false;
332      DateTime now = DateTime.UtcNow;
333      ExecutionTime += now - lastUpdateTime;
334      lastUpdateTime = now;
335      timer.Enabled = true;
336    }
337    #endregion
338  }
339}
Note: See TracBrowser for help on using the repository browser.