#region License Information
/* HeuristicLab
* Copyright (C) 2002-2011 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;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[StorableClass]
[Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator {
private const int MAX_TRIES = 100;
private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
private const string SymbolicExpressionTreeGrammarParameterName = "SymbolicExpressionTreeGrammar";
#region Parameter Properties
public IValueLookupParameter MaximumSymbolicExpressionTreeLengthParameter {
get { return (IValueLookupParameter)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
}
public IValueLookupParameter MaximumSymbolicExpressionTreeDepthParameter {
get { return (IValueLookupParameter)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
}
public IValueLookupParameter SymbolicExpressionTreeGrammarParameter {
get { return (IValueLookupParameter)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
}
#endregion
#region Properties
public IntValue MaximumSymbolicExpressionTreeLength {
get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
}
public IntValue MaximumSymbolicExpressionTreeDepth {
get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
}
public ISymbolicExpressionGrammar SymbolicExpressionTreeGrammar {
get { return SymbolicExpressionTreeGrammarParameter.ActualValue; }
}
#endregion
[StorableConstructor]
protected ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }
protected ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }
public ProbabilisticTreeCreator()
: base() {
Parameters.Add(new ValueLookupParameter(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
Parameters.Add(new ValueLookupParameter(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
Parameters.Add(new ValueLookupParameter(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new ProbabilisticTreeCreator(this, cloner);
}
protected override ISymbolicExpressionTree Create(IRandom random) {
return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
}
public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
int maxTreeLength, int maxTreeDepth) {
SymbolicExpressionTree tree = new SymbolicExpressionTree();
var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
rootNode.AddSubTree(startNode);
PTC2(random, startNode, maxTreeLength, maxTreeDepth);
tree.Root = rootNode;
return tree;
}
private class TreeExtensionPoint {
public ISymbolicExpressionTreeNode Parent { get; set; }
public int ChildIndex { get; set; }
public int ExtensionPointDepth { get; set; }
}
public static void PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
int maxLength, int maxDepth) {
// tree length is limited by the grammar and by the explicit size constraints
int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
int tries = 0;
while (tries++ < MAX_TRIES) {
// select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)
int targetTreeLength;
targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
if (targetTreeLength <= 1 || maxDepth <= 1) return;
bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
// if successful => check constraints and return the tree if everything looks ok
if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
return;
} else {
// clean seedNode
while (seedNode.SubTrees.Count() > 0) seedNode.RemoveSubTree(0);
}
// try a different length MAX_TRIES times
}
throw new ArgumentException("Couldn't create a random valid tree.");
}
private static bool CreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
int targetLength, int maxDepth) {
try {
TryCreateFullTreeFromSeed(random, root, globalGrammar, targetLength, maxDepth);
return true;
}
catch (ArgumentException) { return false; }
}
private static void TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
int targetLength, int maxDepth) {
List extensionPoints = new List();
int currentLength = 1;
int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
int actualArity = SampleArity(random, root, targetLength);
for (int i = 0; i < actualArity; i++) {
// insert a dummy sub-tree and add the pending extension to the list
var dummy = new SymbolicExpressionTreeNode();
root.AddSubTree(dummy);
extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
}
// while there are pending extension points and we have not reached the limit of adding new extension points
while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
int randomIndex = random.Next(extensionPoints.Count);
TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
extensionPoints.RemoveAt(randomIndex);
ISymbolicExpressionTreeNode parent = nextExtension.Parent;
int argumentIndex = nextExtension.ChildIndex;
int extensionDepth = nextExtension.ExtensionPointDepth;
if (extensionDepth + parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth) {
ReplaceWithMinimalTree(random, root, parent, argumentIndex);
} else {
var allowedSymbols = (from s in parent.Grammar.Symbols
where parent.Grammar.IsAllowedChildSymbol(parent.Symbol, s, argumentIndex)
where parent.Grammar.GetMinimumExpressionDepth(s) + extensionDepth - 1 < maxDepth
where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
select s)
.ToList();
var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
var selectedSymbol = allowedSymbols.SelectRandom(weights, random);
ISymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);
parent.RemoveSubTree(argumentIndex);
parent.InsertSubTree(argumentIndex, newTree);
var topLevelNode = newTree as SymbolicExpressionTreeTopLevelNode;
if (topLevelNode != null)
topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
currentLength++;
totalListMinLength--;
actualArity = SampleArity(random, newTree, targetLength - currentLength);
for (int i = 0; i < actualArity; i++) {
// insert a dummy sub-tree and add the pending extension to the list
var dummy = new SymbolicExpressionTreeNode();
newTree.AddSubTree(dummy);
extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
}
totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
}
}
// fill all pending extension points
while (extensionPoints.Count > 0) {
int randomIndex = random.Next(extensionPoints.Count);
TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
extensionPoints.RemoveAt(randomIndex);
ISymbolicExpressionTreeNode parent = nextExtension.Parent;
int a = nextExtension.ChildIndex;
int d = nextExtension.ExtensionPointDepth;
ReplaceWithMinimalTree(random, root, parent, a);
}
}
private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,
int childIndex) {
// determine possible symbols that will lead to the smallest possible tree
var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
group s by parent.Grammar.GetMinimumExpressionLength(s) into g
orderby g.Key
select g).First().ToList();
var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
var tree = selectedSymbol.CreateTreeNode();
if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
parent.RemoveSubTree(childIndex);
parent.InsertSubTree(childIndex, tree);
var topLevelNode = tree as SymbolicExpressionTreeTopLevelNode;
if (topLevelNode != null)
topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
for (int i = 0; i < tree.Grammar.GetMinimumSubtreeCount(tree.Symbol); i++) {
// insert a dummy sub-tree and add the pending extension to the list
var dummy = new SymbolicExpressionTreeNode();
tree.AddSubTree(dummy);
// replace the just inserted dummy by recursive application
ReplaceWithMinimalTree(random, root, tree, i);
}
}
private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
return branch is SymbolicExpressionTreeTopLevelNode;
}
private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
// select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
int maxArity = node.Grammar.GetMaximumSubtreeCount(node.Symbol);
if (maxArity > targetLength) {
maxArity = targetLength;
}
// the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree length
// if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target length then minArity should be at least 2
long aggregatedLongestExpressionLength = 0;
for (int i = 0; i < maxArity; i++) {
aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
select node.Grammar.GetMaximumExpressionLength(s)).Max();
if (aggregatedLongestExpressionLength < targetLength) minArity = i;
else break;
}
// the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree length
// if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target length then maxArity should be at most 0
long aggregatedShortestExpressionLength = 0;
for (int i = 0; i < maxArity; i++) {
aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
select node.Grammar.GetMinimumExpressionLength(s)).Min();
if (aggregatedShortestExpressionLength > targetLength) {
maxArity = i;
break;
}
}
if (minArity > maxArity) throw new ArgumentException();
return random.Next(minArity, maxArity + 1);
}
}
}