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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;
using HeuristicLab.Selection;

namespace HeuristicLab.EvolutionaryTracking.Analyzers {
  /// <summary>
  /// An analyzer that adapts selection pressure based on average three length
  /// </summary>
  [Item("SymbolicExpressionTreeRelativeLengthAnalyzer", "An analyzer that adapts selection pressure based on average three length")]
  [StorableClass]
  class SymbolicExpressionTreeRelativeLengthAnalyzer : SingleSuccessorOperator, IAnalyzer {
    private const string UpdateIntervalParameterName = "UpdateInterval";
    private const string UpdateCounterParameterName = "UpdateCounter";
    private const string ResultsParameterName = "Results";
    private const string GenerationsParameterName = "Generations";

    private const string ExpectedAverageTreeLenghtParameterName = "ExpectedAverageTreeLength";
    private const string RandomSelectionWindowSizeParameterName = "RandomSelectionWindowSize";
    private const string RandomSelectionGenerationsCounterParameterName = "RandomSelectionGenerationsCounter";
    private const string UpperBoundingFactorParameterName = "UpperBoundingFactor";
    private const string LowerBoundingFactorParameterName = "LowerBoundingFactor";
    private const string ActualTournamentGroupSizeParameterName = "TournamentGroupSize";

    readonly MersenneTwister _random = new MersenneTwister(12345);

    #region Parameter properties
    public ValueParameter<IntValue> UpdateIntervalParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
    }
    public ValueParameter<IntValue> UpdateCounterParameter {
      get { return (ValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
    }
    public LookupParameter<ResultCollection> ResultsParameter {
      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
    }
    public LookupParameter<IntValue> GenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters[GenerationsParameterName]; }
    }
    public ValueParameter<DoubleValue> ExpectedAverageTreeLengthParameter {
      get { return (ValueParameter<DoubleValue>)Parameters[ExpectedAverageTreeLenghtParameterName]; }
    }
    public ValueParameter<DoubleValue> UpperBoundingFactorParameter {
      get { return (ValueParameter<DoubleValue>)Parameters[UpperBoundingFactorParameterName]; }
    }
    public ValueParameter<DoubleValue> LowerBoundingFactorParameter {
      get { return (ValueParameter<DoubleValue>)Parameters[LowerBoundingFactorParameterName]; }
    }
    public ValueParameter<IntValue> RandomSelectionWindowSizeParameter {
      get { return (ValueParameter<IntValue>)Parameters[RandomSelectionWindowSizeParameterName]; }
    }
    public ValueParameter<IntValue> RandomSelectionGenerationsCounterParameter {
      get { return (ValueParameter<IntValue>)Parameters[RandomSelectionGenerationsCounterParameterName]; }
    }
    public ValueParameter<IntValue> ActualTournamentGroupSizeParameter {
      get { return (ValueParameter<IntValue>)Parameters[ActualTournamentGroupSizeParameterName]; }
    }
    #endregion

    #region Parameters
    public bool EnabledByDefault {
      get { return true; }
    }
    public IntValue UpdateInterval {
      get { return UpdateIntervalParameter.Value; }
    }
    public IntValue UpdateCounter {
      get { return UpdateCounterParameter.Value; }
    }
    public ResultCollection Results {
      get { return ResultsParameter.ActualValue; }
    }
    public IntValue Generations {
      get { return GenerationsParameter.ActualValue; }
    }
    public DoubleValue ExpectedAverageTreeLength {
      get { return (DoubleValue)ExpectedAverageTreeLengthParameter.ActualValue; }
    }
    public IntValue RandomSelectionWindowSize {
      get { return (IntValue)RandomSelectionWindowSizeParameter.ActualValue; }
    }
    public IntValue RandomSelectionGenerationsCounter {
      get { return (IntValue)RandomSelectionGenerationsCounterParameter.ActualValue; }
    }
    public IntValue ActualTournamentGroupSize {
      get { return (IntValue)ActualTournamentGroupSizeParameter.ActualValue; }
      set { ActualTournamentGroupSizeParameter.ActualValue = value; }
    }
    public DoubleValue LowerBoundingFactor {
      get { return (DoubleValue)LowerBoundingFactorParameter.ActualValue; }
    }
    public DoubleValue UpperBoundingFactor {
      get { return (DoubleValue)UpperBoundingFactorParameter.ActualValue; }
    }
    #endregion

    [StorableConstructor]
    private SymbolicExpressionTreeRelativeLengthAnalyzer(bool deserializing)
      : base() {
    }
    private SymbolicExpressionTreeRelativeLengthAnalyzer(SymbolicExpressionTreeRelativeLengthAnalyzer original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicExpressionTreeRelativeLengthAnalyzer(this, cloner);
    }
    public SymbolicExpressionTreeRelativeLengthAnalyzer()
      : base() {
      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
      Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
      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)));
      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)));
      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)));
      Parameters.Add(new ValueParameter<IntValue>(RandomSelectionWindowSizeParameterName, "Maximum window for random selection (in generations)"));
      Parameters.Add(new ValueParameter<IntValue>(RandomSelectionGenerationsCounterParameterName, "Counter for the consecutive random selection generations"));
      Parameters.Add(new ValueParameter<IntValue>(ActualTournamentGroupSizeParameterName, "Parameter to store the actual tournament size so we can reuse it later.", new IntValue(0)));

      UpdateCounterParameter.Hidden = true;
      UpdateIntervalParameter.Hidden = true;
    }
    #region After deserialization code
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      // check if all the parameters are present and accounted for 
      if (!Parameters.ContainsKey(UpdateIntervalParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
      }
      if (!Parameters.ContainsKey(UpdateCounterParameterName)) {
        Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));
        UpdateCounterParameter.Hidden = true;
      }
    }
    #endregion
    #region IStatefulItem members
    public override void InitializeState() {
      base.InitializeState();
      UpdateCounter.Value = 0;
    }

    public override void ClearState() {
      base.ClearState();
      UpdateCounter.Value = 0;
    }
    #endregion

    public override IOperation Apply() {
      UpdateCounter.Value++;
      if (UpdateCounter.Value == UpdateInterval.Value) {
        UpdateCounter.Value = 0;

        var gaContext = ExecutionContext.Parent.Parent;
        var selectorParameter = gaContext.Parameters["Selector"];
        var selector = selectorParameter.ActualValue as TournamentSelector;
        var gScope = ExecutionContext.Scope;
        while (gScope.Parent != null) gScope = gScope.Parent;

        if (Generations.Value == 0) {
          UpdateCounter.Value = 0; // reset the update counter
          if (ActualTournamentGroupSize.Value == 0)
            ActualTournamentGroupSize = new IntValue(selector.GroupSizeParameter.Value.Value);
          else
            selector.GroupSizeParameter.Value = ActualTournamentGroupSize;

          // check the threshhold value by simulating the average tree length using the GrowTreeCreator
          var randomTrees = new List<ISymbolicExpressionTree>();

          var problemContext = gaContext.Parent;

          var grammar = (ISymbolicExpressionGrammar)problemContext.Parameters["SymbolicExpressionTreeGrammar"].ActualValue;
          var maxDepth = (IntValue)problemContext.Parameters["MaximumSymbolicExpressionTreeDepth"].ActualValue;

          long length = 0;
          const uint size = 1000;
          for (int i = 0; i != size; ++i) {
            randomTrees.Add(GrowTreeCreator.Create(_random, grammar, 0, maxDepth.Value));
            length += randomTrees.Last().Length;
          }
          ExpectedAverageTreeLength.Value = (double)length / size;

          return base.Apply();
        } else if (Generations.Value >= 10) {
          // this should provide a bloat control mechanism while allowing population diversity to increase
          double currentAverageTreeLength = (from s in gScope.SubScopes
                                             let tree = s.Variables.First().Value as ISymbolicExpressionTree
                                             select tree.Length).Average();

          double expectedAverage = ExpectedAverageTreeLength.Value;

          if (currentAverageTreeLength >= UpperBoundingFactor.Value * expectedAverage) {
            SetGroupSize(selector, 1);
          }
          if (RandomSelectionGenerationsCounter.Value == RandomSelectionWindowSize.Value ||
              currentAverageTreeLength <= LowerBoundingFactor.Value * expectedAverage) {

            SetGroupSize(selector, ActualTournamentGroupSize.Value);
            RandomSelectionGenerationsCounter.Value = 0;
          } else {
            RandomSelectionGenerationsCounter.Value++;
          }
        }
      }
      return base.Apply();
    }

    void SetGroupSize(TournamentSelector ts, int value) {
      ts.GroupSizeParameter.Value = new IntValue(value);
    }
  }
}