Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDeleter.cs @ 11171

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

#2115 merged r11170 (copyright update) into trunk

File size: 6.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28
29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
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>
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")]
35  [StorableClass]
36  public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureManipulator {
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
46    public override sealed void ModifyArchitecture(
47      IRandom random,
48      ISymbolicExpressionTree symbolicExpressionTree,
49      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
50      DeleteSubroutine(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
51    }
52
53    public static bool DeleteSubroutine(
54      IRandom random,
55      ISymbolicExpressionTree symbolicExpressionTree,
56      int maxFunctionDefinitions, int maxFunctionArguments) {
57      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
58
59      if (functionDefiningBranches.Count() == 0)
60        // no ADF to delete => abort
61        return false;
62      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
63      // remove the selected defun
64      int defunSubtreeIndex = symbolicExpressionTree.Root.IndexOfSubtree(selectedDefunBranch);
65      symbolicExpressionTree.Root.RemoveSubtree(defunSubtreeIndex);
66
67      // remove references to deleted function
68      foreach (var subtree in symbolicExpressionTree.Root.Subtrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
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);
74        }
75      }
76
77      DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch);
78      return true;
79    }
80
81    private static void DeletionByRandomRegeneration(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) {
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()
86                                from subtree in node.Subtrees.OfType<InvokeFunctionTreeNode>()
87                                where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
88                                select new CutPoint(node, subtree)).FirstOrDefault();
89      while (invocationCutPoint != null) {
90        // deletion by random regeneration
91        ISymbolicExpressionTreeNode replacementTree = null;
92        var allowedSymbolsList = invocationCutPoint.Parent.Grammar.GetAllowedChildSymbols(invocationCutPoint.Parent.Symbol, invocationCutPoint.ChildIndex).ToList();
93        var weights = allowedSymbolsList.Select(s => s.InitialFrequency);
94        var selectedSymbol = allowedSymbolsList.SelectRandom(weights, random);
95
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());
100        replacementTree = selectedSymbol.CreateTreeNode();
101        if (replacementTree.HasLocalParameters)
102          replacementTree.ResetLocalParameters(random);
103        invocationCutPoint.Parent.RemoveSubtree(invocationCutPoint.ChildIndex);
104        invocationCutPoint.Parent.InsertSubtree(invocationCutPoint.ChildIndex, replacementTree);
105
106        ProbabilisticTreeCreator.PTC2(random, replacementTree, maxLength, maxDepth);
107
108        invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
109                              from subtree in node.Subtrees.OfType<InvokeFunctionTreeNode>()
110                              where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
111                              select new CutPoint(node, subtree)).FirstOrDefault();
112      }
113    }
114  }
115}
Note: See TracBrowser for help on using the repository browser.