Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDuplicater.cs @ 5792

Last change on this file since 5792 was 5792, checked in by mkommend, 13 years ago

#1418: Corrected ADFs and adapted unit tests.

File size: 7.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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      // add an invoke symbol for each branch that is allowed to invoke the original function
76      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
77        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
78                                    where symb.FunctionName == selectedBranch.FunctionName
79                                    select symb).SingleOrDefault();
80        if (matchingInvokeSymbol != null) {
81          var invokeSymbol = new InvokeFunction(duplicatedDefunBranch.FunctionName);
82          subtree.Grammar.AddSymbol(invokeSymbol);
83          subtree.Grammar.SetSubtreeCount(invokeSymbol, duplicatedDefunBranch.NumberOfArguments, duplicatedDefunBranch.NumberOfArguments);
84
85          foreach (Symbol symbol in subtree.Grammar.Symbols) {
86            if (subtree.Grammar.IsAllowedChildSymbol(symbol, matchingInvokeSymbol))
87              subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol);
88            else {
89              for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(symbol); i++)
90                if (subtree.Grammar.IsAllowedChildSymbol(symbol, matchingInvokeSymbol, i))
91                  subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol, i);
92            }
93          }
94
95          foreach (Symbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol))
96            if (symbol != invokeSymbol) //avoid duplicate entry invokesymbol / invokesymbol
97              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol);
98          for (int i = 0; i < subtree.Grammar.GetMaximumSubtreeCount(matchingInvokeSymbol); i++) {
99            foreach (Symbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol, i).Except(subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol)))
100              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol, i);
101          }
102        }
103        // in the current subtree:
104        // for all invoke nodes of the original function replace the invoke of the original function with an invoke of the new function randomly
105        var originalFunctionInvocations = from node in subtree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
106                                          where node.Symbol.FunctionName == selectedBranch.FunctionName
107                                          select node;
108        foreach (var originalFunctionInvokeNode in originalFunctionInvocations) {
109          var newInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
110                                 where symb.FunctionName == duplicatedDefunBranch.FunctionName
111                                 select symb).Single();
112          // flip coin wether to replace with newly defined function
113          if (random.NextDouble() < 0.5) {
114            originalFunctionInvokeNode.Symbol = newInvokeSymbol;
115          }
116        }
117      }
118      return true;
119    }
120
121    private static IEnumerable<string> UsedFunctionNames(ISymbolicExpressionTree symbolicExpressionTree) {
122      return from node in symbolicExpressionTree.IterateNodesPrefix()
123             where node.Symbol is Defun
124             select ((DefunTreeNode)node).FunctionName;
125    }
126  }
127}
Note: See TracBrowser for help on using the repository browser.