Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/ArgumentDuplicater.cs @ 12706

Last change on this file since 12706 was 12706, checked in by mkommend, 9 years ago

#2320: Merged r12422, r12423, r12424, r12480, r12481 and r12482 into stable.

File size: 7.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Random;
30
31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
32  /// <summary>
33  /// Manipulates a symbolic expression by duplicating an existing argument node of a function-defining branch.
34  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 94
35  /// </summary>
36  [Item("ArgumentDuplicater", "Manipulates a symbolic expression by duplicating an existing argument node of a function-defining branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 94")]
37  [StorableClass]
38  public sealed class ArgumentDuplicater : SymbolicExpressionTreeArchitectureManipulator {
39    [StorableConstructor]
40    private ArgumentDuplicater(bool deserializing) : base(deserializing) { }
41    private ArgumentDuplicater(ArgumentDuplicater original, Cloner cloner) : base(original, cloner) { }
42    public ArgumentDuplicater() : base() { }
43
44    public override sealed void ModifyArchitecture(
45      IRandom random,
46      ISymbolicExpressionTree symbolicExpressionTree,
47      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
48      DuplicateArgument(random, symbolicExpressionTree, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
49    }
50
51    public override IDeepCloneable Clone(Cloner cloner) {
52      return new ArgumentDuplicater(this, cloner);
53    }
54
55    public static bool DuplicateArgument(
56      IRandom random,
57      ISymbolicExpressionTree symbolicExpressionTree,
58      int maxFunctionDefinitions, int maxFunctionArguments) {
59      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>().ToList();
60
61      var allowedArgumentIndexes = Enumerable.Range(0, maxFunctionArguments);
62      if (!functionDefiningBranches.Any())
63        // no function defining branches => abort
64        return false;
65
66      var selectedDefunBranch = functionDefiningBranches.SampleRandom(random);
67
68      var argumentSymbols = selectedDefunBranch.Grammar.Symbols.OfType<Argument>().ToList();
69      if (!argumentSymbols.Any() || argumentSymbols.Count() >= maxFunctionArguments)
70        // when no argument or number of arguments is already at max allowed value => abort
71        return false;
72
73      var selectedArgumentSymbol = argumentSymbols.SampleRandom(random);
74      var takenIndexes = argumentSymbols.Select(s => s.ArgumentIndex);
75      var newArgumentIndex = allowedArgumentIndexes.Except(takenIndexes).First();
76
77      var newArgSymbol = new Argument(newArgumentIndex);
78
79      // replace existing references to the original argument with references to the new argument randomly in the selectedBranch
80      var argumentNodes = selectedDefunBranch.IterateNodesPrefix().OfType<ArgumentTreeNode>();
81      foreach (var argNode in argumentNodes) {
82        if (argNode.Symbol == selectedArgumentSymbol) {
83          if (random.NextDouble() < 0.5) {
84            argNode.Symbol = newArgSymbol;
85          }
86        }
87      }
88      // find invocations of the functions and duplicate the matching argument branch
89      var invocationNodes = (from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
90                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
91                             where node.Subtrees.Count() == selectedDefunBranch.NumberOfArguments
92                             select node).ToList();
93      // do this repeatedly until no matching invocations are found     
94      while (invocationNodes.Count() > 0) {
95        List<ISymbolicExpressionTreeNode> newlyAddedBranches = new List<ISymbolicExpressionTreeNode>();
96        foreach (var invokeNode in invocationNodes) {
97          // check that the invocation node really has the correct number of arguments
98          if (invokeNode.Subtrees.Count() != selectedDefunBranch.NumberOfArguments) throw new InvalidOperationException();
99          var argumentBranch = invokeNode.GetSubtree(selectedArgumentSymbol.ArgumentIndex);
100          var clonedArgumentBranch = (ISymbolicExpressionTreeNode)argumentBranch.Clone();
101          invokeNode.InsertSubtree(newArgumentIndex, clonedArgumentBranch);
102          newlyAddedBranches.Add(clonedArgumentBranch);
103        }
104        invocationNodes = (from newlyAddedBranch in newlyAddedBranches
105                           from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
106                           where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
107                           where node.Subtrees.Count() == selectedDefunBranch.NumberOfArguments
108                           select node).ToList();
109      }
110      // register the new argument symbol and increase the number of arguments of the ADF
111      selectedDefunBranch.Grammar.AddSymbol(newArgSymbol);
112      selectedDefunBranch.Grammar.SetSubtreeCount(newArgSymbol, 0, 0);
113      // allow the duplicated argument as child of all other arguments where the orginal argument was allowed
114      GrammarModifier.SetAllowedParentSymbols(selectedDefunBranch.Grammar, selectedArgumentSymbol, newArgSymbol);
115      selectedDefunBranch.NumberOfArguments++;
116
117      // increase the arity of the changed ADF in all branches that can use this ADF
118      foreach (var subtree in symbolicExpressionTree.Root.Subtrees) {
119        var matchingInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
120                                    where symb.FunctionName == selectedDefunBranch.FunctionName
121                                    select symb).SingleOrDefault();
122        if (matchingInvokeSymbol != null) {
123          subtree.Grammar.SetSubtreeCount(matchingInvokeSymbol, selectedDefunBranch.NumberOfArguments, selectedDefunBranch.NumberOfArguments);
124          foreach (var symb in subtree.Grammar.Symbols) {
125            if (symb is StartSymbol || symb is ProgramRootSymbol) continue;
126            if (subtree.Grammar.IsAllowedChildSymbol(matchingInvokeSymbol, symb, selectedArgumentSymbol.ArgumentIndex))
127              subtree.Grammar.AddAllowedChildSymbol(matchingInvokeSymbol, symb, newArgumentIndex);
128          }
129        }
130      }
131      return true;
132    }
133  }
134}
Note: See TracBrowser for help on using the repository browser.