Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDuplicater.cs @ 12706

Last change on this file since 12706 was 12706, checked in by mkommend, 9 years ago

#2320: Merged r12422, r12423, r12424, r12480, r12481 and r12482 into stable.

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