source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Analyzers/GenealogyAnalyzer.cs @ 10886

Last change on this file since 10886 was 10886, checked in by bburlacu, 8 years ago

#1772: Simplified GenealogyGraph (and related components) API in an effort to improve speed and memory consumption (eg., by sharing the same arc when walking the graph in both directions: parent-child and child-parent).

File size: 14.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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.Linq;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.EvolutionTracking {
32  [StorableClass]
33  [Item("GenealogyAnalyzer", "An analyzer which performs the necessary instrumentation to record the evolution of a genetic algorithm.")]
34  public class GenealogyAnalyzer<T> : SingleSuccessorOperator, IAnalyzer
35  where T : class,IItem {
36    private const string GenerationsParameterName = "Generations";
37    private const string ResultsParameterName = "Results";
38    private const string PopulationGraphParameterName = "PopulationGraph";
39    public const string QualityParameterName = "Quality";
40    public const string PopulationParameterName = "SymbolicExpressionTree";
41
42    private const string CrossoverParameterName = "Crossover";
43    private const string ManipulatorParameterName = "Mutator";
44    private const string SolutionCreatorParameterName = "SolutionCreator";
45
46    private const string BeforeCrossoverOperatorParameterName = "BeforeCrossoverOperator";
47    private const string AfterCrossoverOperatorParameterName = "AfterCrossoverOperator";
48
49    private const string BeforeManipulatorOperatorParameterName = "BeforeManipulatorOperator";
50    private const string AfterManipulatorOperatorParameterName = "AfterManipulatorOperator";
51
52    private const string EnableCrossoverTrackingParameterName = "EnableCrossoverTracking";
53    private const string EnableManipulatorTrackingParameterName = "EnableManipulatorTracking";
54    private const string EnableSolutionCreatorTrackingParameterName = "EnableSolutionCreatorTracking"; // should always be enabled. maybe superfluous
55
56    #region parameter properties
57    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
58      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[QualityParameterName]; }
59    }
60    public IScopeTreeLookupParameter<T> PopulationParameter {
61      get { return (IScopeTreeLookupParameter<T>)Parameters[PopulationParameterName]; }
62    }
63    public IValueParameter<ICrossoverOperator<T>> BeforeCrossoverOperatorParameter {
64      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[BeforeCrossoverOperatorParameterName]; }
65    }
66    public IValueParameter<ICrossoverOperator<T>> AfterCrossoverOperatorParameter {
67      get { return (IValueParameter<ICrossoverOperator<T>>)Parameters[AfterCrossoverOperatorParameterName]; }
68    }
69    public IValueParameter<IManipulatorOperator<T>> BeforeManipulatorOperatorParameter {
70      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[BeforeManipulatorOperatorParameterName]; }
71    }
72    public IValueParameter<IManipulatorOperator<T>> AfterManipulatorOperatorParameter {
73      get { return (IValueParameter<IManipulatorOperator<T>>)Parameters[AfterManipulatorOperatorParameterName]; }
74    }
75    public ILookupParameter<ResultCollection> ResultsParameter {
76      get { return (ILookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
77    }
78    public ILookupParameter<IntValue> GenerationsParameter {
79      get { return (ILookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
80    }
81    public IValueParameter<BoolValue> EnableCrossoverTrackingParameter {
82      get { return (IValueParameter<BoolValue>)Parameters[EnableCrossoverTrackingParameterName]; }
83    }
84    public IValueParameter<BoolValue> EnableManipulatorTrackingParameter {
85      get { return (IValueParameter<BoolValue>)Parameters[EnableManipulatorTrackingParameterName]; }
86    }
87    public IValueParameter<BoolValue> EnableSolutionCreatorTrackingParameter {
88      get { return (IValueParameter<BoolValue>)Parameters[EnableSolutionCreatorTrackingParameterName]; }
89    }
90    public ILookupParameter<ICrossover> CrossoverParameter {
91      get { return (ILookupParameter<ICrossover>)Parameters[CrossoverParameterName]; }
92    }
93    public ILookupParameter<IManipulator> ManipulatorParameter {
94      get { return (ILookupParameter<IManipulator>)Parameters[ManipulatorParameterName]; }
95    }
96
97    public ILookupParameter<ISolutionCreator> SolutionCreatorParameter {
98      get { return (ILookupParameter<ISolutionCreator>)Parameters[SolutionCreatorParameterName]; }
99    }
100    #endregion
101
102    #region properties
103    public ICrossover Crossover {
104      get { return CrossoverParameter.ActualValue; }
105    }
106    public IManipulator Manipulator {
107      get { return ManipulatorParameter.ActualValue; }
108    }
109    public ICrossoverOperator<T> BeforeCrossoverOperator {
110      get { return BeforeCrossoverOperatorParameter.Value; }
111    }
112    public ICrossoverOperator<T> AfterCrossoverOperator {
113      get { return AfterCrossoverOperatorParameter.Value; }
114    }
115    public IManipulatorOperator<T> BeforeManipulatorOperator {
116      get { return BeforeManipulatorOperatorParameter.Value; }
117    }
118    public IManipulatorOperator<T> AfterManipulatorOperator {
119      get { return AfterManipulatorOperatorParameter.Value; }
120    }
121    public ISolutionCreator SolutionCreator {
122      get { return SolutionCreatorParameter.ActualValue; }
123    }
124    public BoolValue EnableCrossoverTracking {
125      get { return EnableCrossoverTrackingParameter.Value; }
126    }
127    public BoolValue EnableManipulatorTracking {
128      get { return EnableManipulatorTrackingParameter.Value; }
129    }
130    public BoolValue EnableSolutionCreatorTracking {
131      get { return EnableSolutionCreatorTrackingParameter.Value; }
132    }
133    public ResultCollection Results {
134      get { return ResultsParameter.ActualValue; }
135    }
136    public IntValue Generations {
137      get { return GenerationsParameter.ActualValue; }
138    }
139    public IGenealogyGraph<T> GenealogyGraph {
140      get {
141        IResult result;
142        if (!Results.ContainsKey(PopulationGraphParameterName)) {
143          result = new Result(PopulationGraphParameterName, new GenealogyGraph<T>());
144          Results.Add(result);
145        } else {
146          result = Results[PopulationGraphParameterName];
147        }
148        var graph = (IGenealogyGraph<T>)result.Value;
149        return graph;
150      }
151    }
152    #endregion
153
154    public GenealogyAnalyzer() {
155      // the instrumented operators
156      Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
157      Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
158      Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
159      // the analyzer parameters
160      Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
161      Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
162      Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
163      // parameters required by the analyzer to do its work
164      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
165      Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
166      Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
167      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
168      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(BeforeCrossoverOperatorParameterName));
169      Parameters.Add(new ValueParameter<ICrossoverOperator<T>>(AfterCrossoverOperatorParameterName));
170      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(BeforeManipulatorOperatorParameterName));
171      Parameters.Add(new ValueParameter<IManipulatorOperator<T>>(AfterManipulatorOperatorParameterName));
172    }
173    public override IDeepCloneable Clone(Cloner cloner) {
174      return new GenealogyAnalyzer<T>(this, cloner);
175    }
176    protected GenealogyAnalyzer(GenealogyAnalyzer<T> original, Cloner cloner)
177      : base(original, cloner) {
178    }
179    [StorableHook(HookType.AfterDeserialization)]
180    private void AfterDeserialization() {
181      // the instrumented operators
182      if (!Parameters.ContainsKey(CrossoverParameterName))
183        Parameters.Add(new LookupParameter<ICrossover>(CrossoverParameterName, "The crossover operator."));
184      if (!Parameters.ContainsKey(ManipulatorParameterName))
185        Parameters.Add(new LookupParameter<IManipulator>(ManipulatorParameterName, "The manipulator operator."));
186      if (!Parameters.ContainsKey(SolutionCreatorParameterName))
187        Parameters.Add(new LookupParameter<ISolutionCreator>(SolutionCreatorParameterName, "The solution creator operator."));
188      // the analyzer parameters
189      if (!Parameters.ContainsKey(EnableCrossoverTrackingParameterName))
190        Parameters.Add(new ValueParameter<BoolValue>(EnableCrossoverTrackingParameterName, new BoolValue(true)));
191      if (!Parameters.ContainsKey(EnableManipulatorTrackingParameterName))
192        Parameters.Add(new ValueParameter<BoolValue>(EnableManipulatorTrackingParameterName, new BoolValue(true)));
193      if (!Parameters.ContainsKey(EnableSolutionCreatorTrackingParameterName))
194        Parameters.Add(new ValueParameter<BoolValue>(EnableSolutionCreatorTrackingParameterName, new BoolValue(true)));
195      // parameters required by the analyzer to do its work
196      if (!Parameters.ContainsKey(GenerationsParameterName))
197        Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
198      if (!Parameters.ContainsKey(ResultsParameterName))
199        Parameters.Add(new LookupParameter<ResultCollection>(ResultsParameterName));
200      if (!Parameters.ContainsKey(PopulationParameterName)) {
201        Parameters.Add(new ScopeTreeLookupParameter<T>(PopulationParameterName, "The population of individuals."));
202      }
203      if (!Parameters.ContainsKey(QualityParameterName)) {
204        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(QualityParameterName, "The individual qualities."));
205      }
206    }
207
208    public bool EnabledByDefault {
209      get { return false; }
210    }
211
212    private void ConfigureTrackingOperators() {
213      // at the beginning we add the before/after operators to the instrumented operators
214      if (Crossover != null) {
215        var instrumentedCrossover = (InstrumentedOperator)Crossover;
216        instrumentedCrossover.AfterExecutionOperators.Clear();
217        instrumentedCrossover.BeforeExecutionOperators.Clear();
218
219        if (EnableCrossoverTracking.Value) {
220          if (BeforeCrossoverOperator != null) {
221            instrumentedCrossover.BeforeExecutionOperators.Add(BeforeCrossoverOperator);
222          }
223          if (AfterCrossoverOperator != null) {
224            instrumentedCrossover.AfterExecutionOperators.Add(AfterCrossoverOperator);
225          }
226        }
227      }
228
229      if (Manipulator != null) {
230        var instrumentedManipulator = (InstrumentedOperator)Manipulator;
231        instrumentedManipulator.AfterExecutionOperators.Clear();
232        instrumentedManipulator.BeforeExecutionOperators.Clear();
233
234        if (EnableManipulatorTracking.Value) {
235          if (BeforeManipulatorOperator != null) {
236            instrumentedManipulator.BeforeExecutionOperators.Add(BeforeManipulatorOperator);
237          }
238          if (AfterManipulatorOperator != null) {
239            instrumentedManipulator.AfterExecutionOperators.Add(AfterManipulatorOperator);
240          }
241        }
242      }
243    }
244
245    public override IOperation Apply() {
246      var population = PopulationParameter.ActualValue.ToList();
247      var qualities = QualityParameter.ActualValue.ToList();
248
249      if (Generations.Value == 0) {
250        ConfigureTrackingOperators();
251
252        for (int i = 0; i < population.Count; ++i) {
253          var individual = population[i];
254          var vertex = new GenealogyGraphNode<T> { Content = individual, Rank = Generations.Value, };
255          GenealogyGraph.AddVertex(vertex);
256          // save the vertex id in the individual scope (so that we can identify graph indices)
257          ExecutionContext.Scope.SubScopes[i].Variables.Add(new Variable("Id", new StringValue(vertex.Id)));
258        }
259      } else {
260        // TODO: eliminate from the graph extra vertices added by the recombination operators when filling the pool of offspring with offspring selection
261
262        var elite = population.FirstOrDefault(x => GenealogyGraph.Contains(x));
263        if (elite != null) {
264          var vertex = new GenealogyGraphNode<T> {
265            Content = (T)elite.Clone(),
266            Rank = Generations.Value,
267            IsElite = true
268          };
269          // add new vertex to the graph
270          GenealogyGraph.AddVertex(vertex);
271          // swap content between current vertex and previous vertex
272          var previousVertex = (IGenealogyGraphNode<T>)GenealogyGraph[elite];
273          var tmp = vertex.Content;
274          vertex.Content = previousVertex.Content;
275          previousVertex.Content = tmp;
276          // adjust graph content map
277          GenealogyGraph[vertex.Content] = vertex;
278          GenealogyGraph[previousVertex.Content] = previousVertex;
279          GenealogyGraph.AddArc(previousVertex, vertex); // connect current elite with previous elite
280          vertex.Id = previousVertex.Id; // another way would be to introduce the vertex.Id into the scope of the elite
281          vertex.Quality = previousVertex.Quality;
282
283          if (previousVertex.InArcs.Any()) {
284            vertex.InArcs.Last().Data = previousVertex.InArcs.Last().Data; // save the fragment in case there is one
285          }
286        }
287      }
288      // update qualities
289      for (int i = 0; i < population.Count; ++i) {
290        var vertex = (IGenealogyGraphNode)GenealogyGraph[population[i]];
291        vertex.Quality = qualities[i].Value;
292      }
293
294      return base.Apply();
295    }
296  }
297}
Note: See TracBrowser for help on using the repository browser.