Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2457_ExpertSystem/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs @ 16124

Last change on this file since 16124 was 14690, checked in by abeham, 7 years ago

#2457: working on identification of problem instances
File size: 31.1 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.ComponentModel;
25using System.Linq;
26using System.Threading;
27using HeuristicLab.Algorithms.MemPR.Interfaces;
28using HeuristicLab.Analysis;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Data;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.MemPR {
38  [Item("MemPR Algorithm", "Base class for MemPR algorithms")]
39  [StorableClass]
40  public abstract class MemPRAlgorithm<TProblem, TSolution, TPopulationContext, TSolutionContext> : BasicAlgorithm, INotifyPropertyChanged
41      where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem
42      where TSolution : class, IItem
43      where TPopulationContext : MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext>, new()
44      where TSolutionContext : MemPRSolutionContext<TProblem, TSolution, TPopulationContext, TSolutionContext> {
45
46    public override Type ProblemType {
47      get { return typeof(TProblem); }
48    }
49
50    public new TProblem Problem {
51      get { return (TProblem)base.Problem; }
52      set { base.Problem = value; }
53    }
54
55    public override bool SupportsPause {
56      get { return true; }
57    }
58
59    protected string QualityName {
60      get { return Problem != null && Problem.Evaluator != null ? Problem.Evaluator.QualityParameter.ActualName : null; }
61    }
62
63    public int? MaximumEvaluations {
64      get {
65        var val = ((OptionalValueParameter<IntValue>)Parameters["MaximumEvaluations"]).Value;
66        return val != null ? val.Value : (int?)null;
67      }
68      set {
69        var param = (OptionalValueParameter<IntValue>)Parameters["MaximumEvaluations"];
70        param.Value = value.HasValue ? new IntValue(value.Value) : null;
71      }
72    }
73
74    public TimeSpan? MaximumExecutionTime {
75      get {
76        var val = ((OptionalValueParameter<TimeSpanValue>)Parameters["MaximumExecutionTime"]).Value;
77        return val != null ? val.Value : (TimeSpan?)null;
78      }
79      set {
80        var param = (OptionalValueParameter<TimeSpanValue>)Parameters["MaximumExecutionTime"];
81        param.Value = value.HasValue ? new TimeSpanValue(value.Value) : null;
82      }
83    }
84
85    public double? TargetQuality {
86      get {
87        var val = ((OptionalValueParameter<DoubleValue>)Parameters["TargetQuality"]).Value;
88        return val != null ? val.Value : (double?)null;
89      }
90      set {
91        var param = (OptionalValueParameter<DoubleValue>)Parameters["TargetQuality"];
92        param.Value = value.HasValue ? new DoubleValue(value.Value) : null;
93      }
94    }
95
96    protected FixedValueParameter<IntValue> MaximumPopulationSizeParameter {
97      get { return ((FixedValueParameter<IntValue>)Parameters["MaximumPopulationSize"]); }
98    }
99    public int MaximumPopulationSize {
100      get { return MaximumPopulationSizeParameter.Value.Value; }
101      set { MaximumPopulationSizeParameter.Value.Value = value; }
102    }
103
104    public bool SetSeedRandomly {
105      get { return ((FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]).Value.Value; }
106      set { ((FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]).Value.Value = value; }
107    }
108
109    public int Seed {
110      get { return ((FixedValueParameter<IntValue>)Parameters["Seed"]).Value.Value; }
111      set { ((FixedValueParameter<IntValue>)Parameters["Seed"]).Value.Value = value; }
112    }
113
114    public IAnalyzer Analyzer {
115      get { return ((ValueParameter<IAnalyzer>)Parameters["Analyzer"]).Value; }
116      set { ((ValueParameter<IAnalyzer>)Parameters["Analyzer"]).Value = value; }
117    }
118
119    public IConstrainedValueParameter<ISolutionModelTrainer<TPopulationContext>> SolutionModelTrainerParameter {
120      get { return (IConstrainedValueParameter<ISolutionModelTrainer<TPopulationContext>>)Parameters["SolutionModelTrainer"]; }
121    }
122
123    public IConstrainedValueParameter<ILocalSearch<TSolutionContext>> LocalSearchParameter {
124      get { return (IConstrainedValueParameter<ILocalSearch<TSolutionContext>>)Parameters["LocalSearch"]; }
125    }
126
127    [Storable]
128    private TPopulationContext context;
129    public TPopulationContext Context {
130      get { return context; }
131      protected set {
132        if (context == value) return;
133        context = value;
134        OnPropertyChanged("State");
135      }
136    }
137
138    [Storable]
139    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
140    [Storable]
141    private QualityPerClockAnalyzer qualityPerClockAnalyzer;
142    [Storable]
143    private QualityPerEvaluationsAnalyzer qualityPerEvaluationsAnalyzer;
144
145    [StorableConstructor]
146    protected MemPRAlgorithm(bool deserializing) : base(deserializing) { }
147    protected MemPRAlgorithm(MemPRAlgorithm<TProblem, TSolution, TPopulationContext, TSolutionContext> original, Cloner cloner) : base(original, cloner) {
148      context = cloner.Clone(original.context);
149      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
150      qualityPerClockAnalyzer = cloner.Clone(original.qualityPerClockAnalyzer);
151      qualityPerEvaluationsAnalyzer = cloner.Clone(original.qualityPerEvaluationsAnalyzer);
152
153      RegisterEventHandlers();
154    }
155    protected MemPRAlgorithm() {
156      Parameters.Add(new ValueParameter<IAnalyzer>("Analyzer", "The analyzer to apply to the population.", new MultiAnalyzer()));
157      Parameters.Add(new FixedValueParameter<IntValue>("MaximumPopulationSize", "The maximum size of the population that is evolved.", new IntValue(20)));
158      Parameters.Add(new OptionalValueParameter<IntValue>("MaximumEvaluations", "The maximum number of solution evaluations."));
159      Parameters.Add(new OptionalValueParameter<TimeSpanValue>("MaximumExecutionTime", "The maximum runtime.", new TimeSpanValue(TimeSpan.FromMinutes(10))));
160      Parameters.Add(new OptionalValueParameter<DoubleValue>("TargetQuality", "The target quality at which the algorithm terminates."));
161      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether each run of the algorithm should be conducted with a new random seed.", new BoolValue(true)));
162      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The random number seed that is used in case SetSeedRandomly is false.", new IntValue(0)));
163      Parameters.Add(new ConstrainedValueParameter<ISolutionModelTrainer<TPopulationContext>>("SolutionModelTrainer", "The object that creates a solution model that can be sampled."));
164      Parameters.Add(new ConstrainedValueParameter<ILocalSearch<TSolutionContext>>("LocalSearch", "The local search operator to use."));
165
166      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
167      qualityPerClockAnalyzer = new QualityPerClockAnalyzer();
168      qualityPerEvaluationsAnalyzer = new QualityPerEvaluationsAnalyzer();
169
170      RegisterEventHandlers();
171    }
172
173    [StorableHook(HookType.AfterDeserialization)]
174    private void AfterDeserialization() {
175      RegisterEventHandlers();
176    }
177
178    private void RegisterEventHandlers() {
179      MaximumPopulationSizeParameter.Value.ValueChanged += MaximumPopulationSizeOnChanged;
180    }
181
182    private void MaximumPopulationSizeOnChanged(object sender, EventArgs eventArgs) {
183      if (ExecutionState == ExecutionState.Started || ExecutionState == ExecutionState.Paused)
184        throw new InvalidOperationException("Cannot change maximum population size before algorithm finishes.");
185      Prepare();
186    }
187
188    protected override void OnProblemChanged() {
189      base.OnProblemChanged();
190      qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
191      qualityAnalyzer.MaximizationParameter.Hidden = true;
192      qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
193      qualityAnalyzer.QualityParameter.Depth = 1;
194      qualityAnalyzer.QualityParameter.Hidden = true;
195      qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
196      qualityAnalyzer.BestKnownQualityParameter.Hidden = true;
197
198      var multiAnalyzer = Analyzer as MultiAnalyzer;
199      if (multiAnalyzer != null) {
200        multiAnalyzer.Operators.Clear();
201        if (Problem != null) {
202          foreach (var analyzer in Problem.Operators.OfType<IAnalyzer>()) {
203            foreach (var param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
204              param.Depth = 1;
205            multiAnalyzer.Operators.Add(analyzer, analyzer.EnabledByDefault || analyzer is ISimilarityBasedOperator);
206          }
207        }
208        multiAnalyzer.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
209        multiAnalyzer.Operators.Add(qualityPerClockAnalyzer, true);
210        multiAnalyzer.Operators.Add(qualityPerEvaluationsAnalyzer, true);
211      }
212    }
213
214    public override void Prepare() {
215      base.Prepare();
216      Results.Clear();
217      Context = null;
218    }
219
220    protected virtual TPopulationContext CreateContext() {
221      return new TPopulationContext();
222    }
223
224    public void StartSync() {
225      using (var w = new AutoResetEvent(false)) {
226        EventHandler handler = (sender, e) => {
227          if (ExecutionState == ExecutionState.Paused
228          || ExecutionState == ExecutionState.Stopped)
229            w.Set();
230        };
231        ExecutionStateChanged += handler;
232        try {
233          Start();
234          w.WaitOne();
235        } finally { ExecutionStateChanged -= handler; }
236      }
237    }
238
239    protected sealed override void Run(CancellationToken token) {
240      if (Context == null) {
241        Context = CreateContext();
242        if (SetSeedRandomly) Seed = new System.Random().Next();
243        Context.Random.Reset(Seed);
244        Context.Scope.Variables.Add(new Variable("Results", Results));
245        Context.Problem = Problem;
246      }
247
248      if (MaximumExecutionTime.HasValue)
249        CancellationTokenSource.CancelAfter(MaximumExecutionTime.Value);
250
251      IExecutionContext context = null;
252      foreach (var item in Problem.ExecutionContextItems)
253        context = new Core.ExecutionContext(context, item, Context.Scope);
254      context = new Core.ExecutionContext(context, this, Context.Scope);
255      Context.Parent = context;
256
257      if (!Context.Initialized) {
258        // We initialize the population with two local optima
259        while (Context.PopulationCount < 2) {
260          var child = Create(token);
261          Context.LocalSearchEvaluations += HillClimb(child, token);
262          Context.LocalOptimaLevel += child.Fitness;
263          Context.AddToPopulation(child);
264          Context.BestQuality = child.Fitness;
265          Analyze(CancellationToken.None);
266          token.ThrowIfCancellationRequested();
267          if (Terminate()) return;
268        }
269        Context.LocalSearchEvaluations /= 2;
270        Context.LocalOptimaLevel /= 2;
271        Context.Initialized = true;
272      }
273
274      while (!Terminate()) {
275        Iterate(token);
276        Analyze(token);
277        token.ThrowIfCancellationRequested();
278      }
279    }
280
281    private void Iterate(CancellationToken token) {
282      var replaced = false;
283      ISingleObjectiveSolutionScope<TSolution> offspring = null;
284     
285      offspring = Breed(token);
286      if (offspring != null) {
287        var replNew = Replace(offspring, token);
288        if (replNew) {
289          replaced = true;
290          Context.ByBreeding++;
291        }
292      }
293
294      offspring = Relink(token);
295      if (offspring != null) {
296        if (Replace(offspring, token)) {
297          replaced = true;
298          Context.ByRelinking++;
299        }
300      }
301
302      offspring = Delink(token);
303      if (offspring != null) {
304        if (Replace(offspring, token)) {
305          replaced = true;
306          Context.ByDelinking++;
307        }
308      }
309
310      offspring = Sample(token);
311      if (offspring != null) {
312        if (Replace(offspring, token)) {
313          replaced = true;
314          Context.BySampling++;
315        }
316      }
317
318      if (!replaced && offspring != null) {
319        if (Context.HillclimbingSuited(offspring.Fitness)) {
320          HillClimb(offspring, token, CalculateSubspace(Context.Population.Select(x => x.Solution)));
321          if (Replace(offspring, token)) {
322            Context.ByHillclimbing++;
323            replaced = true;
324          }
325        }
326      }
327
328      if (!replaced) {
329        var before = Context.Population.SampleRandom(Context.Random);
330        offspring = (ISingleObjectiveSolutionScope<TSolution>)before.Clone();
331        AdaptiveWalk(offspring, Context.LocalSearchEvaluations * 2, token);
332        if (!Eq(before, offspring))
333          Context.AddAdaptivewalkingResult(before, offspring);
334        if (Replace(offspring, token)) {
335          Context.ByAdaptivewalking++;
336          replaced = true;
337        }
338      }
339
340      Context.Iterations++;
341    }
342
343    protected void Analyze(CancellationToken token) {
344      IResult res;
345      if (!Results.TryGetValue("EvaluatedSolutions", out res))
346        Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
347      else ((IntValue)res.Value).Value = Context.EvaluatedSolutions;
348      if (!Results.TryGetValue("Iterations", out res))
349        Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
350      else ((IntValue)res.Value).Value = Context.Iterations;
351      if (!Results.TryGetValue("LocalSearch Evaluations", out res))
352        Results.Add(new Result("LocalSearch Evaluations", new IntValue(Context.LocalSearchEvaluations)));
353      else ((IntValue)res.Value).Value = Context.LocalSearchEvaluations;
354      if (!Results.TryGetValue("ByBreeding", out res))
355        Results.Add(new Result("ByBreeding", new IntValue(Context.ByBreeding)));
356      else ((IntValue)res.Value).Value = Context.ByBreeding;
357      if (!Results.TryGetValue("ByRelinking", out res))
358        Results.Add(new Result("ByRelinking", new IntValue(Context.ByRelinking)));
359      else ((IntValue)res.Value).Value = Context.ByRelinking;
360      if (!Results.TryGetValue("ByDelinking", out res))
361        Results.Add(new Result("ByDelinking", new IntValue(Context.ByDelinking)));
362      else ((IntValue)res.Value).Value = Context.ByDelinking;
363      if (!Results.TryGetValue("BySampling", out res))
364        Results.Add(new Result("BySampling", new IntValue(Context.BySampling)));
365      else ((IntValue)res.Value).Value = Context.BySampling;
366      if (!Results.TryGetValue("ByHillclimbing", out res))
367        Results.Add(new Result("ByHillclimbing", new IntValue(Context.ByHillclimbing)));
368      else ((IntValue)res.Value).Value = Context.ByHillclimbing;
369      if (!Results.TryGetValue("ByAdaptivewalking", out res))
370        Results.Add(new Result("ByAdaptivewalking", new IntValue(Context.ByAdaptivewalking)));
371      else ((IntValue)res.Value).Value = Context.ByAdaptivewalking;
372
373      var sp = new ScatterPlot("Breeding Correlation", "");
374      sp.Rows.Add(new ScatterPlotDataRow("Parent1 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 }});
375      sp.Rows.Add(new ScatterPlotDataRow("Parent2 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
376      sp.Rows.Add(new ScatterPlotDataRow("Parent Distance vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
377      if (!Results.TryGetValue("BreedingStat", out res)) {
378        Results.Add(new Result("BreedingStat", sp));
379      } else res.Value = sp;
380
381      sp = new ScatterPlot("Relinking Correlation", "");
382      sp.Rows.Add(new ScatterPlotDataRow("A vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 } });
383      sp.Rows.Add(new ScatterPlotDataRow("B vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
384      sp.Rows.Add(new ScatterPlotDataRow("d(A,B) vs Offspring", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
385      if (!Results.TryGetValue("RelinkingStat", out res)) {
386        Results.Add(new Result("RelinkingStat", sp));
387      } else res.Value = sp;
388
389      sp = new ScatterPlot("Delinking Correlation", "");
390      sp.Rows.Add(new ScatterPlotDataRow("A vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item4))) { VisualProperties = { PointSize = 6 } });
391      sp.Rows.Add(new ScatterPlotDataRow("B vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item4))) { VisualProperties = { PointSize = 6 } });
392      sp.Rows.Add(new ScatterPlotDataRow("d(A,B) vs Offspring", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item3, x.Item4))) { VisualProperties = { PointSize = 6 } });
393      if (!Results.TryGetValue("DelinkingStat", out res)) {
394        Results.Add(new Result("DelinkingStat", sp));
395      } else res.Value = sp;
396
397      sp = new ScatterPlot("Sampling Correlation", "");
398      sp.Rows.Add(new ScatterPlotDataRow("AvgFitness vs Sample", "", Context.SamplingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
399      if (!Results.TryGetValue("SampleStat", out res)) {
400        Results.Add(new Result("SampleStat", sp));
401      } else res.Value = sp;
402
403      sp = new ScatterPlot("Hillclimbing Correlation", "");
404      sp.Rows.Add(new ScatterPlotDataRow("Start vs Improvement", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
405      if (!Results.TryGetValue("HillclimbingStat", out res)) {
406        Results.Add(new Result("HillclimbingStat", sp));
407      } else res.Value = sp;
408
409      sp = new ScatterPlot("Adaptivewalking Correlation", "");
410      sp.Rows.Add(new ScatterPlotDataRow("Start vs Best", "", Context.AdaptivewalkingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
411      if (!Results.TryGetValue("AdaptivewalkingStat", out res)) {
412        Results.Add(new Result("AdaptivewalkingStat", sp));
413      } else res.Value = sp;
414
415      Context.RunOperator(Analyzer, Context.Scope, token);
416    }
417
418    protected bool Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) {
419      if (double.IsNaN(child.Fitness)) {
420        Context.Evaluate(child, token);
421        Context.IncrementEvaluatedSolutions(1);
422      }
423      if (Context.IsBetter(child.Fitness, Context.BestQuality)) {
424        Context.BestQuality = child.Fitness;
425        Context.BestSolution = (TSolution)child.Solution.Clone();
426      }
427
428      var popSize = MaximumPopulationSize;
429      if (Context.Population.All(p => !Eq(p, child))) {
430
431        if (Context.PopulationCount < popSize) {
432          Context.AddToPopulation(child);
433          return true;// Context.PopulationCount - 1;
434        }
435       
436        // The set of replacement candidates consists of all solutions at least as good as the new one
437        var candidates = Context.Population.Select((p, i) => new { Index = i, Individual = p })
438                                         .Where(x => x.Individual.Fitness == child.Fitness
439                                           || Context.IsBetter(child, x.Individual)).ToList();
440        if (candidates.Count == 0) return false;// -1;
441
442        var repCand = -1;
443        var avgChildDist = 0.0;
444        var minChildDist = double.MaxValue;
445        var plateau = new List<int>();
446        var worstPlateau = -1;
447        var minAvgPlateauDist = double.MaxValue;
448        var minPlateauDist = double.MaxValue;
449        // If there are equally good solutions it is first tried to replace one of those
450        // The criteria for replacement is that the new solution has better average distance
451        // to all other solutions at this "plateau"
452        foreach (var c in candidates.Where(x => x.Individual.Fitness == child.Fitness)) {
453          var dist = Dist(c.Individual, child);
454          avgChildDist += dist;
455          if (dist < minChildDist) minChildDist = dist;
456          plateau.Add(c.Index);
457        }
458        if (plateau.Count > 2) {
459          avgChildDist /= plateau.Count;
460          foreach (var p in plateau) {
461            var avgDist = 0.0;
462            var minDist = double.MaxValue;
463            foreach (var q in plateau) {
464              if (p == q) continue;
465              var dist = Dist(Context.AtPopulation(p), Context.AtPopulation(q));
466              avgDist += dist;
467              if (dist < minDist) minDist = dist;
468            }
469
470            var d = Dist(Context.AtPopulation(p), child);
471            avgDist += d;
472            avgDist /= plateau.Count;
473            if (d < minDist) minDist = d;
474
475            if (minDist < minPlateauDist || (minDist == minPlateauDist && avgDist < avgChildDist)) {
476              minAvgPlateauDist = avgDist;
477              minPlateauDist = minDist;
478              worstPlateau = p;
479            }
480          }
481          if (minPlateauDist < minChildDist || (minPlateauDist == minChildDist && minAvgPlateauDist < avgChildDist))
482            repCand = worstPlateau;
483        }
484
485        if (repCand < 0) {
486          // If no solution at the same plateau were identified for replacement
487          // a worse solution with smallest distance is chosen
488          var minDist = double.MaxValue;
489          foreach (var c in candidates.Where(x => Context.IsBetter(child, x.Individual))) {
490            var d = Dist(c.Individual, child);
491            if (d < minDist) {
492              minDist = d;
493              repCand = c.Index;
494            }
495          }
496        }
497
498        // If no replacement was identified, this can only mean that there are
499        // no worse solutions and those on the same plateau are all better
500        // stretched out than the new one
501        if (repCand < 0) return false;// -1;
502       
503        Context.ReplaceAtPopulation(repCand, child);
504        return true;// repCand;
505      }
506      return false;// -1;
507    }
508
509    protected bool Eq(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b) {
510      return Eq(a.Solution, b.Solution);
511    }
512    protected abstract bool Eq(TSolution a, TSolution b);
513    protected abstract double Dist(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b);
514    protected abstract ISolutionSubspace<TSolution> CalculateSubspace(IEnumerable<TSolution> solutions, bool inverse = false);
515
516    #region Create
517    protected virtual ISingleObjectiveSolutionScope<TSolution> Create(CancellationToken token) {
518      var child = Context.ToScope(null);
519      Context.RunOperator(Problem.SolutionCreator, child, token);
520      return child;
521    }
522    #endregion
523
524    #region Improve
525    protected virtual int HillClimb(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
526      if (double.IsNaN(scope.Fitness)) {
527        Context.Evaluate(scope, token);
528        Context.IncrementEvaluatedSolutions(1);
529      }
530      var before = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
531      var lscontext = Context.CreateSingleSolutionContext(scope);
532      LocalSearchParameter.Value.Optimize(lscontext);
533      Context.AddHillclimbingResult(before, scope);
534      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
535      return lscontext.EvaluatedSolutions;
536    }
537
538    protected virtual void AdaptiveClimb(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
539      if (double.IsNaN(scope.Fitness)) {
540        Context.Evaluate(scope, token);
541        Context.IncrementEvaluatedSolutions(1);
542      }
543      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
544      AdaptiveWalk(newScope, maxEvals, token, subspace);
545     
546      Context.AddAdaptivewalkingResult(scope, newScope);
547      if (Context.IsBetter(newScope, scope)) {
548        scope.Adopt(newScope);
549      }
550    }
551    protected abstract void AdaptiveWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
552   
553    #endregion
554
555    #region Breed
556    protected virtual ISingleObjectiveSolutionScope<TSolution> Breed(CancellationToken token) {
557      var i1 = Context.Random.Next(Context.PopulationCount);
558      var i2 = Context.Random.Next(Context.PopulationCount);
559      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
560
561      var p1 = Context.AtPopulation(i1);
562      var p2 = Context.AtPopulation(i2);
563
564      if (double.IsNaN(p1.Fitness)) {
565        Context.Evaluate(p1, token);
566        Context.IncrementEvaluatedSolutions(1);
567      }
568      if (double.IsNaN(p2.Fitness)) {
569        Context.Evaluate(p2, token);
570        Context.IncrementEvaluatedSolutions(1);
571      }
572
573      if (!Context.BreedingSuited(p1, p2, Dist(p1, p2))) return null;
574
575      var offspring = Breed(p1, p2, token);
576
577      if (double.IsNaN(offspring.Fitness)) {
578        Context.Evaluate(offspring, token);
579        Context.IncrementEvaluatedSolutions(1);
580      }
581
582      Context.AddBreedingResult(p1, p2, Dist(p1, p2), offspring);
583
584      // new best solutions are improved using hill climbing in full solution space
585      if (Context.Population.All(p => Context.IsBetter(offspring, p)))
586        HillClimb(offspring, token);
587      else if (!Eq(offspring, p1) && !Eq(offspring, p2) && Context.HillclimbingSuited(offspring.Fitness))
588        HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));
589
590      return offspring;
591    }
592
593    protected abstract ISingleObjectiveSolutionScope<TSolution> Breed(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2, CancellationToken token);
594    #endregion
595
596    #region Relink/Delink
597    protected virtual ISingleObjectiveSolutionScope<TSolution> Relink(CancellationToken token) {
598      var i1 = Context.Random.Next(Context.PopulationCount);
599      var i2 = Context.Random.Next(Context.PopulationCount);
600      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
601
602      var p1 = Context.AtPopulation(i1);
603      var p2 = Context.AtPopulation(i2);
604
605      if (!Context.RelinkSuited(p1, p2, Dist(p1, p2))) return null;
606
607      var link = PerformRelinking(p1, p2, token, delink: false);
608
609      // new best solutions are improved using hill climbing in full solution space
610      if (Context.Population.All(p => Context.IsBetter(link, p)))
611        HillClimb(link, token);
612      else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
613        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: true));
614
615      return link;
616    }
617
618    protected virtual ISingleObjectiveSolutionScope<TSolution> Delink(CancellationToken token) {
619      var i1 = Context.Random.Next(Context.PopulationCount);
620      var i2 = Context.Random.Next(Context.PopulationCount);
621      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
622
623      var p1 = Context.AtPopulation(i1);
624      var p2 = Context.AtPopulation(i2);
625     
626      if (!Context.DelinkSuited(p1, p2, Dist(p1, p2))) return null;
627
628      var link = PerformRelinking(p1, p2, token, delink: true);
629
630      // new best solutions are improved using hill climbing in full solution space
631      if (Context.Population.All(p => Context.IsBetter(link, p)))
632        HillClimb(link, token);
633      // intentionally not making hill climbing otherwise after delinking in sub-space
634      return link;
635    }
636
637    protected virtual ISingleObjectiveSolutionScope<TSolution> PerformRelinking(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false) {
638      var relink = Link(a, b, token, delink);
639
640      if (double.IsNaN(relink.Fitness)) {
641        Context.Evaluate(relink, token);
642        Context.IncrementEvaluatedSolutions(1);
643      }
644
645      if (delink) {
646        Context.AddDelinkingResult(a, b, Dist(a, b), relink);
647      } else {
648        Context.AddRelinkingResult(a, b, Dist(a, b), relink);
649      }
650
651      return relink;
652    }
653
654    protected abstract ISingleObjectiveSolutionScope<TSolution> Link(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false);
655    #endregion
656
657    #region Sample
658    protected virtual ISingleObjectiveSolutionScope<TSolution> Sample(CancellationToken token) {
659      if (Context.PopulationCount == MaximumPopulationSize) {
660        SolutionModelTrainerParameter.Value.TrainModel(Context);
661        ISingleObjectiveSolutionScope<TSolution> bestSample = null;
662        var tries = 1;
663        var avgDist = (from a in Context.Population.Shuffle(Context.Random)
664                       from b in Context.Population.Shuffle(Context.Random)
665                       select Dist(a, b)).Average();
666        for (; tries < 100; tries++) {
667          var sample = Context.ToScope(Context.Model.Sample());
668          Context.Evaluate(sample, token);
669          if (bestSample == null || Context.IsBetter(sample, bestSample)) {
670            bestSample = sample;
671            if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
672          }
673          if (!Context.SamplingSuited(avgDist)) break;
674        }
675        Context.IncrementEvaluatedSolutions(tries);
676        Context.AddSamplingResult(bestSample, avgDist);
677        return bestSample;
678      }
679      return null;
680    }
681    #endregion
682
683    protected virtual bool Terminate() {
684      var maximization = ((IValueParameter<BoolValue>)Problem.MaximizationParameter).Value.Value;
685      return MaximumEvaluations.HasValue && Context.EvaluatedSolutions >= MaximumEvaluations.Value
686        || MaximumExecutionTime.HasValue && ExecutionTime >= MaximumExecutionTime.Value
687        || TargetQuality.HasValue && (maximization && Context.BestQuality >= TargetQuality.Value
688                                  || !maximization && Context.BestQuality <= TargetQuality.Value);
689    }
690
691    public event PropertyChangedEventHandler PropertyChanged;
692    protected void OnPropertyChanged(string property) {
693      var handler = PropertyChanged;
694      if (handler != null) handler(this, new PropertyChangedEventArgs(property));
695    }
696  }
697}
Note: See TracBrowser for help on using the repository browser.