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

Last change on this file since 1114 was 193, checked in by Maciej Komosinski, 11 years ago

Set svn:eol-style native for all textual files

  • Property svn:eol-style set to native
File size: 7.1 KB
Line 
1/*
2  Copyright 2009 by Marcin Szubert
3  Licensed under the Academic Free License version 3.0
4*/
5
6package cecj.eval;
7
8import cecj.interaction.InteractionResult;
9import cecj.problems.SymmetricCompetitionProblem;
10import ec.EvolutionState;
11import ec.Individual;
12import ec.simple.SimpleFitness;
13import ec.util.Parameter;
14
15/**
16 * Single elimination tournament competitive evaluator. It is different from the other
17 * coevolutionary evaluators because interactions between individuals must be simulated in strict
18 * order. It depends on the outcome of previous interaction if the individual can compete further.
19 *
20 * Assumes that individuals use <code>SimpleFitness</code>. The fitness assigned by this method is
21 * equal to the height of the tournament subtree that particular individual has traversed - the
22 * number of games won. To reduce the inherent noise of the tournament evaluation scheme, a few
23 * rounds can be played. The number of rounds is specified by a <code>repeats</code> parameter which
24 * is equal to 1 by default. This evaluator can be used if problem being solved implements
25 * <code>SymmetricCompetitionProblem</code> interface.
26 *
27 * Since it would be hard to extend this evaluator with generic archiving or fitness sharing, only
28 * the simplest settings are available.
29 *
30 * @author Marcin Szubert
31 *
32 */
33public class TournamentCoevolutionaryEvaluator extends CoevolutionaryEvaluator {
34
35        private static final String P_REPEATS = "repeats";
36
37        /**
38         * Specifies how many times the tournament should be repeated during single evaluation process.
39         * More repeats can reduce the noise of this evaluation scheme.
40         */
41        private int tournamentRepeats;
42
43        private SymmetricCompetitionProblem problem;
44
45        /**
46         * Represents competing individuals.
47         */
48        private Individual[] competitors;
49
50        /**
51         * Number of competitors - size of the particular subpopulation.
52         */
53        private int numCompetitors;
54
55        /**
56         * Points gathered during the course of competition.
57         */
58        private int[] points;
59
60        /**
61         * An array used as a tournament tree representation. It stores indices of competing
62         * individuals. Neighboring indices compete with each other in certain round.
63         */
64        private int[] competition;
65
66        /**
67         * Stores active competitors ready to be divided into pairs.
68         */
69        private int[] activeCompetitors;
70
71        /**
72         * Indicates if particular competitor is still in game.
73         */
74        private boolean[] active;
75
76        @Override
77        public void setup(final EvolutionState state, final Parameter base) {
78                super.setup(state, base);
79
80                if (!(p_problem instanceof SymmetricCompetitionProblem)) {
81                        state.output.fatal("Tournament evaluator can be used only with symmetric problems");
82                } else {
83                        problem = (SymmetricCompetitionProblem) p_problem;
84                }
85
86                Parameter repeatsParameter = base.push(P_REPEATS);
87                tournamentRepeats = state.parameters.getIntWithDefault(repeatsParameter, null, 1);
88                if (tournamentRepeats <= 0) {
89                        state.output.fatal("Tournament repeats parameter can not be negative.",
90                                        repeatsParameter);
91                }
92        }
93
94        @Override
95        public void evaluatePopulation(EvolutionState state) {
96                for (int subpop = 0; subpop < numSubpopulations; subpop++) {
97                        prepareTournament(state, subpop);
98                        for (int r = 0; r < tournamentRepeats; r++) {
99                                makeTournament(state);
100                        }
101                        assignFitness(state);
102                }
103        }
104
105        /**
106         * Initializes structures used in the tournament series.
107         *
108         * @param state
109         *            current evolutionary state
110         * @param subpop
111         *            index of subpopulation
112         */
113        private void prepareTournament(EvolutionState state, int subpop) {
114                competitors = state.population.subpops[subpop].individuals;
115                numCompetitors = competitors.length;
116
117                points = new int[numCompetitors];
118                active = new boolean[numCompetitors];
119                competition = new int[numCompetitors];
120                activeCompetitors = new int[numCompetitors];
121        }
122
123        /**
124         * Plays a single tournament between earlier selected competitors from particular subpopulation.
125         * Each tournament consists of a sequence of rounds. In each round number of active competitors
126         * is reduced by half according to the results of their games (approximately - if at the start
127         * of the round number of players is odd, one player is given a "bye" and advances to the next
128         * round directly). At the beginning of each round there is a drawing which assigns competitors
129         * in pairs.
130         *
131         * @param state
132         *            current evolutionary state
133         */
134        private void makeTournament(EvolutionState state) {
135                int numActiveCompetitors;
136                for (int c = 0; c < numCompetitors; c++) {
137                        active[c] = true;
138                }
139
140                while ((numActiveCompetitors = findActiveCompetitors()) > 1) {
141                        shuffleCompetitors(state, numActiveCompetitors);
142                        playTournamentRound(state, numActiveCompetitors);
143                }
144        }
145
146        /**
147         * Assigns fitness value to each competing individual according to overall points which it has
148         * gathered during the series of tournaments.
149         *
150         * @param state
151         *            current evolutionary state
152         */
153        private void assignFitness(EvolutionState state) {
154                for (int c = 0; c < numCompetitors; c++) {
155                        Individual competitor = competitors[c];
156                        ((SimpleFitness) competitor.fitness).setFitness(state, points[c], false);
157                }
158        }
159
160        /**
161         * Finds still active competitors according to <code>active</code> array. Found competitor
162         * indices are stored in <code>activeCompetitors</code> array and their number is returned.
163         *
164         * @return number of still active competitors
165         */
166        private int findActiveCompetitors() {
167                int leftCompetitors = 0;
168                for (int c = 0; c < numCompetitors; c++) {
169                        if (active[c]) {
170                                activeCompetitors[leftCompetitors++] = c;
171                        }
172                }
173                return leftCompetitors;
174        }
175
176        /**
177         * Randomly shuffles competitors indices taken from <
178         *
179         * @param state
180         *            current evolutionary state
181         * @param count
182         *            the number of shuffled competitors
183         */
184        private void shuffleCompetitors(EvolutionState state, int count) {
185                int left = count;
186                for (int i = 0; i < count; i++) {
187                        int rand = state.random[0].nextInt(left);
188                        competition[i] = activeCompetitors[rand];
189                        activeCompetitors[rand] = activeCompetitors[--left];
190                }
191        }
192
193        /**
194         * Arranges a competition between neighbors in <code>competition</code> array.
195         *
196         * @param state
197         *            current evolutionary state
198         * @param numLeftCompetitors
199         *            the number of competitors left
200         */
201        private void playTournamentRound(EvolutionState state, int numLeftCompetitors) {
202                for (int i = 0; i + 1 < numLeftCompetitors; i += 2) {
203                        Individual c1 = competitors[competition[i]];
204                        Individual c2 = competitors[competition[i + 1]];
205
206                        // TODO: consider if it is needed to call compete method twice
207                        // maybe it should use internal individual's fitness or return both
208                        // results at once?
209                        InteractionResult score1 = problem.compete(state, c1, c2).first;
210                        InteractionResult score2 = problem.compete(state, c2, c1).first;
211
212                        if (score1.betterThan(score2)) {
213                                points[competition[i]]++;
214                                active[competition[i + 1]] = false;
215                        } else {
216                                points[competition[i + 1]]++;
217                                active[competition[i]] = false;
218                        }
219                }
220
221                // TODO: in case of odd number of competitors, should the one given a
222                // "bye" achieve a point
223                // in this round?
224                if (numLeftCompetitors % 2 != 0) {
225                        points[competition[numLeftCompetitors - 1]]++;
226                }
227        }
228}
Note: See TracBrowser for help on using the repository browser.