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 |
4 |
> |
* explained at http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
|
import java.util.*; |
14 |
|
* genetic algorithm using an Exchanger. A population of chromosomes is |
15 |
|
* distributed among "subpops". Each chromosomes represents a tour, |
16 |
|
* and its fitness is the total tour length. |
17 |
< |
* |
17 |
> |
* |
18 |
|
* A set of worker threads perform updates on subpops. The basic |
19 |
|
* update step is: |
20 |
|
* <ol> |
21 |
|
* <li> Select a breeder b from the subpop |
22 |
|
* <li> Create a strand of its tour with a random starting point and length |
23 |
< |
* <li> Offer the strand to the exchanger, receiving a strand from |
23 |
> |
* <li> Offer the strand to the exchanger, receiving a strand from |
24 |
|
* another subpop |
25 |
< |
* <li> Combine b and the received strand using crossing function to |
25 |
> |
* <li> Combine b and the received strand using crossing function to |
26 |
|
* create new chromosome c. |
27 |
|
* <li> Replace a chromosome in the subpop with c. |
28 |
|
* </ol> |
39 |
|
static final int NCPUS = Runtime.getRuntime().availableProcessors(); |
40 |
|
|
41 |
|
/** Runs start with two threads, increasing by two through max */ |
42 |
< |
static final int DEFAULT_MAX_THREADS = Math.max(4, NCPUS + NCPUS/2); |
42 |
> |
static final int DEFAULT_MAX_THREADS = Math.max(4, NCPUS + NCPUS/2); |
43 |
|
|
44 |
|
/** The number of replication runs per thread value */ |
45 |
|
static final int DEFAULT_REPLICATIONS = 3; |
54 |
|
*/ |
55 |
|
static final int DEFAULT_CITIES = 144; |
56 |
|
|
57 |
< |
// Tuning parameters. |
57 |
> |
// Tuning parameters. |
58 |
|
|
59 |
|
/** |
60 |
|
* The number of chromosomes per subpop. Must be a power of two. |
62 |
|
* Smaller values lead to faster iterations but poorer quality |
63 |
|
* results |
64 |
|
*/ |
65 |
< |
static final int DEFAULT_SUBPOP_SIZE = 32; |
65 |
> |
static final int DEFAULT_SUBPOP_SIZE = 32; |
66 |
|
|
67 |
|
/** |
68 |
|
* The number of iterations per subpop. Convergence appears |
86 |
|
static final int MIN_STRAND_LENGTH = 3; |
87 |
|
|
88 |
|
/** |
89 |
< |
* The probablility mask value for creating random strands, |
89 |
> |
* The probability mask value for creating random strands, |
90 |
|
* that have lengths at least MIN_STRAND_LENGTH, and grow |
91 |
< |
* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) |
91 |
> |
* with exponential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) |
92 |
|
* Must be 1 less than a power of two. |
93 |
|
*/ |
94 |
|
static final int RANDOM_STRAND_MASK = 7; |
95 |
|
|
96 |
|
/** |
97 |
< |
* Probablility control for selecting breeders. |
97 |
> |
* Probability control for selecting breeders. |
98 |
|
* Breeders are selected starting at the best-fitness chromosome, |
99 |
< |
* with exponentially decaying probablility |
100 |
< |
* 1 / (subpopSize >>> BREEDER_DECAY). |
99 |
> |
* with exponentially decaying probability |
100 |
> |
* 1 / (subpopSize >>> BREEDER_DECAY). |
101 |
|
* |
102 |
|
* Larger values usually cause faster convergence but poorer |
103 |
|
* quality results |
105 |
|
static final int BREEDER_DECAY = 1; |
106 |
|
|
107 |
|
/** |
108 |
< |
* Probablility control for selecting dyers. |
108 |
> |
* Probability control for selecting dyers. |
109 |
|
* Dyers are selected starting at the worst-fitness chromosome, |
110 |
< |
* with exponentially decaying probablility |
110 |
> |
* with exponentially decaying probability |
111 |
|
* 1 / (subpopSize >>> DYER_DECAY) |
112 |
|
* |
113 |
|
* Larger values usually cause faster convergence but poorer |
119 |
|
* The set of cities. Created once per program run, to |
120 |
|
* make it easier to compare solutions across different runs. |
121 |
|
*/ |
122 |
< |
static CitySet cities; |
122 |
> |
static CitySet cities; |
123 |
|
|
124 |
|
public static void main(String[] args) throws Exception { |
125 |
|
int maxThreads = DEFAULT_MAX_THREADS; |
201 |
|
} |
202 |
|
|
203 |
|
/** |
204 |
< |
* Perform one run with the given parameters. Each run complete |
204 |
> |
* Performs one run with the given parameters. Each run completes |
205 |
|
* when there are fewer than 2 active threads. When there is |
206 |
|
* only one remaining thread, it will have no one to exchange |
207 |
|
* with, so it is terminated (via interrupt). |
208 |
|
*/ |
209 |
< |
static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) |
209 |
> |
static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) |
210 |
|
throws InterruptedException { |
211 |
|
Population p = new Population(nThreads, nSubpops, subpopSize, nGen); |
212 |
|
ProgressMonitor mon = null; |
225 |
|
// Thread.sleep(100); |
226 |
|
|
227 |
|
long elapsed = stopTime - startTime; |
228 |
< |
double secs = (double)elapsed / 1000000000.0; |
228 |
> |
double secs = (double) elapsed / 1000000000.0; |
229 |
|
p.printSnapshot(secs); |
230 |
|
} |
231 |
|
|
232 |
– |
|
232 |
|
/** |
233 |
|
* A Population creates the subpops, subpops, and threads for a run |
234 |
|
* and has control methods to start, stop, and report progress. |
263 |
|
|
264 |
|
void start() { |
265 |
|
for (int i = 0; i < nThreads; ++i) { |
266 |
< |
threads[i].start(); |
266 |
> |
threads[i].start(); |
267 |
|
} |
268 |
|
} |
269 |
|
|
284 |
|
|
285 |
|
int totalExchanges() { |
286 |
|
int xs = 0; |
287 |
< |
for (int i = 0; i < threads.length; ++i) |
287 |
> |
for (int i = 0; i < threads.length; ++i) |
288 |
|
xs += threads[i].exchanges; |
289 |
|
return xs; |
290 |
|
} |
299 |
|
*/ |
300 |
|
void printSnapshot(double secs) { |
301 |
|
int xs = totalExchanges(); |
302 |
< |
long rate = (xs == 0)? 0L : (long)((secs * 1000000000.0) / xs); |
302 |
> |
long rate = (xs == 0) ? 0L : (long) ((secs * 1000000000.0) / xs); |
303 |
|
Chromosome bestc = subpops[0].chromosomes[0]; |
304 |
|
Chromosome worstc = bestc; |
305 |
|
for (int k = 0; k < subpops.length; ++k) { |
361 |
|
} |
362 |
|
|
363 |
|
/** |
364 |
< |
* A Subpop maintains a set of chromosomes.. |
364 |
> |
* A Subpop maintains a set of chromosomes. |
365 |
|
*/ |
366 |
|
static final class Subpop { |
367 |
|
/** The chromosomes, kept in sorted order */ |
405 |
|
* other. It is hardwired because small variations of it |
406 |
|
* don't matter much. |
407 |
|
* |
408 |
< |
* @param g the first generation to run. |
408 |
> |
* @param g the first generation to run |
409 |
|
*/ |
410 |
|
int runUpdates() throws InterruptedException { |
411 |
|
int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); |
415 |
|
} |
416 |
|
|
417 |
|
/** |
418 |
< |
* Choose a breeder, exchange strand with another subpop, and |
419 |
< |
* cross them to create new chromosome to replace a chosen |
418 |
> |
* Chooses a breeder, exchanges strand with another subpop, and |
419 |
> |
* crosses them to create new chromosome to replace a chosen |
420 |
|
* dyer. |
421 |
|
*/ |
422 |
|
void update() throws InterruptedException { |
431 |
|
} |
432 |
|
|
433 |
|
/** |
434 |
< |
* Choose a breeder, with exponentially decreasing probability |
434 |
> |
* Chooses a breeder, with exponentially decreasing probability |
435 |
|
* starting at best. |
436 |
|
* @return index of selected breeder |
437 |
|
*/ |
446 |
|
} |
447 |
|
|
448 |
|
/** |
449 |
< |
* Choose a chromosome that will be replaced, with |
450 |
< |
* exponentially decreasing probablility starting at |
451 |
< |
* worst, ignoring the excluded index |
449 |
> |
* Chooses a chromosome that will be replaced, with |
450 |
> |
* exponentially decreasing probability starting at |
451 |
> |
* worst, ignoring the excluded index. |
452 |
|
* @param exclude index to ignore; use -1 to not exclude any |
453 |
|
* @return index of selected dyer |
454 |
|
*/ |
462 |
|
return d; |
463 |
|
} |
464 |
|
|
465 |
< |
/** |
465 |
> |
/** |
466 |
|
* Select a random strand of b's. |
467 |
|
* @param breeder the breeder |
468 |
|
*/ |
483 |
|
} |
484 |
|
|
485 |
|
/** |
486 |
< |
* Copy current strand to start of c's, and then append all |
486 |
> |
* Copies current strand to start of c's, and then appends all |
487 |
|
* remaining b's that aren't in the strand. |
488 |
|
* @param breeder the breeder |
489 |
|
* @param child the child |
507 |
|
int first = cs[0]; |
508 |
|
int j = 0; |
509 |
|
int[] bs = breeder.alleles; |
510 |
< |
while (bs[j] != first) |
510 |
> |
while (bs[j] != first) |
511 |
|
++j; |
512 |
|
|
513 |
|
// Append remaining b's that aren't already in tour |
516 |
|
int x = bs[j]; |
517 |
|
if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) |
518 |
|
cs[i++] = x; |
519 |
< |
} |
519 |
> |
} |
520 |
|
|
521 |
|
} |
522 |
|
|
523 |
|
/** |
524 |
< |
* Fix the sort order of a changed Chromosome c at position k |
524 |
> |
* Fixes the sort order of a changed Chromosome c at position k. |
525 |
|
* @param c the chromosome |
526 |
< |
* @param k the index |
526 |
> |
* @param k the index |
527 |
|
*/ |
528 |
|
void fixOrder(Chromosome c, int k) { |
529 |
|
Chromosome[] cs = chromosomes; |
559 |
|
/** Total tour length */ |
560 |
|
int fitness; |
561 |
|
|
562 |
< |
/** |
563 |
< |
* Initialize to random tour |
562 |
> |
/** |
563 |
> |
* Initializes to random tour. |
564 |
|
*/ |
565 |
|
Chromosome(int length, RNG random) { |
566 |
|
alleles = new int[length]; |
576 |
|
} |
577 |
|
|
578 |
|
public int compareTo(Object x) { // to enable sorting |
579 |
< |
int xf = ((Chromosome)x).fitness; |
579 |
> |
int xf = ((Chromosome) x).fitness; |
580 |
|
int f = fitness; |
581 |
< |
return ((f == xf)? 0 :((f < xf)? -1 : 1)); |
581 |
> |
return ((f == xf) ? 0 :((f < xf) ? -1 : 1)); |
582 |
|
} |
583 |
|
|
584 |
|
void recalcFitness() { |
591 |
|
f += cities.distanceBetween(p, n); |
592 |
|
p = n; |
593 |
|
} |
594 |
< |
fitness = (int)(f / len); |
594 |
> |
fitness = (int) (f / len); |
595 |
|
} |
596 |
|
|
597 |
|
/** |
598 |
< |
* Return tour length for points scaled in [0, 1). |
598 |
> |
* Returns tour length for points scaled in [0, 1). |
599 |
|
*/ |
600 |
|
double unitTourLength() { |
601 |
|
int[] a = alleles; |
611 |
|
} |
612 |
|
|
613 |
|
/** |
614 |
< |
* Check that this tour visits each city |
614 |
> |
* Checks that this tour visits each city. |
615 |
|
*/ |
616 |
< |
void validate() { |
616 |
> |
void validate() { |
617 |
|
int len = alleles.length; |
618 |
|
boolean[] used = new boolean[len]; |
619 |
< |
for (int i = 0; i < len; ++i) |
619 |
> |
for (int i = 0; i < len; ++i) |
620 |
|
used[alleles[i]] = true; |
621 |
< |
for (int i = 0; i < len; ++i) |
621 |
> |
for (int i = 0; i < len; ++i) |
622 |
|
if (!used[i]) |
623 |
|
throw new Error("Bad tour"); |
624 |
|
} |
637 |
|
} |
638 |
|
|
639 |
|
/** |
640 |
< |
* A collection of (x,y) points that represent cities. |
640 |
> |
* A collection of (x,y) points that represent cities. |
641 |
|
*/ |
642 |
|
static final class CitySet { |
643 |
|
|
660 |
|
|
661 |
|
for (int i = 0; i < n; i++) { |
662 |
|
for (int j = 0; j < n; j++) { |
663 |
< |
double dx = (double)xPts[i] - (double)xPts[j]; |
664 |
< |
double dy = (double)yPts[i] - (double)yPts[j]; |
663 |
> |
double dx = (double) xPts[i] - (double) xPts[j]; |
664 |
> |
double dy = (double) yPts[i] - (double) yPts[j]; |
665 |
|
double dd = Math.hypot(dx, dy) / 2.0; |
666 |
|
long ld = Math.round(dd); |
667 |
< |
distances[i][j] = (ld >= Integer.MAX_VALUE)? |
668 |
< |
Integer.MAX_VALUE : (int)ld; |
667 |
> |
distances[i][j] = (ld >= Integer.MAX_VALUE) ? |
668 |
> |
Integer.MAX_VALUE : (int) ld; |
669 |
|
} |
670 |
|
} |
671 |
|
} |
672 |
|
|
673 |
|
/** |
674 |
< |
* Returns the cached distance between a pair of cities |
674 |
> |
* Returns the cached distance between a pair of cities. |
675 |
|
*/ |
676 |
|
int distanceBetween(int i, int j) { |
677 |
|
return distances[i][j]; |
678 |
|
} |
679 |
|
|
680 |
|
// Scale ints to doubles in [0,1) |
681 |
< |
static final double PSCALE = (double)0x80000000L; |
681 |
> |
static final double PSCALE = (double) 0x80000000L; |
682 |
|
|
683 |
|
/** |
684 |
< |
* Return distance for points scaled in [0,1). This simplifies |
684 |
> |
* Returns distance for points scaled in [0,1). This simplifies |
685 |
|
* checking results. The expected optimal TSP for random |
686 |
|
* points is believed to be around 0.76 * sqrt(N). For papers |
687 |
|
* discussing this, see |
688 |
|
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
689 |
|
*/ |
690 |
|
double unitDistanceBetween(int i, int j) { |
691 |
< |
double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE; |
692 |
< |
double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE; |
691 |
> |
double dx = ((double) xPts[i] - (double) xPts[j]) / PSCALE; |
692 |
> |
double dy = ((double) yPts[i] - (double) yPts[j]) / PSCALE; |
693 |
|
return Math.hypot(dx, dy); |
694 |
|
} |
695 |
< |
|
695 |
> |
|
696 |
|
} |
697 |
|
|
698 |
|
/** |
704 |
|
|
705 |
|
int seed; |
706 |
|
RNG(int seed) { this.seed = seed; } |
707 |
< |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
707 |
> |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
708 |
|
|
709 |
|
int next() { |
710 |
|
int x = seed; |