1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2014 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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Linq;
|
---|
25 | using HeuristicLab.Common;
|
---|
26 | using HeuristicLab.Core;
|
---|
27 | using HeuristicLab.Data;
|
---|
28 | using HeuristicLab.Parameters;
|
---|
29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
30 |
|
---|
31 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
32 | /// <summary>
|
---|
33 | /// Creates a new argument within one function-defining branch of a symbolic expression tree.
|
---|
34 | /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 106
|
---|
35 | /// </summary>
|
---|
36 | [Item("ArgumentCreater", "Manipulates a symbolic expression by creating a new argument within one function-defining branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 106")]
|
---|
37 | [StorableClass]
|
---|
38 | public sealed class ArgumentCreater : SymbolicExpressionTreeArchitectureManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
|
---|
39 | private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
|
---|
40 | private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
|
---|
41 | #region Parameter Properties
|
---|
42 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
|
---|
43 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
|
---|
44 | }
|
---|
45 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
|
---|
46 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
|
---|
47 | }
|
---|
48 | #endregion
|
---|
49 | #region Properties
|
---|
50 | public IntValue MaximumSymbolicExpressionTreeLength {
|
---|
51 | get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
|
---|
52 | }
|
---|
53 | public IntValue MaximumSymbolicExpressionTreeDepth {
|
---|
54 | get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
|
---|
55 | }
|
---|
56 | #endregion
|
---|
57 | [StorableConstructor]
|
---|
58 | private ArgumentCreater(bool deserializing) : base(deserializing) { }
|
---|
59 | private ArgumentCreater(ArgumentCreater original, Cloner cloner) : base(original, cloner) { }
|
---|
60 | public ArgumentCreater()
|
---|
61 | : base() {
|
---|
62 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
|
---|
63 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
|
---|
64 | }
|
---|
65 |
|
---|
66 | public override sealed void ModifyArchitecture(
|
---|
67 | IRandom random,
|
---|
68 | ISymbolicExpressionTree symbolicExpressionTree,
|
---|
69 | IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
|
---|
70 | CreateNewArgument(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
|
---|
71 | }
|
---|
72 |
|
---|
73 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
74 | return new ArgumentCreater(this, cloner);
|
---|
75 | }
|
---|
76 |
|
---|
77 | public static bool CreateNewArgument(
|
---|
78 | IRandom random,
|
---|
79 | ISymbolicExpressionTree symbolicExpressionTree,
|
---|
80 | int maxTreeLength, int maxTreeDepth,
|
---|
81 | int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
82 | // work on a copy in case we find out later that the tree would be too big
|
---|
83 | // in this case it's easiest to simply return the original tree.
|
---|
84 | ISymbolicExpressionTree clonedTree = (ISymbolicExpressionTree)symbolicExpressionTree.Clone();
|
---|
85 |
|
---|
86 | var functionDefiningBranches = clonedTree.IterateNodesPrefix().OfType<DefunTreeNode>();
|
---|
87 | if (functionDefiningBranches.Count() == 0)
|
---|
88 | // no function defining branch found => abort
|
---|
89 | return false;
|
---|
90 |
|
---|
91 | // select a random function defining branch
|
---|
92 | var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
|
---|
93 | var definedArguments = (from symbol in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
|
---|
94 | select symbol.ArgumentIndex).Distinct();
|
---|
95 | if (definedArguments.Count() >= maxFunctionArguments)
|
---|
96 | // max number of arguments reached => abort
|
---|
97 | return false;
|
---|
98 |
|
---|
99 | var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
|
---|
100 | var newArgumentIndex = allowedArgumentIndexes.Except(definedArguments).First();
|
---|
101 | ArgumentTreeNode newArgumentNode = MakeArgumentNode(newArgumentIndex);
|
---|
102 |
|
---|
103 | // this operation potentially creates very big trees so the access to the length property might throw overflow exception
|
---|
104 | try {
|
---|
105 | if (CreateNewArgumentForDefun(random, clonedTree, selectedDefunBranch, newArgumentNode) && clonedTree.Length <= maxTreeLength && clonedTree.Depth <= maxTreeDepth) {
|
---|
106 |
|
---|
107 | // size constraints are fulfilled
|
---|
108 | // replace root of original tree with root of manipulated tree
|
---|
109 | symbolicExpressionTree.Root = clonedTree.Root;
|
---|
110 | return true;
|
---|
111 | } else {
|
---|
112 | // keep originalTree
|
---|
113 | return false;
|
---|
114 | }
|
---|
115 | }
|
---|
116 | catch (OverflowException) {
|
---|
117 | // keep original tree
|
---|
118 | return false;
|
---|
119 | }
|
---|
120 | }
|
---|
121 |
|
---|
122 | private static bool CreateNewArgumentForDefun(IRandom random, ISymbolicExpressionTree tree, DefunTreeNode defunBranch, ArgumentTreeNode newArgumentNode) {
|
---|
123 | // select a random cut point in the function defining branch
|
---|
124 | // the branch at the cut point is to be replaced by a new argument node
|
---|
125 | var cutPoints = (from node in defunBranch.IterateNodesPrefix()
|
---|
126 | where node.Subtrees.Count() > 0 &&
|
---|
127 | !node.IterateNodesPrefix().OfType<ArgumentTreeNode>().Any() &&
|
---|
128 | !node.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>().Any()
|
---|
129 | from subtree in node.Subtrees
|
---|
130 | select new CutPoint(node, subtree)).ToList();
|
---|
131 |
|
---|
132 | if (cutPoints.Count() == 0)
|
---|
133 | // no cut point found => abort;
|
---|
134 | return false;
|
---|
135 | var selectedCutPoint = cutPoints[random.Next(cutPoints.Count)];
|
---|
136 | // replace the branch at the cut point with an argument node
|
---|
137 | var replacedBranch = selectedCutPoint.Child;
|
---|
138 | selectedCutPoint.Parent.RemoveSubtree(selectedCutPoint.ChildIndex);
|
---|
139 | selectedCutPoint.Parent.InsertSubtree(selectedCutPoint.ChildIndex, newArgumentNode);
|
---|
140 |
|
---|
141 | // find all old invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
|
---|
142 | // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
|
---|
143 | var invocationNodes = (from node in tree.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
|
---|
144 | where node.Symbol.FunctionName == defunBranch.FunctionName
|
---|
145 | where node.Subtrees.Count() == defunBranch.NumberOfArguments
|
---|
146 | select node).ToList();
|
---|
147 | // do this repeatedly until no matching invocations are found
|
---|
148 | while (invocationNodes.Count > 0) {
|
---|
149 | List<ISymbolicExpressionTreeNode> newlyAddedBranches = new List<ISymbolicExpressionTreeNode>();
|
---|
150 | foreach (var invocationNode in invocationNodes) {
|
---|
151 | // check that the invocation node really has the correct number of arguments
|
---|
152 | if (invocationNode.Subtrees.Count() != defunBranch.NumberOfArguments) throw new InvalidOperationException();
|
---|
153 | // append a new argument branch after expanding all argument nodes
|
---|
154 | var clonedBranch = (ISymbolicExpressionTreeNode)replacedBranch.Clone();
|
---|
155 | clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.Subtrees);
|
---|
156 | invocationNode.InsertSubtree(newArgumentNode.Symbol.ArgumentIndex, clonedBranch);
|
---|
157 | newlyAddedBranches.Add(clonedBranch);
|
---|
158 | }
|
---|
159 | // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
|
---|
160 | invocationNodes = (from newlyAddedBranch in newlyAddedBranches
|
---|
161 | from node in newlyAddedBranch.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
|
---|
162 | where node.Symbol.FunctionName == defunBranch.FunctionName
|
---|
163 | where node.Subtrees.Count() == defunBranch.NumberOfArguments
|
---|
164 | select node).ToList();
|
---|
165 | }
|
---|
166 | // increase expected number of arguments of function defining branch
|
---|
167 | // it's possible that the number of actually referenced arguments was reduced (all references were replaced by a single new argument)
|
---|
168 | // but the number of expected arguments is increased anyway
|
---|
169 | defunBranch.NumberOfArguments++;
|
---|
170 | defunBranch.Grammar.AddSymbol(newArgumentNode.Symbol);
|
---|
171 | defunBranch.Grammar.SetSubtreeCount(newArgumentNode.Symbol, 0, 0);
|
---|
172 | // allow the argument as child of any other symbol
|
---|
173 | GrammarModifier.SetAllowedParentSymbols(defunBranch.Grammar, selectedCutPoint.Child.Symbol, newArgumentNode.Symbol);
|
---|
174 |
|
---|
175 | foreach (var subtree in tree.Root.Subtrees) {
|
---|
176 | // when the changed function is known in the branch then update the number of arguments
|
---|
177 | var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == defunBranch.FunctionName).SingleOrDefault();
|
---|
178 | if (matchingSymbol != null) {
|
---|
179 | subtree.Grammar.SetSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments, defunBranch.NumberOfArguments);
|
---|
180 | foreach (var symb in subtree.Grammar.Symbols) {
|
---|
181 | if (symb is StartSymbol || symb is ProgramRootSymbol) continue;
|
---|
182 | if (symb.Name == matchingSymbol.Name) continue; //don't allow invoke as child of invoke
|
---|
183 | if (subtree.Grammar.IsAllowedChildSymbol(selectedCutPoint.Parent.Symbol, symb, selectedCutPoint.ChildIndex))
|
---|
184 | subtree.Grammar.AddAllowedChildSymbol(matchingSymbol, symb, newArgumentNode.Symbol.ArgumentIndex);
|
---|
185 | }
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | return true;
|
---|
190 | }
|
---|
191 |
|
---|
192 | private static ISymbolicExpressionTreeNode ReplaceArgumentsInBranch(ISymbolicExpressionTreeNode branch, IEnumerable<ISymbolicExpressionTreeNode> argumentTrees) {
|
---|
193 | ArgumentTreeNode argNode = branch as ArgumentTreeNode;
|
---|
194 | if (argNode != null) {
|
---|
195 | // replace argument nodes by a clone of the original subtree that provided the result for the argument node
|
---|
196 | return (SymbolicExpressionTreeNode)argumentTrees.ElementAt(argNode.Symbol.ArgumentIndex).Clone();
|
---|
197 | } else {
|
---|
198 | // call recursively for all subtree
|
---|
199 | List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(branch.Subtrees);
|
---|
200 | while (branch.Subtrees.Count() > 0) branch.RemoveSubtree(0);
|
---|
201 | foreach (var subtree in subtrees) {
|
---|
202 | branch.AddSubtree(ReplaceArgumentsInBranch(subtree, argumentTrees));
|
---|
203 | }
|
---|
204 | return branch;
|
---|
205 | }
|
---|
206 | }
|
---|
207 |
|
---|
208 | private static ArgumentTreeNode MakeArgumentNode(int argIndex) {
|
---|
209 | var node = (ArgumentTreeNode)(new Argument(argIndex)).CreateTreeNode();
|
---|
210 | return node;
|
---|
211 | }
|
---|
212 | }
|
---|
213 | }
|
---|