Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineDeleter.cs @ 16140

Last change on this file since 16140 was 16140, checked in by abeham, 6 years ago

#2817: updated to trunk r15680

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