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 |
|
---|
22 | using System;
|
---|
23 | using System.Linq;
|
---|
24 | using HeuristicLab.Core;
|
---|
25 | using HeuristicLab.Data;
|
---|
26 | using HeuristicLab.Operators;
|
---|
27 | using HeuristicLab.Optimization;
|
---|
28 | using HeuristicLab.Parameters;
|
---|
29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
30 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
|
---|
31 | using System.Collections.Generic;
|
---|
32 | using System.Text;
|
---|
33 | using System.Diagnostics;
|
---|
34 |
|
---|
35 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators {
|
---|
36 | /// <summary>
|
---|
37 | /// Manipulates a symbolic expression by adding one new function-defining branch containing
|
---|
38 | /// a proportion of a preexisting branch and by creating a reference to the new branch.
|
---|
39 | /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97
|
---|
40 | /// </summary>
|
---|
41 | [Item("SubroutineCreater", "Manipulates a symbolic expression by adding one new function-defining branch containing a proportion of a preexisting branch and by creating a reference to the new branch.")]
|
---|
42 | [StorableClass]
|
---|
43 | public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureAlteringOperator {
|
---|
44 | public override sealed void ModifyArchitecture(
|
---|
45 | IRandom random,
|
---|
46 | SymbolicExpressionTree symbolicExpressionTree,
|
---|
47 | ISymbolicExpressionGrammar grammar,
|
---|
48 | IntValue maxTreeSize, IntValue maxTreeHeight,
|
---|
49 | IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
|
---|
50 | out bool success) {
|
---|
51 | success = CreateSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
|
---|
52 | }
|
---|
53 |
|
---|
54 | public static bool CreateSubroutine(
|
---|
55 | IRandom random,
|
---|
56 | SymbolicExpressionTree symbolicExpressionTree,
|
---|
57 | ISymbolicExpressionGrammar grammar,
|
---|
58 | int maxTreeSize, int maxTreeHeight,
|
---|
59 | int maxFunctionDefiningBranches, int maxFunctionArguments) {
|
---|
60 | var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
|
---|
61 | if (functionDefiningBranches.Count() >= maxFunctionDefiningBranches)
|
---|
62 | // allowed maximum number of ADF reached => abort
|
---|
63 | return false;
|
---|
64 | string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches) + 1).ToString(); // >= 100 functions => ###
|
---|
65 | var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefiningBranches)
|
---|
66 | select "ADF" + index.ToString(formatString);
|
---|
67 | // find all body branches
|
---|
68 | var bodies = from node in symbolicExpressionTree.IterateNodesPrefix()
|
---|
69 | where node.Symbol is Defun || node.Symbol is StartSymbol
|
---|
70 | select new { Tree = node, Size = node.GetSize() };
|
---|
71 | var totalNumberOfBodyNodes = bodies.Select(x => x.Size).Sum();
|
---|
72 | // select a random body
|
---|
73 | int r = random.Next(totalNumberOfBodyNodes);
|
---|
74 | int aggregatedNumberOfBodyNodes = 0;
|
---|
75 | SymbolicExpressionTreeNode selectedBody = null;
|
---|
76 | foreach (var body in bodies) {
|
---|
77 | aggregatedNumberOfBodyNodes += body.Size;
|
---|
78 | if (aggregatedNumberOfBodyNodes > r)
|
---|
79 | selectedBody = body.Tree;
|
---|
80 | }
|
---|
81 | // sanity check
|
---|
82 | if (selectedBody == null) throw new InvalidOperationException();
|
---|
83 | // select a random node in the selected branch
|
---|
84 | var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
|
---|
85 | from subtree in parent.SubTrees
|
---|
86 | select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList();
|
---|
87 | if (allCutPoints.Count == 0)
|
---|
88 | // no cut points => abort
|
---|
89 | return false;
|
---|
90 | var selectedCutPoint = allCutPoints[random.Next(allCutPoints.Count)];
|
---|
91 | // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
|
---|
92 | List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, 0.25, maxFunctionArguments);
|
---|
93 | string functionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.Name)).First();
|
---|
94 | SymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch;
|
---|
95 | // disconnect the function body from the tree
|
---|
96 | selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex);
|
---|
97 | // disconnect the argument branches from the function
|
---|
98 | DisconnectBranches(functionBody, argumentBranches);
|
---|
99 | // and insert a function invocation symbol instead
|
---|
100 | var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction()).CreateTreeNode();
|
---|
101 | invokeNode.InvokedFunctionName = functionName;
|
---|
102 | selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode);
|
---|
103 | foreach (var argumentBranch in argumentBranches)
|
---|
104 | invokeNode.AddSubTree(argumentBranch);
|
---|
105 |
|
---|
106 | // insert a new function defining branch
|
---|
107 | var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
|
---|
108 | defunNode.Name = functionName;
|
---|
109 | defunNode.AddSubTree(functionBody);
|
---|
110 | symbolicExpressionTree.Root.AddSubTree(defunNode);
|
---|
111 | // copy known symbols from originating branch into new branch
|
---|
112 | foreach (var knownSymbol in selectedBody.DynamicSymbols) {
|
---|
113 | defunNode.AddDynamicSymbol(knownSymbol, selectedBody.GetDynamicSymbolArgumentCount(knownSymbol));
|
---|
114 | }
|
---|
115 | // add function arguments as known symbols to new branch
|
---|
116 | for (int i = 0; i < argumentBranches.Count; i++) {
|
---|
117 | defunNode.AddDynamicSymbol("ARG" + i);
|
---|
118 | }
|
---|
119 | // add new function name to original branch
|
---|
120 | selectedBody.AddDynamicSymbol(functionName, argumentBranches.Count);
|
---|
121 | return true;
|
---|
122 | }
|
---|
123 |
|
---|
124 | private static void DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
|
---|
125 | // remove the subtrees so that we can clone only the root node
|
---|
126 | List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees);
|
---|
127 | while (node.SubTrees.Count > 0) node.SubTrees.RemoveAt(0);
|
---|
128 | // recursively apply function for subtrees or append a argument terminal node
|
---|
129 | foreach (var subtree in subtrees) {
|
---|
130 | if (argumentBranches.Contains(subtree)) {
|
---|
131 | node.AddSubTree(MakeArgumentNode(argumentBranches.IndexOf(subtree)));
|
---|
132 | } else {
|
---|
133 | DisconnectBranches(subtree, argumentBranches);
|
---|
134 | node.AddSubTree(subtree);
|
---|
135 | }
|
---|
136 | }
|
---|
137 | }
|
---|
138 |
|
---|
139 | private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
|
---|
140 | var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode();
|
---|
141 | node.ArgumentIndex = argIndex;
|
---|
142 | return node;
|
---|
143 | }
|
---|
144 |
|
---|
145 | private static List<SymbolicExpressionTreeNode> SelectRandomArgumentBranches(SymbolicExpressionTreeNode selectedRoot,
|
---|
146 | IRandom random,
|
---|
147 | double argumentProbability,
|
---|
148 | int maxArguments) {
|
---|
149 | List<SymbolicExpressionTreeNode> argumentBranches = new List<SymbolicExpressionTreeNode>();
|
---|
150 | foreach (var subTree in selectedRoot.SubTrees) {
|
---|
151 | if (random.NextDouble() < argumentProbability) {
|
---|
152 | if (argumentBranches.Count < maxArguments)
|
---|
153 | argumentBranches.Add(subTree);
|
---|
154 | } else {
|
---|
155 | foreach (var argBranch in SelectRandomArgumentBranches(subTree, random, argumentProbability, maxArguments))
|
---|
156 | if (argumentBranches.Count < maxArguments)
|
---|
157 | argumentBranches.Add(argBranch);
|
---|
158 | }
|
---|
159 | }
|
---|
160 | return argumentBranches;
|
---|
161 | }
|
---|
162 |
|
---|
163 | private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) {
|
---|
164 | return from node in symbolicExpressionTree.IterateNodesPrefix()
|
---|
165 | where node.Symbol is Defun
|
---|
166 | select ((DefunTreeNode)node).Name;
|
---|
167 | }
|
---|
168 | }
|
---|
169 | }
|
---|