/*
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.*;
/*
* MutateSwapPipeline.java
*
* Created: Wed Dec 15 21:41:30 1999
* By: Sean Luke
*/
/**
* MutateSwapPipeline works very similarly to the Swap algorithm
* described in Kumar Chellapilla,
* "A Preliminary Investigation into Evolving Modular Programs without Subtree
* Crossover", GP98.
*
* MutateSwapPipeline picks a random tree, then picks
* randomly from all the swappable nodes in the tree, and swaps two of its subtrees.
* If its chosen tree has no swappable nodes, it repeats
* the choose-tree process. If after tries times
* it has failed to find a tree with swappable nodes, it gives up and simply
* copies the individual.
*
*
"Swapping" means to take a node n, and choose two children
* nodes of n, x and y, such that x's return
* type is swap-compatible with y's slot, and y's return
* type is swap-compatible with x's slot. The subtrees rooted at
* x and y are swapped.
*
*
A "Swappable" node means a node which is capable of swapping
* given the existing function set. In general to swap a node foo,
* it must have at least two children whose return types are type-compatible
* with each other's slots in foo.
*
*
This method is very expensive in searching nodes for
* "swappability". 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.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-swap
* @author Sean Luke
* @version 1.0
*/
public class MutateSwapPipeline extends GPBreedingPipeline
{
public static final String P_MUTATESWAP = "mutate-swap";
public static final String P_NUM_TRIES = "tries";
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;
/** Is our tree fixed? If not, this is -1 */
int tree;
public Parameter defaultBase() { return GPBreedDefaults.base().push(P_MUTATESWAP); }
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("MutateSwapPipeline has an invalid number of tries (it must be >= 1).",base.push(P_NUM_TRIES),def.push(P_NUM_TRIES));
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");
}
}
/** This very expensive method (for types)
might be improved in various ways I guess. */
private boolean swappable(final GPInitializer initializer,
final GPNode node)
{
if (node.children.length < 2)
return false; // fast check
if (initializer.numAtomicTypes + initializer.numSetTypes == 1)
return true; // next fast check
// we're typed, so now we have to check our type compatibility
for(int x=0;x= 2
// pick a random first node
int x = state.random[thread].nextInt(node.children.length);
// pick a random second node
int y = state.random[thread].nextInt(node.children.length-1);
if (y >= x) y++; // adjust for first node
// swap the nodes
GPNode tmp = node.children[x];
node.children[x] = node.children[y];
node.children[y] = tmp;
node.children[x].argposition = (byte)x;
node.children[y].argposition = (byte)y;
// no need to set parent -- it's the same parent of course
}
private void _swapSomething(final GPNode node, final EvolutionState state, final int thread)
{
int numSwappable = 0;
GPInitializer initializer = ((GPInitializer)state.initializer);
for(int x=0;x 0
int swapItem = state.random[thread].nextInt(numSwappable);
numSwappable=0;
// find it
for(int x=0;x= i.trees.length))
// uh oh
state.output.fatal("MutateSwapPipeline 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 swappable?
GPInitializer initializer = ((GPInitializer)state.initializer);
int numswap = numSwappableNodes(initializer, j.trees[t].child,0);
if (numswap==0) continue; // uh oh, try again
// swap the node, or if we're unsuccessful, just leave it alone
pickSwappableNode(initializer, j.trees[t].child,state.random[thread].nextInt(numswap));
// node is now in swappableNode, swap it
swapSomething(swappableNode,state,thread);
j.evaluated = false;
break;
}
// add the new individual, replacing its previous source
inds[q] = j;
}
return n;
}
}
Ads help maintain this website.