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 | |
---|
8 | package ec.parsimony; |
---|
9 | |
---|
10 | import ec.*; |
---|
11 | import ec.util.*; |
---|
12 | import ec.steadystate.*; |
---|
13 | import 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 >= 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 >= 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 | |
---|
75 | public 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 | } |
---|