Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentCreater.cs @ 4524

Last change on this file since 4524 was 4524, checked in by gkronber, 13 years ago

Fixed #1214. The size of the manipulated tree is checked and only if the new tree fulfills the size requirements it is accepted otherwise the original tree is returned instead. Additionally the calculation of tree sizes is checked for overflows now.

File size: 10.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using System;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
31  /// <summary>
32  /// Creates a new argument within one function-defining branch of a symbolic expression tree.
33  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 106
34  /// </summary>
35  [Item("ArgumentCreater", "Manipulates a symbolic expression by creating a new argument within one function-defining branch.")]
36  [StorableClass]
37  public sealed class ArgumentCreater : SymbolicExpressionTreeArchitectureManipulator {
38    public override sealed void ModifyArchitecture(
39      IRandom random,
40      SymbolicExpressionTree symbolicExpressionTree,
41      ISymbolicExpressionGrammar grammar,
42      IntValue maxTreeSize, IntValue maxTreeHeight,
43      IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
44      out bool success) {
45      success = CreateNewArgument(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
46    }
47
48    public static bool CreateNewArgument(
49      IRandom random,
50      SymbolicExpressionTree symbolicExpressionTree,
51      ISymbolicExpressionGrammar grammar,
52      int maxTreeSize, int maxTreeHeight,
53      int maxFunctionDefiningBranches, int maxFunctionArguments) {
54      // work on a copy in case we find out later that the tree would be too big
55      // in this case it's easiest to simply return the original tree.
56      SymbolicExpressionTree clonedTree = (SymbolicExpressionTree)symbolicExpressionTree.Clone();
57
58      var functionDefiningBranches = clonedTree.IterateNodesPrefix().OfType<DefunTreeNode>();
59      if (functionDefiningBranches.Count() == 0)
60        // no function defining branch found => abort
61        return false;
62
63      // select a random function defining branch
64      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
65      var definedArguments = (from symbol in selectedDefunBranch.Grammar.Symbols.OfType<Argument>()
66                              select symbol.ArgumentIndex).Distinct();
67      if (definedArguments.Count() >= maxFunctionArguments)
68        // max number of arguments reached => abort
69        return false;
70
71      var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
72      var newArgumentIndex = allowedArgumentIndexes.Except(definedArguments).First();
73      ArgumentTreeNode newArgumentNode = MakeArgumentNode(newArgumentIndex);
74
75      // this operation potentially creates very big trees so the access to the size property might throw overflow exception
76      try {
77        if (CreateNewArgumentForDefun(random, clonedTree, selectedDefunBranch, newArgumentNode) && clonedTree.Size < maxTreeSize && clonedTree.Height < maxTreeHeight) {
78
79          // size constraints are fulfilled
80          // replace root of original tree with root of manipulated tree
81          symbolicExpressionTree.Root = clonedTree.Root;
82          return true;
83        } else {
84          // keep originalTree
85          return false;
86        }
87      }
88      catch (OverflowException) {
89        // keep original tree
90        return false;
91      }
92    }
93
94
95    private static bool CreateNewArgumentForDefun(IRandom random, SymbolicExpressionTree tree, DefunTreeNode defunBranch, ArgumentTreeNode newArgumentNode) {
96      // select a random cut point in the function defining branch
97      // the branch at the cut point is to be replaced by a new argument node
98      var cutPoints = (from node in defunBranch.IterateNodesPrefix()
99                       where node.SubTrees.Count > 0
100                       from subtree in node.SubTrees
101                       select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).ToList();
102
103      if (cutPoints.Count() == 0)
104        // no cut point found => abort;
105        return false;
106      var selectedCutPoint = cutPoints[random.Next(cutPoints.Count)];
107      // replace the branch at the cut point with an argument node
108      var replacedBranch = selectedCutPoint.ReplacedChild;
109      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedChildIndex);
110      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgumentNode);
111
112      // find all old invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
113      // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
114      var invocationNodes = (from node in tree.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
115                             where node.Symbol.FunctionName == defunBranch.FunctionName
116                             where node.SubTrees.Count == defunBranch.NumberOfArguments
117                             select node).ToList();
118      // do this repeatedly until no matching invocations are found     
119      while (invocationNodes.Count > 0) {
120        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
121        foreach (var invocationNode in invocationNodes) {
122          // check that the invocation node really has the correct number of arguments
123          if (invocationNode.SubTrees.Count != defunBranch.NumberOfArguments) throw new InvalidOperationException();
124          // append a new argument branch after expanding all argument nodes
125          var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
126          clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
127          invocationNode.InsertSubTree(newArgumentNode.Symbol.ArgumentIndex, clonedBranch);
128          newlyAddedBranches.Add(clonedBranch);
129        }
130        // iterate in post-fix order to make sure that the subtrees of n are already adapted when n is processed
131        invocationNodes = (from newlyAddedBranch in newlyAddedBranches
132                           from node in newlyAddedBranch.IterateNodesPostfix().OfType<InvokeFunctionTreeNode>()
133                           where node.Symbol.FunctionName == defunBranch.FunctionName
134                           where node.SubTrees.Count == defunBranch.NumberOfArguments
135                           select node).ToList();
136      }
137      // increase expected number of arguments of function defining branch
138      // it's possible that the number of actually referenced arguments was reduced (all references were replaced by a single new argument)
139      // but the number of expected arguments is increased anyway
140      defunBranch.NumberOfArguments++;
141      defunBranch.Grammar.AddSymbol(newArgumentNode.Symbol);
142      defunBranch.Grammar.SetMinSubtreeCount(newArgumentNode.Symbol, 0);
143      defunBranch.Grammar.SetMaxSubtreeCount(newArgumentNode.Symbol, 0);
144      // allow the argument as child of any other symbol
145      foreach (var symb in defunBranch.Grammar.Symbols)
146        for (int i = 0; i < defunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
147          defunBranch.Grammar.SetAllowedChild(symb, newArgumentNode.Symbol, i);
148        }
149      foreach (var subtree in tree.Root.SubTrees) {
150        // when the changed function is known in the branch then update the number of arguments
151        var matchingSymbol = subtree.Grammar.Symbols.OfType<InvokeFunction>().Where(s => s.FunctionName == defunBranch.FunctionName).SingleOrDefault();
152        if (matchingSymbol != null) {
153          subtree.Grammar.SetMinSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments);
154          subtree.Grammar.SetMaxSubtreeCount(matchingSymbol, defunBranch.NumberOfArguments);
155          foreach (var child in subtree.GetAllowedSymbols(0)) {
156            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingSymbol); i++) {
157              subtree.Grammar.SetAllowedChild(matchingSymbol, child, i);
158            }
159          }
160        }
161      }
162
163      return true;
164    }
165
166    private static SymbolicExpressionTreeNode ReplaceArgumentsInBranch(SymbolicExpressionTreeNode branch, IList<SymbolicExpressionTreeNode> argumentTrees) {
167      ArgumentTreeNode argNode = branch as ArgumentTreeNode;
168      if (argNode != null) {
169        // replace argument nodes by a clone of the original subtree that provided the result for the argument node
170        return (SymbolicExpressionTreeNode)argumentTrees[argNode.Symbol.ArgumentIndex].Clone();
171      } else {
172        // call recursively for all subtree
173        List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(branch.SubTrees);
174        while (branch.SubTrees.Count > 0) branch.RemoveSubTree(0);
175        foreach (var subtree in subtrees) {
176          branch.AddSubTree(ReplaceArgumentsInBranch(subtree, argumentTrees));
177        }
178        return branch;
179      }
180    }
181
182    private static ArgumentTreeNode MakeArgumentNode(int argIndex) {
183      var node = (ArgumentTreeNode)(new Argument(argIndex)).CreateTreeNode();
184      return node;
185    }
186  }
187}
Note: See TracBrowser for help on using the repository browser.