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 |
} |