Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1532:

  • Enabled renaming of symbols
  • Fixed cloning of grammers
  • Added readonly attribute in grammars to lock grammars during the algorithm run
  • Removed useless clone method in cloner
  • Changed CheckedItemCollectionViews to enable scrolling during the locked state
File size: 7.0 KB
RevLine 
[3294]1#region License Information
2/* HeuristicLab
[5445]3 * Copyright (C) 2002-2011 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;
30
[5499]31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3294]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>
[5510]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")]
[3294]37  [StorableClass]
[3534]38  public sealed class SubroutineDuplicater : SymbolicExpressionTreeArchitectureManipulator {
[4722]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
[3294]50    public override sealed void ModifyArchitecture(
51      IRandom random,
[5510]52      ISymbolicExpressionTree symbolicExpressionTree,
53      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
54      DuplicateSubroutine(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
[3294]55    }
56
[3360]57    public static bool DuplicateSubroutine(
[3294]58      IRandom random,
[5510]59      ISymbolicExpressionTree symbolicExpressionTree,
60      int maxFunctionDefinitions, int maxFunctionArguments) {
[3294]61      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
[5510]62      if (functionDefiningBranches.Count() == 0 || functionDefiningBranches.Count() == maxFunctionDefinitions)
[3722]63        // no function defining branches to duplicate or already reached the max number of ADFs
64        return false;
[3294]65
[5510]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)
[3294]68                                 select "ADF" + index.ToString(formatString);
[3338]69      var selectedBranch = functionDefiningBranches.SelectRandom(random);
[3360]70      var duplicatedDefunBranch = (DefunTreeNode)selectedBranch.Clone();
71      string newFunctionName = allowedFunctionNames.Except(UsedFunctionNames(symbolicExpressionTree)).First();
72      duplicatedDefunBranch.FunctionName = newFunctionName;
[5733]73      symbolicExpressionTree.Root.AddSubtree(duplicatedDefunBranch);
[5510]74      duplicatedDefunBranch.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBranch.Grammar.Clone());
[3360]75      // add an invoke symbol for each branch that is allowed to invoke the original function
[5733]76      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
[3360]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) {
[5686]81          var invokeSymbol = new InvokeFunction(duplicatedDefunBranch.FunctionName);
82          subtree.Grammar.AddSymbol(invokeSymbol);
83          subtree.Grammar.SetSubtreeCount(invokeSymbol, duplicatedDefunBranch.NumberOfArguments, duplicatedDefunBranch.NumberOfArguments);
84
[6233]85          foreach (ISymbol symbol in subtree.Grammar.Symbols) {
[5686]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))
[5792]91                  subtree.Grammar.AddAllowedChildSymbol(symbol, invokeSymbol, i);
[5686]92            }
93          }
94
[6233]95          foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol))
[5686]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++) {
[6233]99            foreach (ISymbol symbol in subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol, i).Except(subtree.Grammar.GetAllowedChildSymbols(matchingInvokeSymbol)))
[5686]100              subtree.Grammar.AddAllowedChildSymbol(invokeSymbol, symbol, i);
101          }
[3294]102        }
[3369]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          }
[3360]116        }
117      }
[3294]118      return true;
119    }
120
[5510]121    private static IEnumerable<string> UsedFunctionNames(ISymbolicExpressionTree symbolicExpressionTree) {
[3294]122      return from node in symbolicExpressionTree.IterateNodesPrefix()
123             where node.Symbol is Defun
[3360]124             select ((DefunTreeNode)node).FunctionName;
[3294]125    }
126  }
127}
Note: See TracBrowser for help on using the repository browser.