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";
/** Default size */
public static final int DEFAULT_SIZE = 7;
/** 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;
float averageBuck = ((float)state.population.subpops[subpopulation].individuals.length)/
((float)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;x