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

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

#2701:

  • Added BinaryVectorEqualityComparer (identical to the one in the P3 plugin) to binaryvector plugin
  • Added delinking for absolute coded permutations
  • Some tweaks
File size: 34.3 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.LocalOptimaLevel += child.Fitness;
233          Context.AddToPopulation(child);
234          Context.BestQuality = child.Fitness;
235          Analyze(token);
236          token.ThrowIfCancellationRequested();
237          if (Terminate()) return;
238        }
239        Context.LocalSearchEvaluations /= 2;
240        Context.LocalOptimaLevel /= 2;
241        Context.Initialized = true;
242      }
243
244      while (!Terminate()) {
245        Iterate(token);
246        Analyze(token);
247        token.ThrowIfCancellationRequested();
248      }
249    }
250
251    private void Iterate(CancellationToken token) {
252      var replaced = false;
253      ISingleObjectiveSolutionScope<TSolution> offspring = null;
254     
255      offspring = Breed(token);
256      if (offspring != null) {
257        if (Context.PopulationCount < MaximumPopulationSize)
258          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
259        var replNew = Replace(offspring, token);
260        if (replNew) {
261          replaced = true;
262          Context.ByBreeding++;
263        }
264      }
265
266      offspring = Relink(token);
267      if (offspring != null) {
268        if (Context.PopulationCount < MaximumPopulationSize)
269          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
270        if (Replace(offspring, token)) {
271          replaced = true;
272          Context.ByRelinking++;
273        }
274      }
275
276      offspring = Delink(token);
277      if (offspring != null) {
278        if (Context.PopulationCount < MaximumPopulationSize)
279          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
280        if (Replace(offspring, token)) {
281          replaced = true;
282          Context.ByDelinking++;
283        }
284      }
285
286      offspring = Sample(token);
287      if (offspring != null) {
288        if (Context.PopulationCount < MaximumPopulationSize)
289          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
290        if (Replace(offspring, token)) {
291          replaced = true;
292          Context.BySampling++;
293        }
294      }
295
296      if (!replaced && offspring != null) {
297        if (Context.HillclimbingSuited(offspring)) {
298          AdaptiveClimb(offspring, Context.LocalSearchEvaluations, token);
299          if (Replace(offspring, token)) {
300            Context.ByHillclimbing++;
301            replaced = true;
302          }
303        }
304      }
305
306      if (!replaced) {
307        offspring = (ISingleObjectiveSolutionScope<TSolution>)Context.Population.SampleRandom(Context.Random).Clone();
308        var before = offspring.Fitness;
309        AdaptiveWalk(offspring, Context.LocalSearchEvaluations * 2, token);
310        Context.AdaptivewalkingStat.Add(Tuple.Create(before, offspring.Fitness));
311        if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
312        if (Replace(offspring, token)) {
313          Context.ByAdaptivewalking++;
314          replaced = true;
315        }
316      }
317
318      Context.Iterations++;
319    }
320
321    protected void Analyze(CancellationToken token) {
322      IResult res;
323      if (!Results.TryGetValue("EvaluatedSolutions", out res))
324        Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
325      else ((IntValue)res.Value).Value = Context.EvaluatedSolutions;
326      if (!Results.TryGetValue("Iterations", out res))
327        Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
328      else ((IntValue)res.Value).Value = Context.Iterations;
329      if (!Results.TryGetValue("LocalSearch Evaluations", out res))
330        Results.Add(new Result("LocalSearch Evaluations", new IntValue(Context.LocalSearchEvaluations)));
331      else ((IntValue)res.Value).Value = Context.LocalSearchEvaluations;
332      if (!Results.TryGetValue("ByBreeding", out res))
333        Results.Add(new Result("ByBreeding", new IntValue(Context.ByBreeding)));
334      else ((IntValue)res.Value).Value = Context.ByBreeding;
335      if (!Results.TryGetValue("ByRelinking", out res))
336        Results.Add(new Result("ByRelinking", new IntValue(Context.ByRelinking)));
337      else ((IntValue)res.Value).Value = Context.ByRelinking;
338      if (!Results.TryGetValue("ByDelinking", out res))
339        Results.Add(new Result("ByDelinking", new IntValue(Context.ByDelinking)));
340      else ((IntValue)res.Value).Value = Context.ByDelinking;
341      if (!Results.TryGetValue("BySampling", out res))
342        Results.Add(new Result("BySampling", new IntValue(Context.BySampling)));
343      else ((IntValue)res.Value).Value = Context.BySampling;
344      if (!Results.TryGetValue("ByHillclimbing", out res))
345        Results.Add(new Result("ByHillclimbing", new IntValue(Context.ByHillclimbing)));
346      else ((IntValue)res.Value).Value = Context.ByHillclimbing;
347      if (!Results.TryGetValue("ByAdaptivewalking", out res))
348        Results.Add(new Result("ByAdaptivewalking", new IntValue(Context.ByAdaptivewalking)));
349      else ((IntValue)res.Value).Value = Context.ByAdaptivewalking;
350
351      var sp = new ScatterPlot("Breeding Correlation", "");
352      sp.Rows.Add(new ScatterPlotDataRow("Parent1 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 }});
353      sp.Rows.Add(new ScatterPlotDataRow("Parent2 vs Offspring", "", Context.BreedingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
354      if (!Results.TryGetValue("BreedingStat", out res)) {
355        Results.Add(new Result("BreedingStat", sp));
356      } else res.Value = sp;
357
358      sp = new ScatterPlot("Relinking Correlation", "");
359      sp.Rows.Add(new ScatterPlotDataRow("A vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
360      sp.Rows.Add(new ScatterPlotDataRow("B vs Relink", "", Context.RelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
361      if (!Results.TryGetValue("RelinkingStat", out res)) {
362        Results.Add(new Result("RelinkingStat", sp));
363      } else res.Value = sp;
364
365      sp = new ScatterPlot("Delinking Correlation", "");
366      sp.Rows.Add(new ScatterPlotDataRow("A vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item1, x.Item3))) { VisualProperties = { PointSize = 6 } });
367      sp.Rows.Add(new ScatterPlotDataRow("B vs Delink", "", Context.DelinkingStat.Select(x => new Point2D<double>(x.Item2, x.Item3))) { VisualProperties = { PointSize = 6 } });
368      if (!Results.TryGetValue("DelinkingStat", out res)) {
369        Results.Add(new Result("DelinkingStat", sp));
370      } else res.Value = sp;
371
372      sp = new ScatterPlot("Sampling Correlation", "");
373      sp.Rows.Add(new ScatterPlotDataRow("AvgFitness vs Sample", "", Context.SamplingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
374      if (!Results.TryGetValue("SampleStat", out res)) {
375        Results.Add(new Result("SampleStat", sp));
376      } else res.Value = sp;
377
378      sp = new ScatterPlot("Hillclimbing Correlation", "");
379      sp.Rows.Add(new ScatterPlotDataRow("Start vs End", "", Context.HillclimbingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
380      if (!Results.TryGetValue("HillclimbingStat", out res)) {
381        Results.Add(new Result("HillclimbingStat", sp));
382      } else res.Value = sp;
383
384      sp = new ScatterPlot("Adaptivewalking Correlation", "");
385      sp.Rows.Add(new ScatterPlotDataRow("Start vs Best", "", Context.AdaptivewalkingStat.Select(x => new Point2D<double>(x.Item1, x.Item2))) { VisualProperties = { PointSize = 6 } });
386      if (!Results.TryGetValue("AdaptivewalkingStat", out res)) {
387        Results.Add(new Result("AdaptivewalkingStat", sp));
388      } else res.Value = sp;
389
390      if (Context.BreedingPerformanceModel != null) {
391        var sol = Context.GetSolution(Context.BreedingPerformanceModel, Context.BreedingStat);
392        if (!Results.TryGetValue("Breeding Performance", out res)) {
393          Results.Add(new Result("Breeding Performance", sol));
394        } else res.Value = sol;
395      }
396      if (Context.RelinkingPerformanceModel != null) {
397        var sol = Context.GetSolution(Context.RelinkingPerformanceModel, Context.RelinkingStat);
398        if (!Results.TryGetValue("Relinking Performance", out res)) {
399          Results.Add(new Result("Relinking Performance", sol));
400        } else res.Value = sol;
401      }
402      if (Context.DelinkingPerformanceModel != null) {
403        var sol = Context.GetSolution(Context.DelinkingPerformanceModel, Context.DelinkingStat);
404        if (!Results.TryGetValue("Delinking Performance", out res)) {
405          Results.Add(new Result("Delinking Performance", sol));
406        } else res.Value = sol;
407      }
408      if (Context.SamplingPerformanceModel != null) {
409        var sol = Context.GetSolution(Context.SamplingPerformanceModel, Context.SamplingStat);
410        if (!Results.TryGetValue("Sampling Performance", out res)) {
411          Results.Add(new Result("Sampling Performance", sol));
412        } else res.Value = sol;
413      }
414      if (Context.HillclimbingPerformanceModel != null) {
415        var sol = Context.GetSolution(Context.HillclimbingPerformanceModel, Context.HillclimbingStat);
416        if (!Results.TryGetValue("Hillclimbing Performance", out res)) {
417          Results.Add(new Result("Hillclimbing Performance", sol));
418        } else res.Value = sol;
419      }
420      if (Context.AdaptiveWalkPerformanceModel != null) {
421        var sol = Context.GetSolution(Context.AdaptiveWalkPerformanceModel, Context.AdaptivewalkingStat);
422        if (!Results.TryGetValue("Adaptivewalk Performance", out res)) {
423          Results.Add(new Result("Adaptivewalk Performance", sol));
424        } else res.Value = sol;
425      }
426
427      RunOperator(Analyzer, Context.Scope, token);
428    }
429
430    protected bool Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) {
431      if (double.IsNaN(child.Fitness)) {
432        Evaluate(child, token);
433        Context.IncrementEvaluatedSolutions(1);
434      }
435      if (Context.IsBetter(child.Fitness, Context.BestQuality)) {
436        Context.BestQuality = child.Fitness;
437        Context.BestSolution = (TSolution)child.Solution.Clone();
438      }
439
440      var popSize = MaximumPopulationSize;
441      if (Context.Population.All(p => !Eq(p, child))) {
442
443        if (Context.PopulationCount < popSize) {
444          Context.AddToPopulation(child);
445          return true;// Context.PopulationCount - 1;
446        }
447       
448        // The set of replacement candidates consists of all solutions at least as good as the new one
449        var candidates = Context.Population.Select((p, i) => new { Index = i, Individual = p })
450                                         .Where(x => x.Individual.Fitness == child.Fitness
451                                           || Context.IsBetter(child, x.Individual)).ToList();
452        if (candidates.Count == 0) return false;// -1;
453
454        var repCand = -1;
455        var avgChildDist = 0.0;
456        var minChildDist = double.MaxValue;
457        var plateau = new List<int>();
458        var worstPlateau = -1;
459        var minAvgPlateauDist = double.MaxValue;
460        var minPlateauDist = double.MaxValue;
461        // If there are equally good solutions it is first tried to replace one of those
462        // The criteria for replacement is that the new solution has better average distance
463        // to all other solutions at this "plateau"
464        foreach (var c in candidates.Where(x => x.Individual.Fitness == child.Fitness)) {
465          var dist = Dist(c.Individual, child);
466          avgChildDist += dist;
467          if (dist < minChildDist) minChildDist = dist;
468          plateau.Add(c.Index);
469        }
470        if (plateau.Count > 2) {
471          avgChildDist /= plateau.Count;
472          foreach (var p in plateau) {
473            var avgDist = 0.0;
474            var minDist = double.MaxValue;
475            foreach (var q in plateau) {
476              if (p == q) continue;
477              var dist = Dist(Context.AtPopulation(p), Context.AtPopulation(q));
478              avgDist += dist;
479              if (dist < minDist) minDist = dist;
480            }
481
482            var d = Dist(Context.AtPopulation(p), child);
483            avgDist += d;
484            avgDist /= plateau.Count;
485            if (d < minDist) minDist = d;
486
487            if (minDist < minPlateauDist || (minDist == minPlateauDist && avgDist < avgChildDist)) {
488              minAvgPlateauDist = avgDist;
489              minPlateauDist = minDist;
490              worstPlateau = p;
491            }
492          }
493          if (minPlateauDist < minChildDist || (minPlateauDist == minChildDist && minAvgPlateauDist < avgChildDist))
494            repCand = worstPlateau;
495        }
496
497        if (repCand < 0) {
498          // If no solution at the same plateau were identified for replacement
499          // a worse solution with smallest distance is chosen
500          var minDist = double.MaxValue;
501          foreach (var c in candidates.Where(x => Context.IsBetter(child, x.Individual))) {
502            var d = Dist(c.Individual, child);
503            if (d < minDist) {
504              minDist = d;
505              repCand = c.Index;
506            }
507          }
508        }
509
510        // If no replacement was identified, this can only mean that there are
511        // no worse solutions and those on the same plateau are all better
512        // stretched out than the new one
513        if (repCand < 0) return false;// -1;
514       
515        Context.ReplaceAtPopulation(repCand, child);
516        return true;// repCand;
517      }
518      return false;// -1;
519    }
520
521    protected bool Eq(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b) {
522      return Eq(a.Solution, b.Solution);
523    }
524    protected abstract bool Eq(TSolution a, TSolution b);
525    protected abstract double Dist(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b);
526    protected abstract ISingleObjectiveSolutionScope<TSolution> ToScope(TSolution code, double fitness = double.NaN);
527    protected abstract ISolutionSubspace<TSolution> CalculateSubspace(IEnumerable<TSolution> solutions, bool inverse = false);
528    protected virtual void Evaluate(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token) {
529      var prob = Problem as ISingleObjectiveProblemDefinition;
530      if (prob != null) {
531        var ind = new SingleEncodingIndividual(prob.Encoding, scope);
532        scope.Fitness = prob.Evaluate(ind, Context.Random);
533      } else RunOperator(Problem.Evaluator, scope, token);
534    }
535
536    #region Create
537    protected virtual ISingleObjectiveSolutionScope<TSolution> Create(CancellationToken token) {
538      var child = ToScope(null);
539      RunOperator(Problem.SolutionCreator, child, token);
540      return child;
541    }
542    #endregion
543
544    #region Improve
545    protected virtual int HillClimb(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
546      if (double.IsNaN(scope.Fitness)) {
547        Evaluate(scope, token);
548        Context.IncrementEvaluatedSolutions(1);
549      }
550      var before = scope.Fitness;
551      var lscontext = Context.CreateSingleSolutionContext(scope);
552      LocalSearchParameter.Value.Optimize(lscontext);
553      var after = scope.Fitness;
554      Context.HillclimbingStat.Add(Tuple.Create(before, after));
555      if (Context.HillclimbingStat.Count % 10 == 0) Context.RelearnHillclimbingPerformanceModel();
556      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
557      return lscontext.EvaluatedSolutions;
558    }
559
560    protected virtual void AdaptiveClimb(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
561      if (double.IsNaN(scope.Fitness)) {
562        Evaluate(scope, token);
563        Context.IncrementEvaluatedSolutions(1);
564      }
565      var before = scope.Fitness;
566      var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
567      AdaptiveWalk(newScope, maxEvals, token, subspace);
568      Context.AdaptivewalkingStat.Add(Tuple.Create(before, newScope.Fitness));
569      if (Context.AdaptivewalkingStat.Count % 10 == 0) Context.RelearnAdaptiveWalkPerformanceModel();
570      if (Context.IsBetter(newScope, scope))
571        scope.Adopt(newScope);
572    }
573    protected abstract void AdaptiveWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
574   
575    #endregion
576
577    #region Breed
578    protected virtual ISingleObjectiveSolutionScope<TSolution> Breed(CancellationToken token) {
579      var i1 = Context.Random.Next(Context.PopulationCount);
580      var i2 = Context.Random.Next(Context.PopulationCount);
581      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
582
583      var p1 = Context.AtPopulation(i1);
584      var p2 = Context.AtPopulation(i2);
585
586      if (double.IsNaN(p1.Fitness)) {
587        Evaluate(p1, token);
588        Context.IncrementEvaluatedSolutions(1);
589      }
590      if (double.IsNaN(p2.Fitness)) {
591        Evaluate(p2, token);
592        Context.IncrementEvaluatedSolutions(1);
593      }
594
595      if (Context.BreedingSuited(p1, p2)) {
596        var offspring = Breed(p1, p2, token);
597
598        if (double.IsNaN(offspring.Fitness)) {
599          Evaluate(offspring, token);
600          Context.IncrementEvaluatedSolutions(1);
601        }
602
603        // new best solutions are improved using hill climbing in full solution space
604        if (Context.Population.All(p => Context.IsBetter(offspring, p)))
605          HillClimb(offspring, token);
606        else if (!Eq(offspring, p1) && !Eq(offspring, p2) && Context.HillclimbingSuited(offspring.Fitness))
607          HillClimb(offspring, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));
608
609        Context.AddBreedingResult(p1, p2, offspring);
610        if (Context.BreedingStat.Count % 10 == 0) Context.RelearnBreedingPerformanceModel();
611        return offspring;
612      }
613      return null;
614    }
615
616    protected abstract ISingleObjectiveSolutionScope<TSolution> Breed(ISingleObjectiveSolutionScope<TSolution> p1, ISingleObjectiveSolutionScope<TSolution> p2, CancellationToken token);
617    #endregion
618
619    #region Relink/Delink
620    protected virtual ISingleObjectiveSolutionScope<TSolution> Relink(CancellationToken token) {
621      var i1 = Context.Random.Next(Context.PopulationCount);
622      var i2 = Context.Random.Next(Context.PopulationCount);
623      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
624
625      var p1 = Context.AtPopulation(i1);
626      var p2 = Context.AtPopulation(i2);
627
628      if (!Context.RelinkSuited(p1, p2)) return null;
629
630      var link = PerformRelinking(p1, p2, token, delink: false);
631      if (double.IsNaN(link.Fitness)) {
632        Evaluate(link, token);
633        Context.IncrementEvaluatedSolutions(1);
634      }
635      // new best solutions are improved using hill climbing in full solution space
636      if (Context.Population.All(p => Context.IsBetter(link, p)))
637        HillClimb(link, token);
638      else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
639        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: true));
640
641      return link;
642    }
643
644    protected virtual ISingleObjectiveSolutionScope<TSolution> Delink(CancellationToken token) {
645      var i1 = Context.Random.Next(Context.PopulationCount);
646      var i2 = Context.Random.Next(Context.PopulationCount);
647      while (i1 == i2) i2 = Context.Random.Next(Context.PopulationCount);
648
649      var p1 = Context.AtPopulation(i1);
650      var p2 = Context.AtPopulation(i2);
651     
652      if (!Context.DelinkSuited(p1, p2)) return null;
653
654      var link = PerformRelinking(p1, p2, token, delink: true);
655      if (double.IsNaN(link.Fitness)) {
656        Evaluate(link, token);
657        Context.IncrementEvaluatedSolutions(1);
658      }
659      // new best solutions are improved using hill climbing in full solution space
660      if (Context.Population.All(p => Context.IsBetter(link, p)))
661        HillClimb(link, token);
662      /*else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
663        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));*/
664
665      return link;
666    }
667
668    protected virtual ISingleObjectiveSolutionScope<TSolution> PerformRelinking(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false) {
669      var relink = Link(a, b, token, delink);
670
671      if (double.IsNaN(relink.Fitness)) {
672        Evaluate(relink, token);
673        Context.IncrementEvaluatedSolutions(1);
674      }
675
676      // new best solutions are improved using hill climbing
677      if (Context.Population.All(p => Context.IsBetter(relink, p)))
678        HillClimb(relink, token);
679
680      if (delink) {
681        Context.AddDelinkingResult(a, b, relink);
682        if (Context.DelinkingStat.Count % 10 == 0) Context.RelearnDelinkingPerformanceModel();
683      } else {
684        Context.AddRelinkingResult(a, b, relink);
685        if (context.RelinkingStat.Count % 10 == 0) Context.RelearnRelinkingPerformanceModel();
686      }
687      return relink;
688    }
689
690    protected abstract ISingleObjectiveSolutionScope<TSolution> Link(ISingleObjectiveSolutionScope<TSolution> a, ISingleObjectiveSolutionScope<TSolution> b, CancellationToken token, bool delink = false);
691    #endregion
692
693    #region Sample
694    protected virtual ISingleObjectiveSolutionScope<TSolution> Sample(CancellationToken token) {
695      if (Context.PopulationCount == MaximumPopulationSize) {
696        SolutionModelTrainerParameter.Value.TrainModel(Context);
697        ISingleObjectiveSolutionScope<TSolution> bestSample = null;
698        var tries = 1;
699        for (; tries < 100; tries++) {
700          var sample = ToScope(Context.Model.Sample());
701          Evaluate(sample, token);
702          if (bestSample == null || Context.IsBetter(sample, bestSample)) {
703            bestSample = sample;
704            if (Context.Population.Any(x => !Context.IsBetter(x, bestSample))) break;
705          }
706          if (!Context.SamplingSuited()) break;
707        }
708        Context.IncrementEvaluatedSolutions(tries);
709        Context.AddSamplingResult(bestSample);
710        if (Context.SamplingStat.Count % 10 == 0) Context.RelearnSamplingPerformanceModel();
711        return bestSample;
712      }
713      return null;
714    }
715    #endregion
716
717    protected virtual bool Terminate() {
718      return MaximumEvaluations.HasValue && Context.EvaluatedSolutions >= MaximumEvaluations.Value
719        || MaximumExecutionTime.HasValue && ExecutionTime >= MaximumExecutionTime.Value
720        || TargetQuality.HasValue && (Problem.Maximization && Context.BestQuality >= TargetQuality.Value
721                                  || !Problem.Maximization && Context.BestQuality <= TargetQuality.Value);
722    }
723
724    public event PropertyChangedEventHandler PropertyChanged;
725    protected void OnPropertyChanged(string property) {
726      var handler = PropertyChanged;
727      if (handler != null) handler(this, new PropertyChangedEventArgs(property));
728    }
729
730    #region Engine Helper
731    protected void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {
732      var stack = new Stack<IOperation>();
733      stack.Push(Context.CreateChildOperation(op, scope));
734
735      while (stack.Count > 0) {
736        cancellationToken.ThrowIfCancellationRequested();
737
738        var next = stack.Pop();
739        if (next is OperationCollection) {
740          var coll = (OperationCollection)next;
741          for (int i = coll.Count - 1; i >= 0; i--)
742            if (coll[i] != null) stack.Push(coll[i]);
743        } else if (next is IAtomicOperation) {
744          var operation = (IAtomicOperation)next;
745          try {
746            next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
747          } catch (Exception ex) {
748            stack.Push(operation);
749            if (ex is OperationCanceledException) throw ex;
750            else throw new OperatorExecutionException(operation.Operator, ex);
751          }
752          if (next != null) stack.Push(next);
753        }
754      }
755    }
756    #endregion
757  }
758}
Note: See TracBrowser for help on using the repository browser.