Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HiveStatistics/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDeleter.cs @ 12394

Last change on this file since 12394 was 11205, checked in by ascheibe, 10 years ago

merged rest of trunk into hive statistics branch

File size: 6.1 KB
RevLine 
[3294]1#region License Information
2/* HeuristicLab
[11205]3 * Copyright (C) 2002-2014 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;
23using System.Linq;
[4722]24using HeuristicLab.Common;
[3294]25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28
[5499]29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3294]30  /// <summary>
31  /// Manipulates a symbolic expression by deleting a preexisting function-defining branch.
32  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 108
33  /// </summary>
[5510]34  [Item("SubroutineDeleter", "Manipulates a symbolic expression by deleting a preexisting function-defining branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 108")]
[3294]35  [StorableClass]
[3534]36  public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureManipulator {
[4722]37    [StorableConstructor]
38    private SubroutineDeleter(bool deserializing) : base(deserializing) { }
39    private SubroutineDeleter(SubroutineDeleter original, Cloner cloner) : base(original, cloner) { }
40    public SubroutineDeleter() : base() { }
41
42    public override IDeepCloneable Clone(Cloner cloner) {
43      return new SubroutineDeleter(this, cloner);
44    }
45
[3294]46    public override sealed void ModifyArchitecture(
47      IRandom random,
[5510]48      ISymbolicExpressionTree symbolicExpressionTree,
49      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
50      DeleteSubroutine(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
[3294]51    }
52
53    public static bool DeleteSubroutine(
54      IRandom random,
[5510]55      ISymbolicExpressionTree symbolicExpressionTree,
56      int maxFunctionDefinitions, int maxFunctionArguments) {
[3294]57      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
58
59      if (functionDefiningBranches.Count() == 0)
60        // no ADF to delete => abort
61        return false;
[3338]62      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
[3294]63      // remove the selected defun
[5733]64      int defunSubtreeIndex = symbolicExpressionTree.Root.IndexOfSubtree(selectedDefunBranch);
65      symbolicExpressionTree.Root.RemoveSubtree(defunSubtreeIndex);
[3294]66
67      // remove references to deleted function
[5733]68      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
[3360]69        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
70                                    where symb.FunctionName == selectedDefunBranch.FunctionName
71                                    select symb).SingleOrDefault();
72        if (matchingInvokeSymbol != null) {
73          subtree.Grammar.RemoveSymbol(matchingInvokeSymbol);
[3294]74        }
75      }
[3360]76
77      DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch);
[3294]78      return true;
79    }
[3360]80
[5510]81    private static void DeletionByRandomRegeneration(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) {
[3360]82      // find first invocation and replace it with a randomly generated tree
83      // can't find all invocations in one step because once we replaced a top level invocation
84      // the invocations below it are removed already
85      var invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
[5733]86                                from subtree in node.Subtrees.OfType<InvokeFunctionTreeNode>()
[3360]87                                where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
[5686]88                                select new CutPoint(node, subtree)).FirstOrDefault();
[3360]89      while (invocationCutPoint != null) {
90        // deletion by random regeneration
[5510]91        ISymbolicExpressionTreeNode replacementTree = null;
[5686]92        var allowedSymbolsList = invocationCutPoint.Parent.Grammar.GetAllowedChildSymbols(invocationCutPoint.Parent.Symbol, invocationCutPoint.ChildIndex).ToList();
[5411]93        var weights = allowedSymbolsList.Select(s => s.InitialFrequency);
94        var selectedSymbol = allowedSymbolsList.SelectRandom(weights, random);
[3360]95
[5686]96        int minPossibleLength = invocationCutPoint.Parent.Grammar.GetMinimumExpressionLength(selectedSymbol);
97        int maxLength = Math.Max(minPossibleLength, invocationCutPoint.Child.GetLength());
98        int minPossibleDepth = invocationCutPoint.Parent.Grammar.GetMinimumExpressionDepth(selectedSymbol);
99        int maxDepth = Math.Max(minPossibleDepth, invocationCutPoint.Child.GetDepth());
[3369]100        replacementTree = selectedSymbol.CreateTreeNode();
[3535]101        if (replacementTree.HasLocalParameters)
102          replacementTree.ResetLocalParameters(random);
[5733]103        invocationCutPoint.Parent.RemoveSubtree(invocationCutPoint.ChildIndex);
104        invocationCutPoint.Parent.InsertSubtree(invocationCutPoint.ChildIndex, replacementTree);
[3360]105
[5686]106        ProbabilisticTreeCreator.PTC2(random, replacementTree, maxLength, maxDepth);
[3369]107
[3360]108        invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
[5733]109                              from subtree in node.Subtrees.OfType<InvokeFunctionTreeNode>()
[3360]110                              where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
[5686]111                              select new CutPoint(node, subtree)).FirstOrDefault();
[3360]112      }
113    }
[3294]114  }
115}
Note: See TracBrowser for help on using the repository browser.