/*
Copyright 2006 by Sean Luke and George Mason University
Licensed under the Academic Free License version 3.0
See the file "LICENSE" for more information
*/
package ec.parsimony;
import ec.*;
import ec.util.*;
import ec.steadystate.*;
import ec.select.*;
/*
* BucketTournamentSelection.java
*
* Created: Mon Apr 09 17:02:30 2001
* By: Liviu Panait
*/
/**
*
* Does a tournament selection, limited to the subpopulation it's
* working in at the time.
*
* Bucket Lexicographic Tournament selection works like as follows. There is a
* number of buckets (num-buckets) specified beforehand, and each is
* assigned a rank from 1 to num-buckets. The population, of size pop-size,
* is sorted by fitness. The bottom pop-size/num-buckets individuals are
* placed in the worst ranked bucket, plus any individuals remaining in the population with
* the same fitness as the best individual in the bucket. Then the second worst
* pop-size/num-buckets individuals are placed in the second worst ranked bucket,
* plus any individuals in the population equal in fitness to the best individual in that bucket.
* This continues until there are no individuals in the population. Note that the topmost bucket
* with individuals can hold fewer than pop-size/num-buckets individuals, if
* pop-size is not a multiple of num-buckets. Depending on the number of
* equal-fitness individuals in the population, there can be some top buckets that are never
* filled. The fitness of each individual in a bucket is set to the rank of the bucket holding
* it. Direct bucketing has the effect of trading off fitness differences for size. Thus the
* larger the bucket, the stronger the emphasis on size as a secondary objective.
*
* After ranking the individuals, size individuals are chosen at random from the
* population. Of those individuals, the one with the highest rank is selected. If the two
* individuals are in the same rank, meaning that they have similar fitness, the one
* with the smallest size is selected.
*
*
Bucket Lexicographic Tournament selection is so simple that it doesn't
* need to maintain a cache of any form, so many of the SelectionMethod methods
* just don't do anything at all.
*
Typical Number of Individuals Produced Per produce(...) call
Always 1.
Parameters
base.size
int >= 1 (default 7)
(the tournament size) base.pick-worst
bool = true or false (default)
(should we pick the worst individual in the tournament instead of the best?) base.num-buckets
int >= 1 (default 10)
(the number of buckets)
Default Base
select.bucket-tournament
*
* @author Liviu Panait
* @version 1.0
*/
public class BucketTournamentSelection extends SelectionMethod implements SteadyStateBSourceForm
{
/** Default base */
public static final String P_TOURNAMENT = "bucket-tournament";
/** If the worst individual should be picked in the tournament */
public static final String P_PICKWORST = "pick-worst";
/** Tournament size parameter */
public static final String P_SIZE = "size";
/** The number of buckets */
public static final String P_BUCKETS = "num-buckets";
/** Default number of buckets */
public static final int N_BUCKETS_DEFAULT = 10;
/** Size of the tournament*/
public int size;
/** Do we pick the worst instead of the best? */
public boolean pickWorst;
// the number of buckets
int nBuckets;
// the indexes of the buckets where the individuals should go (will be used instead of fitness)
int[] bucketValues;
public Parameter defaultBase()
{
return SelectDefaults.base().push(P_TOURNAMENT);
}
public void setup(final EvolutionState state, final Parameter base)
{
super.setup(state,base);
Parameter def = defaultBase();
size = state.parameters.getInt(base.push(P_SIZE),def.push(P_SIZE),1);
if (size < 1)
state.output.fatal("Tournament size must be >= 1.",base.push(P_SIZE),def.push(P_SIZE));
if( state.parameters.exists( base.push(P_BUCKETS), def.push(P_BUCKETS)))
{
nBuckets = state.parameters.getInt(base.push(P_BUCKETS),def.push(P_BUCKETS),1);
if (nBuckets < 1)
{
state.output.fatal("The number of buckets size must be >= 1.",base.push(P_BUCKETS),def.push(P_BUCKETS));
}
}
else
{
nBuckets = N_BUCKETS_DEFAULT;
}
pickWorst = state.parameters.getBoolean(base.push(P_PICKWORST),def.push(P_PICKWORST),false);
}
/** Prepare to produce: create the buckets!!!! */
public void prepareToProduce(final EvolutionState state, final int subpopulation, final int thread)
{
bucketValues = new int[ state.population.subpops[subpopulation].individuals.length ];
// correct?
java.util.Arrays.sort(state.population.subpops[subpopulation].individuals,
new java.util.Comparator()
{
public int compare(Object o1, Object o2)
{
Individual a = (Individual) o1;
Individual b = (Individual) o2;
if (a.fitness.betterThan(b.fitness))
return 1;
if (b.fitness.betterThan(a.fitness))
return -1;
return 0;
}
});
// how many individuals in current bucket
int nInd;
double averageBuck = ((double)state.population.subpops[subpopulation].individuals.length)/
((double)nBuckets);
// first individual goes into first bucket
bucketValues[0] = 0;
// now there is one individual in the first bucket
nInd = 1;
for( int i = 1 ; i < state.population.subpops[subpopulation].individuals.length ; i++ )
{
// if there is still some place left in the current bucket, throw the current individual there too
if( nInd < averageBuck )
{
bucketValues[i] = bucketValues[i-1];
nInd++;
}
else // check if it has the same fitness as last individual
{
if( ((Individual)state.population.subpops[subpopulation].individuals[i]).fitness.equivalentTo(
((Individual)state.population.subpops[subpopulation].individuals[i-1]).fitness ) )
{
// now the individual has exactly the same fitness as previous one,
// so we just put it in the same bucket as the previous one(s)
bucketValues[i] = bucketValues[i-1];
nInd++;
}
else
{
// if there are buckets left
if( bucketValues[i-1]+1 < nBuckets )
{
// new bucket!!!!
bucketValues[i] = bucketValues[i-1] - 1;
// with only one individual
nInd = 1;
}
else // no more buckets left, just stick everything in the last bucket
{
bucketValues[i] = bucketValues[i-1];
nInd++;
}
}
}
}
}
public int produce(final int subpopulation,
final EvolutionState state,
final int thread)
{
// pick size random individuals, then pick the best.
Individual[] oldinds = (state.population.subpops[subpopulation].individuals);
int i = state.random[thread].nextInt(oldinds.length);
long si = 0;
for (int x=1;xbucketValues[i] ) { i = j; si = 0; }
else if( bucketValues[i]>bucketValues[j] ) { } // do nothing
else
{
if (si==0)
si = oldinds[i].size();
long sj = oldinds[j].size();
if (sj >= si) // sj's got worse lookin' trees
{ i = j; si = sj; }
}
}
else
{
if( bucketValues[j]
Ads help maintain this website.