/*
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.coevolve;
import ec.*;
import ec.util.*;
import ec.simple.*;
/**
* CompetitiveEvaluator.java
*
CompetitiveEvaluator is a Evaluator which performs competitive fitness evaluations.
Competitive fitness is where individuals' fitness is determined by testing them against
other members of the same subpopulation. Competitive fitness topologies differ from
co-evolution topologies in that co-evolution is a term I generally reserve for
multiple sbupopulations which breed separately but compete against other subpopulations
during evaluation time. Individuals are evaluated regardless of whether or not they've
been evaluated in the past.
Your Problem is responsible for setting up the fitness appropriately.
CompetitiveEvaluator expects to use Problems which adhere to the GroupedProblemForm interface,
which defines a new evaluate(...) function, plus a preprocess(...) and postprocess(...) function.
This competitive fitness evaluator is single-threaded -- maybe we'll hack in multithreading later.
And it only has two individuals competing during any fitness evaluation. The order of individuals in the
subpopulation will be changed during the evaluation process. There are seven evaluation topologies
presently supported:
- Single Elimination Tournament
-
All members of the population are paired up and evaluated. In each pair, the "winner" is the individual
which winds up with the superior fitness. If neither fitness is superior, then the "winner" is picked
at random. Then all the winners are paired up and evaluated, and so on, just like in a single elimination
tournament. It is important that the population size be a power of two, else some individuals
will not have the same number of "wins" as others and may lose the tournament as a result.
- Round Robin
-
Every member of the population are paired up and evaluated with all other members of the population, not
not including the member itself (we might add in self-play as a future later if people ask for it, it's
easy to hack in).
- K-Random-Opponents-One-Way
-
Each individual's fitness is calculated based on K competitions against random opponents.
For details, see "A Comparison of Two Competitive Fitness Functions" by Liviu Panait and
Sean Luke in the Proceedings of GECCO 2002.
- K-Random-Opponents-Two-Way
-
Each individual's fitness is calculated based on K competitions against random opponents. The advantage of
this method over K-Random-Opponents-One-Way is a reduced number of competitions (when I competes
against J, both I's and J's fitnesses are updated, while in the previous method only one of the individuals
has its fitness updated).
For details, see "A Comparison of Two Competitive Fitness Functions" by Liviu Panait and
Sean Luke in the Proceedings of GECCO 2002.
Parameters
base.style
string with possible values:
(the style of the tournament)
single-elim-tournament (a single elimination tournament)
round-robin (a round robin tournament)
rand-1-way (K-Random-Opponents, each game counts for only one of the players)
rand-2-way (K-Random-Opponents, each game counts for both players)
base.group-size
int
(how many individuals per group, used in rand-1-way and rand-2-way tournaments)
group-size >= 1 for rand-1-way or rand-2-way
base.over-eval
bool = true or false (default)
(if the tournament style leads to an individual playing more games than others (as can be the case for rand-2-way),
should the extra games be used for his fitness evaluatiuon?)
*
* @author Sean Luke & Liviu Panait
* @version 1.0
*/
public class CompetitiveEvaluator extends Evaluator
{
public static final int STYLE_SINGLE_ELIMINATION=1;
public static final int STYLE_ROUND_ROBIN=2;
public static final int STYLE_N_RANDOM_COMPETITORS_ONEWAY=3;
public static final int STYLE_N_RANDOM_COMPETITORS_TWOWAY=4;
public static final String P_COMPETE_STYLE = "style";
public int style;
public static final String P_GROUP_SIZE = "group-size";
public int groupSize;
public static final String P_OVER_EVAL = "over-eval";
public boolean allowOverEvaluation;
public void setup( final EvolutionState state, final Parameter base )
{
super.setup( state, base );
String temp;
temp = state.parameters.getStringWithDefault( base.push( P_COMPETE_STYLE ), null, "" );
if( temp.equalsIgnoreCase( "single-elim-tournament" ) )
{
style = STYLE_SINGLE_ELIMINATION;
}
else if( temp.equalsIgnoreCase( "round-robin" ) )
{
style = STYLE_ROUND_ROBIN;
}
else if( temp.equalsIgnoreCase( "rand-1-way" ) )
{
style = STYLE_N_RANDOM_COMPETITORS_ONEWAY;
}
else if( temp.equalsIgnoreCase( "rand-2-way" ) )
{
style = STYLE_N_RANDOM_COMPETITORS_TWOWAY;
}
else if (temp.equalsIgnoreCase( "rand-2-ways" ) )
{
state.output.fatal("'rand-2-ways' is no longer a valid style name: use 'rand-2-way'",
base.push(P_COMPETE_STYLE), null);
}
else
{
state.output.fatal( "Incorrect value for parameter. Acceptable values: " +
"single-elim-tournament, round-robin, rand-1-way, rand-2-way" , base.push( P_COMPETE_STYLE ) );
}
if( style == STYLE_N_RANDOM_COMPETITORS_ONEWAY || style == STYLE_N_RANDOM_COMPETITORS_TWOWAY )
{
groupSize = state.parameters.getInt( base.push( P_GROUP_SIZE ), null, 1 );
if( groupSize < 1 )
{
state.output.fatal( "Incorrect value for parameter", base.push( P_GROUP_SIZE ) );
}
}
allowOverEvaluation = state.parameters.getBoolean( base.push( P_OVER_EVAL ), null, false );
}
public boolean runComplete( final EvolutionState state )
{
return false;
}
public void randomizeOrder(final EvolutionState state, final Individual[] individuals)
{
// copy the inds into a new array, then dump them randomly into the
// subpopulation again
Individual[] queue = new Individual[individuals.length];
int len = queue.length;
System.arraycopy(individuals,0,queue,0,len);
for(int x=len;x>0;x--)
{
int i = state.random[0].nextInt(x);
individuals[x-1] = queue[i];
// get rid of queue[i] by swapping the highest guy there and then
// decreasing the highest value :-)
queue[i] = queue[x-1];
}
}
/**
* An evaluator that performs coevolutionary evaluation. Like SimpleEvaluator,
* it applies evolution pipelines, one per thread, to various subchunks of
* a new population.
*/
public void evaluatePopulation(final EvolutionState state)
{
int numinds[] = new int[state.evalthreads];
int from[] = new int[state.evalthreads];
boolean[] assessFitness = new boolean[state.population.subpops.length];
for(int i = 0; i < assessFitness.length; i++)
assessFitness[i] = true; // update everyone's fitness in preprocess and postprocess
for (int y=0;y 1 )
{
for(int x=0;xx in this thread.
for(int x=from;x queue[x].nOpponentsMet ; y++ )
{
// swap to the end and remove from list
int index = state.random[0].nextInt( queue.length - x - 1 - y )+x+1;
competition[1] = queue[index].ind;
updates[1] = (queue[index].nOpponentsMet < groupSize) || allowOverEvaluation;
prob.evaluate( state, competition, updates, false, subpops, 0 );
queue[x].nOpponentsMet++;
if( updates[1] )
queue[index].nOpponentsMet++;
// swap the players (such that a player will not be considered twice)
EncapsulatedIndividual temp = queue[index];
queue[index] = queue[queue.length - y - 1];
queue[queue.length - y - 1] = temp;
}
}
// if true, it means that the current player needs to play some games with other players with lower indexes.
// this is an unfortunate situation, since all those players have already had their groupSize games for the evaluation
if( queue[x].nOpponentsMet < groupSize )
{
for( int y = queue[x].nOpponentsMet ; y < groupSize ; y++ )
{
// select a random opponent with smaller index (don't even care for duplicates)
int index;
if( x > 0 ) // if x is 0, then there are no players with smaller index, therefore pick a random one
index = state.random[0].nextInt( x );
else
index = state.random[0].nextInt( queue.length-1 )+1;
// use the opponent for the evaluation
competition[1] = queue[index].ind;
updates[1] = (queue[index].nOpponentsMet < groupSize) || allowOverEvaluation;
prob.evaluate( state, competition, updates, false, subpops, 0 );
queue[x].nOpponentsMet++;
if( updates[1] )
queue[index].nOpponentsMet++;
}
}
}
}
int nextPowerOfTwo( int N )
{
int i = 1;
while( i < N )
i *= 2;
return i;
}
int whereToPutInformation;
void fillPositions( int[] positions, int who, int totalPerDepth, int total )
{
if(totalPerDepth >= total - 1 )
{
positions[whereToPutInformation] = who;
whereToPutInformation++;
}
else
{
fillPositions( positions, who, totalPerDepth*2+1, total );
fillPositions( positions, totalPerDepth-who, totalPerDepth*2+1, total );
}
}
}
// used by the K-Random-Opponents-One-Way and K-Random-Opponents-Two-Ways evaluations
class EncapsulatedIndividual
{
public Individual ind;
public int nOpponentsMet;
public EncapsulatedIndividual( Individual ind_, int value_ )
{
ind = ind_;
nOpponentsMet = value_;
}
};
/*
// used by the Single-Elimination-Tournament, (Double-Elimination-Tournament and World-Cup) evaluations
class IndividualAndVictories
{
public Individual ind;
public int victories;
public IndividualAndVictories( Individual ind_, int value_ )
{
ind = ind_;
victories = value_;
}
};
*/
class IndComparator implements SortComparator
{
public boolean lt(Object a, Object b)
{ return ((Individual)a).fitness.betterThan(((Individual)b).fitness); }
public boolean gt(Object a, Object b)
{ return ((Individual)b).fitness.betterThan(((Individual)a).fitness); }
}
abstract class CompetitiveEvaluatorThread implements Runnable
{
public int numinds;
public int from;
public CompetitiveEvaluator me;
public EvolutionState state;
public int threadnum;
public GroupedProblemForm p;
public int subpop;
public Individual[] inds;
}
class RoundRobinCompetitiveEvaluatorThread extends CompetitiveEvaluatorThread
{
public synchronized void run()
{ me.evalRoundRobinPopChunk(state,from,numinds,threadnum,inds, subpop, p); }
}
class NRandomOneWayCompetitiveEvaluatorThread extends CompetitiveEvaluatorThread
{
public synchronized void run()
{ me.evalNRandomOneWayPopChunk(state,from,numinds,threadnum,inds, subpop, p); }
}
class NRandomTwoWayCompetitiveEvaluatorThread extends CompetitiveEvaluatorThread
{
public synchronized void run()
{ me.evalNRandomTwoWayPopChunk(state,from,numinds,threadnum,inds, subpop, p); }
}
Ads help maintain this website.