Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeRelativeLengthAnalyzer.cs @ 9082

Last change on this file since 9082 was 9082, checked in by bburlacu, 11 years ago

#1772: Renamed and refactored genealogy graph components. Added SymbolGraph and FPGraph (frequent pattern graph). Added evolvability and genetic operator average improvement analyzer.

File size: 11.8 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.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.Random;
33using HeuristicLab.Selection;
34
35namespace HeuristicLab.EvolutionaryTracking.Analyzers {
36  /// <summary>
37  /// An analyzer that adapts selection pressure based on average three length
38  /// </summary>
39  [Item("SymbolicExpressionTreeRelativeLengthAnalyzer", "An analyzer that adapts selection pressure based on average three length")]
40  [StorableClass]
41  class SymbolicExpressionTreeRelativeLengthAnalyzer : SingleSuccessorOperator, IAnalyzer {
42    private const string UpdateIntervalParameterName = "UpdateInterval";
43    private const string UpdateCounterParameterName = "UpdateCounter";
44    private const string ResultsParameterName = "Results";
45    private const string GenerationsParameterName = "Generations";
46
47    private const string ExpectedAverageTreeLenghtParameterName = "ExpectedAverageTreeLength";
48    private const string RandomSelectionWindowSizeParameterName = "RandomSelectionWindowSize";
49    private const string RandomSelectionGenerationsCounterParameterName = "RandomSelectionGenerationsCounter";
50    private const string UpperBoundingFactorParameterName = "UpperBoundingFactor";
51    private const string LowerBoundingFactorParameterName = "LowerBoundingFactor";
52    private const string ActualTournamentGroupSizeParameterName = "TournamentGroupSize";
53
54    readonly MersenneTwister random = new MersenneTwister(12345);
55
56    #region Parameter properties
57    public ValueParameter<IntValue> UpdateIntervalParameter {
58      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
59    }
60    public ValueParameter<IntValue> UpdateCounterParameter {
61      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
62    }
63    public LookupParameter<ResultCollection> ResultsParameter {
64      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
65    }
66    public LookupParameter<IntValue> GenerationsParameter {
67      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
68    }
69    public ValueParameter<DoubleValue> ExpectedAverageTreeLengthParameter {
70      get { return (ValueParameter<DoubleValue>)Parameters[ExpectedAverageTreeLenghtParameterName]; }
71    }
72    public ValueParameter<DoubleValue> UpperBoundingFactorParameter {
73      get { return (ValueParameter<DoubleValue>)Parameters[UpperBoundingFactorParameterName]; }
74    }
75    public ValueParameter<DoubleValue> LowerBoundingFactorParameter {
76      get { return (ValueParameter<DoubleValue>)Parameters[LowerBoundingFactorParameterName]; }
77    }
78    public ValueParameter<IntValue> RandomSelectionWindowSizeParameter {
79      get { return (ValueParameter<IntValue>)Parameters[RandomSelectionWindowSizeParameterName]; }
80    }
81    public ValueParameter<IntValue> RandomSelectionGenerationsCounterParameter {
82      get { return (ValueParameter<IntValue>)Parameters[RandomSelectionGenerationsCounterParameterName]; }
83    }
84    public ValueParameter<IntValue> ActualTournamentGroupSizeParameter {
85      get { return (ValueParameter<IntValue>)Parameters[ActualTournamentGroupSizeParameterName]; }
86    }
87    #endregion
88
89    #region Parameters
90    public bool EnabledByDefault {
91      get { return true; }
92    }
93    public IntValue UpdateInterval {
94      get { return UpdateIntervalParameter.Value; }
95    }
96    public IntValue UpdateCounter {
97      get { return UpdateCounterParameter.Value; }
98    }
99    public ResultCollection Results {
100      get { return ResultsParameter.ActualValue; }
101    }
102    public IntValue Generations {
103      get { return GenerationsParameter.ActualValue; }
104    }
105    public DoubleValue ExpectedAverageTreeLength {
106      get { return (DoubleValue)ExpectedAverageTreeLengthParameter.ActualValue; }
107    }
108    public IntValue RandomSelectionWindowSize {
109      get { return (IntValue)RandomSelectionWindowSizeParameter.ActualValue; }
110    }
111    public IntValue RandomSelectionGenerationsCounter {
112      get { return (IntValue)RandomSelectionGenerationsCounterParameter.ActualValue; }
113    }
114    public IntValue ActualTournamentGroupSize {
115      get { return (IntValue)ActualTournamentGroupSizeParameter.ActualValue; }
116      set { ActualTournamentGroupSizeParameter.ActualValue = value; }
117    }
118    public DoubleValue LowerBoundingFactor {
119      get { return (DoubleValue)LowerBoundingFactorParameter.ActualValue; }
120    }
121    public DoubleValue UpperBoundingFactor {
122      get { return (DoubleValue)UpperBoundingFactorParameter.ActualValue; }
123    }
124    #endregion
125
126    [StorableConstructor]
127    protected SymbolicExpressionTreeRelativeLengthAnalyzer(bool deserializing)
128      : base() {
129    }
130    protected SymbolicExpressionTreeRelativeLengthAnalyzer(SymbolicExpressionTreeRelativeLengthAnalyzer original, Cloner cloner)
131      : base(original, cloner) {
132    }
133    public override IDeepCloneable Clone(Cloner cloner) {
134      return new SymbolicExpressionTreeRelativeLengthAnalyzer(this, cloner);
135    }
136    public SymbolicExpressionTreeRelativeLengthAnalyzer()
137      : base() {
138      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
139      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
140      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
141      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
142      Parameters.Add(new ValueParameter<DoubleValue>(ExpectedAverageTreeLenghtParameterName, "The expected statistical average of the tree length for given grammar and depth and random trees", new DoubleValue(0)));
143      Parameters.Add(new ValueParameter<DoubleValue>(UpperBoundingFactorParameterName, "Multiplier for the expected average size, giving the upper bound of the average size length", new DoubleValue(3.0)));
144      Parameters.Add(new ValueParameter<DoubleValue>(LowerBoundingFactorParameterName, "Multiplier for the expected average size, giving the lower bound of the average size length", new DoubleValue(2.0)));
145      Parameters.Add(new ValueParameter<IntValue>(RandomSelectionWindowSizeParameterName, "Maximum window for random selection (in generations)"));
146      Parameters.Add(new ValueParameter<IntValue>(RandomSelectionGenerationsCounterParameterName, "Counter for the consecutive random selection generations"));
147      Parameters.Add(new ValueParameter<IntValue>(ActualTournamentGroupSizeParameterName, "Parameter to store the actual tournament size so we can reuse it later.", new IntValue(0)));
148
149      UpdateCounterParameter.Hidden = true;
150      UpdateIntervalParameter.Hidden = true;
151    }
152    #region After deserialization code
153    [StorableHook(HookType.AfterDeserialization)]
154    private void AfterDeserialization() {
155      // check if all the parameters are present and accounted for
156      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
157        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
158      }
159      if (!Parameters.ContainsKey(UpdateCounterParameterName)) {
160        Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
161        UpdateCounterParameter.Hidden = true;
162      }
163    }
164    #endregion
165    #region IStatefulItem members
166    public override void InitializeState() {
167      base.InitializeState();
168      UpdateCounter.Value = 0;
169    }
170
171    public override void ClearState() {
172      base.ClearState();
173      UpdateCounter.Value = 0;
174    }
175    #endregion
176
177    public override IOperation Apply() {
178      UpdateCounter.Value++;
179      if (UpdateCounter.Value == UpdateInterval.Value) {
180        UpdateCounter.Value = 0;
181
182        var gaContext = ExecutionContext.Parent.Parent;
183        var selectorParameter = gaContext.Parameters["Selector"];
184        var selector = selectorParameter.ActualValue as TournamentSelector;
185        var gScope = ExecutionContext.Scope;
186        while (gScope.Parent != null) gScope = gScope.Parent;
187
188        if (Generations.Value == 0) {
189          UpdateCounter.Value = 0; // reset the update counter
190          if (ActualTournamentGroupSize.Value == 0)
191            ActualTournamentGroupSize = new IntValue(selector.GroupSizeParameter.Value.Value);
192          else
193            selector.GroupSizeParameter.Value = ActualTournamentGroupSize;
194
195          // check the threshhold value by simulating the average tree length using the GrowTreeCreator
196          var randomTrees = new List<ISymbolicExpressionTree>();
197
198          var problemContext = gaContext.Parent;
199
200          var grammar = (ISymbolicExpressionGrammar)problemContext.Parameters["SymbolicExpressionTreeGrammar"].ActualValue;
201          var maxDepth = (IntValue)problemContext.Parameters["MaximumSymbolicExpressionTreeDepth"].ActualValue;
202
203          long length = 0;
204          const uint size = 1000;
205          for (int i = 0; i != size; ++i) {
206            randomTrees.Add(GrowTreeCreator.Create(random, grammar, 0, maxDepth.Value));
207            length += randomTrees.Last().Length;
208          }
209          ExpectedAverageTreeLength.Value = (double)length / size;
210
211          return base.Apply();
212        } else if (Generations.Value >= 10) {
213          // this should provide a bloat control mechanism while allowing population diversity to increase
214          double currentAverageTreeLength = (from s in gScope.SubScopes
215                                             let tree = s.Variables.First().Value as ISymbolicExpressionTree
216                                             select tree.Length).Average();
217
218          double expectedAverage = ExpectedAverageTreeLength.Value;
219
220          if (currentAverageTreeLength >= UpperBoundingFactor.Value * expectedAverage) {
221            SetGroupSize(selector, 1);
222          }
223          if (RandomSelectionGenerationsCounter.Value == RandomSelectionWindowSize.Value ||
224              currentAverageTreeLength <= LowerBoundingFactor.Value * expectedAverage) {
225
226            SetGroupSize(selector, ActualTournamentGroupSize.Value);
227            RandomSelectionGenerationsCounter.Value = 0;
228          } else {
229            RandomSelectionGenerationsCounter.Value++;
230          }
231        }
232      }
233      return base.Apply();
234    }
235
236    void SetGroupSize(TournamentSelector ts, int value) {
237      ts.GroupSizeParameter.Value = new IntValue(value);
238    }
239  }
240}
Note: See TracBrowser for help on using the repository browser.