Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDuplicater.cs @ 15675

Last change on this file since 15675 was 15583, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers

File size: 7.7 KB
RevLine 
[3294]1#region License Information
2/* HeuristicLab
[15583]3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3294]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;
[4068]23using System.Collections.Generic;
[3294]24using System.Linq;
[4068]25using System.Text;
[4722]26using HeuristicLab.Common;
[3294]27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[12422]30using HeuristicLab.Random;
[3294]31
[5499]32namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3294]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>
[5510]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")]
[3294]38  [StorableClass]
[3534]39  public sealed class SubroutineDuplicater : SymbolicExpressionTreeArchitectureManipulator {
[4722]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
[3294]51    public override sealed void ModifyArchitecture(
52      IRandom random,
[5510]53      ISymbolicExpressionTree symbolicExpressionTree,
54      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
55      DuplicateSubroutine(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
[3294]56    }
57
[3360]58    public static bool DuplicateSubroutine(
[3294]59      IRandom random,
[5510]60      ISymbolicExpressionTree symbolicExpressionTree,
61      int maxFunctionDefinitions, int maxFunctionArguments) {
[12422]62      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>().ToList();
63      if (!functionDefiningBranches.Any() || functionDefiningBranches.Count() == maxFunctionDefinitions)
[3722]64        // no function defining branches to duplicate or already reached the max number of ADFs
65        return false;
[3294]66
[5510]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)
[3294]69                                 select "ADF" + index.ToString(formatString);
[12422]70
71      var selectedBranch = functionDefiningBranches.SampleRandom(random);
[3360]72      var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone();
73      string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
74      duplicatedDefunBranch.FunctionName = newFunctionName;
[5733]75      symbolicExpressionTree.Root.AddSubtree(duplicatedDefunBranch);
[5510]76      duplicatedDefunBranch.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBranch.Grammar.Clone());
[8148]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
[3360]87      // add an invoke symbol for each branch that is allowed to invoke the original function
[5733]88      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
[3360]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) {
[5686]93          var invokeSymbol = new InvokeFunction(duplicatedDefunBranch.FunctionName);
94          subtree.Grammar.AddSymbol(invokeSymbol);
95          subtree.Grammar.SetSubtreeCount(invokeSymbol, duplicatedDefunBranch.NumberOfArguments, duplicatedDefunBranch.NumberOfArguments);
96
[6233]97          foreach (ISymbol symbol in subtree.Grammar.Symbols) {
[5686]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))
[5792]103                  subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol, i);
[5686]104            }
105          }
106
[6233]107          foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol))
[5686]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++) {
[6233]111            foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol, i).Except(subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol)))
[5686]112              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol, i);
113          }
[3294]114        }
[3369]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          }
[3360]128        }
129      }
[3294]130      return true;
131    }
132
[5510]133    private static IEnumerable<string> UsedFunctionNames(ISymbolicExpressionTree symbolicExpressionTree) {
[3294]134      return from node in symbolicExpressionTree.IterateNodesPrefix()
135             where node.Symbol is Defun
[3360]136             select ((DefunTreeNode)node).FunctionName;
[3294]137    }
138  }
139}
Note: See TracBrowser for help on using the repository browser.