/*
Copyright 2012 by Uday Kamath, Sean Luke, and George Mason University
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.*;
import ec.gp.koza.*;
import java.util.*;
/**
* SizeFairCrossover works similarly to one written in the paper
* "Size Fair and Homologous Tree Genetic Programming Crossovers" by Langdon (1998).
* SizeFairCrossover tries tries times to find a tree
* that has at least one fair size node based on size fair or homologous
* implementation. If it cannot
* find a valid tree in tries times, it gives up and simply
* copies the individual.
*
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.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?) base.homologous
bool = true or false (default)/td>
(Is the implementation homologous (as opposed to size-fair)?)
Default Base
gp.breed.size-fair
Parameter bases
base.ns.n
nodeselectn (n is 0 or 1)
* @author Uday Kamath and Sean Luke
* @version 1.0
*/
public class SizeFairCrossoverPipeline 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_SIZEFAIR = "size-fair";
public static final String P_TOSS = "toss";
public static final String P_HOMOLOGOUS = "homologous";
public static final int INDS_PRODUCED = 2;
public static final int NUM_SOURCES = 2;
/** 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;
/** Should the pipeline discard the second parent after crossing over? */
public boolean tossSecondParent;
/** Temporary holding place for parents */
public GPIndividual parents[];
public boolean homologous;
public SizeFairCrossoverPipeline()
{
parents = new GPIndividual[2];
}
public Parameter defaultBase()
{
return GPBreedDefaults.base().push(P_SIZEFAIR);
}
public int numSources()
{
return NUM_SOURCES;
}
public Object clone()
{
SizeFairCrossoverPipeline c = (SizeFairCrossoverPipeline) (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));
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);
if(state.parameters.exists(base.push(P_HOMOLOGOUS), null))
{
//get the parameter
homologous = state.parameters.getBoolean(base.push(P_HOMOLOGOUS), null, 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;
// 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 < n + start; /* no increment */) // keep on going until we're filled up
{
// grab two individuals from our sources
if (sources[0] == sources[1]) // grab from the same source
sources[0].produce(2, 2, 0, subpopulation, parents, state, thread);
else // grab from different sources
{
sources[0].produce(1, 1, 0, subpopulation, parents, state, thread);
sources[1].produce(1, 1, 1, subpopulation, parents, state, thread);
}
// at this point, parents[] contains our two selected individuals
// are our tree values valid?
if (tree1 != TREE_UNFIXED && (tree1 < 0 || tree1 >= 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");
}
boolean res1 = false;
boolean res2 = false;
GPTree tree2 = parents[1].trees[t2];
// pick some nodes
GPNode p1 = null;
GPNode p2 = null;
// lets walk on parent2 all nodes to get subtrees for each node, doing it once for O(N) and not O(N^2)
// because depth etc are computed and not stored
ArrayList nodeToSubtrees = new ArrayList();
// also HashMap for size to List() of nodes in that size for O(1) lookup
HashMap sizeToNodes = new HashMap();
this.traverseTreeForDepth(tree2.child, nodeToSubtrees, sizeToNodes);
// sort the ArrayList with comparator that sorts by subtrees
Collections.sort(nodeToSubtrees, new Comparator()
{
public int compare(Object o1, Object o2)
{
NodeInfo node1 = (NodeInfo)o1;
NodeInfo node2 = (NodeInfo)o2;
int comparison = 0;
if (node1.numberOfSubTreesBeneath > node2.numberOfSubTreesBeneath)
comparison = 1;
else if (node1.numberOfSubTreesBeneath < node2.numberOfSubTreesBeneath)
comparison = -1;
else if (node1.numberOfSubTreesBeneath == node2.numberOfSubTreesBeneath)
comparison = 0;
return comparison;
}
});
for (int x = 0; x < numTries; x++)
{
// pick a node in individual 1
p1 = nodeselect1.pickNode(state, subpopulation, thread, parents[0], parents[0].trees[t1]);
// now lets find "similar" in parent 2
p2 = findFairSizeNode(nodeToSubtrees, sizeToNodes, p1, tree2, state, thread);
// check for depth and swap-compatibility limits
res1 = verifyPoints(initializer, p2, p1); // p2 can fill p1's spot -- order is important!
if (n - (q - start) < 2 || tossSecondParent)
res2 = true;
else
res2 = verifyPoints(initializer, p1, p2); // p1 can fill p2's spot -- order is important!
// did we get something that had both nodes verified?
// we reject if EITHER of them is invalid. This is what lil-gp
// does.
// Koza only has numTries set to 1, so it's compatible as well.
if (res1 && res2)
break;
}
// at this point, res1 AND res2 are valid, OR
// either res1 OR res2 is valid and we ran out of tries, OR
// neither res1 nor res2 is valid and we rand out of tries.
// So now we will transfer to a tree which has res1 or res2
// valid, otherwise it'll just get replicated. This is
// compatible with both Koza and lil-gp.
// at this point I could check to see if my sources were breeding
// pipelines -- but I'm too lazy to write that code (it's a little
// complicated) to just swap one individual over or both over,
// -- it might still entail some copying. Perhaps in the future.
// It would make things faster perhaps, not requiring all that
// cloning.
// Create some new individuals based on the old ones -- since
// GPTree doesn't deep-clone, this should be just fine. Perhaps we
// should change this to proto off of the main species prototype,
// but
// we have to then copy so much stuff over; it's not worth it.
GPIndividual j1 = (GPIndividual) (parents[0].lightClone());
GPIndividual j2 = null;
if (n - (q - start) >= 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 < j1.trees.length; x++)
{
if (x == t1 && res1) // we've got a tree with a kicking cross
// position!
{
j1.trees[x] = (GPTree) (parents[0].trees[x].lightClone());
j1.trees[x].owner = j1;
j1.trees[x].child = parents[0].trees[x].child.cloneReplacing(p2, p1);
j1.trees[x].child.parent = j1.trees[x];
j1.trees[x].child.argposition = 0;
j1.evaluated = false;
} // it's changed
else
{
j1.trees[x] = (GPTree) (parents[0].trees[x].lightClone());
j1.trees[x].owner = j1;
j1.trees[x].child = (GPNode) (parents[0].trees[x].child.clone());
j1.trees[x].child.parent = j1.trees[x];
j1.trees[x].child.argposition = 0;
}
}
if (n - (q - start) >= 2 && !tossSecondParent)
for (int x = 0; x < j2.trees.length; x++)
{
if (x == t2 && res2) // we've got a tree with a kicking
// cross position!
{
j2.trees[x] = (GPTree) (parents[1].trees[x].lightClone());
j2.trees[x].owner = j2;
j2.trees[x].child = parents[1].trees[x].child.cloneReplacing(p1, p2);
j2.trees[x].child.parent = j2.trees[x];
j2.trees[x].child.argposition = 0;
j2.evaluated = false;
} // it's changed
else
{
j2.trees[x] = (GPTree) (parents[1].trees[x].lightClone());
j2.trees[x].owner = j2;
j2.trees[x].child = (GPNode) (parents[1].trees[x].child.clone());
j2.trees[x].child.parent = j2.trees[x];
j2.trees[x].child.argposition = 0;
}
}
// add the individuals to the population
inds[q] = j1;
q++;
if (q < n + start && !tossSecondParent)
{
inds[q] = j2;
q++;
}
}
return n;
}
/**
* This method finds a node using the logic given in the langdon paper.
* @param nodeToSubtrees For Tree of Parent2 all precomputed stats about depth,subtrees etc
* @param sizeToNodes Quick lookup for LinkedList of size to Nodes
* @param parent1SelectedNode Node selected in parent1
* @param tree2 Tree of parent2
* @param state Evolution State passed for getting access to Random Object of MersenneTwiser
* @param thread thread number
*/
protected GPNode findFairSizeNode(ArrayList nodeToSubtrees,
HashMap sizeToNodes,
GPNode parent1SelectedNode,
GPTree tree2,
EvolutionState state,
int thread)
{
GPNode selectedNode = null;
// get the size of subtrees of parent1
int parent1SubTrees = parent1SelectedNode.numNodes(GPNode.NODESEARCH_NONTERMINALS);
// the maximum length in mate we are looking for
int maxmatesublen = (parent1SubTrees == 0) ? 0 : 2 * parent1SubTrees + 1;
// lets see if for all lengths we have trees corresponding
boolean[] mateSizeAvailable = new boolean[maxmatesublen + 1];
// initialize the array to false
for (int i = 0; i < maxmatesublen; i++)
mateSizeAvailable[i] = false;
// check for ones we have
for (int i = 0; i < nodeToSubtrees.size(); i++)
{
NodeInfo nodeInfo = (NodeInfo)nodeToSubtrees.get(i);
// get the length of trees
int subtree = nodeInfo.numberOfSubTreesBeneath;
if (subtree <= maxmatesublen)
mateSizeAvailable[subtree] = true;
}
// choose matesublen so mean size change=0 if possible
int countOfPositives = 0;
int countOfNegatives = 0;
int sumOfPositives = 0;
int sumOfNegatives = 0;
int l;
for (l = 1; l < parent1SubTrees; l++)
if (mateSizeAvailable[l])
{
countOfNegatives++;
sumOfNegatives += parent1SubTrees - l;
}
for (l = parent1SubTrees + 1; l <= maxmatesublen; l++)
if (mateSizeAvailable[l])
{
countOfPositives++;
sumOfPositives += l - parent1SubTrees;
}
// if they are missing use the same
int mateSublengthSelected = 0;
if (sumOfPositives == 0 || sumOfNegatives == 0)
{
//if so then check if mate has the length and use that
if(mateSizeAvailable[parent1SubTrees])
{
mateSublengthSelected = parent1SubTrees;
}
//else we go with zero
}
else
{
// probability of same is dependent on do we find same sub trees
// else 0.0
double pzero = (mateSizeAvailable[parent1SubTrees]) ? 1.0 / parent1SubTrees : 0.0;
// positive probability
double ppositive = (1.0 - pzero) / (countOfPositives + ((double) (countOfNegatives * sumOfPositives) / (sumOfNegatives)));
// negative probability
double pnegative = (1.0 - pzero) / (countOfNegatives + ((double) (countOfPositives * sumOfNegatives) / (sumOfPositives)));
// total probability, just for making sure math is right ;-)
double total = countOfNegatives * pnegative + pzero + countOfPositives * ppositive;
// putting an assert for floating point calculations, similar to what langdon does
// assert(total<1.01&&total>.99);
// now create a Roulette Wheel
RouletteWheelSelector wheel = new RouletteWheelSelector(maxmatesublen);
// add probabilities to the wheel
// all below the length of parent node get pnegative
// all above get ppositive and one on node gets pzero
for (l = 1; l < parent1SubTrees; l++)
if (mateSizeAvailable[l])
wheel.add(pnegative, l);
if (mateSizeAvailable[parent1SubTrees])
wheel.add(pzero, parent1SubTrees);
for (l = parent1SubTrees + 1; l <= maxmatesublen; l++)
if (mateSizeAvailable[l])
wheel.add(ppositive, l);
// spin the wheel
mateSublengthSelected = wheel.roulette(state, thread);
}
// now we have length chosen, but there can be many nodes with that
//
LinkedList listOfNodes = (LinkedList)(sizeToNodes.get(Integer.valueOf(mateSublengthSelected)));
if(listOfNodes == null)
{
state.output. fatal("In SizeFairCrossoverPipeline, nodes for tree length " + mateSublengthSelected + " is null, indicates some serious error");
}
// in size fair we choose the elements at random for given length
int chosenNode = 0;
// if using fair size get random from the list
if(!homologous)
{
chosenNode = state.random[thread].nextInt(listOfNodes.size());
}
// if homologous
else
{
if(listOfNodes.size() > 1)
{
GPInitializer initializer = ((GPInitializer) state.initializer);
int currentMinDistance = Integer.MAX_VALUE;
for(int i =0 ; i< listOfNodes.size(); i++)
{
// get the GP node
GPNode selectedMateNode = ((NodeInfo)listOfNodes.get(i)).node;
// now lets traverse selected and parent 1 to see divergence
GPNode currentMateNode = selectedMateNode;
GPNode currentParent1Node = parent1SelectedNode;
// found a match?
boolean foundAMatchInAncestor = false;
int distance =0;
while(currentMateNode.parent != null &&
currentMateNode.parent instanceof GPNode &&
currentParent1Node.parent != null &&
currentParent1Node.parent instanceof GPNode &&
!foundAMatchInAncestor)
{
GPNode parent1 = (GPNode)currentParent1Node.parent;
GPNode parent2 = (GPNode)currentMateNode.parent;
// if there is match between compatibility of parents break
if(parent1.swapCompatibleWith(initializer, parent2))
{
foundAMatchInAncestor = true;
break;
}
else
{
// need to go one level above of both
currentMateNode = parent2;
currentParent1Node = parent1;
//increment the distance
distance = distance +1;
}
}
// find the one with least distance
if(distance < currentMinDistance)
{
currentMinDistance = distance;
chosenNode = i;
}
}
}
// else take the first node, no choice
}
NodeInfo nodeInfoSelected = (NodeInfo)listOfNodes.get(chosenNode);
selectedNode = nodeInfoSelected.node;
return selectedNode;
}
/**
* Recursively travel the tree so that depth and subtree below are computed
* only once and can be reused later.
*
* @param node
* @param nodeToDepth
*/
public void traverseTreeForDepth(GPNode node,
ArrayList nodeToDepth,
HashMap sizeToNodes)
{
GPNode[] children = node.children;
NodeInfo nodeInfo = new NodeInfo(node, node.numNodes(GPNode.NODESEARCH_NONTERMINALS));
nodeToDepth.add(nodeInfo);
// check to see if there is list in map for that size
LinkedList listForSize = (LinkedList)(sizeToNodes.get(Integer.valueOf(nodeInfo.numberOfSubTreesBeneath)));
if (listForSize == null)
{
listForSize = new LinkedList();
sizeToNodes.put(new Integer(nodeInfo.numberOfSubTreesBeneath), listForSize);
}
// add it to the list no matter what
listForSize.add(nodeInfo);
// recurse
if (children.length > 0)
{
for (int i = 0; i < children.length; i++)
{
traverseTreeForDepth(children[i], nodeToDepth, sizeToNodes);
}
}
}
/**
* Inner class to do a quick Roulette Wheel Selection
*
*/
static class RouletteWheelSelector
{
int[] length;
double[] probability;
int currentIndex = 0;
int maxLength = 0;
RouletteWheelSelector(int size)
{
length = new int[size];
probability =new double[size];
}
public void add(double currentProbability, int currentLength)
{
length[currentIndex] = currentLength;
probability[currentIndex] = currentProbability;
currentIndex = currentIndex +1;
if(currentLength > maxLength) maxLength = currentLength;
}
public int roulette(EvolutionState state, int thread)
{
int winner = 0;
int selectedLength = 0;
// accumulate
for (int i = 1; i < currentIndex; i++)
{
probability[i] += probability[i-1];
}
int bot = 0; // binary chop search
int top = currentIndex - 1;
double f = state.random[thread].nextDouble() * probability[top];
for(int loop =0; loop< 20; loop++)
{
int index = (top + bot) / 2;
if (index > 0 && f < probability[index - 1])
top = index - 1;
else if (f > probability[index])
bot = index + 1;
else
{
if (f == probability[index] && index + 1 < currentIndex)
winner = index + 1;
else
winner = index;
break;
}
}
// check for bounds
if(winner < 0 || winner >= currentIndex)
{
state.output.fatal("roulette() method winner " + winner + " out of range 0..." + (currentIndex-1));
winner=0; //safe default
}
if(length[winner] < 1 || length[winner] > maxLength)
{
state.output.fatal("roulette() method " + length[winner] + " is out of range 1..." + maxLength);
// range is specified on creation
return maxLength; //safe default
}
selectedLength = length[winner];
return selectedLength;
}
}
/**
*Used for O(1) information of number of subtrees
*
*/
static class NodeInfo
{
// numberOfSubTrees beneath
int numberOfSubTreesBeneath;
// actual node
GPNode node;
public NodeInfo(GPNode node, int numberOfSubtrees)
{
this.node = node;
this.numberOfSubTreesBeneath = numberOfSubtrees;
}
public void setSubtrees(int totalSubtrees)
{
this.numberOfSubTreesBeneath = totalSubtrees;
}
public int getSubtrees()
{
return numberOfSubTreesBeneath;
}
public GPNode getNode()
{
return node;
}
}
}
Ads help maintain this website.