/*
Copyright 2006 by Sean Luke
Licensed under the Academic Free License version 3.0
See the file "LICENSE" for more information
*/
package ec.gp.breed;
import ec.*;
import ec.util.*;
import ec.gp.*;
/*
* MutateDemotePipeline.java
*
* Created: Wed Dec 15 21:41:30 1999
* By: Sean Luke
*/
/**
* MutateDemotePipeline works very similarly to the DemoteNode algorithm
* described in Kumar Chellapilla,
* "A Preliminary Investigation into Evolving Modular Programs without Subtree
* Crossover", GP98, and is also similar to the "insertion" operator found in
* Una-May O'Reilly's thesis,
*
* "An Analysis of Genetic Programming".
*
* MutateDemotePipeline tries picks a random tree, then picks
* randomly from all the demotable nodes in the tree, and demotes one.
* If its chosen tree has no demotable nodes, or demoting
* its chosen demotable node would make the tree too deep, it repeats
* the choose-tree-then-choose-node process. If after tries times
* it has failed to find a valid tree and demotable node, it gives up and simply
* copies the individual.
*
*
"Demotion" means to take a node n and insert a new node m
* between n and n's parent. n becomes a child of
* m; the place where it becomes a child is determined at random
* from all the type-compatible slots of m. The other child slots
* of m are filled with randomly-generated terminals.
* Chellapilla's version of the algorithm always
* places n in child slot 0 of m. Because this would be
* unneccessarily restrictive on strong typing, MutateDemotePipeline instead
* picks the slot at random from all available valid choices.
*
*
A "Demotable" node means a node which is capable of demotion
* given the existing function set. In general to demote a node foo,
* there must exist in the function set a nonterminal whose return type
* is type-compatible with the child slot foo holds in its parent;
* this nonterminal must also have a child slot which is type-compatible
* with foo's return type.
*
*
This method is very expensive in searching nodes for
* "demotability". However, if the number of types is 1 (the
* GP run is typeless) then the type-constraint-checking
* code is bypassed and the method runs a little faster.
*
Typical Number of Individuals Produced Per produce(...) call
...as many as the source produces
Number of Sources
1
Parameters
base.tries
int >= 1
(number of times to try finding valid pairs of nodes) base.maxdepth
int >= 1
(maximum valid depth of a mutated tree) base.tree.0
0 < int < (num trees in individuals), if exists
(tree chosen for mutation; if parameter doesn't exist, tree is picked at random)
Default Base
gp.breed.mutate-demote
* @author Sean Luke
* @version 1.0
*/
public class MutateDemotePipeline extends GPBreedingPipeline
{
public static final String P_MUTATEDEMOTE = "mutate-demote";
public static final String P_NUM_TRIES = "tries";
public static final String P_MAXDEPTH = "maxdepth";
public static final int NUM_SOURCES = 1;
/** The number of times the pipeline tries to build a valid mutated
tree before it gives up and just passes on the original */
int numTries;
/** The maximum depth of a mutated tree */
int maxDepth;
/** Is our tree fixed? If not, this is -1 */
int tree;
public Parameter defaultBase() { return GPBreedDefaults.base().push(P_MUTATEDEMOTE); }
public int numSources() { return NUM_SOURCES; }
public void setup(final EvolutionState state, final Parameter base)
{
super.setup(state,base);
Parameter def = defaultBase();
numTries = state.parameters.getInt(base.push(P_NUM_TRIES),
def.push(P_NUM_TRIES),1);
if (numTries == 0)
state.output.fatal("MutateDemotePipeline has an invalid number of tries (it must be >= 1).",base.push(P_NUM_TRIES),def.push(P_NUM_TRIES));
maxDepth = state.parameters.getInt(base.push(P_MAXDEPTH),
def.push(P_MAXDEPTH),1);
if (maxDepth==0)
state.output.fatal("The MutateDemotePipeline " + base + "has an invalid maximum depth (it must be >= 1).",base.push(P_MAXDEPTH),def.push(P_MAXDEPTH));
tree = TREE_UNFIXED;
if (state.parameters.exists(base.push(P_TREE).push(""+0),
def.push(P_TREE).push(""+0)))
{
tree = state.parameters.getInt(base.push(P_TREE).push(""+0),
def.push(P_TREE).push(""+0),0);
if (tree==-1)
state.output.fatal("Tree fixed value, if defined, must be >= 0");
}
}
private boolean demotable(final GPInitializer initializer,
final GPNode node, final GPFunctionSet set)
{
GPType t;
if (node.parent instanceof GPNode) // ugh, expensive
t = ((GPNode)(node.parent)).constraints(initializer).childtypes[node.argposition];
else
t = ((GPTree)(node.parent)).constraints(initializer).treetype;
// Now, out of the nonterminals compatible with that return type,
// do any also have a child compatible with that return type? This
// will be VERY expensive
for(int x=0;x 0
int demoteItem = state.random[thread].nextInt(numDemotable);
numDemotable=0;
// find it
for(int x=0;x 0
int demoteItem = state.random[thread].nextInt(numDemotable);
numDemotable=0;
// find it
// clone the node
GPNode cnode = (GPNode)(set.nonterminals[0][demoteItem].lightClone());
GPType[] chityp = cnode.constraints(((GPInitializer)state.initializer)).childtypes;
// choose a spot to hang the old parent under
int choice = state.random[thread].nextInt(cnode.children.length);
for(int z=0;z maxDepth) return false;
// checks done!
return true;
}
public int produce(final int min,
final int max,
final int start,
final int subpopulation,
final Individual[] inds,
final EvolutionState state,
final int thread)
{
// grab n individuals from our source and stick 'em right into inds.
// we'll modify them from there
int n = sources[0].produce(min,max,start,subpopulation,inds,state,thread);
// should we bother?
if (!state.random[thread].nextBoolean(likelihood))
return reproduce(n, start, subpopulation, inds, state, thread, false); // DON'T produce children from source -- we already did
GPInitializer initializer = ((GPInitializer)state.initializer);
// now let's mutate 'em
for(int q=start; q < n+start; q++)
{
GPIndividual i = (GPIndividual)inds[q];
if (tree!=TREE_UNFIXED && (tree<0 || tree >= i.trees.length))
// uh oh
state.output.fatal("MutateDemotePipeline 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");
GPIndividual j;
if (sources[0] instanceof BreedingPipeline)
// it's already a copy, so just smash the tree in
{
j=i;
}
else // need to copy it
{
j = (GPIndividual)(i.lightClone());
// Fill in various tree information that didn't get filled in there
j.trees = new GPTree[i.trees.length];
for(int x=0;x1) t = state.random[thread].nextInt(i.trees.length);
else t = 0;
else t = tree;
// is the tree demotable?
int numdemote = numDemotableNodes(initializer, j.trees[t].child,0,j.trees[t].constraints(initializer).functionset);
if (numdemote==0) continue; // uh oh, try again
// demote the node, or if we're unsuccessful, just leave it alone
pickDemotableNode(initializer, j.trees[t].child,state.random[thread].nextInt(numdemote),j.trees[t].constraints(initializer).functionset);
// does this node exceed the maximum depth limits?
if (!verifyPoint(demotableNode)) continue; // uh oh, try again
// demote it
demoteSomething(demotableNode,state,thread,j.trees[t].constraints(initializer).functionset);
j.evaluated = false;
break;
}
// add the new individual, replacing its previous source
inds[q] = j;
}
return n;
}
}
Ads help maintain this website.