source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs @ 9083

#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;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
  /// <summary>
  /// A base class for operators that manipulate real-valued vectors.
  /// </summary>
  [Item("TracingSymbolicExpressionTreeManipulator", "A base class for operators that manipulate symbolic expression trees.")]
  [StorableClass]
  public abstract class TracingSymbolicExpressionTreeManipulator : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    [Storable]
    private readonly Dictionary<Type, byte> manipulationTypes = new Dictionary<Type, byte>();

    #region Parameter Properties
    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    }
    #endregion

    #region Properties
    public ISymbolicExpressionTree SymbolicExpressionTree {
      get { return SymbolicExpressionTreeParameter.ActualValue; }
    }
    #endregion

    [StorableConstructor]
    protected TracingSymbolicExpressionTreeManipulator(bool deserializing) : base(deserializing) { }
    protected TracingSymbolicExpressionTreeManipulator(TracingSymbolicExpressionTreeManipulator original, Cloner cloner)
      : base(original, cloner) {
      this.manipulationTypes = new Dictionary<Type, byte>(original.manipulationTypes);
    }
    public TracingSymbolicExpressionTreeManipulator()
      : base() {
      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree on which the operator should be applied."));

      manipulationTypes.Add(typeof(FullTreeShaker), ManipulationType.FullTreeShaker);
      manipulationTypes.Add(typeof(OnePointShaker), ManipulationType.OnePointShaker);
      manipulationTypes.Add(typeof(ChangeNodeTypeManipulation), ManipulationType.ChangeNodeTypeManipulation);
      manipulationTypes.Add(typeof(ReplaceBranchManipulation), ManipulationType.ReplaceBranchManipulation);
    }

    public sealed override IOperation Apply() {
      ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;

      AddTracingVariablesToGlobalScope();

      /* The following block needs to be explained in more detail;
       * If the tree was already affected by crossover (before mutation), then:
       * - it will already be contained in the GlobalTraceMap
       * - In order to preserve information, a clone of the tree is created
       * - The clone represents the intermediate stage of the tree, before mutation is applied
       * - The clone therefore represents the child after crossover so GlobalTraceMap[clone] will get tree's parents
       *   and GlobalFragmentMap[clone] will get the subtree from clone that represents the cloned fragment
       * - After tree is mutated, we set GlobalTraceMap[tree] = clone and GlobalFragmentMap[tree] = modified node from tree
       */
      Fragment fragment = null;
      if (GlobalTraceMap.ContainsKey(tree)) {
        var clone = (IItem)tree.Clone();
        GlobalCloneMap[clone] = GlobalCloneMap[tree];
        GlobalCloneMap[tree] = clone;
        GlobalTraceMap[clone] = GlobalTraceMap[tree]; // clone gets parents of tree
        GlobalTraceMap[tree] = new ItemList<IItem> { clone }; // tree gets clone as parent
        fragment = (Fragment)GlobalFragmentMap[tree];
        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment.Root); // returns -1 if fragment is not present in tree (can happen if fragment is null)
        GlobalFragmentMap[clone] = new Fragment(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
      } else {
        GlobalTraceMap[tree] = new ItemList<IItem> { GlobalCloneMap[tree] };
      }

      var concreteType = this.GetType();

      if (!manipulationTypes.ContainsKey(concreteType))
        throw new Exception(this.Name + ": Unknown manipulation type (key not found in the dictionary).");

      var nodes0 = tree.IterateNodesBreadth().ToList(); // list of nodes before manipulation
      Manipulate(RandomParameter.ActualValue, tree);
      var nodes1 = tree.IterateNodesBreadth().ToList(); // list of nodes after manipulation
      int min = Math.Min(nodes0.Count, nodes1.Count);

      switch (manipulationTypes[concreteType]) {
        case ManipulationType.FullTreeShaker: {
            // the FullTreeShaker changes the local parameters of all the nodes in the tree
            // therefore, the whole tree is considered to be the fragment
            fragment = new Fragment(tree.Root.GetSubtree(0).GetSubtree(0));
            break;
          }
        case ManipulationType.OnePointShaker: {
            var original = (ISymbolicExpressionTree)GlobalCloneMap[tree];
            var nodesOriginal = original.IterateNodesBreadth().ToList();
            int i = 0;
            var comparer = SymbolicExpressionTreeNodeComparer;
            while (i != min && comparer.Equals(nodesOriginal[i], nodes1[i])) ++i;
            fragment = new Fragment(i == min ? null : nodes1[i], 1);
            break;
          }
        case ManipulationType.ChangeNodeTypeManipulation: {
            int i = 0;
            while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
            fragment = new Fragment(i == min ? null : nodes1[i], 1);
            break;
          }
        case ManipulationType.ReplaceBranchManipulation: {
            int i = 0;
            while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
            fragment = new Fragment(i == min ? null : nodes1[i]);
            break;
          }
        default:
          throw new Exception(Name + ": Unknown manipulaton type.");
      }

      GlobalFragmentMap[tree] = fragment;
      return base.Apply();
    }

    protected abstract void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree);

    private struct ManipulationType {
      public const byte FullTreeShaker = 1;
      public const byte OnePointShaker = 2;
      public const byte ChangeNodeTypeManipulation = 3;
      public const byte ReplaceBranchManipulation = 4;
    }
  }
}