Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentDuplicater.cs @ 4477

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

Merged r4458, r4459,r4462,r4464 from data analysis exploration branch into trunk. #1142

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