Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ParameterBinding/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/SubroutineDeleter.cs @ 4745

Last change on this file since 4745 was 4722, checked in by swagner, 14 years ago

Merged cloning refactoring branch back into trunk (#922)

File size: 6.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Encodings.SymbolicExpressionTreeEncoding.Creators;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
32  /// <summary>
33  /// Manipulates a symbolic expression by deleting a preexisting function-defining branch.
34  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 108
35  /// </summary>
36  [Item("SubroutineDeleter", "Manipulates a symbolic expression by deleting a preexisting function-defining branch.")]
37  [StorableClass]
38  public sealed class SubroutineDeleter : SymbolicExpressionTreeArchitectureManipulator {
39    [StorableConstructor]
40    private SubroutineDeleter(bool deserializing) : base(deserializing) { }
41    private SubroutineDeleter(SubroutineDeleter original, Cloner cloner) : base(original, cloner) { }
42    public SubroutineDeleter() : base() { }
43
44    public override IDeepCloneable Clone(Cloner cloner) {
45      return new SubroutineDeleter(this, cloner);
46    }
47
48    public override sealed void ModifyArchitecture(
49      IRandom random,
50      SymbolicExpressionTree symbolicExpressionTree,
51      ISymbolicExpressionGrammar grammar,
52      IntValue maxTreeSize, IntValue maxTreeHeight,
53      IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
54      out bool success) {
55      success = DeleteSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
56    }
57
58    public static bool DeleteSubroutine(
59      IRandom random,
60      SymbolicExpressionTree symbolicExpressionTree,
61      ISymbolicExpressionGrammar grammar,
62      int maxTreeSize, int maxTreeHeight,
63      int maxFunctionDefiningBranches, int maxFunctionArguments) {
64      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
65
66      if (functionDefiningBranches.Count() == 0)
67        // no ADF to delete => abort
68        return false;
69      var selectedDefunBranch = functionDefiningBranches.SelectRandom(random);
70      // remove the selected defun
71      int defunSubtreeIndex = symbolicExpressionTree.Root.SubTrees.IndexOf(selectedDefunBranch);
72      symbolicExpressionTree.Root.RemoveSubTree(defunSubtreeIndex);
73
74      // remove references to deleted function
75      foreach (var subtree in symbolicExpressionTree.Root.SubTrees.OfType<SymbolicExpressionTreeTopLevelNode>()) {
76        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
77                                    where symb.FunctionName == selectedDefunBranch.FunctionName
78                                    select symb).SingleOrDefault();
79        if (matchingInvokeSymbol != null) {
80          subtree.Grammar.RemoveSymbol(matchingInvokeSymbol);
81        }
82      }
83
84      DeletionByRandomRegeneration(random, symbolicExpressionTree, selectedDefunBranch);
85      return true;
86    }
87
88    private static void DeletionByRandomRegeneration(IRandom random, SymbolicExpressionTree symbolicExpressionTree, DefunTreeNode selectedDefunBranch) {
89      // find first invocation and replace it with a randomly generated tree
90      // can't find all invocations in one step because once we replaced a top level invocation
91      // the invocations below it are removed already
92      var invocationCutPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
93                                from subtree in node.SubTrees.OfType<InvokeFunctionTreeNode>()
94                                where subtree.Symbol.FunctionName == selectedDefunBranch.FunctionName
95                                select new { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
96      while (invocationCutPoint != null) {
97        // deletion by random regeneration
98        SymbolicExpressionTreeNode replacementTree = null;
99        // TODO: should weight symbols by tickets
100        var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random);
101
102        int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol);
103        int maxSize = Math.Max(minPossibleSize, invocationCutPoint.ReplacedChild.GetSize());
104        int minPossibleHeight = invocationCutPoint.Parent.Grammar.GetMinExpressionDepth(selectedSymbol);
105        int maxHeight = Math.Max(minPossibleHeight, invocationCutPoint.ReplacedChild.GetHeight());
106        replacementTree = selectedSymbol.CreateTreeNode();
107        if (replacementTree.HasLocalParameters)
108          replacementTree.ResetLocalParameters(random);
109        invocationCutPoint.Parent.RemoveSubTree(invocationCutPoint.ReplacedChildIndex);
110        invocationCutPoint.Parent.InsertSubTree(invocationCutPoint.ReplacedChildIndex, replacementTree);
111
112        ProbabilisticTreeCreator.PTC2(random, replacementTree, maxSize, maxHeight, 0, 0);
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 { Parent = node, ReplacedChildIndex = node.SubTrees.IndexOf(subtree), ReplacedChild = subtree }).FirstOrDefault();
118      }
119    }
120  }
121}
Note: See TracBrowser for help on using the repository browser.