--- jsr166/src/test/loops/TSPExchangerTest.java 2006/02/13 12:39:23 1.4 +++ jsr166/src/test/loops/TSPExchangerTest.java 2011/12/05 04:08:46 1.13 @@ -1,7 +1,7 @@ /* * Written by Doug Lea and Bill Scherer with assistance from members * of JCP JSR-166 Expert Group and released to the public domain, as - * explained at http://creativecommons.org/licenses/publicdomain + * explained at http://creativecommons.org/publicdomain/zero/1.0/ */ import java.util.*; @@ -14,15 +14,15 @@ import java.util.concurrent.locks.*; * genetic algorithm using an Exchanger. A population of chromosomes is * distributed among "subpops". Each chromosomes represents a tour, * and its fitness is the total tour length. - * + * * A set of worker threads perform updates on subpops. The basic * update step is: *
    *
  1. Select a breeder b from the subpop *
  2. Create a strand of its tour with a random starting point and length - *
  3. Offer the strand to the exchanger, receiving a strand from + *
  4. Offer the strand to the exchanger, receiving a strand from * another subpop - *
  5. Combine b and the received strand using crossing function to + *
  6. Combine b and the received strand using crossing function to * create new chromosome c. *
  7. Replace a chromosome in the subpop with c. *
@@ -54,7 +54,7 @@ public class TSPExchangerTest { */ static final int DEFAULT_CITIES = 144; - // Tuning parameters. + // Tuning parameters. /** * The number of chromosomes per subpop. Must be a power of two. @@ -62,7 +62,7 @@ public class TSPExchangerTest { * Smaller values lead to faster iterations but poorer quality * results */ - static final int DEFAULT_SUBPOP_SIZE = 32; + static final int DEFAULT_SUBPOP_SIZE = 32; /** * The number of iterations per subpop. Convergence appears @@ -86,18 +86,18 @@ public class TSPExchangerTest { static final int MIN_STRAND_LENGTH = 3; /** - * The probablility mask value for creating random strands, + * The probability mask value for creating random strands, * that have lengths at least MIN_STRAND_LENGTH, and grow - * with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) + * with exponential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) * Must be 1 less than a power of two. */ static final int RANDOM_STRAND_MASK = 7; /** - * Probablility control for selecting breeders. + * Probability control for selecting breeders. * Breeders are selected starting at the best-fitness chromosome, - * with exponentially decaying probablility - * 1 / (subpopSize >>> BREEDER_DECAY). + * with exponentially decaying probability + * 1 / (subpopSize >>> BREEDER_DECAY). * * Larger values usually cause faster convergence but poorer * quality results @@ -105,9 +105,9 @@ public class TSPExchangerTest { static final int BREEDER_DECAY = 1; /** - * Probablility control for selecting dyers. + * Probability control for selecting dyers. * Dyers are selected starting at the worst-fitness chromosome, - * with exponentially decaying probablility + * with exponentially decaying probability * 1 / (subpopSize >>> DYER_DECAY) * * Larger values usually cause faster convergence but poorer @@ -119,7 +119,7 @@ public class TSPExchangerTest { * The set of cities. Created once per program run, to * make it easier to compare solutions across different runs. */ - static CitySet cities; + static CitySet cities; public static void main(String[] args) throws Exception { int maxThreads = DEFAULT_MAX_THREADS; @@ -206,7 +206,7 @@ public class TSPExchangerTest { * only one remaining thread, it will have no one to exchange * with, so it is terminated (via interrupt). */ - static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) + static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) throws InterruptedException { Population p = new Population(nThreads, nSubpops, subpopSize, nGen); ProgressMonitor mon = null; @@ -225,7 +225,7 @@ public class TSPExchangerTest { // Thread.sleep(100); long elapsed = stopTime - startTime; - double secs = (double)elapsed / 1000000000.0; + double secs = (double) elapsed / 1000000000.0; p.printSnapshot(secs); } @@ -264,7 +264,7 @@ public class TSPExchangerTest { void start() { for (int i = 0; i < nThreads; ++i) { - threads[i].start(); + threads[i].start(); } } @@ -285,7 +285,7 @@ public class TSPExchangerTest { int totalExchanges() { int xs = 0; - for (int i = 0; i < threads.length; ++i) + for (int i = 0; i < threads.length; ++i) xs += threads[i].exchanges; return xs; } @@ -300,7 +300,7 @@ public class TSPExchangerTest { */ void printSnapshot(double secs) { int xs = totalExchanges(); - long rate = (xs == 0)? 0L : (long)((secs * 1000000000.0) / xs); + long rate = (xs == 0) ? 0L : (long) ((secs * 1000000000.0) / xs); Chromosome bestc = subpops[0].chromosomes[0]; Chromosome worstc = bestc; for (int k = 0; k < subpops.length; ++k) { @@ -362,7 +362,7 @@ public class TSPExchangerTest { } /** - * A Subpop maintains a set of chromosomes.. + * A Subpop maintains a set of chromosomes.. */ static final class Subpop { /** The chromosomes, kept in sorted order */ @@ -406,7 +406,7 @@ public class TSPExchangerTest { * other. It is hardwired because small variations of it * don't matter much. * - * @param g the first generation to run. + * @param g the first generation to run. */ int runUpdates() throws InterruptedException { int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); @@ -448,7 +448,7 @@ public class TSPExchangerTest { /** * Choose a chromosome that will be replaced, with - * exponentially decreasing probablility starting at + * exponentially decreasing probability starting at * worst, ignoring the excluded index * @param exclude index to ignore; use -1 to not exclude any * @return index of selected dyer @@ -463,7 +463,7 @@ public class TSPExchangerTest { return d; } - /** + /** * Select a random strand of b's. * @param breeder the breeder */ @@ -508,7 +508,7 @@ public class TSPExchangerTest { int first = cs[0]; int j = 0; int[] bs = breeder.alleles; - while (bs[j] != first) + while (bs[j] != first) ++j; // Append remaining b's that aren't already in tour @@ -517,14 +517,14 @@ public class TSPExchangerTest { int x = bs[j]; if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) cs[i++] = x; - } + } } /** * Fix the sort order of a changed Chromosome c at position k * @param c the chromosome - * @param k the index + * @param k the index */ void fixOrder(Chromosome c, int k) { Chromosome[] cs = chromosomes; @@ -560,7 +560,7 @@ public class TSPExchangerTest { /** Total tour length */ int fitness; - /** + /** * Initialize to random tour */ Chromosome(int length, RNG random) { @@ -577,9 +577,9 @@ public class TSPExchangerTest { } public int compareTo(Object x) { // to enable sorting - int xf = ((Chromosome)x).fitness; + int xf = ((Chromosome) x).fitness; int f = fitness; - return ((f == xf)? 0 :((f < xf)? -1 : 1)); + return ((f == xf) ? 0 :((f < xf) ? -1 : 1)); } void recalcFitness() { @@ -592,7 +592,7 @@ public class TSPExchangerTest { f += cities.distanceBetween(p, n); p = n; } - fitness = (int)(f / len); + fitness = (int) (f / len); } /** @@ -614,12 +614,12 @@ public class TSPExchangerTest { /** * Check that this tour visits each city */ - void validate() { + void validate() { int len = alleles.length; boolean[] used = new boolean[len]; - for (int i = 0; i < len; ++i) + for (int i = 0; i < len; ++i) used[alleles[i]] = true; - for (int i = 0; i < len; ++i) + for (int i = 0; i < len; ++i) if (!used[i]) throw new Error("Bad tour"); } @@ -638,7 +638,7 @@ public class TSPExchangerTest { } /** - * A collection of (x,y) points that represent cities. + * A collection of (x,y) points that represent cities. */ static final class CitySet { @@ -661,39 +661,39 @@ public class TSPExchangerTest { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - double dx = (double)xPts[i] - (double)xPts[j]; - double dy = (double)yPts[i] - (double)yPts[j]; + double dx = (double) xPts[i] - (double) xPts[j]; + double dy = (double) yPts[i] - (double) yPts[j]; double dd = Math.hypot(dx, dy) / 2.0; long ld = Math.round(dd); - distances[i][j] = (ld >= Integer.MAX_VALUE)? - Integer.MAX_VALUE : (int)ld; + distances[i][j] = (ld >= Integer.MAX_VALUE) ? + Integer.MAX_VALUE : (int) ld; } } } /** - * Returns the cached distance between a pair of cities + * Returns the cached distance between a pair of cities. */ int distanceBetween(int i, int j) { return distances[i][j]; } // Scale ints to doubles in [0,1) - static final double PSCALE = (double)0x80000000L; + static final double PSCALE = (double) 0x80000000L; /** - * Return distance for points scaled in [0,1). This simplifies + * Returns distance for points scaled in [0,1). This simplifies * checking results. The expected optimal TSP for random * points is believed to be around 0.76 * sqrt(N). For papers * discussing this, see * http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html */ double unitDistanceBetween(int i, int j) { - double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE; - double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE; + double dx = ((double) xPts[i] - (double) xPts[j]) / PSCALE; + double dy = ((double) yPts[i] - (double) yPts[j]) / PSCALE; return Math.hypot(dx, dy); } - + } /** @@ -705,7 +705,7 @@ public class TSPExchangerTest { int seed; RNG(int seed) { this.seed = seed; } - RNG() { this.seed = seedGenerator.nextInt() | 1; } + RNG() { this.seed = seedGenerator.nextInt() | 1; } int next() { int x = seed;