Ratio Bucket Lexicographic Tournament selection works like as follows. The sizes of buckets are * proportioned so that low-fitness individuals are placed into much larger buckets than high-fitness * individuals. A bucket ratio 1/ratio is specified beforehand. The bottom 1/ratio individuals * of the population are placed into the bottom bucket. If any individuals remain in the population * with the same fitness as the best individual in the bottom bucket, they too are placed in that bucket. * Of the remaining population, the next 1/ratio individuals are placed into the next bucket, plus any * individuals remaining in the population with the same fitness as the best individual now in that bucket, * and so on. This continues until every member of the population has been placed in a bucket. Once again, * the fitness of every individual in a bucket is set to the rank of the bucket relative to other buckets. * Ratio bucketing thus allows parsimony to have more of an effect on average when two similar low-fitness * individuals are considered than when two high-fitness individuals are considered. * * 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.ratio float >= 2 (default) |
(the ratio of worst out of remaining individuals that go in the next bucket) |
Default Base
select.ratio-bucket-tournament
*
* @author Liviu Panait
* @version 1.0
*/
public class RatioBucketTournamentSelection extends SelectionMethod implements SteadyStateBSourceForm
{
/** default base */
public static final String P_RATIO_BUCKET_TOURNAMENT = "ratio-bucket-tournament";
/** size parameter */
public static final String P_SIZE = "size";
/** Default size */
public static final int DEFAULT_SIZE = 7;
/** Size of the tournament*/
public int size;
/** if the worst individual should be picked in the tournament */
public static final String P_PICKWORST = "pick-worst";
/** Do we pick the worst instead of the best? */
public boolean pickWorst;
/** The value of RATIO: each step, the worse 1/RATIO individuals are assigned the same fitness */
public static final String P_RATIO = "ratio";
/** The default value for RATIO */
static float defaultRATIO = 2;
/** The value of RATIO */
public float ratio;
// 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_RATIO_BUCKET_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_RATIO), def.push(P_RATIO)))
{
ratio = state.parameters.getFloat(base.push(P_RATIO),def.push(P_RATIO),2.0f);
if( ratio<2 )
{
state.output.fatal("The value of b must be >= 2.",base.push(P_RATIO),def.push(P_RATIO));
}
}
else
{
ratio = defaultRATIO;
}
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 totalInds = ((float)state.population.subpops[subpopulation].individuals.length);
float averageBuck = Math.max( totalInds/ratio, 1 );
// first individual goes into first bucket
bucketValues[0] = 0;
// now there is one individual in the first bucket
nInd = 1;
totalInds--;
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
{
// new bucket!!!!
averageBuck = Math.max( totalInds/ratio, 1 );
bucketValues[i] = bucketValues[i-1] - 1; // decrease the fitness, so that high fit individuals have lower bucket values
// with only one individual
nInd = 1;
}
}
totalInds--;
}
}
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