[3294] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[14312] | 3 | * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[3294] | 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 |
|
---|
| 22 | using System;
|
---|
[4068] | 23 | using System.Collections.Generic;
|
---|
[3294] | 24 | using System.Linq;
|
---|
[4068] | 25 | using System.Text;
|
---|
[4722] | 26 | using HeuristicLab.Common;
|
---|
[3294] | 27 | using HeuristicLab.Core;
|
---|
| 28 | using HeuristicLab.Data;
|
---|
[5686] | 29 | using HeuristicLab.Parameters;
|
---|
[3294] | 30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
[12891] | 31 | using HeuristicLab.Random;
|
---|
[3294] | 32 |
|
---|
[5499] | 33 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
[3294] | 34 | /// <summary>
|
---|
| 35 | /// Manipulates a symbolic expression by adding one new function-defining branch containing
|
---|
| 36 | /// a proportion of a preexisting branch and by creating a reference to the new branch.
|
---|
| 37 | /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97
|
---|
| 38 | /// </summary>
|
---|
[5510] | 39 | [Item("SubroutineCreater", "Manipulates a symbolic expression by adding one new function-defining branch containing a proportion of a preexisting branch and by creating a reference to the new branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97")]
|
---|
[3294] | 40 | [StorableClass]
|
---|
[5510] | 41 | public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
|
---|
[3360] | 42 | private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05;
|
---|
[5510] | 43 | private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
|
---|
| 44 | private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
|
---|
| 45 | #region Parameter Properties
|
---|
| 46 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
|
---|
| 47 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
|
---|
| 48 | }
|
---|
| 49 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
|
---|
| 50 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
|
---|
| 51 | }
|
---|
| 52 | #endregion
|
---|
| 53 | #region Properties
|
---|
| 54 | public IntValue MaximumSymbolicExpressionTreeLength {
|
---|
| 55 | get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
|
---|
| 56 | }
|
---|
| 57 | public IntValue MaximumSymbolicExpressionTreeDepth {
|
---|
| 58 | get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
|
---|
| 59 | }
|
---|
| 60 | #endregion
|
---|
[4722] | 61 | [StorableConstructor]
|
---|
| 62 | private SubroutineCreater(bool deserializing) : base(deserializing) { }
|
---|
| 63 | private SubroutineCreater(SubroutineCreater original, Cloner cloner) : base(original, cloner) { }
|
---|
[5686] | 64 | public SubroutineCreater()
|
---|
| 65 | : base() {
|
---|
[5510] | 66 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
|
---|
| 67 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
|
---|
| 68 | }
|
---|
[4722] | 69 |
|
---|
| 70 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 71 | return new SubroutineCreater(this, cloner);
|
---|
| 72 | }
|
---|
| 73 |
|
---|
[3294] | 74 | public override sealed void ModifyArchitecture(
|
---|
| 75 | IRandom random,
|
---|
[5510] | 76 | ISymbolicExpressionTree symbolicExpressionTree,
|
---|
| 77 | IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
|
---|
| 78 | CreateSubroutine(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
|
---|
[3294] | 79 | }
|
---|
| 80 |
|
---|
| 81 | public static bool CreateSubroutine(
|
---|
| 82 | IRandom random,
|
---|
[5510] | 83 | ISymbolicExpressionTree symbolicExpressionTree,
|
---|
| 84 | int maxTreeLength, int maxTreeDepth,
|
---|
| 85 | int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
[3294] | 86 | var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
|
---|
[5510] | 87 | if (functionDefiningBranches.Count() >= maxFunctionDefinitions)
|
---|
[3294] | 88 | // allowed maximum number of ADF reached => abort
|
---|
| 89 | return false;
|
---|
[5549] | 90 | if (symbolicExpressionTree.Length + 4 > maxTreeLength)
|
---|
| 91 | // defining a new function causes an length increase by 4 nodes (max) if the max tree length is reached => abort
|
---|
[3360] | 92 | return false;
|
---|
[5510] | 93 | string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
|
---|
| 94 | var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
|
---|
[3294] | 95 | select "ADF" + index.ToString(formatString);
|
---|
[3360] | 96 |
|
---|
| 97 | // select a random body (either the result producing branch or an ADF branch)
|
---|
[5733] | 98 | var bodies = from node in symbolicExpressionTree.Root.Subtrees
|
---|
[5549] | 99 | select new { Tree = node, Length = node.GetLength() };
|
---|
| 100 | var totalNumberOfBodyNodes = bodies.Select(x => x.Length).Sum();
|
---|
[3294] | 101 | int r = random.Next(totalNumberOfBodyNodes);
|
---|
| 102 | int aggregatedNumberOfBodyNodes = 0;
|
---|
[5510] | 103 | ISymbolicExpressionTreeNode selectedBody = null;
|
---|
[3294] | 104 | foreach (var body in bodies) {
|
---|
[5549] | 105 | aggregatedNumberOfBodyNodes += body.Length;
|
---|
[3294] | 106 | if (aggregatedNumberOfBodyNodes > r)
|
---|
| 107 | selectedBody = body.Tree;
|
---|
| 108 | }
|
---|
| 109 | // sanity check
|
---|
| 110 | if (selectedBody == null) throw new InvalidOperationException();
|
---|
[3360] | 111 |
|
---|
| 112 | // select a random cut point in the selected branch
|
---|
[5686] | 113 | var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
|
---|
[5733] | 114 | from subtree in parent.Subtrees
|
---|
[5686] | 115 | select new CutPoint(parent, subtree)).ToList();
|
---|
[12891] | 116 | if (!allCutPoints.Any())
|
---|
[3294] | 117 | // no cut points => abort
|
---|
| 118 | return false;
|
---|
[3360] | 119 | string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
|
---|
[12891] | 120 | var selectedCutPoint = allCutPoints.SampleRandom(random);
|
---|
| 121 |
|
---|
[3294] | 122 | // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
|
---|
[5686] | 123 | List<CutPoint> argumentCutPoints = SelectRandomArgumentBranches(selectedCutPoint.Child, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
|
---|
| 124 | ISymbolicExpressionTreeNode functionBody = selectedCutPoint.Child;
|
---|
[3294] | 125 | // disconnect the function body from the tree
|
---|
[5733] | 126 | selectedCutPoint.Parent.RemoveSubtree(selectedCutPoint.ChildIndex);
|
---|
[3294] | 127 | // disconnect the argument branches from the function
|
---|
[5686] | 128 | functionBody = DisconnectBranches(functionBody, argumentCutPoints);
|
---|
[3360] | 129 | // insert a function invocation symbol instead
|
---|
| 130 | var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
|
---|
[5733] | 131 | selectedCutPoint.Parent.InsertSubtree(selectedCutPoint.ChildIndex, invokeNode);
|
---|
[3360] | 132 | // add the branches selected as argument as subtrees of the function invocation node
|
---|
[5686] | 133 | foreach (var argumentCutPoint in argumentCutPoints)
|
---|
[5733] | 134 | invokeNode.AddSubtree(argumentCutPoint.Child);
|
---|
[3294] | 135 |
|
---|
| 136 | // insert a new function defining branch
|
---|
| 137 | var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
|
---|
[3360] | 138 | defunNode.FunctionName = newFunctionName;
|
---|
[5733] | 139 | defunNode.AddSubtree(functionBody);
|
---|
| 140 | symbolicExpressionTree.Root.AddSubtree(defunNode);
|
---|
[3360] | 141 | // the grammar in the newly defined function is a clone of the grammar of the originating branch
|
---|
[5510] | 142 | defunNode.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBody.Grammar.Clone());
|
---|
[8148] | 143 |
|
---|
| 144 | var allowedChildSymbols = selectedBody.Grammar.GetAllowedChildSymbols(selectedBody.Symbol);
|
---|
| 145 | foreach (var allowedChildSymbol in allowedChildSymbols)
|
---|
| 146 | defunNode.Grammar.AddAllowedChildSymbol(defunNode.Symbol, allowedChildSymbol);
|
---|
| 147 | var maxSubtrees = selectedBody.Grammar.GetMaximumSubtreeCount(selectedBody.Symbol);
|
---|
| 148 | for (int i = 0; i < maxSubtrees; i++) {
|
---|
| 149 | foreach (var allowedChildSymbol in selectedBody.Grammar.GetAllowedChildSymbols(selectedBody.Symbol, i))
|
---|
| 150 | defunNode.Grammar.AddAllowedChildSymbol(defunNode.Symbol, allowedChildSymbol);
|
---|
| 151 | }
|
---|
| 152 |
|
---|
[5686] | 153 | // remove all argument symbols from grammar except that one contained in cutpoints
|
---|
| 154 | var oldArgumentSymbols = selectedBody.Grammar.Symbols.OfType<Argument>().ToList();
|
---|
[3360] | 155 | foreach (var oldArgSymb in oldArgumentSymbols)
|
---|
| 156 | defunNode.Grammar.RemoveSymbol(oldArgSymb);
|
---|
| 157 | // find unique argument indexes and matching symbols in the function defining branch
|
---|
| 158 | var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
|
---|
| 159 | select node.Symbol.ArgumentIndex).Distinct();
|
---|
| 160 | // add argument symbols to grammar of function defining branch
|
---|
[5686] | 161 | GrammarModifier.AddArgumentSymbol(selectedBody.Grammar, defunNode.Grammar, newArgumentIndexes, argumentCutPoints);
|
---|
[3360] | 162 | defunNode.NumberOfArguments = newArgumentIndexes.Count();
|
---|
[5686] | 163 | if (defunNode.NumberOfArguments != argumentCutPoints.Count) throw new InvalidOperationException();
|
---|
[3360] | 164 | // add invoke symbol for newly defined function to the original branch
|
---|
[5686] | 165 | GrammarModifier.AddInvokeSymbol(selectedBody.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
|
---|
[3360] | 166 |
|
---|
| 167 | // when the new function body was taken from another function definition
|
---|
| 168 | // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
|
---|
| 169 | if (selectedBody.Symbol is Defun) {
|
---|
| 170 | var originalFunctionDefinition = selectedBody as DefunTreeNode;
|
---|
[5733] | 171 | foreach (var subtree in symbolicExpressionTree.Root.Subtrees) {
|
---|
[3360] | 172 | var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
|
---|
| 173 | where symb.FunctionName == originalFunctionDefinition.FunctionName
|
---|
| 174 | select symb).SingleOrDefault();
|
---|
| 175 | // when the original branch can be invoked from the subtree then also allow invocation of the function
|
---|
| 176 | if (originalBranchInvokeSymbol != null) {
|
---|
[5686] | 177 | GrammarModifier.AddInvokeSymbol(subtree.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
|
---|
[3360] | 178 | }
|
---|
| 179 | }
|
---|
[3294] | 180 | }
|
---|
| 181 | return true;
|
---|
| 182 | }
|
---|
| 183 |
|
---|
[5686] | 184 | private static ISymbolicExpressionTreeNode DisconnectBranches(ISymbolicExpressionTreeNode node, List<CutPoint> argumentCutPoints) {
|
---|
| 185 | int argumentIndex = argumentCutPoints.FindIndex(x => x.Child == node);
|
---|
| 186 | if (argumentIndex != -1) {
|
---|
[3360] | 187 | var argSymbol = new Argument(argumentIndex);
|
---|
| 188 | return argSymbol.CreateTreeNode();
|
---|
| 189 | }
|
---|
[3294] | 190 | // remove the subtrees so that we can clone only the root node
|
---|
[5733] | 191 | List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
|
---|
| 192 | while (node.Subtrees.Count() > 0) node.RemoveSubtree(0);
|
---|
[3294] | 193 | // recursively apply function for subtrees or append a argument terminal node
|
---|
| 194 | foreach (var subtree in subtrees) {
|
---|
[5733] | 195 | node.AddSubtree(DisconnectBranches(subtree, argumentCutPoints));
|
---|
[3294] | 196 | }
|
---|
| 197 | return node;
|
---|
| 198 | }
|
---|
| 199 |
|
---|
[5686] | 200 | private static List<CutPoint> SelectRandomArgumentBranches(ISymbolicExpressionTreeNode selectedRoot,
|
---|
[3294] | 201 | IRandom random,
|
---|
[3360] | 202 | double cutProbability,
|
---|
[3294] | 203 | int maxArguments) {
|
---|
[3360] | 204 | // breadth first determination of argument cut-off points
|
---|
| 205 | // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
|
---|
[5686] | 206 | List<CutPoint> argumentBranches = new List<CutPoint>();
|
---|
[3360] | 207 | if (selectedRoot is ArgumentTreeNode) {
|
---|
[5686] | 208 | argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
|
---|
[3360] | 209 | return argumentBranches;
|
---|
| 210 | } else {
|
---|
| 211 | // get the number of argument nodes (which must be cut-off) in the sub-trees
|
---|
[5733] | 212 | var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.Subtrees
|
---|
[3360] | 213 | let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
|
---|
| 214 | select nArgumentsInTree).ToList();
|
---|
| 215 | // determine the minimal number of new argument nodes for each sub-tree
|
---|
[5686] | 216 | //if we exceed the maxArguments return the same cutpoint as the start cutpoint to create a ADF that returns only its argument
|
---|
[3360] | 217 | var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
|
---|
| 218 | if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
|
---|
[5686] | 219 | argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
|
---|
[3360] | 220 | return argumentBranches;
|
---|
[3294] | 221 | }
|
---|
[3360] | 222 | // cut-off in the sub-trees in random order
|
---|
[5733] | 223 | var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.Subtrees.Count())
|
---|
[5686] | 224 | select new { Index = index, OrderValue = random.NextDouble() })
|
---|
| 225 | .OrderBy(x => x.OrderValue)
|
---|
| 226 | .Select(x => x.Index);
|
---|
[3360] | 227 | foreach (var subtreeIndex in randomIndexes) {
|
---|
[5733] | 228 | var subtree = selectedRoot.GetSubtree(subtreeIndex);
|
---|
[3360] | 229 | minNewArgumentsForSubtrees[subtreeIndex] = 0;
|
---|
| 230 | // => cut-off at 0..n points somewhere in the current sub-tree
|
---|
| 231 | // determine the maximum number of new arguments that should be created in the branch
|
---|
| 232 | // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
|
---|
| 233 | int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
|
---|
| 234 | // when no argument is allowed from the current branch then we have to include the whole branch into the function
|
---|
| 235 | // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
|
---|
| 236 | if (maxArgumentsFromBranch == 0) {
|
---|
| 237 | // don't cut at all => the whole sub-tree branch is included in the function body
|
---|
| 238 | // (we already checked ahead of time that there are no arguments left over in the subtree)
|
---|
| 239 | } else if (random.NextDouble() >= cutProbability) {
|
---|
| 240 | argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
|
---|
| 241 | } else {
|
---|
| 242 | // cut-off at current sub-tree
|
---|
[5686] | 243 | argumentBranches.Add(new CutPoint(subtree.Parent, subtree));
|
---|
[3360] | 244 | }
|
---|
| 245 | }
|
---|
| 246 | return argumentBranches;
|
---|
[3294] | 247 | }
|
---|
| 248 | }
|
---|
| 249 | }
|
---|
| 250 | }
|
---|