Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs @ 8213

Last change on this file since 8213 was 8213, checked in by bburlacu, 12 years ago

#1772: Performance improvements for the GenealogyGraph. Minor refactoring to VisualGenealogyGraphArc and VisualGenealogyGraphNode classes. Added new functionality to the SymbolicExpressionTreeFragmentsAnalyzer, minor refactoring in the other two analyzers. Refactored View code. Updated project references and plugin dependencies and added HeuristicLab.Problems.DataAnalysis.Symbolic to the branch.

File size: 7.0 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.EvolutionaryTracking;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
31using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
32
33namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
34  /// <summary>
35  /// A base class for operators that perform a crossover of symbolic expression trees.
36  /// </summary>
37  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
38  [StorableClass]
39  public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
40    private const string ParentsParameterName = "Parents";
41    private const string ChildParameterName = "Child";
42    private const string GlobalTraceMapParameterName = "GlobalTraceMap";
43    private const string GlobalCloneMapParameterName = "GlobalCloneMap";
44    private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
45
46    #region Parameter Properties
47    public ILookupParameter<ItemArray<ISymbolicExpressionTree>> ParentsParameter {
48      get { return (ScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[ParentsParameterName]; }
49    }
50    public ILookupParameter<ISymbolicExpressionTree> ChildParameter {
51      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[ChildParameterName]; }
52    }
53    public LookupParameter<CloneMapType> GlobalCloneMapParameter {
54      get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
55    }
56    public LookupParameter<TraceMapType> GlobalTraceMapParameter {
57      get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
58    }
59    public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
60      get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
61    }
62    #endregion
63
64    #region Properties
65    public ItemArray<ISymbolicExpressionTree> Parents {
66      get { return ParentsParameter.ActualValue; }
67    }
68    public ISymbolicExpressionTree Child {
69      get { return ChildParameter.ActualValue; }
70      set { ChildParameter.ActualValue = value; }
71    }
72    public CloneMapType GlobalCloneMap {
73      get { return GlobalCloneMapParameter.ActualValue; }
74    }
75    public TraceMapType GlobalTraceMap {
76      get { return GlobalTraceMapParameter.ActualValue; }
77    }
78    public CloneMapType GlobalFragmentMap {
79      get { return GlobalFragmentMapParameter.ActualValue; }
80    }
81    #endregion
82
83    [StorableConstructor]
84    protected TracingSymbolicExpressionTreeCrossover(bool deserializing)
85      : base(deserializing) {
86    }
87
88    protected TracingSymbolicExpressionTreeCrossover(TracingSymbolicExpressionTreeCrossover original, Cloner cloner)
89      : base(original, cloner) {
90    }
91
92    protected TracingSymbolicExpressionTreeCrossover()
93      : base() {
94      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
95      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
96      Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
97      Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
98      Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
99    }
100
101    public sealed override IOperation Apply() {
102      if (Parents.Length != 2)
103        throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
104
105      // add global trace cache if not already present in global scope
106      var gScope = ExecutionContext.Scope;
107      while (gScope.Parent != null)
108        gScope = gScope.Parent;
109      if (GlobalTraceMap == null)
110        gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
111      if (GlobalFragmentMap == null)
112        gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
113
114      // get original parents (this info will be needed later to construct the genealogy graph)
115      var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
116
117      // save the nodes of parent0 in a list so we can track what modifications are made by crossover
118      var nodes0 = Parents[0].IterateNodesBreadth().ToList();
119
120      // perform crossover
121      Child = Crossover(Random, Parents[0], Parents[1]);
122
123      // create another list of parent0's nodes, so we can compare it with the first list to see what changed
124      var nodes1 = Child.IterateNodesBreadth().ToList();
125
126      // compare the two nodes lists and check the difference (comparing node references so we avoid false functional identity).
127      // if no difference is found, then it is assumed that the whole tree was swapped with itself (it can happen), so the index is 0
128      int i, min = Math.Min(nodes0.Count, nodes1.Count);
129      for (i = 0; i != min; ++i)
130        if (nodes0[i] != nodes1[i]) break;
131      // add heredity information into the global variables
132      GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
133      GlobalFragmentMap[Child] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]); // map child to the index of its fragment
134      return base.Apply();
135    }
136
137    public abstract ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1);
138  }
139}
Note: See TracBrowser for help on using the repository browser.