source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Operators/SymbolicExpressionTreeGenealogyGraphBuilder.cs @ 9835

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

#1772: Merged remaining trunk changes into the EvolutionaryTracking branch.

File size: 15.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.Linq;
24using System.Threading;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Problems.DataAnalysis;
34using HeuristicLab.Problems.DataAnalysis.Symbolic;
35// type definitions for ease of use
36using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
37using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
38
39namespace HeuristicLab.EvolutionaryTracking {
40  /// <summary>
41  /// Builds a genealogy graph of the algorithms population.
42  /// </summary>
43  [Item("SymbolicExpressionTreeGenealogyGraphBuilder", "An operator that tracks the genealogy of tree individuals")]
44  [StorableClass]
45  public sealed class SymbolicExpressionTreeGenealogyGraphBuilder : SingleSuccessorOperator {
46    #region Parameter names
47    private const string ResultsParameterName = "Results";
48    private const string ElitesParameterName = "Elites";
49    private const string GenerationsParameterName = "Generations";
50    private const string MaximumGenerationsParameterName = "MaximumGenerations";
51    private const string MaximumSelectionPressureParameterName = "MaximumSelectionPressure";
52    private const string SelectionPressureParameterName = "SelectionPressure";
53    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
54    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
55    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
56    private const string PopulationGraphParameterName = "PopulationGraph";
57    private const string PopulationGraphParameterDescription = "Individual lineages";
58    private const string SymbolicExpressionInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
59    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
60    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
61    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
62    private const string SymbolicExpressionTreeQualityParameterName = "Quality";
63    #endregion
64    #region Parameters
65    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
66      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
67    }
68    public IScopeTreeLookupParameter<DoubleValue> SymbolicExpressionTreeQualityParameter {
69      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[SymbolicExpressionTreeQualityParameterName]; }
70    }
71    public LookupParameter<ResultCollection> ResultsParameter {
72      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
73    }
74    public LookupParameter<IntValue> ElitesParameter {
75      get { return (LookupParameter<IntValue>)Parameters[ElitesParameterName]; }
76    }
77    public LookupParameter<IntValue> GenerationsParameter {
78      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
79    }
80    public LookupParameter<IntValue> MaximumGenerationsParameter {
81      get { return (LookupParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
82    }
83    public LookupParameter<DoubleValue> SelectionPressureParameter {
84      get { return (LookupParameter<DoubleValue>)Parameters[SelectionPressureParameterName]; }
85    }
86    public LookupParameter<DoubleValue> MaximumSelectionPressureParameter {
87      get { return (LookupParameter<DoubleValue>)Parameters[MaximumSelectionPressureParameterName]; }
88    }
89    // problem data, interpreter and evaluator
90    public LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter> SymbolicExpressionInterpreterParameter {
91      get { return (LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[SymbolicExpressionInterpreterParameterName]; }
92    }
93    public LookupParameter<RegressionProblemData> SymbolicRegressionProblemDataParameter {
94      get { return (LookupParameter<RegressionProblemData>)Parameters[SymbolicRegressionProblemDataParameterName]; }
95    }
96    public LookupParameter<IEvaluator> SymbolicDataAnalysisProblemEvaluatorParameter {
97      get { return (LookupParameter<IEvaluator>)Parameters[SymbolicDataAnalysisProblemEvaluatorParameterName]; }
98    }
99    // genealogy global parameters
100    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
101      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
102    }
103    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
104      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
105    }
106    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
107      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
108    }
109    #endregion
110    #region Parameter properties
111    public bool EnabledByDefault {
112      get { return true; }
113    }
114    public ResultCollection Results {
115      get { return ResultsParameter.ActualValue; }
116    }
117    public IntValue Elites {
118      get { return ElitesParameter.ActualValue; }
119    }
120    public IntValue Generations {
121      get { return GenerationsParameter.ActualValue; }
122    }
123    public IntValue MaximumGenerations {
124      get { return MaximumGenerationsParameter.ActualValue; }
125    }
126    public DoubleValue SelectionPressure {
127      get { return SelectionPressureParameter.ActualValue; }
128    }
129    public DoubleValue MaximumSelectionPressure {
130      get { return MaximumSelectionPressureParameter.ActualValue; }
131    }
132    public CloneMapType GlobalCloneMap {
133      get { return GlobalCloneMapParameter.ActualValue; }
134    }
135    public TraceMapType GlobalTraceMap {
136      get { return GlobalTraceMapParameter.ActualValue; }
137    }
138    public CloneMapType GlobalFragmentMap {
139      get { return GlobalFragmentMapParameter.ActualValue; }
140    }
141    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
142      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
143    }
144    public RegressionProblemData SymbolicRegressionProblemData {
145      get { return SymbolicRegressionProblemDataParameter.ActualValue; }
146    }
147    public IEvaluator SymbolicDataAnalysisEvaluator {
148      get { return SymbolicDataAnalysisProblemEvaluatorParameter.ActualValue; }
149    }
150    #endregion
151
152    [StorableConstructor]
153    private SymbolicExpressionTreeGenealogyGraphBuilder(bool deserializing) : base(deserializing) { }
154    private SymbolicExpressionTreeGenealogyGraphBuilder(SymbolicExpressionTreeGenealogyGraphBuilder original, Cloner cloner) : base(original, cloner) { }
155    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeGenealogyGraphBuilder(this, cloner); }
156    public SymbolicExpressionTreeGenealogyGraphBuilder()
157      : base() {
158      #region Add parameters
159      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "The number of elites."));
160      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
161      Parameters.Add(new LookupParameter<IntValue>(MaximumGenerationsParameterName, "The maximum number of generations"));
162      Parameters.Add(new LookupParameter<DoubleValue>(SelectionPressureParameterName, "The current selection (ony for OSGA)"));
163      Parameters.Add(new LookupParameter<DoubleValue>(MaximumSelectionPressureParameterName, "Maximum allowed value of selection pressure."));
164      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing the whole genealogy."));
165      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
166      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
167      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
168      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
169      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
170      Parameters.Add(new LookupParameter<IEvaluator>(SymbolicDataAnalysisProblemEvaluatorParameterName, "The fitness evaluator"));
171      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze"));
172      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));
173      #endregion
174    }
175
176    [StorableHook(HookType.AfterDeserialization)]
177    private void AfterDeserialization() { }
178
179    #region IStatefulItem members
180    public override void InitializeState() {
181      base.InitializeState();
182    }
183
184    public override void ClearState() {
185      base.ClearState();
186    }
187    #endregion
188
189    public override IOperation Apply() {
190      if (!Parameters.ContainsKey("Results")) return base.Apply();
191
192      SymbolicExpressionTreeGenealogyGraph graph;
193      if (Results.ContainsKey(PopulationGraphParameterName)) {
194        graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphParameterName].Value);
195      } else {
196        graph = new SymbolicExpressionTreeGenealogyGraph();
197        Results.Add(new Result(PopulationGraphParameterName, PopulationGraphParameterDescription, graph));
198      }
199
200      var trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
201      var qualities = SymbolicExpressionTreeQualityParameter.ActualValue.ToArray();
202
203      if (trees.Length != qualities.Length)
204        throw new Exception("Error: trees and qualities array sizes do not match!");
205
206      // add all individuals to the evolutionary graph
207      int generation = Generations.Value;
208
209      var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q.Value }).OrderByDescending(x => x.Quality).ToList();
210
211      if (generation == 0) {
212        // add the trees in the graph and return
213        foreach (var pair in pairs) {
214          var tree = pair.Tree;
215          var quality = pair.Quality;
216          graph.AddNode(new SymbolicExpressionGenealogyGraphNode {
217            SymbolicExpressionTree = tree,
218            Quality = quality,
219            Rank = generation
220          });
221        }
222        return base.Apply();
223      }
224
225      var graphNodes = (from i in Enumerable.Range(0, trees.Length)
226                        let tree = pairs[i].Tree
227                        let quality = pairs[i].Quality
228                        select new SymbolicExpressionGenealogyGraphNode {
229                          SymbolicExpressionTree = tree,
230                          Quality = quality,
231                          Rank = generation,
232                          IsElite = i < Elites.Value
233                        }).Concat
234        // the following query addds the intermediate nodes that were created when
235        // crossover was followed by mutation (they are not present in the scope)
236        (from t in trees
237         where GlobalTraceMap.ContainsKey(t)
238         let parents = GlobalTraceMap[t]
239         where parents.Count == 1
240         // 1 parent means mutation
241         let p = (ISymbolicExpressionTree)parents[0]
242         select new SymbolicExpressionGenealogyGraphNode {
243           SymbolicExpressionTree = p,
244           Quality = Evaluate(p),
245           Rank = generation - 0.5
246           // an intermediate parent that would normally be 'invisible' to the evolutionary process
247         }
248        ).ToList();
249
250      foreach (var node in graphNodes) {
251        graph.AddNode(node);
252      }
253
254      graphNodes.Sort((a, b) => b.Rank.CompareTo(a.Rank));
255
256      foreach (var node in graphNodes) {
257        var tree = node.SymbolicExpressionTree;
258        if (!GlobalTraceMap.ContainsKey(tree)) {
259          var nodes = graph.GetGraphNodes(tree);
260          if (nodes.Count > 1) {
261            // link elites from previous generation
262            var last = nodes[nodes.Count - 2];
263            var arc = new Arc { Source = last, Target = node, Data = new Fragment { Root = null } };
264            last.AddForwardArc(arc);
265            node.AddReverseArc(arc);
266          }
267          continue;
268        }
269
270        var parents = GlobalTraceMap[tree].Cast<ISymbolicExpressionTree>().ToList();
271        var fragment = GlobalFragmentMap[tree];
272        foreach (var p in parents) {
273          var nodes = graph.GetGraphNodes(p);
274          if (nodes == null) {
275            throw new Exception("Node cannot have no parents");
276          }
277          var sourceNode = nodes.LastOrDefault(n => n.Rank < node.Rank);
278          if (sourceNode == null) {
279            throw new Exception("Source node cannot be null");
280          }
281          var arc = new Arc { Source = sourceNode, Target = node, Data = fragment };
282          sourceNode.AddForwardArc(arc);
283          node.AddReverseArc(arc);
284        }
285        // the root parent is the one that receives the subtree/fragment from the other parent
286        // so it does not actually pass a subtree to the child, therefore the fragment is null
287        // so in case of crossover, we add a null fragment below
288        if (parents.Count > 1) node.InEdges[0].Data = new Fragment { Root = null };
289      }
290
291      // notify listeners that the genealogy graph was updated
292      graph.Updated();
293
294      return base.Apply();
295    }
296
297    /// <summary>
298    /// Evaluate a symbolic expression tree. We perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
299    /// </summary>
300    /// <param name="tree">The symbolic expression tree to evaluate</param>
301    /// <returns>A double value representing the individual quality</returns>
302    private double Evaluate(IItem tree) {
303      var subScope = new Scope();
304      subScope.Variables.Add(new Core.Variable("SymbolicExpressionTree", tree)); // inject expected variables into the subscope
305      ExecutionContext.Scope.SubScopes.Add(subScope);
306      var context = new Core.ExecutionContext(ExecutionContext, SymbolicDataAnalysisEvaluator, subScope);
307      SymbolicDataAnalysisEvaluator.Execute(context, new CancellationToken()); // call evaluator.Apply()
308      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value; // get the quality
309      ExecutionContext.Scope.SubScopes.Remove(subScope); // remove the subscope
310      return quality;
311    }
312  }
313}
Note: See TracBrowser for help on using the repository browser.