Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OKBJavaConnector/ECJClient/src/ec/parsimony/RatioBucketTournamentSelection.java @ 7611

Last change on this file since 7611 was 6152, checked in by bfarka, 14 years ago

added ecj and custom statistics to communicate with the okb services #1441

File size: 9.4 KB
Line 
1/*
2  Copyright 2006 by Sean Luke and George Mason University
3  Licensed under the Academic Free License version 3.0
4  See the file "LICENSE" for more information
5*/
6
7
8package ec.parsimony;
9
10import ec.*;
11import ec.util.*;
12import ec.steadystate.*;
13import ec.select.*;
14
15/*
16 * RatioBucketTournamentSelection.java
17 *
18 * Created: Mon Apr 09 17:02:30 2001
19 * By: Liviu Panait
20 */
21
22/**
23 *
24 * Does a tournament selection, limited to the subpopulation it's
25 * working in at the time.
26 *
27 * <p>Ratio Bucket Lexicographic Tournament selection works like as follows. The sizes of buckets are
28 * proportioned so that low-fitness individuals are placed into much larger buckets than high-fitness
29 * individuals.  A bucket ratio <i>1/ratio</i> is specified beforehand.  The bottom <i>1/ratio</i> individuals
30 * of the population are placed into the bottom bucket. If any individuals remain in the population
31 * with the same fitness as the best individual in the bottom bucket, they too are placed in that bucket.
32 * Of the remaining population, the next <i>1/ratio</i> individuals are placed into the next bucket, plus any
33 * individuals remaining in the population with the same fitness as the best individual now in that bucket,
34 * and so on.  This continues until every member of the population has been placed in a bucket. Once again,
35 * the fitness of every individual in a bucket is set to the rank of the bucket relative to other buckets.
36 * Ratio bucketing thus allows parsimony to have more of an effect on average when two similar low-fitness
37 * individuals are considered than when two high-fitness individuals are considered.
38 *
39 * After ranking the individuals, <i>size</i> individuals are chosen at random from the
40 * population. Of those individuals, the one with the highest rank is selected. If the two
41 * individuals are in the same rank, meaning that they have similar fitness, the one
42 * with the smallest size is selected.
43 *
44 * <p>Bucket Lexicographic Tournament selection is so simple that it doesn't
45 * need to maintain a cache of any form, so many of the SelectionMethod methods
46 * just don't do anything at all.
47 *
48
49 <p><b>Typical Number of Individuals Produced Per <tt>produce(...)</tt> call</b><br>
50 Always 1.
51
52 <p><b>Parameters</b><br>
53 <table>
54 <tr><td valign=top><i>base.</i><tt>size</tt><br>
55 <font size=-1>int &gt;= 1 (default 7)</font></td>
56 <td valign=top>(the tournament size)</td></tr>
57
58 <tr><td valign=top><i>base.</i><tt>pick-worst</tt><br>
59 <font size=-1> bool = <tt>true</tt> or <tt>false</tt> (default)</font></td>
60 <td valign=top>(should we pick the <i>worst</i> individual in the tournament instead of the <i>best</i>?)</td></tr>
61
62 <tr><td valign=top><i>base.</i><tt>ratio</tt><br>
63 <font size=-1>float &gt;= 2 (default)</font></td>
64 <td valign=top>(the ratio of worst out of remaining individuals that go in the next bucket)</td></tr>
65 </table>
66
67 <p><b>Default Base</b><br>
68 select.ratio-bucket-tournament
69
70 *
71 * @author Liviu Panait
72 * @version 1.0
73 */
74
75public class RatioBucketTournamentSelection extends SelectionMethod implements SteadyStateBSourceForm
76    {
77    /** default base */
78    public static final String P_RATIO_BUCKET_TOURNAMENT = "ratio-bucket-tournament";
79
80    /** size parameter */
81    public static final String P_SIZE = "size";
82
83    /** Default size */
84    public static final int DEFAULT_SIZE = 7;
85
86    /** Size of the tournament*/
87    public int size;
88
89    /** if the worst individual should be picked in the tournament */
90    public static final String P_PICKWORST = "pick-worst";
91
92    /** Do we pick the worst instead of the best? */
93    public boolean pickWorst;
94
95    /** The value of RATIO: each step, the worse 1/RATIO individuals are assigned the same fitness */
96    public static final String P_RATIO = "ratio";
97
98    /** The default value for RATIO */
99    static float defaultRATIO = 2;
100
101    /** The value of RATIO */
102    public float ratio;
103
104    // the indexes of the buckets where the individuals should go (will be used instead of fitness)
105    int[] bucketValues;
106 
107    public Parameter defaultBase()
108        {
109        return SelectDefaults.base().push(P_RATIO_BUCKET_TOURNAMENT);
110        }
111   
112    public void setup(final EvolutionState state, final Parameter base)
113        {
114        super.setup(state,base);
115       
116        Parameter def = defaultBase();
117
118        size = state.parameters.getInt(base.push(P_SIZE),def.push(P_SIZE),1);
119        if (size < 1)
120            state.output.fatal("Tournament size must be >= 1.",base.push(P_SIZE),def.push(P_SIZE));
121
122        if( state.parameters.exists( base.push(P_RATIO), def.push(P_RATIO)))
123            {
124            ratio = state.parameters.getFloat(base.push(P_RATIO),def.push(P_RATIO),2.0f);
125            if( ratio<2 )
126                {
127                state.output.fatal("The value of b must be >= 2.",base.push(P_RATIO),def.push(P_RATIO));
128                }
129            }
130        else
131            {
132            ratio = defaultRATIO;
133            }
134
135        pickWorst = state.parameters.getBoolean(base.push(P_PICKWORST),def.push(P_PICKWORST),false);
136        }
137
138    /** Prepare to produce: create the buckets!!!! */
139    public void prepareToProduce(final EvolutionState state, final int subpopulation, final int thread)
140        {
141        bucketValues = new int[ state.population.subpops[subpopulation].individuals.length ];
142       
143        // correct?
144        java.util.Arrays.sort(state.population.subpops[subpopulation].individuals,
145            new java.util.Comparator()
146                {
147                public int compare(Object o1, Object o2)
148                    {
149                    Individual a = (Individual) o1;
150                    Individual b = (Individual) o2;
151                    if (a.fitness.betterThan(b.fitness))
152                        return 1;
153                    if (b.fitness.betterThan(a.fitness))
154                        return -1;
155                    return 0;
156                    }
157                });
158
159        // how many individuals in current bucket
160        int nInd;
161
162        float totalInds = ((float)state.population.subpops[subpopulation].individuals.length);
163        float averageBuck = Math.max( totalInds/ratio, 1 );
164
165        // first individual goes into first bucket
166        bucketValues[0] = 0;
167
168        // now there is one individual in the first bucket
169        nInd = 1;
170        totalInds--;
171
172        for( int i = 1 ; i < state.population.subpops[subpopulation].individuals.length ; i++ )
173            {
174            // if there is still some place left in the current bucket, throw the current individual there too
175            if( nInd < averageBuck )
176                {
177                bucketValues[i] = bucketValues[i-1];
178                nInd++;
179                }
180            else // check if it has the same fitness as last individual
181                {
182                if( ((Individual)state.population.subpops[subpopulation].individuals[i]).fitness.equivalentTo(
183                        ((Individual)state.population.subpops[subpopulation].individuals[i-1]).fitness ) )
184                    {
185                    // now the individual has exactly the same fitness as previous one,
186                    // so we just put it in the same bucket as the previous one(s)
187                    bucketValues[i] = bucketValues[i-1];
188                    nInd++;
189                    }
190                else
191                    {
192                    // new bucket!!!!
193                    averageBuck = Math.max( totalInds/ratio, 1 );
194                    bucketValues[i] = bucketValues[i-1] - 1; // decrease the fitness, so that high fit individuals have lower bucket values
195                    // with only one individual
196                    nInd = 1;
197                    }
198                }
199            totalInds--;
200            }
201        }
202
203    public int produce(final int subpopulation,
204        final EvolutionState state,
205        final int thread)
206        {
207        // pick size random individuals, then pick the best.
208        Individual[] oldinds = (state.population.subpops[subpopulation].individuals);
209        int i = state.random[thread].nextInt(oldinds.length);
210        long si = 0;
211
212        for (int x=1;x<size;x++)
213            {
214            int j = state.random[thread].nextInt(oldinds.length);
215            if (pickWorst)
216                {
217                if( bucketValues[j]>bucketValues[i] ) { i = j; si = 0; }
218                else if( bucketValues[i]>bucketValues[j] ) { } // do nothing
219                else
220                    {
221                    if (si==0)
222                        si = oldinds[i].size();
223                    long sj = oldinds[j].size();
224
225                    if (sj >= si) // sj's got worse lookin' trees
226                        { i = j; si = sj; }
227                    }
228                }
229            else
230                {
231                if( bucketValues[j]<bucketValues[i] ) { i = j; si = 0; }
232                else if( bucketValues[i]<bucketValues[j] ) { } // do nothing
233                else
234                    {
235                    if (si==0)
236                        si = oldinds[i].size();
237                    long sj = oldinds[j].size();
238
239                    if (sj < si) // sj's got better lookin' trees
240                        { i = j; si = sj; }
241                    }
242                }
243            }
244        return i;
245        }
246
247    // included for SteadyState
248    public void individualReplaced(final SteadyStateEvolutionState state,
249        final int subpopulation,
250        final int thread,
251        final int individual)
252        { return; }
253   
254    public void sourcesAreProperForm(final SteadyStateEvolutionState state)
255        { return; }
256   
257    }
Note: See TracBrowser for help on using the repository browser.