1 |
dl |
1.1 |
/* |
2 |
|
|
* Written by Bill Scherer and Doug Lea with assistance from members |
3 |
|
|
* of JCP JSR-166 Expert Group and released to the public domain. Use, |
4 |
|
|
* modify, and redistribute this code in any way without |
5 |
|
|
* acknowledgement. |
6 |
|
|
*/ |
7 |
|
|
|
8 |
|
|
import java.util.concurrent.*; |
9 |
|
|
import java.util.concurrent.atomic.*; |
10 |
|
|
import java.util.concurrent.locks.*; |
11 |
|
|
|
12 |
|
|
public class TSPExchangerTest { |
13 |
|
|
// Set SLS true to use as default the settings in Scherer, Lea, and |
14 |
|
|
// Scott paper. Otherwise smaller values are used to speed up testing |
15 |
|
|
static final boolean SLS = false; |
16 |
|
|
|
17 |
|
|
static final int DEFAULT_THREADS = SLS? 32: 8; |
18 |
|
|
static final int DEFAULT_CITIES = SLS? 100: 50; |
19 |
|
|
static final int DEFAULT_POPULATION = SLS? 1000: 500; |
20 |
|
|
static final int DEFAULT_BREEDERS = SLS? 200: 100; |
21 |
|
|
static final int DEFAULT_GENERATIONS = SLS? 20000: 10000; |
22 |
|
|
|
23 |
|
|
|
24 |
|
|
public static void main(String[] args) throws Exception { |
25 |
|
|
int maxThreads = DEFAULT_THREADS; |
26 |
|
|
int nCities = DEFAULT_CITIES; |
27 |
|
|
int pSize = DEFAULT_POPULATION; |
28 |
|
|
int nBreeders = DEFAULT_BREEDERS; |
29 |
|
|
int numGenerations = DEFAULT_GENERATIONS; |
30 |
|
|
|
31 |
|
|
// Parse and check args |
32 |
|
|
int argc = 0; |
33 |
|
|
try { |
34 |
|
|
while (argc < args.length) { |
35 |
|
|
String option = args[argc++]; |
36 |
|
|
if (option.equals("-b")) |
37 |
|
|
nBreeders = Integer.parseInt(args[argc]); |
38 |
|
|
else if (option.equals("-c")) |
39 |
|
|
nCities = Integer.parseInt(args[argc]); |
40 |
|
|
else if (option.equals("-g")) |
41 |
|
|
numGenerations = Integer.parseInt(args[argc]); |
42 |
|
|
else if (option.equals("-p")) |
43 |
|
|
pSize = Integer.parseInt(args[argc]); |
44 |
|
|
else |
45 |
|
|
maxThreads = Integer.parseInt(option); |
46 |
|
|
argc++; |
47 |
|
|
} |
48 |
|
|
} |
49 |
|
|
catch (NumberFormatException e) { |
50 |
|
|
reportUsageErrorAndDie(); |
51 |
|
|
System.exit(0); |
52 |
|
|
} |
53 |
|
|
catch (Exception e) { |
54 |
|
|
reportUsageErrorAndDie(); |
55 |
|
|
} |
56 |
|
|
|
57 |
|
|
// Display runtime parameters |
58 |
|
|
System.out.print("TSPExchangerTest -b " + nBreeders); |
59 |
|
|
System.out.print(" -c " + nCities); |
60 |
|
|
System.out.print(" -g " + numGenerations); |
61 |
|
|
System.out.print(" -p " + pSize); |
62 |
|
|
System.out.print(" max threads " + maxThreads); |
63 |
|
|
System.out.println(); |
64 |
|
|
|
65 |
|
|
// warmup |
66 |
|
|
System.out.print("Threads: " + 2 + "\t"); |
67 |
|
|
oneRun(2, |
68 |
|
|
nCities, |
69 |
|
|
pSize, |
70 |
|
|
nBreeders, |
71 |
|
|
numGenerations); |
72 |
|
|
Thread.sleep(100); |
73 |
|
|
|
74 |
|
|
int k = 4; |
75 |
|
|
for (int i = 2; i <= maxThreads;) { |
76 |
|
|
System.out.print("Threads: " + i + "\t"); |
77 |
|
|
oneRun(i, |
78 |
|
|
nCities, |
79 |
|
|
pSize, |
80 |
|
|
nBreeders, |
81 |
|
|
numGenerations); |
82 |
|
|
Thread.sleep(100); |
83 |
|
|
if (i == k) { |
84 |
|
|
k = i << 1; |
85 |
|
|
i = i + (i >>> 1); |
86 |
|
|
} |
87 |
|
|
else |
88 |
|
|
i = k; |
89 |
|
|
} |
90 |
|
|
} |
91 |
|
|
|
92 |
|
|
private static void reportUsageErrorAndDie() { |
93 |
|
|
System.out.print("usage: TSPExchangerTest [-b #breeders] [-c #cities]"); |
94 |
|
|
System.out.println(" [-g #generations]"); |
95 |
|
|
System.out.println(" [-p population size] [ #threads]"); |
96 |
|
|
System.exit(0); |
97 |
|
|
} |
98 |
|
|
|
99 |
|
|
static void oneRun(int nThreads, |
100 |
|
|
int nCities, |
101 |
|
|
int pSize, |
102 |
|
|
int nBreeders, |
103 |
|
|
int numGenerations) |
104 |
|
|
throws Exception { |
105 |
|
|
CyclicBarrier runBarrier = new CyclicBarrier(nThreads + 1); |
106 |
|
|
Population p = new Population(nCities, pSize, nBreeders, nThreads, |
107 |
|
|
numGenerations, runBarrier); |
108 |
|
|
|
109 |
|
|
// Run the test |
110 |
|
|
long startTime = System.currentTimeMillis(); |
111 |
|
|
runBarrier.await(); // start 'em off |
112 |
|
|
runBarrier.await(); // wait 'til they're done |
113 |
|
|
long stopTime = System.currentTimeMillis(); |
114 |
|
|
long elapsed = stopTime - startTime; |
115 |
|
|
long rate = (numGenerations * 1000) / elapsed; |
116 |
|
|
double secs = (double)elapsed / 1000.0; |
117 |
|
|
|
118 |
|
|
// Display results |
119 |
|
|
System.out.print(LoopHelpers.rightJustify((int)p.bestFitness()) + |
120 |
|
|
" fitness"); |
121 |
|
|
System.out.print(LoopHelpers.rightJustify(rate) + " gen/s \t"); |
122 |
|
|
System.out.print(secs + "s elapsed"); |
123 |
|
|
System.out.println(); |
124 |
|
|
} |
125 |
|
|
|
126 |
|
|
static final class Population { |
127 |
|
|
final Chromosome[] individuals; |
128 |
|
|
final Exchanger<Chromosome> x; |
129 |
|
|
final CitySet cities; |
130 |
|
|
final int[] dyers; |
131 |
|
|
final int[] breeders; |
132 |
|
|
final CyclicBarrier generationBarrier; |
133 |
|
|
final Thread[] threads; |
134 |
|
|
final boolean[] doneMating; |
135 |
|
|
final ReentrantLock matingBarrierLock; |
136 |
|
|
final Condition matingBarrier; |
137 |
|
|
final LoopHelpers.SimpleRandom[] rngs; |
138 |
|
|
final int nThreads; |
139 |
|
|
volatile int matingBarrierCount; |
140 |
|
|
|
141 |
|
|
// action to run between each generation |
142 |
|
|
class BarrierAction implements Runnable { |
143 |
|
|
public void run() { |
144 |
|
|
prepareToBreed(); |
145 |
|
|
resetMatingBarrier(); |
146 |
|
|
} |
147 |
|
|
} |
148 |
|
|
|
149 |
|
|
Population(int nCities, |
150 |
|
|
int pSize, |
151 |
|
|
int nBreeders, |
152 |
|
|
int nThreads, |
153 |
|
|
int nGen, |
154 |
|
|
CyclicBarrier runBarrier) { |
155 |
|
|
this.nThreads = nThreads; |
156 |
|
|
// rngs[nThreads] is for global actions; others are per-thread |
157 |
|
|
this.rngs = new LoopHelpers.SimpleRandom[nThreads+1]; |
158 |
|
|
for (int i = 0; i < rngs.length; ++i) |
159 |
|
|
rngs[i] = new LoopHelpers.SimpleRandom(); |
160 |
|
|
this.cities = new CitySet(nCities, rngs[nThreads]); |
161 |
|
|
this.individuals = new Chromosome[pSize]; |
162 |
|
|
for (int i = 0; i < individuals.length; i++) |
163 |
|
|
individuals[i] = new Chromosome(cities, nCities, |
164 |
|
|
rngs[nThreads]); |
165 |
|
|
this.doneMating = new boolean[nThreads]; |
166 |
|
|
this.dyers = new int[nBreeders]; |
167 |
|
|
this.breeders = new int[nBreeders]; |
168 |
|
|
|
169 |
|
|
this.x = new Exchanger(); |
170 |
|
|
|
171 |
|
|
this.matingBarrierLock = new ReentrantLock(); |
172 |
|
|
this.matingBarrier = matingBarrierLock.newCondition(); |
173 |
|
|
|
174 |
|
|
BarrierAction ba = new BarrierAction(); |
175 |
|
|
this.generationBarrier = new CyclicBarrier(nThreads, ba); |
176 |
|
|
ba.run(); // prepare for first generation |
177 |
|
|
|
178 |
|
|
this.threads = new Thread[nThreads]; |
179 |
|
|
for (int i = 0; i < nThreads; i++) { |
180 |
|
|
Runner r = new Runner(i, this, runBarrier, nGen); |
181 |
|
|
threads[i] = new Thread(r); |
182 |
|
|
threads[i].start(); |
183 |
|
|
} |
184 |
|
|
} |
185 |
|
|
|
186 |
|
|
double averageFitness() { |
187 |
|
|
double total = 0; |
188 |
|
|
for (int i = 0; i < individuals.length; i++) |
189 |
|
|
total += individuals[i].fitness; |
190 |
|
|
return total/(double)individuals.length; |
191 |
|
|
} |
192 |
|
|
|
193 |
|
|
double bestFitness() { |
194 |
|
|
double best = individuals[0].fitness; |
195 |
|
|
for (int i = 0; i < individuals.length; i++) |
196 |
|
|
if (individuals[i].fitness < best) |
197 |
|
|
best = individuals[i].fitness; |
198 |
|
|
return best; |
199 |
|
|
} |
200 |
|
|
|
201 |
|
|
void resetMatingBarrier() { |
202 |
|
|
matingBarrierCount = nThreads - 1; |
203 |
|
|
} |
204 |
|
|
|
205 |
|
|
void awaitMatingBarrier(int tid) { |
206 |
|
|
doneMating[tid] = true; // heuristically set before lock |
207 |
|
|
matingBarrierLock.lock(); |
208 |
|
|
try { |
209 |
|
|
int m = matingBarrierCount--; |
210 |
|
|
if (m < 1) { |
211 |
|
|
for (int i = 0; i < doneMating.length; ++i) |
212 |
|
|
doneMating[i] = false; |
213 |
|
|
Thread.interrupted(); // clear |
214 |
|
|
matingBarrier.signalAll(); |
215 |
|
|
} else { |
216 |
|
|
doneMating[tid] = true; |
217 |
|
|
if (m == 1 && nThreads > 2) { |
218 |
|
|
for (int j = 0; j < doneMating.length; ++j) { |
219 |
|
|
if (!doneMating[j]) { |
220 |
|
|
threads[j].interrupt(); |
221 |
|
|
break; |
222 |
|
|
} |
223 |
|
|
} |
224 |
|
|
} |
225 |
|
|
try { |
226 |
|
|
do { |
227 |
|
|
matingBarrier.await(); |
228 |
|
|
} while (matingBarrierCount >= 0); |
229 |
|
|
} catch(InterruptedException ie) {} |
230 |
|
|
} |
231 |
|
|
} finally { |
232 |
|
|
matingBarrierLock.unlock(); |
233 |
|
|
} |
234 |
|
|
} |
235 |
|
|
|
236 |
|
|
void prepareToBreed() { |
237 |
|
|
|
238 |
|
|
// Calculate statistics |
239 |
|
|
double totalFitness = 0; |
240 |
|
|
double worstFitness = 0; |
241 |
|
|
double bestFitness = individuals[0].fitness; |
242 |
|
|
|
243 |
|
|
for (int i = 0; i < individuals.length; i++) { |
244 |
|
|
totalFitness += individuals[i].fitness; |
245 |
|
|
if (individuals[i].fitness > worstFitness) |
246 |
|
|
worstFitness = individuals[i].fitness; |
247 |
|
|
if (individuals[i].fitness < bestFitness) |
248 |
|
|
bestFitness = individuals[i].fitness; |
249 |
|
|
} |
250 |
|
|
|
251 |
|
|
double[] lifeNorm = new double[individuals.length]; |
252 |
|
|
double lifeNormTotal = 0; |
253 |
|
|
double[] deathNorm = new double[individuals.length]; |
254 |
|
|
double deathNormTotal = 0; |
255 |
|
|
for (int i = 0; i < individuals.length; i++) { |
256 |
|
|
deathNorm[i] = (individuals[i].fitness - bestFitness) |
257 |
|
|
/ (worstFitness - bestFitness + 1) + .05; |
258 |
|
|
deathNorm[i] = (deathNorm[i] * deathNorm[i]); |
259 |
|
|
lifeNorm[i] = 1.0 - deathNorm[i]; |
260 |
|
|
lifeNormTotal += lifeNorm[i]; |
261 |
|
|
deathNormTotal += deathNorm[i]; |
262 |
|
|
} |
263 |
|
|
|
264 |
|
|
double deathScale = deathNormTotal / (double)0x7FFFFFFF; |
265 |
|
|
double lifeScale = lifeNormTotal / (double)0x7FFFFFFF; |
266 |
|
|
|
267 |
|
|
int nSub = breeders.length / nThreads; |
268 |
|
|
LoopHelpers.SimpleRandom random = rngs[nThreads]; |
269 |
|
|
|
270 |
|
|
// Select breeders (need to be distinct) |
271 |
|
|
for (int i = 0; i < nSub; i++) { |
272 |
|
|
boolean newBreeder; |
273 |
|
|
int lucky; |
274 |
|
|
do { |
275 |
|
|
newBreeder = true; |
276 |
|
|
double choice = lifeScale * (double)random.next(); |
277 |
|
|
for (lucky = 0; lucky < individuals.length; lucky++) { |
278 |
|
|
choice -= lifeNorm[lucky]; |
279 |
|
|
if (choice <= 0) |
280 |
|
|
break; |
281 |
|
|
} |
282 |
|
|
for (int j = 0; j < i; j++) |
283 |
|
|
if (breeders[j] == lucky) |
284 |
|
|
newBreeder = false; |
285 |
|
|
} while (!newBreeder); |
286 |
|
|
breeders[i] = lucky; |
287 |
|
|
} |
288 |
|
|
|
289 |
|
|
// Select dead guys (need to be distinct) |
290 |
|
|
for (int i = 0; i < nSub; i++) { |
291 |
|
|
boolean newDead; |
292 |
|
|
int victim; |
293 |
|
|
do { |
294 |
|
|
newDead = true; |
295 |
|
|
double choice = deathScale * (double)random.next(); |
296 |
|
|
for (victim = 0; victim < individuals.length; victim++) { |
297 |
|
|
choice -= deathNorm[victim]; |
298 |
|
|
if (choice <= 0) |
299 |
|
|
break; |
300 |
|
|
} |
301 |
|
|
for (int j = 0; j < i; j++) |
302 |
|
|
if (dyers[j] == victim) |
303 |
|
|
newDead = false; |
304 |
|
|
} while (!newDead); |
305 |
|
|
dyers[i] = victim; |
306 |
|
|
} |
307 |
|
|
|
308 |
|
|
} |
309 |
|
|
|
310 |
|
|
|
311 |
|
|
void nextGeneration(int tid, int matings) |
312 |
|
|
throws InterruptedException, BrokenBarrierException { |
313 |
|
|
|
314 |
|
|
int firstChild = ((individuals.length * tid) / nThreads); |
315 |
|
|
int lastChild = ((individuals.length * (tid + 1)) / nThreads); |
316 |
|
|
int nChildren = lastChild - firstChild; |
317 |
|
|
|
318 |
|
|
int firstSub = ((breeders.length * tid) / nThreads); |
319 |
|
|
int lastSub = ((breeders.length * (tid + 1)) / nThreads); |
320 |
|
|
int nSub = lastSub - firstSub; |
321 |
|
|
|
322 |
|
|
Chromosome[] children = new Chromosome[nChildren]; |
323 |
|
|
|
324 |
|
|
LoopHelpers.SimpleRandom random = rngs[tid]; |
325 |
|
|
|
326 |
|
|
for (int i = 0; i < nSub; i++) { |
327 |
|
|
Chromosome parent = individuals[breeders[firstSub + i]]; |
328 |
|
|
Chromosome offspring = new Chromosome(parent); |
329 |
|
|
int k = 0; |
330 |
|
|
while (k < matings && matingBarrierCount > 0) { |
331 |
|
|
try { |
332 |
|
|
Chromosome other = x.exchange(offspring); |
333 |
|
|
offspring = offspring.reproduceWith(other, random); |
334 |
|
|
++k; |
335 |
|
|
} catch (InterruptedException to) { |
336 |
|
|
break; |
337 |
|
|
} |
338 |
|
|
} |
339 |
|
|
if (k != 0) |
340 |
|
|
children[i] = offspring; |
341 |
|
|
else { |
342 |
|
|
// No peers, so we mate with ourselves |
343 |
|
|
for ( ; i < nSub - 1; i += 2) { |
344 |
|
|
int cur = firstSub + i; |
345 |
|
|
Chromosome bro = individuals[breeders[cur]]; |
346 |
|
|
Chromosome sis = individuals[breeders[cur + 1]]; |
347 |
|
|
|
348 |
|
|
children[i] = bro.breedWith(sis, matings, random); |
349 |
|
|
children[i+1] = sis.breedWith(bro, matings, random); |
350 |
|
|
} |
351 |
|
|
|
352 |
|
|
// Not even a sibling, so we go to asexual reproduction |
353 |
|
|
if (i < nSub) |
354 |
|
|
children[i] = individuals[breeders[firstSub + 1]]; |
355 |
|
|
break; |
356 |
|
|
} |
357 |
|
|
|
358 |
|
|
} |
359 |
|
|
|
360 |
|
|
awaitMatingBarrier(tid); |
361 |
|
|
|
362 |
|
|
// Kill off dead guys |
363 |
|
|
for (int i = 0; i < nSub; i++) { |
364 |
|
|
individuals[dyers[firstSub + 1]] = children[i]; |
365 |
|
|
} |
366 |
|
|
|
367 |
|
|
generationBarrier.await(); |
368 |
|
|
} |
369 |
|
|
} |
370 |
|
|
|
371 |
|
|
static final class Chromosome { |
372 |
|
|
private final CitySet cities; |
373 |
|
|
private final int[] alleles; |
374 |
|
|
private final int length; |
375 |
|
|
public double fitness; // immutable after publication |
376 |
|
|
|
377 |
|
|
// Basic constructor - gets randomized genetic code |
378 |
|
|
Chromosome(CitySet cities, int length, |
379 |
|
|
LoopHelpers.SimpleRandom random) { |
380 |
|
|
this.length = length; |
381 |
|
|
this.cities = cities; |
382 |
|
|
// Initialize alleles to a random shuffle |
383 |
|
|
alleles = new int[length]; |
384 |
|
|
for (int i = 0; i < length; i++) |
385 |
|
|
alleles[i] = i; |
386 |
|
|
for (int i = length - 1; i > 0; i--) { |
387 |
|
|
int tmp = alleles[i]; |
388 |
|
|
int idx = random.next() % length; |
389 |
|
|
alleles[i] = alleles[idx]; |
390 |
|
|
alleles[idx] = tmp; |
391 |
|
|
} |
392 |
|
|
recalcFitness(); |
393 |
|
|
} |
394 |
|
|
|
395 |
|
|
// Copy constructor - clones parent's genetic code |
396 |
|
|
Chromosome(Chromosome clone) { |
397 |
|
|
length = clone.length; |
398 |
|
|
cities = clone.cities; |
399 |
|
|
fitness = clone.fitness; |
400 |
|
|
alleles = new int[length]; |
401 |
|
|
System.arraycopy(clone.alleles, 0, alleles, 0, length); |
402 |
|
|
} |
403 |
|
|
|
404 |
|
|
int getAllele(int offset) { |
405 |
|
|
return alleles[offset % length]; |
406 |
|
|
} |
407 |
|
|
void setAllele(int offset, int v) { |
408 |
|
|
alleles[offset % length] = v; |
409 |
|
|
} |
410 |
|
|
|
411 |
|
|
void recalcFitness() { |
412 |
|
|
fitness = cities.distanceBetween(alleles[0], alleles[length-1]); |
413 |
|
|
for (int i = 1; i < length; i++) { |
414 |
|
|
fitness += cities.distanceBetween(alleles[i-1], alleles[i]); |
415 |
|
|
} |
416 |
|
|
} |
417 |
|
|
|
418 |
|
|
Chromosome breedWith(Chromosome partner, int n, |
419 |
|
|
LoopHelpers.SimpleRandom random) { |
420 |
|
|
Chromosome offspring = new Chromosome(this); |
421 |
|
|
for (int i = 0; i < n; i++) |
422 |
|
|
offspring = offspring.reproduceWith(partner, random); |
423 |
|
|
return offspring; |
424 |
|
|
} |
425 |
|
|
|
426 |
|
|
Chromosome reproduceWith(Chromosome other, |
427 |
|
|
LoopHelpers.SimpleRandom random) { |
428 |
|
|
Chromosome child = new Chromosome(this); |
429 |
|
|
int coStart = random.next() % length; |
430 |
|
|
int coLen = 3; |
431 |
|
|
while (1 == (random.next() & 1) && (coLen < length)) |
432 |
|
|
coLen++; |
433 |
|
|
int cPos, pPos; |
434 |
|
|
|
435 |
|
|
int join = other.getAllele(coStart); |
436 |
|
|
child.alleles[0] = join; |
437 |
|
|
|
438 |
|
|
for (pPos = 0; alleles[pPos] != join; pPos++) |
439 |
|
|
; |
440 |
|
|
|
441 |
|
|
for (cPos = 1; cPos < coLen; cPos++) |
442 |
|
|
child.setAllele(cPos, other.getAllele(coStart + cPos)); |
443 |
|
|
|
444 |
|
|
for (int i = 0; i < length; i++) { |
445 |
|
|
boolean found = false; |
446 |
|
|
int allele = getAllele(pPos++); |
447 |
|
|
for (int j = 0; j < coLen; j++) { |
448 |
|
|
if (found = (child.getAllele(j) == allele)) |
449 |
|
|
break; |
450 |
|
|
} |
451 |
|
|
if (!found) |
452 |
|
|
child.setAllele(cPos++, allele); |
453 |
|
|
} |
454 |
|
|
|
455 |
|
|
child.recalcFitness(); |
456 |
|
|
return child; |
457 |
|
|
} |
458 |
|
|
|
459 |
|
|
} |
460 |
|
|
/** |
461 |
|
|
* A collection of (x,y) points that represent cities |
462 |
|
|
*/ |
463 |
|
|
static final class CitySet { |
464 |
|
|
final int XMAX = 1000; |
465 |
|
|
final int YMAX = 1000; |
466 |
|
|
final int length; |
467 |
|
|
final int xPts[]; |
468 |
|
|
final int yPts[]; |
469 |
|
|
final double distances[]; |
470 |
|
|
|
471 |
|
|
CitySet(int n, LoopHelpers.SimpleRandom random) { |
472 |
|
|
this.length = n; |
473 |
|
|
xPts = new int[n]; |
474 |
|
|
yPts = new int [n]; |
475 |
|
|
for (int i = 0; i < n; i++) { |
476 |
|
|
xPts[i] = random.next() % XMAX; |
477 |
|
|
yPts[i] = random.next() % YMAX; |
478 |
|
|
} |
479 |
|
|
distances = new double[n * n]; |
480 |
|
|
for (int i = 0; i < n; i++) { |
481 |
|
|
for (int j = 0; j < n; j++) { |
482 |
|
|
double dX = (double)(xPts[i] - xPts[j]); |
483 |
|
|
double dY = (double)(yPts[i] - yPts[j]); |
484 |
|
|
distances[i + j * n] = Math.hypot(dX, dY); |
485 |
|
|
} |
486 |
|
|
} |
487 |
|
|
} |
488 |
|
|
|
489 |
|
|
// Retrieve the cached distance between a pair of cities |
490 |
|
|
double distanceBetween(int idx1, int idx2) { |
491 |
|
|
return distances[idx1 + idx2 * length]; |
492 |
|
|
} |
493 |
|
|
} |
494 |
|
|
|
495 |
|
|
static final class Runner implements Runnable { |
496 |
|
|
final Population pop; |
497 |
|
|
final CyclicBarrier b; |
498 |
|
|
final int nGen; |
499 |
|
|
final int tid; |
500 |
|
|
static final boolean verbose = false; |
501 |
|
|
|
502 |
|
|
Runner(int tid, Population p, CyclicBarrier b, int n) { |
503 |
|
|
this.tid = tid; |
504 |
|
|
this.pop = p; |
505 |
|
|
this.b = b; |
506 |
|
|
this.nGen = n; |
507 |
|
|
} |
508 |
|
|
|
509 |
|
|
public void run() { |
510 |
|
|
try { |
511 |
|
|
b.await(); |
512 |
|
|
for (int i = 0; i < nGen; i++) { |
513 |
|
|
if (verbose && 0 == tid && 0 == i % 1000) { |
514 |
|
|
System.out.print("Gen " + i + " fitness:"); |
515 |
|
|
System.out.print(" best=" + (int)pop.bestFitness()); |
516 |
|
|
System.out.println("; avg=" + (int)pop.averageFitness()); |
517 |
|
|
} |
518 |
|
|
int matings = (((nGen - i) * 2) / (nGen)) + 1; |
519 |
|
|
pop.nextGeneration(tid, matings); |
520 |
|
|
} |
521 |
|
|
b.await(); |
522 |
|
|
} |
523 |
|
|
catch (InterruptedException e) { |
524 |
|
|
e.printStackTrace(System.out); |
525 |
|
|
System.exit(0); |
526 |
|
|
} |
527 |
|
|
catch (BrokenBarrierException e) { |
528 |
|
|
e.printStackTrace(System.out); |
529 |
|
|
System.exit(0); |
530 |
|
|
} |
531 |
|
|
} |
532 |
|
|
} |
533 |
|
|
} |