Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OKBJavaConnector/ECJClient/src/ec/gp/breed/MutateAllNodesPipeline.java @ 11194

Last change on this file since 11194 was 6152, checked in by bfarka, 14 years ago

added ecj and custom statistics to communicate with the okb services #1441

File size: 11.2 KB
Line 
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
8package ec.gp.breed;
9import ec.*;
10import ec.util.*;
11import 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 &lt; int &lt; (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
62public 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    }
Note: See TracBrowser for help on using the repository browser.