1 | /* |
---|
2 | Copyright 2006 by Sean Luke |
---|
3 | Licensed under the Academic Free License version 3.0 |
---|
4 | See the file "LICENSE" for more information |
---|
5 | */ |
---|
6 | |
---|
7 | |
---|
8 | package ec.gp.breed; |
---|
9 | import ec.*; |
---|
10 | import ec.util.*; |
---|
11 | import ec.gp.*; |
---|
12 | |
---|
13 | /* |
---|
14 | * MutateAllNodesPipeline.java |
---|
15 | * |
---|
16 | * Created: Wed Dec 15 21:41:30 1999 |
---|
17 | * By: Sean Luke |
---|
18 | */ |
---|
19 | |
---|
20 | /** |
---|
21 | * MutateAllNodesPipeline implements the AllNodes mutation algorithm described |
---|
22 | * in Kumar Chellapilla, |
---|
23 | * "A Preliminary Investigation into Evolving Modular Programs without Subtree |
---|
24 | * Crossover", GP98. |
---|
25 | * |
---|
26 | * <p>MutateAllNodesPipeline chooses a subtree and for each node <i>n</i> |
---|
27 | * in that subtree, it replaces <i>n</i> with a randomly-picked node of the same |
---|
28 | * arity and type constraints. Thus the original topological structure is |
---|
29 | * the same but the nodes are different. |
---|
30 | * |
---|
31 | |
---|
32 | <p><b>Typical Number of Individuals Produced Per <tt>produce(...)</tt> call</b><br> |
---|
33 | ...as many as the source produces |
---|
34 | |
---|
35 | <p><b>Number of Sources</b><br> |
---|
36 | 1 |
---|
37 | |
---|
38 | <p><b>Parameters</b><br> |
---|
39 | <table> |
---|
40 | <tr><td valign=top><i>base</i>.<tt>ns</tt>.0<br> |
---|
41 | <font size=-1>classname, inherits and != GPNodeSelector</font></td> |
---|
42 | <td valign=top>(GPNodeSelector for tree)</td></tr> |
---|
43 | |
---|
44 | <tr><td valign=top><i>base</i>.<tt>tree.0</tt><br> |
---|
45 | <font size=-1>0 < int < (num trees in individuals), if exists</font></td> |
---|
46 | <td valign=top>(tree chosen for mutation; if parameter doesn't exist, tree is picked at random)</td></tr> |
---|
47 | </table> |
---|
48 | |
---|
49 | <p><b>Default Base</b><br> |
---|
50 | gp.breed.mutate-all-nodes |
---|
51 | |
---|
52 | <p><b>Parameter bases</b><br> |
---|
53 | <table> |
---|
54 | <tr><td valign=top><i>base</i>.<tt>ns</tt><br> |
---|
55 | <td>The GPNodeSelector selector</td></tr> |
---|
56 | </table> |
---|
57 | |
---|
58 | * @author Sean Luke |
---|
59 | * @version 1.0 |
---|
60 | */ |
---|
61 | |
---|
62 | public class MutateAllNodesPipeline extends GPBreedingPipeline |
---|
63 | { |
---|
64 | public static final String P_MUTATEALLNODES = "mutate-all-nodes"; |
---|
65 | public static final int NUM_SOURCES = 1; |
---|
66 | |
---|
67 | /** How the pipeline chooses a subtree to mutate */ |
---|
68 | public GPNodeSelector nodeselect; |
---|
69 | |
---|
70 | /** Is our tree fixed? If not, this is -1 */ |
---|
71 | int tree; |
---|
72 | |
---|
73 | public Parameter defaultBase() |
---|
74 | { |
---|
75 | return GPBreedDefaults.base().push(P_MUTATEALLNODES); |
---|
76 | } |
---|
77 | |
---|
78 | public int numSources() { return NUM_SOURCES; } |
---|
79 | |
---|
80 | public Object clone() |
---|
81 | { |
---|
82 | MutateAllNodesPipeline c = (MutateAllNodesPipeline)(super.clone()); |
---|
83 | |
---|
84 | // deep-cloned stuff |
---|
85 | c.nodeselect = (GPNodeSelector)(nodeselect.clone()); |
---|
86 | return c; |
---|
87 | } |
---|
88 | |
---|
89 | |
---|
90 | public void setup(final EvolutionState state, final Parameter base) |
---|
91 | { |
---|
92 | super.setup(state,base); |
---|
93 | |
---|
94 | Parameter def = defaultBase(); |
---|
95 | |
---|
96 | Parameter p = base.push(P_NODESELECTOR).push(""+0); |
---|
97 | nodeselect = (GPNodeSelector) |
---|
98 | (state.parameters.getInstanceForParameter( |
---|
99 | p,def.push(P_NODESELECTOR).push(""+0), |
---|
100 | GPNodeSelector.class)); |
---|
101 | nodeselect.setup(state,p); |
---|
102 | |
---|
103 | tree = TREE_UNFIXED; |
---|
104 | if (state.parameters.exists(base.push(P_TREE).push(""+0), |
---|
105 | def.push(P_TREE).push(""+0))) |
---|
106 | { |
---|
107 | tree = state.parameters.getInt(base.push(P_TREE).push(""+0), |
---|
108 | def.push(P_TREE).push(""+0),0); |
---|
109 | if (tree==-1) |
---|
110 | state.output.fatal("Tree fixed value, if defined, must be >= 0"); |
---|
111 | } |
---|
112 | } |
---|
113 | |
---|
114 | |
---|
115 | /** Returns a node which is swap-compatible with returntype, and whose arguments are swap-compatible with the current children of original. You need to clone this node. */ |
---|
116 | |
---|
117 | private GPNode pickCompatibleNode( |
---|
118 | final GPNode original, final GPFunctionSet set, |
---|
119 | final EvolutionState state, final GPType returntype, final int thread) |
---|
120 | { |
---|
121 | // an expensive procedure: we will linearly search for a valid node |
---|
122 | int numValidNodes = 0; |
---|
123 | |
---|
124 | int type = returntype.type; |
---|
125 | GPInitializer initializer = ((GPInitializer)state.initializer); |
---|
126 | int len = original.constraints(initializer).childtypes.length; |
---|
127 | boolean failed; |
---|
128 | |
---|
129 | if (initializer.numAtomicTypes + |
---|
130 | initializer.numSetTypes == 1) // easy |
---|
131 | numValidNodes = set.nodesByArity[type][len].length; |
---|
132 | else for(int x=0;x<set.nodesByArity[type][len].length;x++) // ugh, the hard way -- nodes swap-compatible with type, and of arity len |
---|
133 | { |
---|
134 | failed = false; |
---|
135 | for(int y=0;y<set.nodesByArity[type][len][x].constraints(initializer).childtypes.length;y++) |
---|
136 | if (!set.nodesByArity[type][len][x].constraints(initializer). |
---|
137 | childtypes[y].compatibleWith(initializer,original.children[y]. |
---|
138 | constraints(initializer).returntype)) |
---|
139 | { failed = true; break; } |
---|
140 | if (!failed) numValidNodes++; |
---|
141 | } |
---|
142 | |
---|
143 | // we must have at least success -- the node itself. Otherwise we're |
---|
144 | // in deep doo-doo. |
---|
145 | |
---|
146 | // now pick a random node number |
---|
147 | int nodenum = state.random[thread].nextInt(numValidNodes); |
---|
148 | |
---|
149 | // find and return that node |
---|
150 | int prosnode = 0; |
---|
151 | |
---|
152 | if (numValidNodes == set.nodesByArity[type][len].length) // easy |
---|
153 | return set.nodesByArity[type][len][nodenum]; |
---|
154 | else for(int x=0;x<set.nodesByArity[type][len].length;x++) // ugh, the hard way -- nodes swap-compatible with type, and of arity len |
---|
155 | { |
---|
156 | failed = false; |
---|
157 | for(int y=0;y<set.nodesByArity[type][len][x].constraints(initializer).childtypes.length;y++) |
---|
158 | if (!set.nodesByArity[type][len][x].constraints(initializer). |
---|
159 | childtypes[y].compatibleWith(initializer,original.children[y]. |
---|
160 | constraints(initializer).returntype)) |
---|
161 | { failed = true; break; } |
---|
162 | if (!failed) |
---|
163 | { |
---|
164 | if (prosnode == nodenum) // got it! |
---|
165 | return set.nodesByArity[type][len][x]; |
---|
166 | prosnode++; |
---|
167 | } |
---|
168 | } |
---|
169 | |
---|
170 | // should never be able to get here |
---|
171 | throw new InternalError(); // whoops! |
---|
172 | |
---|
173 | } |
---|
174 | |
---|
175 | |
---|
176 | /** Returns a brand-new tree which is swap-compatible with returntype, created by making nodes "compatible" with the equivalent nodes in the tree rooted at original. You need to set the parent and argumentposition of the root yourself.*/ |
---|
177 | |
---|
178 | private GPNode generateCompatibleTree(final GPNode original, final GPFunctionSet set, final EvolutionState state, final GPType returntype, final int thread) |
---|
179 | { |
---|
180 | // pick a new node and clone it |
---|
181 | GPNode node = (GPNode)(pickCompatibleNode(original,set,state,returntype,thread).lightClone()); |
---|
182 | |
---|
183 | // reset it |
---|
184 | node.resetNode(state,thread); |
---|
185 | |
---|
186 | // fill in its children |
---|
187 | GPInitializer initializer = ((GPInitializer)state.initializer); |
---|
188 | for (int x=0;x<node.children.length;x++) |
---|
189 | { |
---|
190 | node.children[x] = generateCompatibleTree(original.children[x],set,state,original.constraints(initializer).childtypes[x],thread); |
---|
191 | node.children[x].parent = node; |
---|
192 | node.children[x].argposition = (byte)x; |
---|
193 | } |
---|
194 | return node; |
---|
195 | } |
---|
196 | |
---|
197 | |
---|
198 | |
---|
199 | public int produce(final int min, |
---|
200 | final int max, |
---|
201 | final int start, |
---|
202 | final int subpopulation, |
---|
203 | final Individual[] inds, |
---|
204 | final EvolutionState state, |
---|
205 | final int thread) |
---|
206 | { |
---|
207 | // grab n individuals from our source and stick 'em right into inds. |
---|
208 | // we'll modify them from there |
---|
209 | int n = sources[0].produce(min,max,start,subpopulation,inds,state,thread); |
---|
210 | |
---|
211 | // should we bother? |
---|
212 | if (!state.random[thread].nextBoolean(likelihood)) |
---|
213 | return reproduce(n, start, subpopulation, inds, state, thread, false); // DON'T produce children from source -- we already did |
---|
214 | |
---|
215 | |
---|
216 | |
---|
217 | |
---|
218 | GPInitializer initializer = ((GPInitializer)state.initializer); |
---|
219 | |
---|
220 | // now let's mutate 'em |
---|
221 | for(int q=start; q < n+start; q++) |
---|
222 | { |
---|
223 | GPIndividual i = (GPIndividual)inds[q]; |
---|
224 | |
---|
225 | if (tree!=TREE_UNFIXED && (tree<0 || tree >= i.trees.length)) |
---|
226 | // uh oh |
---|
227 | state.output.fatal("MutateAllNodesPipeline attempted to fix tree.0 to a value which was out of bounds of the array of the individual's trees. Check the pipeline's fixed tree values -- they may be negative or greater than the number of trees in an individual"); |
---|
228 | |
---|
229 | int t; |
---|
230 | // pick random tree |
---|
231 | if (tree==TREE_UNFIXED) |
---|
232 | if (i.trees.length>1) t = state.random[thread].nextInt(i.trees.length); |
---|
233 | else t = 0; |
---|
234 | else t = tree; |
---|
235 | |
---|
236 | // prepare the nodeselector |
---|
237 | nodeselect.reset(); |
---|
238 | |
---|
239 | // pick a node |
---|
240 | |
---|
241 | GPNode p1=null; // the node we pick |
---|
242 | GPNode p2=null; |
---|
243 | |
---|
244 | // pick a node in individual 1 |
---|
245 | p1 = nodeselect.pickNode(state,subpopulation,thread,i,i.trees[t]); |
---|
246 | |
---|
247 | // generate a tree with a new root but the same children, |
---|
248 | // which we will replace p1 with |
---|
249 | |
---|
250 | GPType type; |
---|
251 | type = p1.parentType(initializer); |
---|
252 | |
---|
253 | p2 = generateCompatibleTree(p1,i.trees[t].constraints(initializer).functionset,state,type,thread); |
---|
254 | // we'll need to set p2.argposition and p2.parent further down |
---|
255 | |
---|
256 | |
---|
257 | GPIndividual j; |
---|
258 | |
---|
259 | if (sources[0] instanceof BreedingPipeline) |
---|
260 | // it's already a copy, so just smash the tree in |
---|
261 | { |
---|
262 | j=i; |
---|
263 | p2.parent = p1.parent; |
---|
264 | p2.argposition = p1.argposition; |
---|
265 | if (p2.parent instanceof GPNode) |
---|
266 | ((GPNode)(p2.parent)).children[p2.argposition] = p2; |
---|
267 | else ((GPTree)(p2.parent)).child = p2; |
---|
268 | j.evaluated = false; // we've modified it |
---|
269 | } |
---|
270 | else // need to copy it in |
---|
271 | { |
---|
272 | j = (GPIndividual)(i.lightClone()); |
---|
273 | |
---|
274 | // Fill in various tree information that didn't get filled in there |
---|
275 | j.trees = new GPTree[i.trees.length]; |
---|
276 | |
---|
277 | for(int x=0;x<j.trees.length;x++) |
---|
278 | { |
---|
279 | if (x==t) // we've got a tree with a kicking cross position! |
---|
280 | { |
---|
281 | j.trees[x] = (GPTree)(i.trees[x].lightClone()); |
---|
282 | j.trees[x].owner = j; |
---|
283 | j.trees[x].child = i.trees[x].child.cloneReplacingNoSubclone(p2,p1); |
---|
284 | j.trees[x].child.parent = j.trees[x]; |
---|
285 | j.trees[x].child.argposition = 0; |
---|
286 | j.evaluated = false; |
---|
287 | } // it's changed |
---|
288 | else |
---|
289 | { |
---|
290 | j.trees[x] = (GPTree)(i.trees[x].lightClone()); |
---|
291 | j.trees[x].owner = j; |
---|
292 | j.trees[x].child = (GPNode)(i.trees[x].child.clone()); |
---|
293 | j.trees[x].child.parent = j.trees[x]; |
---|
294 | j.trees[x].child.argposition = 0; |
---|
295 | } |
---|
296 | } |
---|
297 | } |
---|
298 | |
---|
299 | // add the new individual, replacing its previous source |
---|
300 | inds[q] = j; |
---|
301 | } |
---|
302 | return n; |
---|
303 | } |
---|
304 | } |
---|