source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeEvolvabilityAnalyzer.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: 17.1 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Threading;
5using HeuristicLab.Analysis;
6using HeuristicLab.Common;
7using HeuristicLab.Core;
8using HeuristicLab.Data;
9using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
10using HeuristicLab.Operators;
11using HeuristicLab.Optimization;
12using HeuristicLab.Parameters;
13using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
14using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
15
16namespace HeuristicLab.EvolutionaryTracking {
17  /// <summary>
18  /// Evolvability Analyzer
19  /// </summary>
20  [Item("SymbolicExpressionEvolvabilityAnalyzer", "An operator that measures relative improvements obtained by genetic operators and relative reproductive success.")]
21  [StorableClass]
22  public sealed class SymbolicExpressionEvolvabilityAnalyzer : SingleSuccessorOperator, IAnalyzer {
23    #region Parameter names
24    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
25    private const string SymbolicExpressionTreeQualityParameterName = "Quality";
26    private const string UpdateIntervalParameterName = "UpdateInterval";
27    private const string UpdateCounterParameterName = "UpdateCounter";
28    private const string ResultsParameterName = "Results";
29    private const string PopulationGraphParameterName = "PopulationGraph";
30    private const string PopulationSizeParameterName = "PopulationSize";
31    private const string ElitesParameterName = "Elites";
32    private const string RelativeReproductiveSuccessResultName = "RelativeReproductiveSuccess";
33    private const string GeneticOperatorsAverageImprovementResultName = "GeneticOperatorsAverageImprovement";
34    private const string ConstantOptimizationIntermediateParentsParameterName = "ConstantOptimizeIntermediateParents";
35    private const string ConstantOptimizationEvaluatorParameterName = "ConstantOptimizationOperator";
36    private const string RandomParameterName = "Random";
37    #endregion
38
39    #region Parameter properties
40    public LookupParameter<IRandom> RandomParameter {
41      get { return (LookupParameter<IRandom>)Parameters[RandomParameterName]; }
42    }
43    public ValueParameter<IntValue> UpdateIntervalParameter {
44      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
45    }
46    public ValueParameter<IntValue> UpdateCounterParameter {
47      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
48    }
49    public ValueParameter<BoolValue> ConstantOptimizationIntermediateParentsParameter {
50      get { return (ValueParameter<BoolValue>)Parameters[ConstantOptimizationIntermediateParentsParameterName]; }
51    }
52    public IFixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator> ConstantOptimizationEvaluatorParameter {
53      get { return (IFixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>)Parameters[ConstantOptimizationEvaluatorParameterName]; }
54    }
55    public LookupParameter<ResultCollection> ResultsParameter {
56      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
57    }
58    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
59      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
60    }
61    public IScopeTreeLookupParameter<DoubleValue> SymbolicExpressionTreeQualityParameter {
62      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[SymbolicExpressionTreeQualityParameterName]; }
63    }
64    public LookupParameter<IntValue> ElitesParameter {
65      get { return (LookupParameter<IntValue>)Parameters[ElitesParameterName]; }
66    }
67    public LookupParameter<IntValue> PopulationSizeParameter {
68      get { return (LookupParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
69    }
70    #endregion
71
72    #region Parameters
73    public IntValue UpdateInterval {
74      get { return UpdateIntervalParameter.Value; }
75    }
76    public IntValue UpdateCounter {
77      get { return UpdateCounterParameter.Value; }
78    }
79    public ResultCollection Results {
80      get { return ResultsParameter.ActualValue; }
81    }
82    public IntValue PopulationSize {
83      get { return PopulationSizeParameter.ActualValue; }
84    }
85    public IntValue Elites {
86      get { return ElitesParameter.ActualValue; }
87    }
88    public BoolValue ConstantOptimizationIntermediateParents {
89      get { return ConstantOptimizationIntermediateParentsParameter.Value; }
90    }
91    public SymbolicRegressionConstantOptimizationEvaluator ConstantOptimizationEvaluator {
92      get { return ConstantOptimizationEvaluatorParameter.Value; }
93    }
94    #endregion
95
96    [StorableConstructor]
97    private SymbolicExpressionEvolvabilityAnalyzer(bool deserializing) : base(deserializing) { }
98    private SymbolicExpressionEvolvabilityAnalyzer(SymbolicExpressionEvolvabilityAnalyzer original, Cloner cloner) : base(original, cloner) { }
99    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionEvolvabilityAnalyzer(this, cloner); }
100
101    public SymbolicExpressionEvolvabilityAnalyzer() {
102      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees to analyze."));
103      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(SymbolicExpressionTreeQualityParameterName, "The qualities of the symbolic expression trees"));
104      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
105      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
106      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
107      Parameters.Add(new LookupParameter<IntValue>(PopulationSizeParameterName, "The population size."));
108      Parameters.Add(new LookupParameter<IntValue>(ElitesParameterName, "Number of elites in the population."));
109      Parameters.Add(new ValueParameter<BoolValue>(ConstantOptimizationIntermediateParentsParameterName, "Controls whether or not the constant values of the intermediate nodes should be updated.", new BoolValue(false)));
110      Parameters.Add(new ValueLookupParameter<IRandom>(RandomParameterName, "The random generator to use."));
111      Parameters.Add(new FixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>(ConstantOptimizationEvaluatorParameterName, "The operator used to perform the constant optimization"));
112
113      UpdateCounterParameter.Hidden = true;
114      UpdateIntervalParameter.Hidden = true;
115
116      //Changed the ActualName of the EvaluationPartitionParameter so that it matches the parameter name of symbolic regression problems.
117      ConstantOptimizationEvaluator.EvaluationPartitionParameter.ActualName = "FitnessCalculationPartition";
118      ConstantOptimizationEvaluator.UpdateConstantsInTree = false;
119    }
120
121    [StorableHook(HookType.AfterDeserialization)]
122    private void AfterDeserialization() {
123      if (!Parameters.ContainsKey(ConstantOptimizationEvaluatorParameterName)) {
124        Parameters.Add(new FixedValueParameter<SymbolicRegressionConstantOptimizationEvaluator>(ConstantOptimizationEvaluatorParameterName, "The operator used to perform the constant optimization"));
125        //Changed the ActualName of the EvaluationPartitionParameter so that it matches the parameter name of symbolic regression problems.
126        ConstantOptimizationEvaluator.EvaluationPartitionParameter.ActualName = "FitnessCalculationPartition";
127        ConstantOptimizationEvaluator.UpdateConstantsInTree = false;
128      }
129
130      if (!Parameters.ContainsKey(ConstantOptimizationIntermediateParentsParameterName))
131        Parameters.Add(new ValueParameter<BoolValue>(ConstantOptimizationIntermediateParentsParameterName, "Controls whether or not the constant values of the intermediate parents should be updated.", new BoolValue(false)));
132    }
133
134    #region IStatefulItem members
135    public override void InitializeState() {
136      base.InitializeState();
137      UpdateCounter.Value = 0;
138    }
139
140    public override void ClearState() {
141      base.ClearState();
142      UpdateCounter.Value = 0;
143    }
144    #endregion
145
146    public override IOperation Apply() {
147      UpdateCounter.Value++;
148
149      if (UpdateCounter.Value == UpdateInterval.Value) {
150        UpdateCounter.Value = 0;
151        if (!Results.ContainsKey(PopulationGraphParameterName)) return base.Apply();
152        var genealogyGraph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphParameterName].Value;
153        if (genealogyGraph == null) return base.Apply();
154
155        ISymbolicExpressionTree[] trees = SymbolicExpressionTreeParameter.ActualValue.ToArray();
156        var currentGen = (from tree in trees
157                          select genealogyGraph.GetGraphNodes(tree).Last()).Where(n => n.InEdges != null).ToList();
158        var intermediateGen = (from graphNode in currentGen
159                               where graphNode.InEdges.Count == 1
160                               // mutation
161                               let source = (SymbolicExpressionGenealogyGraphNode)graphNode.InEdges[0].Source
162                               where graphNode.SymbolicExpressionTree != source.SymbolicExpressionTree // skip elites
163                               select source).ToList();
164        // currentGen will contain nodes corresponding to individuals in the current generation
165        // + intermediate individuals (that were created via crossover, then mutated)
166        currentGen.AddRange(intermediateGen);
167        currentGen.Sort((a, b) => b.InEdges.Count.CompareTo(a.InEdges.Count)); // sort by InEdge count descending so that crossover offspring are first in the list
168
169        int successfulOffspring = 0;
170        var crossoverImprovements = new List<double>();
171        var mutationImprovements = new List<double>();
172
173        foreach (var graphNode in currentGen) {
174          var quality = graphNode.Quality;
175          double parentQuality = 0.0;
176          if (graphNode.InEdges == null) throw new Exception("InEdges should not be null.");
177          switch (graphNode.InEdges.Count) {
178            case 2: {
179                parentQuality = graphNode.InEdges.Max(e => ((SymbolicExpressionGenealogyGraphNode)e.Source).Quality);
180                crossoverImprovements.Add(quality - parentQuality);
181                break;
182              }
183            case 1: {
184                parentQuality = graphNode.InEdges.Max(e => ((SymbolicExpressionGenealogyGraphNode)e.Source).Quality);
185                if (ConstantOptimizationIntermediateParents.Value && ConstantOptimizationEvaluator != null) {
186
187                  //Get the optimized fitness of the intermediate parent (without actually updating the constants in the tree)
188                  var intermediateParent = ((SymbolicExpressionGenealogyGraphNode)graphNode.InEdges[0].Source).SymbolicExpressionTree;
189                  parentQuality = Evaluate(intermediateParent, ConstantOptimizationEvaluator);
190                }
191                mutationImprovements.Add(quality - parentQuality);
192                break;
193              }
194          }
195          if (quality > parentQuality)
196            successfulOffspring++;
197        }
198        // reproductive success
199        double reproductiveSuccess = (double)successfulOffspring / (PopulationSize.Value - Elites.Value);
200        const string reproductiveSuccessDataTableName = "Reproductive success";
201        if (!Results.ContainsKey(RelativeReproductiveSuccessResultName))
202          Results.Add(new Result(RelativeReproductiveSuccessResultName, new DataTable(reproductiveSuccessDataTableName)));
203        var relativeReproductiveSuccessTable = (DataTable)Results[RelativeReproductiveSuccessResultName].Value;
204        if (!relativeReproductiveSuccessTable.Rows.ContainsKey(reproductiveSuccessDataTableName))
205          relativeReproductiveSuccessTable.Rows.Add(new DataRow(reproductiveSuccessDataTableName) { VisualProperties = { StartIndexZero = true } });
206        relativeReproductiveSuccessTable.Rows[reproductiveSuccessDataTableName].Values.Add(reproductiveSuccess);
207
208        // average and relative number of leaf nodes
209        if (!Results.ContainsKey("RelativeProportionOfLeafNodes"))
210          Results.Add(new Result("RelativeProportionOfLeafNodes", new DataTable("Proportion of leaf nodes")));
211        var relativeProportionOfLeafNodesTable = (DataTable)Results["RelativeProportionOfLeafNodes"].Value;
212        if (!relativeProportionOfLeafNodesTable.Rows.ContainsKey("Percent of leaf nodes"))
213          relativeProportionOfLeafNodesTable.Rows.Add(new DataRow("Percent of leaf nodes") { VisualProperties = { StartIndexZero = true } });
214        if (!relativeProportionOfLeafNodesTable.Rows.ContainsKey("Average number of leafs"))
215          relativeProportionOfLeafNodesTable.Rows.Add(new DataRow("Average number of leafs") { VisualProperties = { StartIndexZero = true } });
216
217        double totalNodes = trees.Sum(x => x.Length);
218        double totalLeafs = trees.Sum(t => t.IterateNodesPostfix().Count(n => n.SubtreeCount == 0));
219
220        relativeProportionOfLeafNodesTable.Rows["Percent of leaf nodes"].Values.Add(totalLeafs / totalNodes);
221        relativeProportionOfLeafNodesTable.Rows["Average number of leafs"].Values.Add(totalLeafs / trees.Length);
222
223        // genetic operators best and average improvement values
224        if (!Results.ContainsKey(GeneticOperatorsAverageImprovementResultName)) {
225          Results.Add(new Result(GeneticOperatorsAverageImprovementResultName, new DataTable()));
226        }
227        var table = (DataTable)Results[GeneticOperatorsAverageImprovementResultName].Value;
228
229        double cxAvgImprovement = 0.0;
230        double cxMaxImprovement = 0.0;
231        if (crossoverImprovements.Count > 0) {
232          cxAvgImprovement = crossoverImprovements.Average();
233          cxMaxImprovement = crossoverImprovements.Max();
234        }
235        double mutAvgImprovement = 0.0;
236        double mutMaxImprovement = 0.0;
237        if (mutationImprovements.Count > 0) {
238          mutAvgImprovement = mutationImprovements.Average();
239          mutMaxImprovement = mutationImprovements.Max();
240        }
241
242        if (!table.Rows.ContainsKey("Average crossover improvement")) {
243          table.Rows.Add(new DataRow("Average crossover improvement") { VisualProperties = { StartIndexZero = true } });
244        }
245        table.Rows["Average crossover improvement"].Values.Add(cxAvgImprovement);
246
247        if (!table.Rows.ContainsKey("Average mutation improvement")) {
248          table.Rows.Add(new DataRow("Average mutation improvement") { VisualProperties = { StartIndexZero = true } });
249        }
250        table.Rows["Average mutation improvement"].Values.Add(mutAvgImprovement);
251
252        if (!table.Rows.ContainsKey("Best crossover improvement")) {
253          table.Rows.Add(new DataRow("Best crossover improvement") { VisualProperties = { StartIndexZero = true } });
254        }
255        table.Rows["Best crossover improvement"].Values.Add(cxMaxImprovement);
256
257        if (!table.Rows.ContainsKey("Best mutation improvement")) {
258          table.Rows.Add(new DataRow("Best mutation improvement") { VisualProperties = { StartIndexZero = true } });
259        }
260        table.Rows["Best mutation improvement"].Values.Add(mutMaxImprovement);
261
262        if (!table.Rows.ContainsKey("Average improvement")) {
263          table.Rows.Add(new DataRow("Average improvement") { VisualProperties = { StartIndexZero = true } });
264        }
265        table.Rows["Average improvement"].Values.Add((cxAvgImprovement + mutAvgImprovement) / 2);
266
267        if (!table.Rows.ContainsKey("Best improvement")) {
268          table.Rows.Add(new DataRow("Best improvement") { VisualProperties = { StartIndexZero = true } });
269        }
270        table.Rows["Best improvement"].Values.Add(Math.Max(cxMaxImprovement, mutMaxImprovement));
271      }
272      return base.Apply();
273    }
274
275    /// <summary>
276    /// Evaluate a symbolic expression tree. We perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
277    /// </summary>
278    /// <param name="tree">The symbolic expression tree to evaluate</param>
279    /// <param name="evaluator">The symbolic regression single objective evaluator to use</param>
280    /// <returns>A double value representing the fitness</returns>
281    private double Evaluate(IItem tree, SymbolicRegressionSingleObjectiveEvaluator evaluator) {
282      var subScope = new Scope();
283      subScope.Variables.Add(new Variable("SymbolicExpressionTree", tree)); // inject expected variables into the subscope
284      ExecutionContext.Scope.SubScopes.Add(subScope);
285      var context = new Core.ExecutionContext(ExecutionContext, evaluator, subScope);
286      evaluator.Execute(context, new CancellationToken()); // call evaluator.Apply()
287      double quality = ((DoubleValue)subScope.Variables["Quality"].Value).Value; // get the quality
288      ExecutionContext.Scope.SubScopes.Remove(subScope); // remove the subscope
289      return quality;
290    }
291
292    public bool EnabledByDefault { get { return true; } }
293  }
294}
Note: See TracBrowser for help on using the repository browser.