Free cookie consent management tool by TermsFeed Policy Generator

source: branches/1888_OaaS/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDuplicater.cs @ 17869

Last change on this file since 17869 was 8148, checked in by mkommend, 12 years ago

#1885: Corrected SubroutineCreator to adapt the grammar according to the new ADF.

File size: 7.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
32  /// <summary>
33  /// Manipulates a symbolic expression by duplicating a preexisting function-defining branch.
34  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 88
35  /// </summary>
36  [Item("SubroutineDuplicater", "Manipulates a symbolic expression by duplicating a preexisting function-defining branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 88")]
37  [StorableClass]
38  public sealed class SubroutineDuplicater : SymbolicExpressionTreeArchitectureManipulator {
39    [StorableConstructor]
40    private SubroutineDuplicater(bool deserializing) : base(deserializing) { }
41    private SubroutineDuplicater(SubroutineDuplicater original, Cloner cloner)
42      : base(original, cloner) {
43    }
44    public SubroutineDuplicater() : base() { }
45
46    public override IDeepCloneable Clone(Cloner cloner) {
47      return new SubroutineDuplicater(this, cloner);
48    }
49
50    public override sealed void ModifyArchitecture(
51      IRandom random,
52      ISymbolicExpressionTree symbolicExpressionTree,
53      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
54      DuplicateSubroutine(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
55    }
56
57    public static bool DuplicateSubroutine(
58      IRandom random,
59      ISymbolicExpressionTree symbolicExpressionTree,
60      int maxFunctionDefinitions, int maxFunctionArguments) {
61      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
62      if (functionDefiningBranches.Count() == 0 || functionDefiningBranches.Count() == maxFunctionDefinitions)
63        // no function defining branches to duplicate or already reached the max number of ADFs
64        return false;
65
66      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions) + 1).ToString(); // >= 100 functions => ###
67      var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
68                                 select "ADF" + index.ToString(formatString);
69      var selectedBranch = functionDefiningBranches.SelectRandom(random);
70      var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone();
71      string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
72      duplicatedDefunBranch.FunctionName = newFunctionName;
73      symbolicExpressionTree.Root.AddSubtree(duplicatedDefunBranch);
74      duplicatedDefunBranch.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBranch.Grammar.Clone());
75
76      var allowedChildSymbols = selectedBranch.Grammar.GetAllowedChildSymbols(selectedBranch.Symbol);
77      foreach (var allowedChildSymbol in allowedChildSymbols)
78        duplicatedDefunBranch.Grammar.AddAllowedChildSymbol(duplicatedDefunBranch.Symbol, allowedChildSymbol);
79      var maxSubtrees = selectedBranch.Grammar.GetMaximumSubtreeCount(selectedBranch.Symbol);
80      for (int i = 0; i < maxSubtrees; i++) {
81        foreach (var allowedChildSymbol in selectedBranch.Grammar.GetAllowedChildSymbols(selectedBranch.Symbol, i))
82          duplicatedDefunBranch.Grammar.AddAllowedChildSymbol(duplicatedDefunBranch.Symbol, allowedChildSymbol);
83      }
84
85      // add an invoke symbol for each branch that is allowed to invoke the original function
86      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
87        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
88                                    where symb.FunctionName == selectedBranch.FunctionName
89                                    select symb).SingleOrDefault();
90        if (matchingInvokeSymbol != null) {
91          var invokeSymbol = new InvokeFunction(duplicatedDefunBranch.FunctionName);
92          subtree.Grammar.AddSymbol(invokeSymbol);
93          subtree.Grammar.SetSubtreeCount(invokeSymbol, duplicatedDefunBranch.NumberOfArguments, duplicatedDefunBranch.NumberOfArguments);
94
95          foreach (ISymbol symbol in subtree.Grammar.Symbols) {
96            if (subtree.Grammar.IsAllowedChildSymbol(symbol, matchingInvokeSymbol))
97              subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol);
98            else {
99              for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(symbol); i++)
100                if (subtree.Grammar.IsAllowedChildSymbol(symbol, matchingInvokeSymbol, i))
101                  subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol, i);
102            }
103          }
104
105          foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol))
106            if (symbol != invokeSymbol) //avoid duplicate entry invokesymbol / invokesymbol
107              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol);
108          for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(matchingInvokeSymbol); i++) {
109            foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol, i).Except(subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol)))
110              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol, i);
111          }
112        }
113        // in the current subtree:
114        // for all invoke nodes of the original function replace the invoke of the original function with an invoke of the new function randomly
115        var originalFunctionInvocations = from node in subtree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
116                                          where node.Symbol.FunctionName == selectedBranch.FunctionName
117                                          select node;
118        foreach (var originalFunctionInvokeNode in originalFunctionInvocations) {
119          var newInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
120                                 where symb.FunctionName == duplicatedDefunBranch.FunctionName
121                                 select symb).Single();
122          // flip coin wether to replace with newly defined function
123          if (random.NextDouble() < 0.5) {
124            originalFunctionInvokeNode.Symbol = newInvokeSymbol;
125          }
126        }
127      }
128      return true;
129    }
130
131    private static IEnumerable<string> UsedFunctionNames(ISymbolicExpressionTree symbolicExpressionTree) {
132      return from node in symbolicExpressionTree.IterateNodesPrefix()
133             where node.Symbol is Defun
134             select ((DefunTreeNode)node).FunctionName;
135    }
136  }
137}
Note: See TracBrowser for help on using the repository browser.