Free cookie consent management tool by TermsFeed Policy Generator

source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs @ 15704

Last change on this file since 15704 was 15704, checked in by abeham, 6 years ago

#1614:

  • fixed exception in case no solution could be found
  • fixed behavior in GRASP regarding infeasible solutions
File size: 9.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Diagnostics;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33
34namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms {
35  [Item("Context-based Algorithm", "Algorithms that make use of contexts to facilitate applying operators.")]
36  [StorableClass]
37  public abstract class ContextAlgorithm<TContext, TEncoding> : BasicAlgorithm
38    where TContext : class, IContext, new()
39    where TEncoding : class, IEncoding {
40
41    public override Type ProblemType {
42      get { return typeof(SingleObjectiveBasicProblem<TEncoding>); }
43    }
44
45    public new SingleObjectiveBasicProblem<TEncoding> Problem {
46      get { return (SingleObjectiveBasicProblem<TEncoding>)base.Problem; }
47      set { base.Problem = value; }
48    }
49
50    [Storable]
51    private TContext context;
52    public TContext Context {
53      get { return context; }
54    }
55
56    [Storable]
57    private ValueParameter<IAnalyzer> analyzerParameter;
58    public IValueParameter<IAnalyzer> AnalyzerParameter {
59      get { return analyzerParameter; }
60    }
61    [Storable]
62    private FixedValueParameter<IntValue> maximumIterationsParameter;
63    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
64      get { return maximumIterationsParameter; }
65    }
66    [Storable]
67    private FixedValueParameter<IntValue> maximumEvaluationsParameter;
68    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
69      get { return maximumEvaluationsParameter; }
70    }
71    [Storable]
72    private FixedValueParameter<TimeSpanValue> maximumRuntimeParameter;
73    public IFixedValueParameter<TimeSpanValue> MaximumRuntimeParameter {
74      get { return maximumRuntimeParameter; }
75    }
76    [Storable]
77    private FixedValueParameter<BoolValue> stopAtBestKnownQualityParameter;
78    public IFixedValueParameter<BoolValue> StopAtBestKnownQualityParameter {
79      get { return stopAtBestKnownQualityParameter; }
80    }
81
82    public IAnalyzer Analyzer {
83      get { return analyzerParameter.Value; }
84      set { analyzerParameter.Value = value; }
85    }
86    public int MaximumIterations {
87      get { return maximumIterationsParameter.Value.Value; }
88      set { maximumIterationsParameter.Value.Value = value; }
89    }
90    public int MaximumEvaluations {
91      get { return maximumEvaluationsParameter.Value.Value; }
92      set { maximumEvaluationsParameter.Value.Value = value; }
93    }
94    public TimeSpan MaximumRuntime {
95      get { return maximumRuntimeParameter.Value.Value; }
96      set { maximumRuntimeParameter.Value.Value = value; }
97    }
98    public bool StopAtBestKnownQuality {
99      get { return stopAtBestKnownQualityParameter.Value.Value; }
100      set { stopAtBestKnownQualityParameter.Value.Value = value; }
101    }
102
103    private Stopwatch stopwatch;
104    [Storable]
105    private TimeSpan elapsed;
106    [Storable]
107    private IndexedDataTable<double> qualityPerClock;
108    [Storable]
109    private IndexedDataRow<double> firstHitGraph;
110
111    [StorableConstructor]
112    protected ContextAlgorithm(bool deserializing) : base(deserializing) { }
113    protected ContextAlgorithm(ContextAlgorithm<TContext, TEncoding> original, Cloner cloner)
114      : base(original, cloner) {
115      context = cloner.Clone(original.context);
116      analyzerParameter = cloner.Clone(original.analyzerParameter);
117      maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
118      maximumEvaluationsParameter = cloner.Clone(original.maximumEvaluationsParameter);
119      maximumRuntimeParameter = cloner.Clone(original.maximumRuntimeParameter);
120      stopAtBestKnownQualityParameter = cloner.Clone(original.stopAtBestKnownQualityParameter);
121      elapsed = original.elapsed;
122      qualityPerClock = cloner.Clone(original.qualityPerClock);
123      firstHitGraph = cloner.Clone(original.firstHitGraph);
124      if (context != null)
125        context.BestQualityChanged += ContextOnBestQualityChanged;
126    }
127    protected ContextAlgorithm()
128      : base() {
129      Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
130      Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run or < 1 to ignore.", new IntValue(0)));
131      Parameters.Add(maximumEvaluationsParameter = new FixedValueParameter<IntValue>("MaximumEvaluations", "The number of evaluated solutions that the algorithm should perform or < 1 to ignore.", new IntValue(0)));
132      Parameters.Add(maximumRuntimeParameter = new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The timespan that the algorithm is allowed to run.", new TimeSpanValue(TimeSpan.FromMinutes(1))));
133      Parameters.Add(stopAtBestKnownQualityParameter = new FixedValueParameter<BoolValue>("StopAtBestKnownQuality", "Whether the algorithm should terminate if the best known quality has been found.", new BoolValue(true)));
134    }
135
136    protected override void Initialize(CancellationToken cancellationToken) {
137      base.Initialize(cancellationToken);
138      context = new TContext();
139      context.Scope.Variables.Add(new Variable("Results", Results));
140      context.BestQualityChanged += ContextOnBestQualityChanged;
141
142      IExecutionContext ctxt = null;
143      foreach (var item in Problem.ExecutionContextItems)
144        ctxt = new Core.ExecutionContext(ctxt, item, Context.Scope);
145      ctxt = new Core.ExecutionContext(ctxt, this, Context.Scope);
146      context.Parent = ctxt;
147
148      context.Iterations = 0;
149      context.EvaluatedSolutions = 0;
150      context.BestQuality = double.NaN;
151
152      qualityPerClock = new IndexedDataTable<double>("Quality Per Clock");
153      firstHitGraph = new IndexedDataRow<double>("First-hit Graph");
154      qualityPerClock.Rows.Add(firstHitGraph);
155      Results.Add(new Result("QualityPerClock", qualityPerClock));
156
157      elapsed = TimeSpan.Zero;
158      stopwatch = Stopwatch.StartNew();
159    }
160
161    protected override void Run(CancellationToken cancellationToken) {
162      if (stopwatch == null || !stopwatch.IsRunning) stopwatch = Stopwatch.StartNew();
163    }
164
165    private void ContextOnBestQualityChanged(object sender, EventArgs e) {
166      if (double.IsNaN(Context.BestQuality)) return;
167      var newEntry = Tuple.Create((elapsed + stopwatch.Elapsed).TotalSeconds, Context.BestQuality);
168
169      if (firstHitGraph.Values.Count == 0) {
170        firstHitGraph.Values.Add(newEntry); // record the first data
171        firstHitGraph.Values.Add(Tuple.Create(newEntry.Item1, newEntry.Item2)); // last entry records max number of evaluations
172        return;
173      }
174
175      var improvement = firstHitGraph.Values.Last().Item2 != newEntry.Item2;
176      if (improvement) {
177        firstHitGraph.Values[firstHitGraph.Values.Count - 1] = newEntry; // record the improvement
178        firstHitGraph.Values.Add(Tuple.Create(newEntry.Item1, newEntry.Item2)); // last entry records max number of evaluations
179      } else {
180        firstHitGraph.Values[firstHitGraph.Values.Count - 1] = Tuple.Create(newEntry.Item1, newEntry.Item2);
181      }
182    }
183
184    public override void Prepare() {
185      if (context != null) {
186        context.BestQualityChanged -= ContextOnBestQualityChanged;
187        context = null;
188      }
189      base.Prepare();
190    }
191
192    protected override void OnPaused() {
193      elapsed += stopwatch.Elapsed;
194      stopwatch.Reset();
195      if (firstHitGraph.Values.Count > 0)
196        firstHitGraph.Values[firstHitGraph.Values.Count - 1] = Tuple.Create(elapsed.TotalSeconds, Context.BestQuality);
197      base.OnPaused();
198    }
199
200    protected override void OnStopped() {
201      if (stopwatch.IsRunning) {
202        elapsed += stopwatch.Elapsed;
203        stopwatch.Reset();
204        if (firstHitGraph.Values.Count > 0)
205          firstHitGraph.Values[firstHitGraph.Values.Count - 1] = Tuple.Create(elapsed.TotalSeconds, Context.BestQuality);
206      }
207      // base call must be done last as the results will be cloned and a run is created
208      base.OnStopped();
209    }
210
211    [StorableHook(HookType.AfterDeserialization)]
212    private void AfterDeserialization() {
213      if (context != null) context.BestQualityChanged += ContextOnBestQualityChanged;
214    }
215
216    protected virtual bool StoppingCriterion() {
217      return MaximumIterations > 0 && Context.Iterations > MaximumIterations
218        || MaximumEvaluations > 0 && Context.EvaluatedSolutions > MaximumEvaluations
219        || MaximumRuntime > TimeSpan.Zero && ExecutionTime > MaximumRuntime
220        || StopAtBestKnownQuality && !double.IsNaN(Problem.BestKnownQuality)
221          && Context.BestQuality.IsAlmost(Problem.BestKnownQuality);
222    }
223  }
224}
Note: See TracBrowser for help on using the repository browser.