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> |
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 |
97 |
|
* Probability control for selecting breeders. |
98 |
|
* Breeders are selected starting at the best-fitness chromosome, |
99 |
|
* with exponentially decaying probability |
100 |
< |
* 1 / (subpopSize >>> BREEDER_DECAY). |
100 |
> |
* 1 / (subpopSize >>> BREEDER_DECAY). |
101 |
|
* |
102 |
|
* Larger values usually cause faster convergence but poorer |
103 |
|
* quality results |
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; |
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; |
264 |
|
|
265 |
|
void start() { |
266 |
|
for (int i = 0; i < nThreads; ++i) { |
267 |
< |
threads[i].start(); |
267 |
> |
threads[i].start(); |
268 |
|
} |
269 |
|
} |
270 |
|
|
285 |
|
|
286 |
|
int totalExchanges() { |
287 |
|
int xs = 0; |
288 |
< |
for (int i = 0; i < threads.length; ++i) |
288 |
> |
for (int i = 0; i < threads.length; ++i) |
289 |
|
xs += threads[i].exchanges; |
290 |
|
return xs; |
291 |
|
} |
362 |
|
} |
363 |
|
|
364 |
|
/** |
365 |
< |
* A Subpop maintains a set of chromosomes.. |
365 |
> |
* A Subpop maintains a set of chromosomes.. |
366 |
|
*/ |
367 |
|
static final class Subpop { |
368 |
|
/** The chromosomes, kept in sorted order */ |
406 |
|
* other. It is hardwired because small variations of it |
407 |
|
* don't matter much. |
408 |
|
* |
409 |
< |
* @param g the first generation to run. |
409 |
> |
* @param g the first generation to run. |
410 |
|
*/ |
411 |
|
int runUpdates() throws InterruptedException { |
412 |
|
int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); |
463 |
|
return d; |
464 |
|
} |
465 |
|
|
466 |
< |
/** |
466 |
> |
/** |
467 |
|
* Select a random strand of b's. |
468 |
|
* @param breeder the breeder |
469 |
|
*/ |
508 |
|
int first = cs[0]; |
509 |
|
int j = 0; |
510 |
|
int[] bs = breeder.alleles; |
511 |
< |
while (bs[j] != first) |
511 |
> |
while (bs[j] != first) |
512 |
|
++j; |
513 |
|
|
514 |
|
// Append remaining b's that aren't already in tour |
517 |
|
int x = bs[j]; |
518 |
|
if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) |
519 |
|
cs[i++] = x; |
520 |
< |
} |
520 |
> |
} |
521 |
|
|
522 |
|
} |
523 |
|
|
524 |
|
/** |
525 |
|
* Fix the sort order of a changed Chromosome c at position k |
526 |
|
* @param c the chromosome |
527 |
< |
* @param k the index |
527 |
> |
* @param k the index |
528 |
|
*/ |
529 |
|
void fixOrder(Chromosome c, int k) { |
530 |
|
Chromosome[] cs = chromosomes; |
560 |
|
/** Total tour length */ |
561 |
|
int fitness; |
562 |
|
|
563 |
< |
/** |
563 |
> |
/** |
564 |
|
* Initialize to random tour |
565 |
|
*/ |
566 |
|
Chromosome(int length, RNG random) { |
614 |
|
/** |
615 |
|
* Check that this tour visits each city |
616 |
|
*/ |
617 |
< |
void validate() { |
617 |
> |
void validate() { |
618 |
|
int len = alleles.length; |
619 |
|
boolean[] used = new boolean[len]; |
620 |
< |
for (int i = 0; i < len; ++i) |
620 |
> |
for (int i = 0; i < len; ++i) |
621 |
|
used[alleles[i]] = true; |
622 |
< |
for (int i = 0; i < len; ++i) |
622 |
> |
for (int i = 0; i < len; ++i) |
623 |
|
if (!used[i]) |
624 |
|
throw new Error("Bad tour"); |
625 |
|
} |
638 |
|
} |
639 |
|
|
640 |
|
/** |
641 |
< |
* A collection of (x,y) points that represent cities. |
641 |
> |
* A collection of (x,y) points that represent cities. |
642 |
|
*/ |
643 |
|
static final class CitySet { |
644 |
|
|
665 |
|
double dy = (double)yPts[i] - (double)yPts[j]; |
666 |
|
double dd = Math.hypot(dx, dy) / 2.0; |
667 |
|
long ld = Math.round(dd); |
668 |
< |
distances[i][j] = (ld >= Integer.MAX_VALUE)? |
668 |
> |
distances[i][j] = (ld >= Integer.MAX_VALUE)? |
669 |
|
Integer.MAX_VALUE : (int)ld; |
670 |
|
} |
671 |
|
} |
693 |
|
double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE; |
694 |
|
return Math.hypot(dx, dy); |
695 |
|
} |
696 |
< |
|
696 |
> |
|
697 |
|
} |
698 |
|
|
699 |
|
/** |