source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs @ 14544

Last change on this file since 14544 was 14544, checked in by abeham, 3 years ago

#2701:

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