1 |
/* |
2 |
* Written by Doug Lea and Bill Scherer with assistance from members |
3 |
* of JCP JSR-166 Expert Group and released to the public domain, as |
4 |
* explained at http://creativecommons.org/licenses/publicdomain |
5 |
*/ |
6 |
|
7 |
import java.util.*; |
8 |
import java.util.concurrent.*; |
9 |
import java.util.concurrent.atomic.*; |
10 |
import java.util.concurrent.locks.*; |
11 |
|
12 |
/** |
13 |
* A parallel Traveling Salesperson Problem (TSP) program based on a |
14 |
* genetic algorithm using an Exchanger. A population of chromosomes |
15 |
* is distributed among "pools". The chromosomes represent tours, and |
16 |
* their fitness is the total tour length. A Task is associated with |
17 |
* each pool. Each task repeatedly does, for a fixed number of |
18 |
* iterations (generations): |
19 |
* <ol> |
20 |
* <li> Select a breeder b from the pool |
21 |
* <li> Create a strand of its tour with a random starting point and length |
22 |
* <li> Offer the strand to the exchanger, receiving a strand from |
23 |
* another pool |
24 |
* <li> Combine b and the received strand using crossing function to |
25 |
* create new chromosome c. |
26 |
* <li> Replace a chromosome in the pool with c. |
27 |
* </ol> |
28 |
* |
29 |
* See below for more details. |
30 |
* <p> |
31 |
* |
32 |
*/ |
33 |
public class TSPExchangerTest { |
34 |
static final int NCPUS = Runtime.getRuntime().availableProcessors(); |
35 |
|
36 |
static final int DEFAULT_MAX_THREADS = NCPUS + 6; |
37 |
|
38 |
/** |
39 |
* The problem size. Each city is a random point. The goal is to |
40 |
* find a tour among them with smallest total Euclidean distance. |
41 |
*/ |
42 |
static final int DEFAULT_CITIES = 144; |
43 |
|
44 |
// Tuning parameters. |
45 |
|
46 |
/** |
47 |
* The number of chromosomes per pool. Must be a power of two. |
48 |
* |
49 |
* Smaller values lead to faster iterations but poorer quality |
50 |
* results |
51 |
*/ |
52 |
static final int DEFAULT_POOL_SIZE = 32; |
53 |
|
54 |
/** |
55 |
* The number of iterations per task. Convergence appears |
56 |
* to be roughly proportional to #cities-squared |
57 |
*/ |
58 |
static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES; |
59 |
|
60 |
/** |
61 |
* The number of pools. The total population is #pools * poolSize, |
62 |
* which should be roughly on the order of #cities-squared |
63 |
* |
64 |
* Smaller values lead to faster total runs but poorer quality |
65 |
* results |
66 |
*/ |
67 |
static final int DEFAULT_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE; |
68 |
|
69 |
/** |
70 |
* The minimum length for a random chromosome strand. |
71 |
* Must be at least 1. |
72 |
*/ |
73 |
static final int MIN_STRAND_LENGTH = 3; |
74 |
|
75 |
/** |
76 |
* The probablility mask value for creating random strands, |
77 |
* that have lengths at least MIN_STRAND_LENGTH, and grow |
78 |
* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) |
79 |
* Must be 1 less than a power of two. |
80 |
*/ |
81 |
static final int RANDOM_STRAND_MASK = 7; |
82 |
|
83 |
/** |
84 |
* Probablility control for selecting breeders. |
85 |
* Breeders are selected starting at the best-fitness chromosome, |
86 |
* with exponentially decaying probablility |
87 |
* 1 / (poolSize >>> BREEDER_DECAY). |
88 |
* |
89 |
* Larger values usually cause faster convergence but poorer |
90 |
* quality results |
91 |
*/ |
92 |
static final int BREEDER_DECAY = 1; |
93 |
|
94 |
/** |
95 |
* Probablility control for selecting dyers. |
96 |
* Dyers are selected starting at the worst-fitness chromosome, |
97 |
* with exponentially decaying probablility |
98 |
* 1 / (poolSize >>> DYER_DECAY) |
99 |
* |
100 |
* Larger values usually cause faster convergence but poorer |
101 |
* quality results |
102 |
*/ |
103 |
static final int DYER_DECAY = 1; |
104 |
|
105 |
static final boolean verbose = false; |
106 |
static final long SNAPSHOT_RATE = 10000; // in milliseconds |
107 |
|
108 |
/** |
109 |
* The set of cities. Created once per program run, to |
110 |
* make it easier to compare solutions across different runs. |
111 |
*/ |
112 |
static CitySet cities; |
113 |
|
114 |
public static void main(String[] args) throws Exception { |
115 |
int maxThreads = DEFAULT_MAX_THREADS; |
116 |
int nCities = DEFAULT_CITIES; |
117 |
int poolSize = DEFAULT_POOL_SIZE; |
118 |
int nGen = nCities * nCities; |
119 |
int nPools = nCities * nCities / poolSize; |
120 |
|
121 |
try { |
122 |
int argc = 0; |
123 |
while (argc < args.length) { |
124 |
String option = args[argc++]; |
125 |
if (option.equals("-c")) { |
126 |
nCities = Integer.parseInt(args[argc]); |
127 |
nGen = nCities * nCities; |
128 |
nPools = nCities * nCities / poolSize; |
129 |
} |
130 |
else if (option.equals("-p")) |
131 |
poolSize = Integer.parseInt(args[argc]); |
132 |
else if (option.equals("-g")) |
133 |
nGen = Integer.parseInt(args[argc]); |
134 |
else if (option.equals("-n")) |
135 |
nPools = Integer.parseInt(args[argc]); |
136 |
else |
137 |
maxThreads = Integer.parseInt(option); |
138 |
argc++; |
139 |
} |
140 |
} |
141 |
catch (Exception e) { |
142 |
reportUsageErrorAndDie(); |
143 |
} |
144 |
|
145 |
System.out.print("TSPExchangerTest"); |
146 |
System.out.print(" -c " + nCities); |
147 |
System.out.print(" -g " + nGen); |
148 |
System.out.print(" -p " + poolSize); |
149 |
System.out.print(" -n " + nPools); |
150 |
System.out.print(" max threads " + maxThreads); |
151 |
System.out.println(); |
152 |
|
153 |
cities = new CitySet(nCities); |
154 |
|
155 |
for (int i = 2; i <= maxThreads; i += 2) |
156 |
oneRun(i, nPools, poolSize, nGen); |
157 |
} |
158 |
|
159 |
static void reportUsageErrorAndDie() { |
160 |
System.out.print("usage: TSPExchangerTest"); |
161 |
System.out.print(" [-c #cities]"); |
162 |
System.out.print(" [-p #poolSize]"); |
163 |
System.out.print(" [-g #generations]"); |
164 |
System.out.print(" [-n #pools]"); |
165 |
System.out.print(" #threads]"); |
166 |
System.out.println(); |
167 |
System.exit(0); |
168 |
} |
169 |
|
170 |
/** |
171 |
* Perform one run with the given parameters. Each run completes |
172 |
* when there are fewer than nThreads-2 tasks remaining. This |
173 |
* avoids measuring termination effects, as well as cases where |
174 |
* the one last remaining task has no one left to exchange with, |
175 |
* so the pool is abruptly terminated. |
176 |
*/ |
177 |
static void oneRun(int nThreads, int nPools, int poolSize, int nGen) |
178 |
throws InterruptedException { |
179 |
Population p = new Population(nThreads, nPools, poolSize, nGen); |
180 |
ProgressMonitor mon = null; |
181 |
if (verbose) { |
182 |
mon = new ProgressMonitor(p); |
183 |
mon.start(); |
184 |
} |
185 |
p.printSnapshot(0); |
186 |
long startTime = System.nanoTime(); |
187 |
p.start(); |
188 |
p.awaitTasks(); |
189 |
long stopTime = System.nanoTime(); |
190 |
if (mon != null) |
191 |
mon.interrupt(); |
192 |
p.shutdown(); |
193 |
Thread.sleep(100); |
194 |
|
195 |
long elapsed = stopTime - startTime; |
196 |
long rate = elapsed / (nPools * nGen); |
197 |
double secs = (double)elapsed / 1000000000.0; |
198 |
p.printSnapshot(secs); |
199 |
System.out.printf("%10d ns per transfer\n", rate); |
200 |
} |
201 |
|
202 |
|
203 |
/** |
204 |
* A Population creates the pools, tasks, and threads for a run |
205 |
* and has control methods to start, stop, and report progress. |
206 |
*/ |
207 |
static final class Population { |
208 |
final Task[] tasks; |
209 |
final Exchanger<Strand> exchanger; |
210 |
final ThreadPoolExecutor exec; |
211 |
final CountDownLatch done; |
212 |
final int nGen; |
213 |
final int poolSize; |
214 |
final int nThreads; |
215 |
|
216 |
Population(int nThreads, int nPools, int poolSize, int nGen) { |
217 |
this.nThreads = nThreads; |
218 |
this.nGen = nGen; |
219 |
this.poolSize = poolSize; |
220 |
this.exchanger = new Exchanger<Strand>(); |
221 |
this.done = new CountDownLatch(Math.max(1, nPools - nThreads - 2)); |
222 |
this.tasks = new Task[nPools]; |
223 |
for (int i = 0; i < nPools; i++) |
224 |
tasks[i] = new Task(this); |
225 |
BlockingQueue<Runnable> tq = |
226 |
new LinkedBlockingQueue<Runnable>(); |
227 |
this.exec = new ThreadPoolExecutor(nThreads, nThreads, |
228 |
0L, TimeUnit.MILLISECONDS, |
229 |
tq); |
230 |
exec.prestartAllCoreThreads(); |
231 |
} |
232 |
|
233 |
/** Start the tasks */ |
234 |
void start() { |
235 |
for (int i = 0; i < tasks.length; i++) |
236 |
exec.execute(tasks[i]); |
237 |
} |
238 |
|
239 |
/** Stop the tasks */ |
240 |
void shutdown() { |
241 |
exec.shutdownNow(); |
242 |
} |
243 |
|
244 |
/** Called by task upon terminations */ |
245 |
void taskDone() { |
246 |
done.countDown(); |
247 |
} |
248 |
|
249 |
/** Wait for (all but one) task to complete */ |
250 |
void awaitTasks() throws InterruptedException { |
251 |
done.await(); |
252 |
} |
253 |
|
254 |
/** |
255 |
* Called by a task to resubmit itself after completing |
256 |
* fewer than nGen iterations. |
257 |
*/ |
258 |
void resubmit(Task task) { |
259 |
try { |
260 |
exec.execute(task); |
261 |
} catch(RejectedExecutionException ignore) {} |
262 |
} |
263 |
|
264 |
void printSnapshot(double secs) { |
265 |
int gens = 0; |
266 |
Chromosome bestc = tasks[0].chromosomes[0]; |
267 |
Chromosome worstc = bestc; |
268 |
for (int k = 0; k < tasks.length; ++k) { |
269 |
gens += tasks[k].gen; |
270 |
Chromosome[] cs = tasks[k].chromosomes; |
271 |
if (cs[0].fitness < bestc.fitness) |
272 |
bestc = cs[0]; |
273 |
int w = cs[cs.length-1].fitness; |
274 |
if (cs[cs.length-1].fitness > worstc.fitness) |
275 |
worstc = cs[cs.length-1]; |
276 |
} |
277 |
double sqrtn = Math.sqrt(cities.length); |
278 |
double best = bestc.unitTourLength() / sqrtn; |
279 |
double worst = worstc.unitTourLength() / sqrtn; |
280 |
int avegen = (done.getCount() == 0)? nGen : gens / tasks.length; |
281 |
System.out.printf("Time:%9.3f Best:%7.3f Worst:%7.3f Gen:%6d Threads:%4d\n", |
282 |
secs, best, worst, avegen, nThreads); |
283 |
} |
284 |
|
285 |
} |
286 |
|
287 |
/** |
288 |
* A Task updates its pool of chromosomes.. |
289 |
*/ |
290 |
static final class Task implements Runnable { |
291 |
/** The pool of chromosomes, kept in sorted order */ |
292 |
final Chromosome[] chromosomes; |
293 |
final Population pop; |
294 |
/** The common exchanger, same for all tasks */ |
295 |
final Exchanger<Strand> exchanger; |
296 |
/** The current strand being exchanged */ |
297 |
Strand strand; |
298 |
/** Bitset used in cross */ |
299 |
final int[] inTour; |
300 |
final RNG rng; |
301 |
final int poolSize; |
302 |
final int nGen; |
303 |
final int genPerRun; |
304 |
int gen; |
305 |
|
306 |
Task(Population pop) { |
307 |
this.pop = pop; |
308 |
this.nGen = pop.nGen; |
309 |
this.gen = 0; |
310 |
this.poolSize = pop.poolSize; |
311 |
this.genPerRun = 4 * poolSize * Math.min(NCPUS, pop.nThreads); |
312 |
this.exchanger = pop.exchanger; |
313 |
this.rng = new RNG(); |
314 |
int length = cities.length; |
315 |
this.strand = new Strand(length); |
316 |
this.inTour = new int[(length >>> 5) + 1]; |
317 |
this.chromosomes = new Chromosome[poolSize]; |
318 |
for (int j = 0; j < poolSize; ++j) |
319 |
chromosomes[j] = new Chromosome(length, rng); |
320 |
Arrays.sort(chromosomes); |
321 |
} |
322 |
|
323 |
/** |
324 |
* Run one or more update cycles. An average of genPerRun |
325 |
* iterations are performed per run, and then the task is |
326 |
* resubmitted. The rate is proportional to both pool size and |
327 |
* number of threads. This keeps average rate of breeding |
328 |
* across pools approximately constant across different test |
329 |
* runs. |
330 |
*/ |
331 |
public void run() { |
332 |
try { |
333 |
int maxGen = gen + 1 + rng.next() % genPerRun; |
334 |
if (maxGen > nGen) |
335 |
maxGen = nGen; |
336 |
while (gen++ < maxGen) |
337 |
update(); |
338 |
if (maxGen < nGen) |
339 |
pop.resubmit(this); |
340 |
else |
341 |
pop.taskDone(); |
342 |
} catch (InterruptedException ie) { |
343 |
pop.taskDone(); |
344 |
} |
345 |
} |
346 |
|
347 |
/** |
348 |
* Choose a breeder, exchange strand with another pool, and |
349 |
* cross them to create new chromosome to replace a chosen |
350 |
* dyer. |
351 |
*/ |
352 |
void update() throws InterruptedException { |
353 |
int b = chooseBreeder(); |
354 |
int d = chooseDyer(b); |
355 |
Chromosome breeder = chromosomes[b]; |
356 |
Chromosome child = chromosomes[d]; |
357 |
chooseStrand(breeder); |
358 |
strand = exchanger.exchange(strand); |
359 |
cross(breeder, child); |
360 |
fixOrder(child, d); |
361 |
} |
362 |
|
363 |
/** |
364 |
* Choose a breeder, with exponentially decreasing probability |
365 |
* starting at best. |
366 |
* @return index of selected breeder |
367 |
*/ |
368 |
int chooseBreeder() { |
369 |
int mask = (poolSize >>> BREEDER_DECAY) - 1; |
370 |
int b = 0; |
371 |
while ((rng.next() & mask) != mask) { |
372 |
if (++b >= poolSize) |
373 |
b = 0; |
374 |
} |
375 |
return b; |
376 |
} |
377 |
|
378 |
/** |
379 |
* Choose a chromosome that will be replaced, with |
380 |
* exponentially decreasing probablility starting at |
381 |
* worst, ignoring the excluded index |
382 |
* @param exclude index to ignore; use -1 to not exclude any |
383 |
* @return index of selected dyer |
384 |
*/ |
385 |
int chooseDyer(int exclude) { |
386 |
int mask = (poolSize >>> DYER_DECAY) - 1; |
387 |
int d = poolSize - 1; |
388 |
while (d == exclude || (rng.next() & mask) != mask) { |
389 |
if (--d < 0) |
390 |
d = poolSize - 1; |
391 |
} |
392 |
return d; |
393 |
} |
394 |
|
395 |
/** |
396 |
* Select a random strand of b's. |
397 |
* @param breeder the breeder |
398 |
*/ |
399 |
void chooseStrand(Chromosome breeder) { |
400 |
int[] bs = breeder.alleles; |
401 |
int length = bs.length; |
402 |
int strandLength = MIN_STRAND_LENGTH; |
403 |
while (strandLength < length && |
404 |
(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK) |
405 |
strandLength++; |
406 |
strand.strandLength = strandLength; |
407 |
int[] ss = strand.alleles; |
408 |
int k = (rng.next() & 0x7FFFFFFF) % length; |
409 |
for (int i = 0; i < strandLength; ++i) { |
410 |
ss[i] = bs[k]; |
411 |
if (++k >= length) k = 0; |
412 |
} |
413 |
} |
414 |
|
415 |
/** |
416 |
* Copy current strand to start of c's, and then append all |
417 |
* remaining b's that aren't in the strand. |
418 |
* @param breeder the breeder |
419 |
* @param child the child |
420 |
*/ |
421 |
void cross(Chromosome breeder, Chromosome child) { |
422 |
for (int k = 0; k < inTour.length; ++k) // clear bitset |
423 |
inTour[k] = 0; |
424 |
|
425 |
// Copy current strand to c |
426 |
int[] cs = child.alleles; |
427 |
int ssize = strand.strandLength; |
428 |
int[] ss = strand.alleles; |
429 |
int i; |
430 |
for (i = 0; i < ssize; ++i) { |
431 |
int x = ss[i]; |
432 |
cs[i] = x; |
433 |
inTour[x >>> 5] |= 1 << (x & 31); // record in bit set |
434 |
} |
435 |
|
436 |
// Find index of matching origin in b |
437 |
int first = cs[0]; |
438 |
int j = 0; |
439 |
int[] bs = breeder.alleles; |
440 |
while (bs[j] != first) |
441 |
++j; |
442 |
|
443 |
// Append remaining b's that aren't already in tour |
444 |
while (i < cs.length) { |
445 |
if (++j >= bs.length) j = 0; |
446 |
int x = bs[j]; |
447 |
if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) |
448 |
cs[i++] = x; |
449 |
} |
450 |
|
451 |
} |
452 |
|
453 |
/** |
454 |
* Fix the sort order of a changed Chromosome c at position k |
455 |
* @param c the chromosome |
456 |
* @param k the index |
457 |
*/ |
458 |
void fixOrder(Chromosome c, int k) { |
459 |
Chromosome[] cs = chromosomes; |
460 |
int oldFitness = c.fitness; |
461 |
c.recalcFitness(); |
462 |
int newFitness = c.fitness; |
463 |
if (newFitness < oldFitness) { |
464 |
int j = k; |
465 |
int p = j - 1; |
466 |
while (p >= 0 && cs[p].fitness > newFitness) { |
467 |
cs[j] = cs[p]; |
468 |
j = p--; |
469 |
} |
470 |
cs[j] = c; |
471 |
} else if (newFitness > oldFitness) { |
472 |
int j = k; |
473 |
int n = j + 1; |
474 |
while (n < cs.length && cs[n].fitness < newFitness) { |
475 |
cs[j] = cs[n]; |
476 |
j = n++; |
477 |
} |
478 |
cs[j] = c; |
479 |
} |
480 |
} |
481 |
} |
482 |
|
483 |
/** |
484 |
* A Chromosome is a candidate TSP tour. |
485 |
*/ |
486 |
static final class Chromosome implements Comparable { |
487 |
/** Index of cities in tour order */ |
488 |
final int[] alleles; |
489 |
/** Total tour length */ |
490 |
int fitness; |
491 |
|
492 |
/** |
493 |
* Initialize to random tour |
494 |
*/ |
495 |
Chromosome(int length, RNG random) { |
496 |
alleles = new int[length]; |
497 |
for (int i = 0; i < length; i++) |
498 |
alleles[i] = i; |
499 |
for (int i = length - 1; i > 0; i--) { |
500 |
int idx = (random.next() & 0x7FFFFFFF) % alleles.length; |
501 |
int tmp = alleles[i]; |
502 |
alleles[i] = alleles[idx]; |
503 |
alleles[idx] = tmp; |
504 |
} |
505 |
recalcFitness(); |
506 |
} |
507 |
|
508 |
public int compareTo(Object x) { // to enable sorting |
509 |
int xf = ((Chromosome)x).fitness; |
510 |
int f = fitness; |
511 |
return ((f == xf)? 0 :((f < xf)? -1 : 1)); |
512 |
} |
513 |
|
514 |
void recalcFitness() { |
515 |
int[] a = alleles; |
516 |
int len = a.length; |
517 |
int p = a[0]; |
518 |
long f = cities.distanceBetween(a[len-1], p); |
519 |
for (int i = 1; i < len; i++) { |
520 |
int n = a[i]; |
521 |
f += cities.distanceBetween(p, n); |
522 |
p = n; |
523 |
} |
524 |
fitness = (int)(f / len); |
525 |
} |
526 |
|
527 |
double unitTourLength() { |
528 |
int[] a = alleles; |
529 |
int len = a.length; |
530 |
int p = a[0]; |
531 |
double f = cities.unitDistanceBetween(a[len-1], p); |
532 |
for (int i = 1; i < len; i++) { |
533 |
int n = a[i]; |
534 |
f += cities.unitDistanceBetween(p, n); |
535 |
p = n; |
536 |
} |
537 |
return f; |
538 |
} |
539 |
|
540 |
void validate() { // Ensure that this is a valid tour. |
541 |
int len = alleles.length; |
542 |
boolean[] used = new boolean[len]; |
543 |
for (int i = 0; i < len; ++i) |
544 |
used[alleles[i]] = true; |
545 |
for (int i = 0; i < len; ++i) |
546 |
if (!used[i]) |
547 |
throw new Error("Bad tour"); |
548 |
} |
549 |
|
550 |
} |
551 |
|
552 |
/** |
553 |
* A Strand is a random sub-sequence of a Chromosome. Each task |
554 |
* creates only one strand, and then trades it with others, |
555 |
* refilling it on each iteration. |
556 |
*/ |
557 |
static final class Strand { |
558 |
final int[] alleles; |
559 |
int strandLength; |
560 |
Strand(int length) { alleles = new int[length]; } |
561 |
} |
562 |
|
563 |
/** |
564 |
* A collection of (x,y) points that represent cities. |
565 |
*/ |
566 |
static final class CitySet { |
567 |
|
568 |
final int length; |
569 |
final int[] xPts; |
570 |
final int[] yPts; |
571 |
final int[][] distances; |
572 |
|
573 |
CitySet(int n) { |
574 |
this.length = n; |
575 |
this.xPts = new int[n]; |
576 |
this.yPts = new int[n]; |
577 |
this.distances = new int[n][n]; |
578 |
|
579 |
RNG random = new RNG(); |
580 |
for (int i = 0; i < n; i++) { |
581 |
xPts[i] = (random.next() & 0x7FFFFFFF); |
582 |
yPts[i] = (random.next() & 0x7FFFFFFF); |
583 |
} |
584 |
|
585 |
for (int i = 0; i < n; i++) { |
586 |
for (int j = 0; j < n; j++) { |
587 |
double dx = (double)xPts[i] - (double)xPts[j]; |
588 |
double dy = (double)yPts[i] - (double)yPts[j]; |
589 |
double dd = Math.hypot(dx, dy) / 2.0; |
590 |
long ld = Math.round(dd); |
591 |
distances[i][j] = (ld >= Integer.MAX_VALUE)? |
592 |
Integer.MAX_VALUE : (int)ld; |
593 |
} |
594 |
} |
595 |
} |
596 |
|
597 |
/** |
598 |
* Returns the cached distance between a pair of cities |
599 |
*/ |
600 |
int distanceBetween(int i, int j) { |
601 |
return distances[i][j]; |
602 |
} |
603 |
|
604 |
// Scale ints to doubles in [0,1) |
605 |
static final double PSCALE = (double)0x80000000L; |
606 |
|
607 |
/** |
608 |
* Return distance for points scaled in [0,1). This simplifies |
609 |
* checking results. The expected optimal TSP for random |
610 |
* points is believed to be around 0.76 * sqrt(N). For papers |
611 |
* discussing this, see |
612 |
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
613 |
*/ |
614 |
double unitDistanceBetween(int i, int j) { |
615 |
double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE; |
616 |
double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE; |
617 |
return Math.hypot(dx, dy); |
618 |
} |
619 |
|
620 |
} |
621 |
|
622 |
/** |
623 |
* Cheap XorShift random number generator |
624 |
*/ |
625 |
static final class RNG { |
626 |
/** Seed generator for XorShift RNGs */ |
627 |
static final Random seedGenerator = new Random(); |
628 |
|
629 |
int seed; |
630 |
RNG(int seed) { this.seed = seed; } |
631 |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
632 |
|
633 |
int next() { |
634 |
int x = seed; |
635 |
x ^= x << 6; |
636 |
x ^= x >>> 21; |
637 |
x ^= x << 7; |
638 |
seed = x; |
639 |
return x; |
640 |
} |
641 |
} |
642 |
|
643 |
static final class ProgressMonitor extends Thread { |
644 |
final Population pop; |
645 |
ProgressMonitor(Population p) { pop = p; } |
646 |
public void run() { |
647 |
double time = 0; |
648 |
try { |
649 |
while (!Thread.interrupted()) { |
650 |
sleep(SNAPSHOT_RATE); |
651 |
time += SNAPSHOT_RATE; |
652 |
pop.printSnapshot(time / 1000.0); |
653 |
} |
654 |
} catch (InterruptedException ie) {} |
655 |
} |
656 |
} |
657 |
} |