Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2895_PushGP_GenealogyAnalysis/HeuristicLab.Problems.ProgramSynthesis.GenealogyAnalysis/Analyzers/GenealogyAnalyzer.cs @ 16811

Last change on this file since 16811 was 15771, checked in by bburlacu, 7 years ago

#2895: Add solution skeleton for PushGP with genealogy analysis.
File size: 16.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 License Information
21
22using System.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.ProgramSynthesis {
33  [StorableClass]
34  [Item("GenealogyAnalyzer", "An analyzer which performs the necessary instrumentation to record the evolution of a genetic algorithm.")]
35  public abstract class GenealogyAnalyzer<T> : SingleSuccessorOperator, IAnalyzer
36  where T : class, IItem {
37    #region parameter names
38    private const string GenerationsParameterName = "Generations";
39    private const string ResultsParameterName = "Results";
40    private const string PopulationGraphParameterName = "PopulationGraph";
41    public const string QualityParameterName = "Quality";
42    public const string PopulationParameterName = "SymbolicExpressionTree";
43
44    private const string CrossoverParameterName = "Crossover";
45    private const string ManipulatorParameterName = "Mutator";
46    private const string SolutionCreatorParameterName = "SolutionCreator";
47
48    private const string BeforeCrossoverOperatorParameterName = "BeforeCrossoverOperator";
49    private const string AfterCrossoverOperatorParameterName = "AfterCrossoverOperator";
50
51    private const string BeforeManipulatorOperatorParameterName = "BeforeManipulatorOperator";
52    private const string AfterManipulatorOperatorParameterName = "AfterManipulatorOperator";
53
54    private const string EnableCrossoverTrackingParameterName = "EnableCrossoverTracking";
55    private const string EnableManipulatorTrackingParameterName = "EnableManipulatorTracking";
56    private const string EnableSolutionCreatorTrackingParameterName = "EnableSolutionCreatorTracking"; // should always be enabled. maybe superfluous
57    private const string TrimOlderGenerationsParameterName = "TrimOlderGenerations";
58    #endregion parameter names
59
60    #region parameter properties
61
62    public IFixedValueParameter<BoolValue> TrimOlderGenerationsParameter {
63      get { return (IFixedValueParameter<BoolValue>)Parameters[TrimOlderGenerationsParameterName]; }
64    }
65
66    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
67      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
68    }
69
70    public IScopeTreeLookupParameter<T> PopulationParameter {
71      get { return (IScopeTreeLookupParameter<T>)Parameters[PopulationParameterName]; }
72    }
73
74    public IValueParameter<ICrossoverOperator<T>> BeforeCrossoverOperatorParameter {
75      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[BeforeCrossoverOperatorParameterName]; }
76    }
77
78    public IValueParameter<ICrossoverOperator<T>> AfterCrossoverOperatorParameter {
79      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[AfterCrossoverOperatorParameterName]; }
80    }
81
82    public IValueParameter<IManipulatorOperator<T>> BeforeManipulatorOperatorParameter {
83      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[BeforeManipulatorOperatorParameterName]; }
84    }
85
86    public IValueParameter<IManipulatorOperator<T>> AfterManipulatorOperatorParameter {
87      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[AfterManipulatorOperatorParameterName]; }
88    }
89
90    public ILookupParameter<ResultCollection> ResultsParameter {
91      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
92    }
93
94    public ILookupParameter<IntValue> GenerationsParameter {
95      get { return (ILookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
96    }
97
98    public IValueParameter<BoolValue> EnableCrossoverTrackingParameter {
99      get { return (IValueParameter<BoolValue>)Parameters[EnableCrossoverTrackingParameterName]; }
100    }
101
102    public IValueParameter<BoolValue> EnableManipulatorTrackingParameter {
103      get { return (IValueParameter<BoolValue>)Parameters[EnableManipulatorTrackingParameterName]; }
104    }
105
106    public IValueParameter<BoolValue> EnableSolutionCreatorTrackingParameter {
107      get { return (IValueParameter<BoolValue>)Parameters[EnableSolutionCreatorTrackingParameterName]; }
108    }
109
110    public ILookupParameter<ICrossover> CrossoverParameter {
111      get { return (ILookupParameter<ICrossover>)Parameters[CrossoverParameterName]; }
112    }
113
114    public ILookupParameter<IManipulator> ManipulatorParameter {
115      get { return (ILookupParameter<IManipulator>)Parameters[ManipulatorParameterName]; }
116    }
117
118    public ILookupParameter<ISolutionCreator> SolutionCreatorParameter {
119      get { return (ILookupParameter<ISolutionCreator>)Parameters[SolutionCreatorParameterName]; }
120    }
121    #endregion parameter properties
122
123    #region properties
124    public ICrossoverOperator<T> BeforeCrossoverOperator {
125      get { return BeforeCrossoverOperatorParameter.Value; }
126    }
127
128    public ICrossoverOperator<T> AfterCrossoverOperator {
129      get { return AfterCrossoverOperatorParameter.Value; }
130    }
131
132    public IManipulatorOperator<T> BeforeManipulatorOperator {
133      get { return BeforeManipulatorOperatorParameter.Value; }
134    }
135
136    public IManipulatorOperator<T> AfterManipulatorOperator {
137      get { return AfterManipulatorOperatorParameter.Value; }
138    }
139
140    public BoolValue EnableCrossoverTracking {
141      get { return EnableCrossoverTrackingParameter.Value; }
142    }
143
144    public BoolValue EnableManipulatorTracking {
145      get { return EnableManipulatorTrackingParameter.Value; }
146    }
147
148    public BoolValue EnableSolutionCreatorTracking {
149      get { return EnableSolutionCreatorTrackingParameter.Value; }
150    }
151
152    public bool TrimOlderGenerations {
153      get { return TrimOlderGenerationsParameter.Value.Value; }
154    }
155    #endregion properties
156
157    protected GenealogyAnalyzer() {
158      #region add parameters
159      // the instrumented operators
160      Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
161      Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
162      Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
163      // the analyzer parameters
164      Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
165      Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
166      Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
167      // parameters required by the analyzer to do its work
168      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
169      Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
170      Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
171      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
172      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(BeforeCrossoverOperatorParameterName));
173      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(AfterCrossoverOperatorParameterName));
174      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(BeforeManipulatorOperatorParameterName));
175      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(AfterManipulatorOperatorParameterName));
176      Parameters.Add(new FixedValueParameter<BoolValue>(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory."));
177      #endregion add parameters
178    }
179
180    protected GenealogyAnalyzer(GenealogyAnalyzer<T> original, Cloner cloner)
181      : base(original, cloner) {
182    }
183
184    [StorableConstructor]
185    protected GenealogyAnalyzer(bool deserializing) : base(deserializing) { }
186
187    [StorableHook(HookType.AfterDeserialization)]
188    private void AfterDeserialization() {
189      // the instrumented operators
190      if (!Parameters.ContainsKey(CrossoverParameterName))
191        Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
192      if (!Parameters.ContainsKey(ManipulatorParameterName))
193        Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
194      if (!Parameters.ContainsKey(SolutionCreatorParameterName))
195        Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
196      // the analyzer parameters
197      if (!Parameters.ContainsKey(EnableCrossoverTrackingParameterName))
198        Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
199      if (!Parameters.ContainsKey(EnableManipulatorTrackingParameterName))
200        Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
201      if (!Parameters.ContainsKey(EnableSolutionCreatorTrackingParameterName))
202        Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
203      // parameters required by the analyzer to do its work
204      if (!Parameters.ContainsKey(GenerationsParameterName))
205        Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
206      if (!Parameters.ContainsKey(ResultsParameterName))
207        Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
208      if (!Parameters.ContainsKey(PopulationParameterName)) {
209        Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
210      }
211      if (!Parameters.ContainsKey(QualityParameterName)) {
212        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
213      }
214      if (!Parameters.ContainsKey(TrimOlderGenerationsParameterName))
215        Parameters.Add(new FixedValueParameter<BoolValue>(TrimOlderGenerationsParameterName, "Remove all the generations older than the last generation from the genealoy graph to save memory."));
216    }
217
218    public bool EnabledByDefault {
219      get { return false; }
220    }
221
222    private void ConfigureTrackingOperators() {
223      // at the beginning we add the before/after operators to the instrumented operators
224      var crossover = CrossoverParameter.ActualValue;
225      if (crossover != null) {
226        var instrumentedCrossover = (InstrumentedOperator)crossover;
227        instrumentedCrossover.AfterExecutionOperators.Clear();
228        instrumentedCrossover.BeforeExecutionOperators.Clear();
229
230        if (EnableCrossoverTracking.Value) {
231          if (BeforeCrossoverOperator != null) {
232            instrumentedCrossover.BeforeExecutionOperators.Add(BeforeCrossoverOperator);
233          }
234          if (AfterCrossoverOperator != null) {
235            instrumentedCrossover.AfterExecutionOperators.Add(AfterCrossoverOperator);
236          }
237        }
238      }
239      var manipulator = ManipulatorParameter.ActualValue;
240      if (manipulator != null) {
241        var instrumentedManipulator = (InstrumentedOperator)manipulator;
242        instrumentedManipulator.AfterExecutionOperators.Clear();
243        instrumentedManipulator.BeforeExecutionOperators.Clear();
244
245        if (EnableManipulatorTracking.Value) {
246          if (BeforeManipulatorOperator != null) {
247            instrumentedManipulator.BeforeExecutionOperators.Add(BeforeManipulatorOperator);
248          }
249          if (AfterManipulatorOperator != null) {
250            instrumentedManipulator.AfterExecutionOperators.Add(AfterManipulatorOperator);
251          }
252        }
253      }
254    }
255
256    protected abstract void EvaluateIntermediateChildren();
257
258    public override IOperation Apply() {
259      IGenealogyGraph<T> genealogyGraph;
260      var results = ResultsParameter.ActualValue;
261      if (!results.ContainsKey(PopulationGraphParameterName)) {
262        genealogyGraph = new GenealogyGraph<T>();
263        results.Add(new Result(PopulationGraphParameterName, genealogyGraph));
264      } else {
265        genealogyGraph = (IGenealogyGraph<T>)results[PopulationGraphParameterName].Value;
266      }
267
268      var population = PopulationParameter.ActualValue;
269      var qualities = QualityParameter.ActualValue;
270
271      int generation = GenerationsParameter.ActualValue.Value;
272      if (generation == 0) {
273        ConfigureTrackingOperators();
274
275        for (int i = 0; i < population.Length; ++i) {
276          var individual = population[i];
277          var vertex = new GenealogyGraphNode<T>(individual) { Rank = generation };
278          genealogyGraph.AddVertex(vertex);
279          // save the vertex id in the individual scope (so that we can identify graph indices)
280          ExecutionContext.Scope.SubScopes[i].Variables.Add(new Variable("Id", new StringValue(vertex.Id)));
281        }
282      } else {
283        int index = 0;
284        T elite = null;
285        // identify previous elite individual
286        for (int i = 0; i < population.Length; ++i) {
287          if (genealogyGraph.GetByContent(population[i]).Rank.Equals(generation - 1)) {
288            elite = population[i];
289            index = i;
290            break;
291          }
292        }
293        // add current elite and connect with previous
294        #region add elite in the graph and connect it with the previous elite
295        if (elite != null) {
296          var prevVertex = genealogyGraph.GetByContent(elite);
297          prevVertex.IsElite = true; // mark elites in the graph retroactively
298          var v = (IGenealogyGraphNode<T>)prevVertex.Clone();
299          v.Rank = generation;
300          v.IsElite = false;
301          population[index] = v.Data;
302          genealogyGraph.AddVertex(v);
303          genealogyGraph.AddArc(prevVertex, v);
304          // inject the graph node unique id to the scope
305          ExecutionContext.Scope.SubScopes[index].Variables[BeforeManipulatorOperator.ChildParameter.ActualName].Value = v.Data;
306          ExecutionContext.Scope.SubScopes[index].Variables["Id"].Value = new StringValue(v.Id);
307        }
308        #endregion add elite in the graph and connect it with the previous elite
309      }
310      // update qualities
311      for (int i = 0; i < population.Length; ++i) {
312        var vertex = genealogyGraph.GetByContent(population[i]);
313        vertex.Quality = qualities[i].Value;
314      }
315      // update qualities for intermediate vertices
316      EvaluateIntermediateChildren();
317
318      // remove extra graph nodes (added by the instrumented operators in the case of offspring selection)
319      var pop = new HashSet<T>(population);
320      var discarded = genealogyGraph.GetByRank(generation).Where(x => !pop.Contains(x.Data)).ToList();
321      for (int i = 0; i < discarded.Count; ++i) {
322        var v = discarded[i];
323        if (v.InDegree == 1) {
324          var p = v.Parents.First();
325          if (p.Rank.Equals(generation - 0.5))
326            // the individual was a product of mutation. since it wasn't selected, we must remove both it and its parent
327            // ("intermediate" vertex result of crossover)
328            discarded.Add(v.Parents.First());
329        }
330      }
331      genealogyGraph.RemoveVertices(discarded);
332
333      //trim
334      if (TrimOlderGenerations) {
335        var vertices = genealogyGraph.Vertices.Where(x => x.Rank < generation - 1).ToList(); // select all ranks older than the previous generation
336        genealogyGraph.RemoveVertices(vertices);
337      }
338
339      return base.Apply();
340    }
341  }
342}
Note: See TracBrowser for help on using the repository browser.