source: java/ecj/cecj/eval/TournamentCoevolutionaryEvaluator.java @ 1305

/*
  Copyright 2009 by Marcin Szubert
  Licensed under the Academic Free License version 3.0
*/

package cecj.eval;

import cecj.interaction.InteractionResult;
import cecj.problems.SymmetricCompetitionProblem;
import ec.EvolutionState;
import ec.Individual;
import ec.simple.SimpleFitness;
import ec.util.Parameter;

/**
 * Single elimination tournament competitive evaluator. It is different from the other
 * coevolutionary evaluators because interactions between individuals must be simulated in strict
 * order. It depends on the outcome of previous interaction if the individual can compete further.
 * 
 * Assumes that individuals use <code>SimpleFitness</code>. The fitness assigned by this method is
 * equal to the height of the tournament subtree that particular individual has traversed - the
 * number of games won. To reduce the inherent noise of the tournament evaluation scheme, a few
 * rounds can be played. The number of rounds is specified by a <code>repeats</code> parameter which
 * is equal to 1 by default. This evaluator can be used if problem being solved implements
 * <code>SymmetricCompetitionProblem</code> interface.
 * 
 * Since it would be hard to extend this evaluator with generic archiving or fitness sharing, only
 * the simplest settings are available.
 * 
 * @author Marcin Szubert
 * 
 */
public class TournamentCoevolutionaryEvaluator extends CoevolutionaryEvaluator {

        private static final String P_REPEATS = "repeats";

        /**
         * Specifies how many times the tournament should be repeated during single evaluation process.
         * More repeats can reduce the noise of this evaluation scheme.
         */
        private int tournamentRepeats;

        private SymmetricCompetitionProblem problem;

        /**
         * Represents competing individuals.
         */
        private Individual[] competitors;

        /**
         * Number of competitors - size of the particular subpopulation.
         */
        private int numCompetitors;

        /**
         * Points gathered during the course of competition.
         */
        private int[] points;

        /**
         * An array used as a tournament tree representation. It stores indices of competing
         * individuals. Neighboring indices compete with each other in certain round.
         */
        private int[] competition;

        /**
         * Stores active competitors ready to be divided into pairs.
         */
        private int[] activeCompetitors;

        /**
         * Indicates if particular competitor is still in game.
         */
        private boolean[] active;

        @Override
        public void setup(final EvolutionState state, final Parameter base) {
                super.setup(state, base);

                if (!(p_problem instanceof SymmetricCompetitionProblem)) {
                        state.output.fatal("Tournament evaluator can be used only with symmetric problems");
                } else {
                        problem = (SymmetricCompetitionProblem) p_problem;
                }

                Parameter repeatsParameter = base.push(P_REPEATS);
                tournamentRepeats = state.parameters.getIntWithDefault(repeatsParameter, null, 1);
                if (tournamentRepeats <= 0) {
                        state.output.fatal("Tournament repeats parameter can not be negative.",
                                        repeatsParameter);
                }
        }

        @Override
        public void evaluatePopulation(EvolutionState state) {
                for (int subpop = 0; subpop < numSubpopulations; subpop++) {
                        prepareTournament(state, subpop);
                        for (int r = 0; r < tournamentRepeats; r++) {
                                makeTournament(state);
                        }
                        assignFitness(state);
                }
        }

        /**
         * Initializes structures used in the tournament series.
         * 
         * @param state
         *            current evolutionary state
         * @param subpop
         *            index of subpopulation
         */
        private void prepareTournament(EvolutionState state, int subpop) {
                competitors = state.population.subpops[subpop].individuals;
                numCompetitors = competitors.length;

                points = new int[numCompetitors];
                active = new boolean[numCompetitors];
                competition = new int[numCompetitors];
                activeCompetitors = new int[numCompetitors];
        }

        /**
         * Plays a single tournament between earlier selected competitors from particular subpopulation.
         * Each tournament consists of a sequence of rounds. In each round number of active competitors
         * is reduced by half according to the results of their games (approximately - if at the start
         * of the round number of players is odd, one player is given a "bye" and advances to the next
         * round directly). At the beginning of each round there is a drawing which assigns competitors
         * in pairs.
         * 
         * @param state
         *            current evolutionary state
         */
        private void makeTournament(EvolutionState state) {
                int numActiveCompetitors;
                for (int c = 0; c < numCompetitors; c++) {
                        active[c] = true;
                }

                while ((numActiveCompetitors = findActiveCompetitors()) > 1) {
                        shuffleCompetitors(state, numActiveCompetitors);
                        playTournamentRound(state, numActiveCompetitors);
                }
        }

        /**
         * Assigns fitness value to each competing individual according to overall points which it has
         * gathered during the series of tournaments.
         * 
         * @param state
         *            current evolutionary state
         */
        private void assignFitness(EvolutionState state) {
                for (int c = 0; c < numCompetitors; c++) {
                        Individual competitor = competitors[c];
                        ((SimpleFitness) competitor.fitness).setFitness(state, points[c], false);
                }
        }

        /**
         * Finds still active competitors according to <code>active</code> array. Found competitor
         * indices are stored in <code>activeCompetitors</code> array and their number is returned.
         * 
         * @return number of still active competitors
         */
        private int findActiveCompetitors() {
                int leftCompetitors = 0;
                for (int c = 0; c < numCompetitors; c++) {
                        if (active[c]) {
                                activeCompetitors[leftCompetitors++] = c;
                        }
                }
                return leftCompetitors;
        }

        /**
         * Randomly shuffles competitors indices taken from <
         * 
         * @param state
         *            current evolutionary state
         * @param count
         *            the number of shuffled competitors
         */
        private void shuffleCompetitors(EvolutionState state, int count) {
                int left = count;
                for (int i = 0; i < count; i++) {
                        int rand = state.random[0].nextInt(left);
                        competition[i] = activeCompetitors[rand];
                        activeCompetitors[rand] = activeCompetitors[--left];
                }
        }

        /**
         * Arranges a competition between neighbors in <code>competition</code> array.
         * 
         * @param state
         *            current evolutionary state
         * @param numLeftCompetitors
         *            the number of competitors left
         */
        private void playTournamentRound(EvolutionState state, int numLeftCompetitors) {
                for (int i = 0; i + 1 < numLeftCompetitors; i += 2) {
                        Individual c1 = competitors[competition[i]];
                        Individual c2 = competitors[competition[i + 1]];

                        // TODO: consider if it is needed to call compete method twice
                        // maybe it should use internal individual's fitness or return both
                        // results at once?
                        InteractionResult score1 = problem.compete(state, c1, c2).first;
                        InteractionResult score2 = problem.compete(state, c2, c1).first;

                        if (score1.betterThan(score2)) {
                                points[competition[i]]++;
                                active[competition[i + 1]] = false;
                        } else {
                                points[competition[i + 1]]++;
                                active[competition[i]] = false;
                        }
                }

                // TODO: in case of odd number of competitors, should the one given a
                // "bye" achieve a point
                // in this round?
                if (numLeftCompetitors % 2 != 0) {
                        points[competition[numLeftCompetitors - 1]]++;
                }
        }
}