Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14680 was 14680, checked in by abeham, 8 years ago

#2701: disabled learning

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