#region License Information
/* HeuristicLab
* Copyright (C) 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 .
*/
#endregion
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Parameters;
using HEAL.Attic;
using HeuristicLab.Random;
namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
[Item("SemanticSimilarityCrossover", "An operator which performs subtree swapping based on the notion semantic similarity between subtrees\n" +
"(criteria: mean of the absolute differences between the estimated output values of the two subtrees, falling into a user-defined range)\n" +
"- Take two parent individuals P0 and P1\n" +
"- Randomly choose a node N from the P0\n" +
"- Find the first node M that satisfies the semantic similarity criteria\n" +
"- Swap N for M and return P0")]
[StorableType("8AB40F60-5664-42AB-9DD9-78707476C1B2")]
public sealed class SymbolicDataAnalysisExpressionSemanticSimilarityCrossover : SymbolicDataAnalysisExpressionCrossover where T : class, IDataAnalysisProblemData {
private const string SemanticSimilarityRangeParameterName = "SemanticSimilarityRange";
#region Parameter properties
public IValueParameter SemanticSimilarityRangeParameter {
get { return (IValueParameter)Parameters[SemanticSimilarityRangeParameterName]; }
}
#endregion
#region Properties
public DoubleRange SemanticSimilarityRange {
get { return SemanticSimilarityRangeParameter.Value; }
}
#endregion
[StorableConstructor]
private SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(StorableConstructorFlag _) : base(_) { }
private SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(SymbolicDataAnalysisExpressionCrossover original, Cloner cloner) : base(original, cloner) { }
public SymbolicDataAnalysisExpressionSemanticSimilarityCrossover()
: base() {
Parameters.Add(new ValueLookupParameter(SemanticSimilarityRangeParameterName, "Semantic similarity interval.", new DoubleRange(0.0001, 10)));
name = "SemanticSimilarityCrossover";
}
public override IDeepCloneable Clone(Cloner cloner) {
return new SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(this, cloner);
}
public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;
List rows = GenerateRowsToEvaluate().ToList();
T problemData = ProblemDataParameter.ActualValue;
return Cross(random, parent0, parent1, interpreter, problemData, rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value, SemanticSimilarityRange);
}
///
/// Takes two parent individuals P0 and P1.
/// Randomly choose a node i from the first parent, then get a node j from the second parent that matches the semantic similarity criteria.
///
public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, ISymbolicDataAnalysisExpressionTreeInterpreter interpreter,
T problemData, List rows, int maxDepth, int maxLength, DoubleRange range) {
var crossoverPoints0 = new List();
parent0.Root.ForEachNodePostfix((n) => {
if (n.Parent != null && n.Parent != parent0.Root)
crossoverPoints0.Add(new CutPoint(n.Parent, n));
});
var crossoverPoint0 = crossoverPoints0.SampleRandom(random);
int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
var allowedBranches = new List();
parent1.Root.ForEachNodePostfix((n) => {
if (n.Parent != null && n.Parent != parent1.Root) {
if (n.GetDepth() + level <= maxDepth && n.GetLength() + length <= maxLength && crossoverPoint0.IsMatchingPointType(n))
allowedBranches.Add(n);
}
});
if (allowedBranches.Count == 0)
return parent0;
var dataset = problemData.Dataset;
// create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
var rootSymbol = new ProgramRootSymbol();
var startSymbol = new StartSymbol();
var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol);
List estimatedValues0 = interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows).ToList();
crossoverPoint0.Child.Parent = crossoverPoint0.Parent; // restore parent
ISymbolicExpressionTreeNode selectedBranch = null;
// pick the first node that fulfills the semantic similarity conditions
foreach (var node in allowedBranches) {
var parent = node.Parent;
var tree1 = CreateTreeFromNode(random, node, startSymbol, rootSymbol); // this will affect node.Parent
List estimatedValues1 = interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows).ToList();
node.Parent = parent; // restore parent
OnlineCalculatorError errorState;
double ssd = OnlineMeanAbsoluteErrorCalculator.Calculate(estimatedValues0, estimatedValues1, out errorState);
if (range.Start <= ssd && ssd <= range.End) {
selectedBranch = node;
break;
}
}
// perform the actual swap
if (selectedBranch != null)
Swap(crossoverPoint0, selectedBranch);
return parent0;
}
}
}