/*
Copyright 2006 by Sean Luke
Licensed under the Academic Free License version 3.0
See the file "LICENSE" for more information
*/
package ec.gp.koza;
import ec.*;
import ec.util.*;
import ec.gp.*;
/*
* CrossoverPipeline.java
*
* Created: Mon Aug 30 19:15:21 1999
* By: Sean Luke
*/
/**
* CrossoverPipeline is a GPBreedingPipeline which performs a strongly-typed
* version of
* Koza-style "Subtree Crossover". Two individuals are selected,
* then a single tree is chosen in each such that the two trees
* have the same GPTreeConstraints. Then a random node is chosen
* in each tree such that each node's return type is type-compatible
* with the argument type of the slot in the parent which contains
* the other node.
* If by swapping subtrees at these nodes the two trees will not
* violate maximum depth constraints, then the trees perform the
* swap, otherwise, they repeat the hunt for random nodes.
*
* The pipeline tries at most tries times to a pair
* of random nodes BOTH with valid swap constraints. If it
* cannot find any such pairs after tries times, it
* uses the pair of its last attempt. If either of the nodes in the pair
* is valid, that node gets substituted with the other node. Otherwise
* an individual invalid node isn't changed at all (it's "reproduced").
*
*
Compatibility with constraints.
* Since Koza-I/II only tries 1 time, and then follows this policy, this is
* compatible with Koza. lil-gp either tries 1 time, or tries forever.
* Either way, this is compatible with lil-gp. My hacked
* lil-gp kernel
* either tries 1 time, n times, or forever. This is compatible
* as well.
*
*
This pipeline typically produces up to 2 new individuals (the two newly-
* swapped individuals) per produce(...) call. If the system only
* needs a single individual, the pipeline will throw one of the
* new individuals away. The user can also have the pipeline always
* throw away the second new individual instead of adding it to the population.
* In this case, the pipeline will only typically
* produce 1 new individual per produce(...) call.
Typical Number of Individuals Produced Per produce(...) call
2 * minimum typical number of individuals produced by each source, unless tossSecondParent
is set, in which case it's simply the minimum typical number.
Number of Sources
2
Parameters
base.tries
int >= 1
(number of times to try finding valid pairs of nodes) base.maxdepth
int >= 1
(maximum valid depth of a crossed-over subtree) base.maxsize
int >= 1
(maximum valid size, in nodes, of a crossed-over subtree) base.tree.0
0 < int < (num trees in individuals), if exists
(first tree for the crossover; if parameter doesn't exist, tree is picked at random) base.tree.1
0 < int < (num trees in individuals), if exists
(second tree for the crossover; if parameter doesn't exist, tree is picked at random. This tree must have the same GPTreeConstraints as tree.0, if tree.0 is defined.) base.ns.n
classname, inherits and != GPNodeSelector,
or String same
(GPNodeSelector for parent n (n is 0 or 1) If, for ns.1 the value is same, then ns.1 a copy of whatever ns.0 is. Note that the default version has no n) base.toss
bool = true or false (default)/td>
(after crossing over with the first new individual, should its second sibling individual be thrown away instead of adding it to the population?)
Default Base
gp.koza.xover
Parameter bases
base.ns.n
nodeselectn (n is 0 or 1)
*
* @author Sean Luke
* @version 1.0
*/
public class CrossoverPipeline extends GPBreedingPipeline
{
private static final long serialVersionUID = 1;
public static final String P_NUM_TRIES = "tries";
public static final String P_MAXDEPTH = "maxdepth";
public static final String P_MAXSIZE = "maxsize";
public static final String P_CROSSOVER = "xover";
public static final String P_TOSS = "toss";
public static final int INDS_PRODUCED = 2;
public static final int NUM_SOURCES = 2;
public static final int NO_SIZE_LIMIT = -1;
/** How the pipeline selects a node from individual 1 */
public GPNodeSelector nodeselect1;
/** How the pipeline selects a node from individual 2 */
public GPNodeSelector nodeselect2;
/** Is the first tree fixed? If not, this is -1 */
public int tree1;
/** Is the second tree fixed? If not, this is -1 */
public int tree2;
/** How many times the pipeline attempts to pick nodes until it gives up. */
public int numTries;
/** The deepest tree the pipeline is allowed to form. Single terminal trees are depth 1. */
public int maxDepth;
/** The largest tree (measured as a nodecount) the pipeline is allowed to form. */
public int maxSize;
/** Should the pipeline discard the second parent after crossing over? */
public boolean tossSecondParent;
/** Temporary holding place for parents */
public GPIndividual parents[];
public CrossoverPipeline() { parents = new GPIndividual[2]; }
public Parameter defaultBase() { return GPKozaDefaults.base().push(P_CROSSOVER); }
public int numSources() { return NUM_SOURCES; }
public Object clone()
{
CrossoverPipeline c = (CrossoverPipeline)(super.clone());
// deep-cloned stuff
c.nodeselect1 = (GPNodeSelector)(nodeselect1.clone());
c.nodeselect2 = (GPNodeSelector)(nodeselect2.clone());
c.parents = (GPIndividual[]) parents.clone();
return c;
}
public void setup(final EvolutionState state, final Parameter base)
{
super.setup(state,base);
Parameter def = defaultBase();
Parameter p = base.push(P_NODESELECTOR).push("0");
Parameter d = def.push(P_NODESELECTOR).push("0");
nodeselect1 = (GPNodeSelector)
(state.parameters.getInstanceForParameter(
p,d, GPNodeSelector.class));
nodeselect1.setup(state,p);
p = base.push(P_NODESELECTOR).push("1");
d = def.push(P_NODESELECTOR).push("1");
if (state.parameters.exists(p,d) &&
state.parameters.getString(p,d).equals(V_SAME))
// can't just copy it this time; the selectors
// use internal caches. So we have to clone it no matter what
nodeselect2 = (GPNodeSelector)(nodeselect1.clone());
else
{
nodeselect2 = (GPNodeSelector)
(state.parameters.getInstanceForParameter(
p,d, GPNodeSelector.class));
nodeselect2.setup(state,p);
}
numTries = state.parameters.getInt(base.push(P_NUM_TRIES),
def.push(P_NUM_TRIES),1);
if (numTries == 0)
state.output.fatal("GPCrossover Pipeline 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("GPCrossover Pipeline has an invalid maximum depth (it must be >= 1).",base.push(P_MAXDEPTH),def.push(P_MAXDEPTH));
maxSize = NO_SIZE_LIMIT;
if (state.parameters.exists(base.push(P_MAXSIZE), def.push(P_MAXSIZE)))
{
maxSize = state.parameters.getInt(base.push(P_MAXSIZE), def.push(P_MAXSIZE), 1);
if (maxSize < 1)
state.output.fatal("Maximum tree size, if defined, must be >= 1");
}
tree1 = TREE_UNFIXED;
if (state.parameters.exists(base.push(P_TREE).push(""+0),
def.push(P_TREE).push(""+0)))
{
tree1 = state.parameters.getInt(base.push(P_TREE).push(""+0),
def.push(P_TREE).push(""+0),0);
if (tree1==-1)
state.output.fatal("Tree fixed value, if defined, must be >= 0");
}
tree2 = TREE_UNFIXED;
if (state.parameters.exists(base.push(P_TREE).push(""+1),
def.push(P_TREE).push(""+1)))
{
tree2 = state.parameters.getInt(base.push(P_TREE).push(""+1),
def.push(P_TREE).push(""+1),0);
if (tree2==-1)
state.output.fatal("Tree fixed value, if defined, must be >= 0");
}
tossSecondParent = state.parameters.getBoolean(base.push(P_TOSS),
def.push(P_TOSS),false);
}
/** Returns 2 * minimum number of typical individuals produced by any sources, else
1* minimum number if tossSecondParent is true. */
public int typicalIndsProduced()
{
return (tossSecondParent? minChildProduction(): minChildProduction()*2);
}
/** Returns true if inner1 can feasibly be swapped into inner2's position. */
public boolean verifyPoints(final GPInitializer initializer,
final GPNode inner1, final GPNode inner2)
{
// first check to see if inner1 is swap-compatible with inner2
// on a type basis
if (!inner1.swapCompatibleWith(initializer, inner2)) return false;
// next check to see if inner1 can fit in inner2's spot
if (inner1.depth()+inner2.atDepth() > maxDepth) return false;
// check for size
// NOTE: this is done twice, which is more costly than it should be. But
// on the other hand it allows us to toss a child without testing both times
// and it's simpler to have it all here in the verifyPoints code.
if (maxSize != NO_SIZE_LIMIT)
{
// first easy check
int inner1size = inner1.numNodes(GPNode.NODESEARCH_ALL);
int inner2size = inner2.numNodes(GPNode.NODESEARCH_ALL);
if (inner1size > inner2size) // need to test further
{
// let's keep on going for the more complex test
GPNode root2 = ((GPTree)(inner2.rootParent())).child;
int root2size = root2.numNodes(GPNode.NODESEARCH_ALL);
if (root2size - inner2size + inner1size > maxSize) // take root2, remove inner2 and swap in inner1. Is it still small enough?
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)
{
// how many individuals should we make?
int n = typicalIndsProduced();
if (n < min) n = min;
if (n > max) n = max;
// should we bother?
if (!state.random[thread].nextBoolean(likelihood))
return reproduce(n, start, subpopulation, inds, state, thread, true); // DO produce children from source -- we've not done so already
GPInitializer initializer = ((GPInitializer)state.initializer);
for(int q=start;q= parents[0].trees.length))
// uh oh
state.output.fatal("GP Crossover Pipeline 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");
if (tree2!=TREE_UNFIXED && (tree2<0 || tree2 >= parents[1].trees.length))
// uh oh
state.output.fatal("GP Crossover Pipeline attempted to fix tree.1 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");
int t1=0; int t2=0;
if (tree1==TREE_UNFIXED || tree2==TREE_UNFIXED)
{
do
// pick random trees -- their GPTreeConstraints must be the same
{
if (tree1==TREE_UNFIXED)
if (parents[0].trees.length > 1)
t1 = state.random[thread].nextInt(parents[0].trees.length);
else t1 = 0;
else t1 = tree1;
if (tree2==TREE_UNFIXED)
if (parents[1].trees.length>1)
t2 = state.random[thread].nextInt(parents[1].trees.length);
else t2 = 0;
else t2 = tree2;
} while (parents[0].trees[t1].constraints(initializer) != parents[1].trees[t2].constraints(initializer));
}
else
{
t1 = tree1;
t2 = tree2;
// make sure the constraints are okay
if (parents[0].trees[t1].constraints(initializer)
!= parents[1].trees[t2].constraints(initializer)) // uh oh
state.output.fatal("GP Crossover Pipeline's two tree choices are both specified by the user -- but their GPTreeConstraints are not the same");
}
// validity results...
boolean res1 = false;
boolean res2 = false;
// prepare the nodeselectors
nodeselect1.reset();
nodeselect2.reset();
// pick some nodes
GPNode p1=null;
GPNode p2=null;
for(int x=0;x=2 && !tossSecondParent) j2 = (GPIndividual)(parents[1].lightClone());
// Fill in various tree information that didn't get filled in there
j1.trees = new GPTree[parents[0].trees.length];
if (n-(q-start)>=2 && !tossSecondParent) j2.trees = new GPTree[parents[1].trees.length];
// at this point, p1 or p2, or both, may be null.
// If not, swap one in. Else just copy the parent.
for(int x=0;x=2 && !tossSecondParent)
for(int x=0;x
Ads help maintain this website.