Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentDuplicater.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: 7.2 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.Linq;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27using System.Collections.Generic;
28using System;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
31  /// <summary>
32  /// Manipulates a symbolic expression by duplicating an existing argument node of a function-defining branch.
33  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 94
34  /// </summary>
35  [Item("ArgumentDuplicater", "Manipulates a symbolic expression by duplicating an existing argument node of a function-defining branch.")]
36  [StorableClass]
37  public sealed class ArgumentDuplicater : 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 = DuplicateArgument(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
46    }
47
48    public static bool DuplicateArgument(
49      IRandom random,
50      SymbolicExpressionTree symbolicExpressionTree,
51      ISymbolicExpressionGrammar grammar,
52      int maxTreeSize, int maxTreeHeight,
53      int maxFunctionDefiningBranches, int maxFunctionArguments) {
54      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
55
56      var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
57      if (functionDefiningBranches.Count() == 0)
58        // no function defining branches => abort
59        return false;
60
61      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
62      var argumentSymbols = selectedDefunBranch.Grammar.Symbols.OfType<Argument>();
63      if (argumentSymbols.Count() == 0 || argumentSymbols.Count() >= maxFunctionArguments)
64        // when no argument or number of arguments is already at max allowed value => abort
65        return false;
66      var selectedArgumentSymbol = argumentSymbols.SelectRandom(random);
67      var takenIndexes = argumentSymbols.Select(s => s.ArgumentIndex);
68      var newArgumentIndex = allowedArgumentIndexes.Except(takenIndexes).First();
69
70      var newArgSymbol = new Argument(newArgumentIndex);
71
72      // replace existing references to the original argument with references to the new argument randomly in the selectedBranch
73      var argumentNodes = selectedDefunBranch.IterateNodesPrefix().OfType<ArgumentTreeNode>();
74      foreach (var argNode in argumentNodes) {
75        if (argNode.Symbol == selectedArgumentSymbol) {
76          if (random.NextDouble() < 0.5) {
77            argNode.Symbol = newArgSymbol;
78          }
79        }
80      }
81      // find invocations of the functions and duplicate the matching argument branch
82      var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
83                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
84                             where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
85                             select node).ToList();
86      // do this repeatedly until no matching invocations are found     
87      while (invocationNodes.Count() > 0) {
88        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
89        foreach (var invokeNode in invocationNodes) {
90          // check that the invocation node really has the correct number of arguments
91          if (invokeNode.SubTrees.Count != selectedDefunBranch.NumberOfArguments) throw new InvalidOperationException();
92          var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
93          var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
94          invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
95          newlyAddedBranches.Add(clonedArgumentBranch);
96        }
97        invocationNodes = (from newlyAddedBranch in newlyAddedBranches
98                           from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
99                           where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
100                           where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
101                           select node).ToList();
102      }
103      // register the new argument symbol and increase the number of arguments of the ADF
104      selectedDefunBranch.Grammar.AddSymbol(newArgSymbol);
105      selectedDefunBranch.Grammar.SetMinSubtreeCount(newArgSymbol, 0);
106      selectedDefunBranch.Grammar.SetMaxSubtreeCount(newArgSymbol, 0);
107      // allow the argument as child of any other symbol
108      foreach (var symb in selectedDefunBranch.Grammar.Symbols)
109        for (int i = 0; i < selectedDefunBranch.Grammar.GetMaxSubtreeCount(symb); i++) {
110          selectedDefunBranch.Grammar.SetAllowedChild(symb, newArgSymbol, i);
111        }
112      selectedDefunBranch.NumberOfArguments++;
113
114      // increase the arity of the changed ADF in all branches that can use this ADF
115      foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
116        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
117                                    where symb.FunctionName == selectedDefunBranch.FunctionName
118                                    select symb).SingleOrDefault();
119        if (matchingInvokeSymbol != null) {
120          subtree.Grammar.SetMinSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
121          subtree.Grammar.SetMaxSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments);
122          foreach (var child in subtree.GetAllowedSymbols(0)) {
123            for (int i = 0; i < subtree.Grammar.GetMaxSubtreeCount(matchingInvokeSymbol); i++) {
124              subtree.Grammar.SetAllowedChild(matchingInvokeSymbol, child, i);
125            }
126          }
127        }
128      }
129      return true;
130    }
131  }
132}
Note: See TracBrowser for help on using the repository browser.