source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs @ 13496

Last change on this file since 13496 was 13496, checked in by bburlacu, 5 years ago

#1772: Update diversification operators (add extra evaluations to the evaluation counter, add the option for strict schema matching, add additional replacement ratio update rules.

File size: 17.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.Collections.Generic;
24using System.Linq;
25using System.Threading.Tasks;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30using HeuristicLab.EvolutionTracking;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
37  [Item("SchemaEvaluator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
38  [StorableClass]
39  public class SchemaEvaluator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
40    #region parameter names
41    private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
42    private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
43    private const string ReplacementRatioParameterName = "ReplacementRatio";
44    private const string SchemaParameterName = "Schema";
45    private const string PopulationSizeParameterName = "PopulationSize";
46    private const string RandomParameterName = "Random";
47    private const string EvaluatorParameterName = "Evaluator";
48    private const string ProblemDataParameterName = "ProblemData";
49    private const string InterpreterParameterName = "SymbolicExpressionTreeInterpreter";
50    private const string EstimationLimitsParameterName = "EstimationLimits";
51    private const string ApplyLinearScalingParameterName = "ApplyLinearScaling";
52    private const string MutatorParameterName = "Mutator";
53    private const string CrossoverParameterName = "Crossover";
54    private const string RandomReplacementParameterName = "RandomReplacement";
55    private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
56    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
57    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
58    private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
59    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
60    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
61    #endregion
62
63    #region parameters
64    public ILookupParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
65      get { return (ILookupParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
66    }
67    public ILookupParameter<BoolValue> ExclusiveMatchingParameter {
68      get { return (ILookupParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
69    }
70    public ILookupParameter<BoolValue> ExecuteInParallelParameter {
71      get { return (ILookupParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
72    }
73    public ILookupParameter<IntValue> MaxDegreeOfParallelismParameter {
74      get { return (ILookupParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
75    }
76    public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
77      get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
78    }
79    public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
80      get { return (ILookupParameter<IRegressionProblemData>)Parameters[ProblemDataParameterName]; }
81    }
82    public ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter> InterpreterParameter {
83      get { return (ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[InterpreterParameterName]; }
84    }
85    public ILookupParameter<DoubleLimit> EstimationLimitsParameter {
86      get { return (ILookupParameter<DoubleLimit>)Parameters[EstimationLimitsParameterName]; }
87    }
88    public ILookupParameter<BoolValue> ApplyLinearScalingParameter {
89      get { return (ILookupParameter<BoolValue>)Parameters[ApplyLinearScalingParameterName]; }
90    }
91    public ILookupParameter<BoolValue> RandomReplacementParameter {
92      get { return (ILookupParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
93    }
94    public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
95      get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
96    }
97    public ILookupParameter<ISymbolicExpressionTreeCrossover> CrossoverParameter {
98      get { return (ILookupParameter<ISymbolicExpressionTreeCrossover>)Parameters[CrossoverParameterName]; }
99    }
100    public ILookupParameter<IRandom> RandomParameter {
101      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
102    }
103    public ILookupParameter<IntValue> PopulationSizeParameter {
104      get { return (ILookupParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
105    }
106    public ILookupParameter<ISymbolicExpressionTree> SchemaParameter {
107      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SchemaParameterName]; }
108    }
109    public ILookupParameter<PercentValue> MinimumSchemaFrequencyParameter {
110      get { return (ILookupParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
111    }
112    public ILookupParameter<PercentValue> ReplacementRatioParameter {
113      get { return (ILookupParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
114    }
115    public ILookupParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
116      get { return (ILookupParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
117    }
118    public LookupParameter<IntValue> NumberOfChangedTreesParameter {
119      get { return (LookupParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
120    }
121    public LookupParameter<BoolValue> StrictSchemaMatchingParameter {
122      get { return (LookupParameter<BoolValue>)Parameters[StrictSchemaMatchingParameterName]; }
123    }
124    #endregion
125
126    #region parameter properties
127    public PercentValue MinimumSchemaFrequency { get { return MinimumSchemaFrequencyParameter.ActualValue; } }
128    public PercentValue ReplacementRatio { get { return ReplacementRatioParameter.ActualValue; } }
129    public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
130    public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
131    public IntValue NumberOfChangedTrees { get { return NumberOfChangedTreesParameter.ActualValue; } }
132    #endregion
133
134    private readonly SymbolicExpressionTreePhenotypicSimilarityCalculator calculator = new SymbolicExpressionTreePhenotypicSimilarityCalculator();
135    private readonly QueryMatch qm;
136
137    public Func<double, double> ReplacementRule { get; set; }
138
139    private readonly ISymbolicExpressionTreeNodeEqualityComparer comp = new SymbolicExpressionTreeNodeEqualityComparer {
140      MatchConstantValues = false,
141      MatchVariableWeights = false,
142      MatchVariableNames = true
143    };
144
145    public ISymbolicExpressionTree Schema { get; set; }
146
147    [Storable]
148    private readonly UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
149
150    [StorableHook(HookType.AfterDeserialization)]
151    private void AfterDeserialization() {
152      if (!Parameters.ContainsKey(StrictSchemaMatchingParameterName))
153        Parameters.Add(new LookupParameter<BoolValue>(StrictSchemaMatchingParameterName));
154    }
155
156    public SchemaEvaluator() {
157      qm = new QueryMatch(comp) { MatchParents = true };
158      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
159      #region add parameters
160      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
161      Parameters.Add(new LookupParameter<PercentValue>(MinimumSchemaFrequencyParameterName));
162      Parameters.Add(new LookupParameter<PercentValue>(ReplacementRatioParameterName));
163      Parameters.Add(new LookupParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName));
164      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(PopulationSizeParameterName));
165      Parameters.Add(new LookupParameter<IRandom>(RandomParameterName));
166      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>(EvaluatorParameterName));
167      Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
168      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(InterpreterParameterName));
169      Parameters.Add(new LookupParameter<DoubleLimit>(EstimationLimitsParameterName));
170      Parameters.Add(new LookupParameter<BoolValue>(ApplyLinearScalingParameterName));
171      Parameters.Add(new LookupParameter<BoolValue>(StrictSchemaMatchingParameterName));
172      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
173      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeCrossover>(CrossoverParameterName));
174      Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
175      Parameters.Add(new LookupParameter<IntValue>(NumberOfChangedTreesParameterName));
176      Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
177      Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
178      Parameters.Add(new LookupParameter<BoolValue>(ExclusiveMatchingParameterName));
179      Parameters.Add(new LookupParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName));
180      #endregion
181    }
182
183    [StorableConstructor]
184    protected SchemaEvaluator(bool deserializing) : base(deserializing) { }
185
186    protected SchemaEvaluator(SchemaEvaluator original, Cloner cloner) : base(original, cloner) {
187      this.comp = original.comp == null ? new SymbolicExpressionTreeNodeEqualityComparer {
188        MatchConstantValues = false,
189        MatchVariableWeights = false,
190        MatchVariableNames = true
191      } : (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
192      this.qm = new QueryMatch(comp) { MatchParents = original.qm?.MatchParents ?? true };
193      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
194    }
195
196    public override IDeepCloneable Clone(Cloner cloner) {
197      return new SchemaEvaluator(this, cloner);
198    }
199
200    public override IOperation Apply() {
201      var strictSchemaMatching = StrictSchemaMatchingParameter.ActualValue.Value;
202      if (strictSchemaMatching) {
203        comp.MatchVariableWeights = true;
204        comp.MatchConstantValues = true;
205      } else {
206        comp.MatchVariableWeights = false;
207        comp.MatchConstantValues = false;
208      }
209
210      var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
211      var trees = individuals.Select(x => (ISymbolicExpressionTree)x.Variables["SymbolicExpressionTree"].Value).ToList();
212
213      var random = RandomParameter.ActualValue;
214      var mutator = MutatorParameter.ActualValue;
215
216      var s = Schema;
217      var sRoot = s.Root.GetSubtree(0).GetSubtree(0);
218      int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
219
220      // first apply the length and root equality checks in order to filter the individuals
221      var exclusiveMatching = ExclusiveMatchingParameter.ActualValue.Value;
222      var filtered = new List<int>();
223      for (int i = 0; i < individuals.Count; ++i) {
224        if (exclusiveMatching && individuals[i].Variables.ContainsKey("AlreadyMatched")) continue;
225        var t = trees[i];
226        var tRoot = t.Root.GetSubtree(0).GetSubtree(0);
227        if (t.Length < s.Length || !qm.Comparer.Equals(tRoot, sRoot)) continue;
228        filtered.Add(i);
229      }
230
231      // if we don't have enough filtered individuals, then we are done
232      // if the schema exceeds the minimum frequency, it gets processed further
233      if (filtered.Count < countThreshold) {
234        return base.Apply();
235      }
236
237      // check if the filtered individuals match the schema
238      var sNodes = QueryMatch.InitializePostOrder(sRoot);
239      var matchingIndividuals = new ScopeList();
240      bool executeInParallel = ExecuteInParallelParameter.ActualValue.Value;
241      int maxDegreeOfParallelism = MaxDegreeOfParallelismParameter.ActualValue.Value;
242
243      if (executeInParallel) {
244        var matching = new bool[filtered.Count];
245
246        Parallel.For(0, filtered.Count, new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism },
247          i => {
248            var index = filtered[i];
249            var t = trees[index];
250            var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
251            if (qm.Match(tNodes, sNodes)) {
252              matching[i] = true;
253            }
254          });
255
256        matchingIndividuals.AddRange(filtered.Where((x, i) => matching[i]).Select(x => individuals[x]));
257      } else {
258        for (int i = 0; i < filtered.Count; ++i) {
259          // break early if it becomes impossible to reach the minimum threshold
260          if (matchingIndividuals.Count + filtered.Count - i < countThreshold)
261            break;
262
263          var index = filtered[i];
264          var tRoot = trees[index].Root.GetSubtree(0).GetSubtree(0);
265          var tNodes = QueryMatch.InitializePostOrder(tRoot);
266          if (qm.Match(tNodes, sNodes))
267            matchingIndividuals.Add(individuals[index]);
268        }
269      }
270
271      if (matchingIndividuals.Count < countThreshold) {
272        return base.Apply();
273      }
274
275      var similarity = CalculateSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
276      if (similarity < MinimumPhenotypicSimilarity.Value) {
277        return base.Apply();
278      }
279
280      double replacementRatio;
281      var adaptiveReplacementRatio = UseAdaptiveReplacementRatioParameter.ActualValue.Value;
282
283      if (adaptiveReplacementRatio) {
284        var r = (double)matchingIndividuals.Count / individuals.Count;
285        replacementRatio = ReplacementRule(r);
286      } else {
287        replacementRatio = ReplacementRatio.Value;
288      }
289
290      int n = (int)Math.Floor(matchingIndividuals.Count * replacementRatio);
291      var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
292                                                         : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
293      var mutationOc = new OperationCollection { Parallel = false }; // cannot be parallel due to the before/after operators which insert vertices in the genealogy graph
294      var updateEstimatedValues = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
295      foreach (var ind in individualsToReplace) {
296        var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
297        var updateOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
298        mutationOc.Add(mutatorOp);
299        updateEstimatedValues.Add(updateOp);
300        if (exclusiveMatching)
301          ind.Variables.Add(new Core.Variable("AlreadyMatched"));
302      }
303
304      NumberOfChangedTrees.Value += individualsToReplace.Count; // a lock is not necessary here because the SchemaEvaluators cannot be executed in parallel
305
306      return new OperationCollection(mutationOc, updateEstimatedValues, base.Apply());
307    }
308
309    public static double CalculateSimilarity(ScopeList individuals, ISolutionSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
310      double similarity = 0;
311      int count = individuals.Count;
312      if (count < 2) return double.NaN;
313      if (parallel) {
314        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
315        var simArray = new double[count - 1];
316        Parallel.For(0, count - 1, parallelOptions, i => {
317          double innerSim = 0;
318          for (int j = i + 1; j < count; ++j) {
319            innerSim += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
320          }
321          simArray[i] = innerSim;
322        });
323        similarity = simArray.Sum();
324      } else {
325        for (int i = 0; i < count - 1; ++i) {
326          for (int j = i + 1; j < count; ++j) {
327            similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
328          }
329        }
330      }
331      return similarity / (count * (count - 1) / 2.0);
332    }
333  }
334}
Note: See TracBrowser for help on using the repository browser.