Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs @ 12952

Last change on this file since 12952 was 12952, checked in by bburlacu, 8 years ago

#1772: Add tracking of the number of trees that are mutated during the diversification phase by the SchemaEvaluator.

File size: 8.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.EvolutionTracking;
30using HeuristicLab.Operators;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34
35namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tracking {
36  [Item("SchemaCreator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
37  [StorableClass]
38  public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
39    private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
40    private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
41    private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
42    private const string ReplacementRatioParameterName = "ReplacementRatio";
43    private const string RandomReplacementParameterName = "RandomReplacement";
44
45    #region parameters
46    public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
47      get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
48    }
49
50    public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
51      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
52    }
53
54    public IFixedValueParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
55      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
56    }
57
58    public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
59      get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
60    }
61
62    private IFixedValueParameter<BoolValue> RandomReplacementParameter {
63      get { return (IFixedValueParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
64    }
65    #endregion
66
67    #region parameter properties
68    public int MinimumSchemaLength {
69      get { return MinimumSchemaLengthParameter.Value.Value; }
70    }
71    #endregion
72
73    public SchemaCreator() {
74      Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
75      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.05)));
76      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.8)));
77      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.2)));
78      Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
79    }
80
81    protected SchemaCreator(SchemaCreator original, Cloner cloner) : base(original, cloner) { }
82
83    public override IDeepCloneable Clone(Cloner cloner) {
84      return new SchemaCreator(this, cloner);
85    }
86
87    [StorableConstructor]
88    protected SchemaCreator(bool deserializing) : base(deserializing) { }
89
90    public override IOperation Apply() {
91      // apply only when at least one generation has passed
92      var gen = Generations.Value;
93      if (gen < 1 || GenealogyGraph == null)
94        return base.Apply();
95      // for now, only consider crossover offspring
96      var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
97      var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
98      var anySubtreeSymbol = new AnySubtreeSymbol();
99
100      var schemaEvaluator = new SchemaEvaluator();
101      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
102      var schemaCleanupOperator = new SchemaCleanupOperator();
103
104      var changedTreesReducer = new DataReducer();
105      changedTreesReducer.ParameterToReduce.ActualName = schemaEvaluator.ChangedTreesParameter.ActualName;
106      changedTreesReducer.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
107      changedTreesReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Assign); // asign the sum to the target parameter
108      changedTreesReducer.TargetParameter.ActualName = "NumberOfChangedTrees";
109
110      var valuesCollector = new DataTableValuesCollector();
111      valuesCollector.CollectedValues.Add(new LookupParameter<IntValue>("NumberOfChangedTrees"));
112      valuesCollector.DataTableParameter.ActualName = "Diversification";
113
114      var resultCollector = new ResultsCollector();
115      resultCollector.CollectedValues.Add(new LookupParameter<DataTable>("Diversification"));
116
117      var reduceChangedTrees = ExecutionContext.CreateChildOperation(changedTreesReducer);
118      var collectValues = ExecutionContext.CreateChildOperation(valuesCollector);
119      var collectResults = ExecutionContext.CreateChildOperation(resultCollector);
120
121      var oc = new OperationCollection();
122
123      #region create schemas and add subscopes representing the individuals
124      foreach (var g in groups) {
125        var parent = g.Key;
126        if (parent.Data.Length < MinimumSchemaLength)
127          continue;
128        bool replaced = false;
129        var schema = (ISymbolicExpressionTree)parent.Data.Clone();
130        var nodes = schema.IterateNodesPrefix().ToList();
131        var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
132        var indices = arcs.Select(x => ((IFragment<ISymbolicExpressionTreeNode>)x.Data).Index1).Distinct().ToArray();
133        Array.Sort(indices);
134        var nodesToReplace = indices.Where(x => x >= 2).Select(x => nodes[x]).ToList();
135        for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
136          var node = nodesToReplace[i];
137
138          // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
139          if ((schema.Length - node.GetLength() + 1) < MinimumSchemaLength)
140            continue;
141
142          var replacement = anySubtreeSymbol.CreateTreeNode();
143          ReplaceSubtree(node, replacement, false);
144          replaced = true;
145        }
146        if (replaced) {
147          var scope = new Scope("Schema");
148          scope.Variables.Add(new Core.Variable("Schema", schema));
149          scope.SubScopes.AddRange(ShallowCopy(scopes));
150
151          oc.Add(ExecutionContext.CreateChildOperation(schemaEvaluator, scope));
152          ExecutionContext.Scope.SubScopes.Add(scope);
153        }
154      }
155      #endregion
156
157      var cleanup = ExecutionContext.CreateChildOperation(schemaCleanupOperator);
158      // return an operation collection containing all the scope operations + base.Apply()
159      return new OperationCollection { oc, reduceChangedTrees, collectValues, collectResults, cleanup, base.Apply() };
160    }
161
162    private static ScopeList ShallowCopy(ScopeList scopes) {
163      var scopeList = new ScopeList();
164      // shallow-copy means that we create a new scope but reuse the variables
165      foreach (var scope in scopes) {
166        var s = new Scope(scope.Name);
167        foreach (var v in scope.Variables)
168          s.Variables.Add(v);
169        scopeList.Add(s);
170      }
171      return scopeList;
172    }
173
174    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement,
175      bool preserveChildren = true) {
176      var parent = original.Parent;
177      if (parent == null)
178        throw new ArgumentException("Parent cannot be null for node " + original);
179      var index = parent.IndexOfSubtree(original);
180      parent.RemoveSubtree(index);
181      parent.InsertSubtree(index, replacement);
182
183      if (preserveChildren) {
184        var subtrees = original.Subtrees.ToList();
185
186        for (int i = subtrees.Count - 1; i >= 0; --i)
187          original.RemoveSubtree(i);
188
189        for (int i = 0; i < subtrees.Count; ++i) {
190          replacement.AddSubtree(subtrees[i]);
191        }
192      }
193    }
194  }
195}
Note: See TracBrowser for help on using the repository browser.