| 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. Each chromosome is |
| 17 |
< |
* initialized as a random tour. A Task is associated with each pool. |
| 18 |
< |
* Each task repeatedly does, for a fixed number of iterations |
| 19 |
< |
* (generations): |
| 20 |
< |
* |
| 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 |
| 31 |
|
* |
| 32 |
|
*/ |
| 33 |
|
public class TSPExchangerTest { |
| 34 |
< |
static final int DEFAULT_MAX_THREADS = |
| 35 |
< |
(Runtime.getRuntime().availableProcessors() + 2); |
| 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 |
| 102 |
|
*/ |
| 103 |
|
static final int DYER_DECAY = 1; |
| 104 |
|
|
| 105 |
< |
/** |
| 107 |
< |
* The probability mask for a task to give up running and |
| 108 |
< |
* resubmit itself. On each iteration, a task stops iterating |
| 109 |
< |
* and resubmits itself with probability 1 / (RESUBMIT_MASK+1). |
| 110 |
< |
* This avoids some tasks running to completion before others |
| 111 |
< |
* even start when there are more pools than threads. |
| 112 |
< |
* |
| 113 |
< |
* Must be 1 less than a power of two. |
| 114 |
< |
*/ |
| 115 |
< |
static final int RESUBMIT_MASK = 63; |
| 116 |
< |
|
| 117 |
< |
static final boolean verbose = true; |
| 105 |
> |
static final boolean verbose = false; |
| 106 |
|
static final long SNAPSHOT_RATE = 10000; // in milliseconds |
| 107 |
|
|
| 108 |
|
/** |
| 169 |
|
|
| 170 |
|
/** |
| 171 |
|
* Perform one run with the given parameters. Each run completes |
| 172 |
< |
* when all but one of the tasks has finished. The last remaining |
| 173 |
< |
* task may have no one left to exchange with, so the pool is |
| 174 |
< |
* abruptly terminated. |
| 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 { |
| 218 |
|
this.nGen = nGen; |
| 219 |
|
this.poolSize = poolSize; |
| 220 |
|
this.exchanger = new Exchanger<Strand>(); |
| 221 |
< |
this.done = new CountDownLatch(nPools-1); |
| 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); |
| 256 |
|
* fewer than nGen iterations. |
| 257 |
|
*/ |
| 258 |
|
void resubmit(Task task) { |
| 259 |
< |
exec.execute(task); |
| 259 |
> |
try { |
| 260 |
> |
exec.execute(task); |
| 261 |
> |
} catch(RejectedExecutionException ignore) {} |
| 262 |
|
} |
| 263 |
|
|
| 264 |
|
void printSnapshot(double secs) { |
| 265 |
|
int gens = 0; |
| 266 |
< |
double best = Double.MAX_VALUE; |
| 267 |
< |
double worst = 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 |
< |
float b = cs[0].fitness; |
| 272 |
< |
if (b < best) |
| 273 |
< |
best = b; |
| 274 |
< |
float w = cs[cs.length-1].fitness; |
| 275 |
< |
if (w > worst) |
| 276 |
< |
worst = w; |
| 277 |
< |
} |
| 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:%9.3f Worst:%9.3f Gen:%6d Threads:%4d\n", |
| 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 |
|
|
| 292 |
– |
float averageFitness() { // currently unused |
| 293 |
– |
float total = 0; |
| 294 |
– |
int count = 0; |
| 295 |
– |
for (int k = 0; k < tasks.length; ++k) { |
| 296 |
– |
Chromosome[] cs = tasks[k].chromosomes; |
| 297 |
– |
for (int i = 0; i < cs.length; i++) |
| 298 |
– |
total += cs[i].fitness; |
| 299 |
– |
count += cs.length; |
| 300 |
– |
} |
| 301 |
– |
return total/(float)count; |
| 302 |
– |
} |
| 285 |
|
} |
| 286 |
|
|
| 287 |
|
/** |
| 300 |
|
final RNG rng; |
| 301 |
|
final int poolSize; |
| 302 |
|
final int nGen; |
| 303 |
+ |
final int genPerRun; |
| 304 |
|
int gen; |
| 305 |
|
|
| 306 |
|
Task(Population 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; |
| 321 |
|
} |
| 322 |
|
|
| 323 |
|
/** |
| 324 |
< |
* Run one or more update cycles. |
| 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 |
< |
for (;;) { |
| 333 |
> |
int maxGen = gen + 1 + rng.next() % genPerRun; |
| 334 |
> |
if (maxGen > nGen) |
| 335 |
> |
maxGen = nGen; |
| 336 |
> |
while (gen++ < maxGen) |
| 337 |
|
update(); |
| 338 |
< |
if (++gen >= nGen) { |
| 339 |
< |
pop.taskDone(); |
| 340 |
< |
return; |
| 341 |
< |
} |
| 350 |
< |
if ((rng.next() & RESUBMIT_MASK) == 1) { |
| 351 |
< |
pop.resubmit(this); |
| 352 |
< |
return; |
| 353 |
< |
} |
| 354 |
< |
} |
| 338 |
> |
if (maxGen < nGen) |
| 339 |
> |
pop.resubmit(this); |
| 340 |
> |
else |
| 341 |
> |
pop.taskDone(); |
| 342 |
|
} catch (InterruptedException ie) { |
| 343 |
|
pop.taskDone(); |
| 344 |
|
} |
| 457 |
|
*/ |
| 458 |
|
void fixOrder(Chromosome c, int k) { |
| 459 |
|
Chromosome[] cs = chromosomes; |
| 460 |
< |
float oldFitness = c.fitness; |
| 460 |
> |
int oldFitness = c.fitness; |
| 461 |
|
c.recalcFitness(); |
| 462 |
< |
float newFitness = c.fitness; |
| 462 |
> |
int newFitness = c.fitness; |
| 463 |
|
if (newFitness < oldFitness) { |
| 464 |
|
int j = k; |
| 465 |
|
int p = j - 1; |
| 487 |
|
/** Index of cities in tour order */ |
| 488 |
|
final int[] alleles; |
| 489 |
|
/** Total tour length */ |
| 490 |
< |
float fitness; |
| 490 |
> |
int fitness; |
| 491 |
|
|
| 492 |
|
/** |
| 493 |
|
* Initialize to random tour |
| 506 |
|
} |
| 507 |
|
|
| 508 |
|
public int compareTo(Object x) { // to enable sorting |
| 509 |
< |
float xf = ((Chromosome)x).fitness; |
| 510 |
< |
float f = fitness; |
| 509 |
> |
int xf = ((Chromosome)x).fitness; |
| 510 |
> |
int f = fitness; |
| 511 |
|
return ((f == xf)? 0 :((f < xf)? -1 : 1)); |
| 512 |
|
} |
| 513 |
|
|
| 515 |
|
int[] a = alleles; |
| 516 |
|
int len = a.length; |
| 517 |
|
int p = a[0]; |
| 518 |
< |
float f = cities.distanceBetween(a[len-1], p); |
| 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 = f; |
| 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. |
| 561 |
|
} |
| 562 |
|
|
| 563 |
|
/** |
| 564 |
< |
* A collection of (x,y) points that represent cities. Distances |
| 565 |
< |
* are scaled in [0,1) to simply checking results. The expected |
| 566 |
< |
* optimal TSP for random points is believed to be around 0.76 * |
| 567 |
< |
* sqrt(N). For papers discussing this, see |
| 568 |
< |
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html for |
| 564 |
> |
* A collection of (x,y) points that represent cities. |
| 565 |
|
*/ |
| 566 |
|
static final class CitySet { |
| 571 |
– |
// Scale ints to doubles in [0,1) |
| 572 |
– |
static final double PSCALE = (double)0x80000000L; |
| 567 |
|
|
| 568 |
|
final int length; |
| 569 |
|
final int[] xPts; |
| 570 |
|
final int[] yPts; |
| 571 |
< |
final float[][] distances; |
| 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 float[n][n]; |
| 577 |
> |
this.distances = new int[n][n]; |
| 578 |
|
|
| 579 |
|
RNG random = new RNG(); |
| 580 |
|
for (int i = 0; i < n; i++) { |
| 584 |
|
|
| 585 |
|
for (int i = 0; i < n; i++) { |
| 586 |
|
for (int j = 0; j < n; j++) { |
| 587 |
< |
double dX = (xPts[i] - xPts[j]) / PSCALE; |
| 588 |
< |
double dY = (yPts[i] - yPts[j]) / PSCALE; |
| 589 |
< |
distances[i][j] = (float)Math.hypot(dX, dY); |
| 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 |
< |
// Retrieve the cached distance between a pair of cities |
| 598 |
< |
float distanceBetween(int i, int j) { |
| 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 |
|
/** |
| 628 |
|
|
| 629 |
|
int seed; |
| 630 |
|
RNG(int seed) { this.seed = seed; } |
| 631 |
< |
RNG() { this.seed = seedGenerator.nextInt(); } |
| 631 |
> |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
| 632 |
|
|
| 633 |
|
int next() { |
| 634 |
|
int x = seed; |
