Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1772:

  • Slight refactor in QueryMatch.cs
  • Added a parameter to the genealogy analyzer for removing older generations from the graph (useful to conserve memory in experiments)
  • Updated wildcard nodes (added persistence & cloning)
  • Implemented diversification strategy based on schema frequencies & phenotypic similarity as a separate operator (for now keep also the analyzer)
  • Updated license headers
  • Added QueryMatch performance test (to be expanded)
File size: 7.3 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.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.EvolutionTracking;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tracking {
33  [Item("SchemaCreator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
34  [StorableClass]
35  public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
36    private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
37    private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
38    private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
39    private const string ReplacementRatioParameterName = "ReplacementRatio";
40    private const string RandomReplacementParameterName = "RandomReplacement";
41
42    #region parameters
43    public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
44      get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
45    }
46
47    public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
48      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
49    }
50
51    public IFixedValueParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
52      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
53    }
54
55    public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
56      get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
57    }
58
59    private IFixedValueParameter<BoolValue> RandomReplacementParameter {
60      get { return (IFixedValueParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
61    }
62    #endregion
63
64    #region parameter properties
65    public int MinimumSchemaLength {
66      get { return MinimumSchemaLengthParameter.Value.Value; }
67    }
68    #endregion
69
70    public SchemaCreator() {
71      Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
72      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.05)));
73      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.8)));
74      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.2)));
75      Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
76    }
77
78    protected SchemaCreator(SchemaCreator original, Cloner cloner) : base(original, cloner) { }
79
80    public override IDeepCloneable Clone(Cloner cloner) {
81      return new SchemaCreator(this, cloner);
82    }
83
84    [StorableConstructor]
85    protected SchemaCreator(bool deserializing) : base(deserializing) { }
86
87    public override IOperation Apply() {
88      // apply only when at least one generation has passed
89      var gen = Generations.Value;
90      if (gen < 1 || GenealogyGraph == null)
91        return base.Apply();
92      // for now, only consider crossover offspring
93      var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
94      var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
95      var anySubtreeSymbol = new AnySubtreeSymbol();
96
97      var schemaEvaluator = new SchemaEvaluator();
98      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
99      var schemaCleanupOperator = new SchemaCleanupOperator();
100
101      var oc = new OperationCollection();
102
103      #region create schemas and add subscopes representing the individuals
104      foreach (var g in groups) {
105        var parent = g.Key;
106        if (parent.Data.Length < MinimumSchemaLength)
107          continue;
108        bool replaced = false;
109        var schema = (ISymbolicExpressionTree)parent.Data.Clone();
110        var nodes = schema.IterateNodesPrefix().ToList();
111        var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
112        var indices = arcs.Select(x => ((IFragment<ISymbolicExpressionTreeNode>)x.Data).Index1).Distinct().ToArray();
113        Array.Sort(indices);
114        var nodesToReplace = indices.Where(x => x >= 2).Select(x => nodes[x]).ToList();
115        for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
116          var replacement = anySubtreeSymbol.CreateTreeNode();
117          ReplaceSubtree(nodesToReplace[i], replacement, false);
118          replaced = true;
119        }
120        if (replaced) {
121          var scope = new Scope("Schema");
122          scope.Variables.Add(new Core.Variable("Schema", schema));
123          scope.SubScopes.AddRange(ShallowCopy(scopes));
124
125          oc.Add(ExecutionContext.CreateChildOperation(schemaEvaluator, scope));
126          ExecutionContext.Scope.SubScopes.Add(scope);
127        }
128      }
129      #endregion
130
131      var cleanup = ExecutionContext.CreateChildOperation(schemaCleanupOperator);
132      // return an operation collection containing all the scope operations + base.Apply()
133      return new OperationCollection { oc, cleanup, base.Apply() };
134    }
135
136    private static ScopeList ShallowCopy(ScopeList scopes) {
137      var scopeList = new ScopeList();
138      // shallow-copy means that we create a new scope but reuse the variables
139      foreach (var scope in scopes) {
140        var s = new Scope(scope.Name);
141        foreach (var v in scope.Variables)
142          s.Variables.Add(v);
143        scopeList.Add(s);
144      }
145      return scopeList;
146    }
147
148    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement,
149      bool preserveChildren = true) {
150      var parent = original.Parent;
151      if (parent == null)
152        throw new ArgumentException("Parent cannot be null for node " + original);
153      var index = parent.IndexOfSubtree(original);
154      parent.RemoveSubtree(index);
155      parent.InsertSubtree(index, replacement);
156
157      if (preserveChildren) {
158        var subtrees = original.Subtrees.ToList();
159
160        for (int i = subtrees.Count - 1; i >= 0; --i)
161          original.RemoveSubtree(i);
162
163        for (int i = 0; i < subtrees.Count; ++i) {
164          replacement.AddSubtree(subtrees[i]);
165        }
166      }
167    }
168  }
169}
Note: See TracBrowser for help on using the repository browser.