--- jsr166/src/test/loops/TSPExchangerTest.java 2005/12/10 20:08:51 1.2 +++ jsr166/src/test/loops/TSPExchangerTest.java 2015/01/15 18:34:19 1.18 @@ -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.*; @@ -11,30 +11,42 @@ import java.util.concurrent.locks.*; /** * A parallel Traveling Salesperson Problem (TSP) program based on a - * genetic algorithm using an Exchanger. A population of chromosomes - * is distributed among "pools". The chromosomes represent tours, and - * their fitness is the total tour length. Each chromosome is - * initialized as a random tour. A Task is associated with each pool. - * Each task repeatedly does, for a fixed number of iterations - * (generations): + * 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 pool + *
  2. Select a breeder b from the subpop *
  3. Create a strand of its tour with a random starting point and length - *
  4. Offer the strand to the exchanger, receiving a strand from - * another pool - *
  5. Combine b and the received strand using crossing function to + *
  6. Offer the strand to the exchanger, receiving a strand from + * another subpop + *
  7. Combine b and the received strand using crossing function to * create new chromosome c. - *
  8. Replace a chromosome in the pool with c. + *
  9. Replace a chromosome in the subpop with c. *
* + * This continues for a given number of generations per subpop. + * Because there are normally more subpops than threads, each worker + * thread performs small (randomly sized) run of updates for one + * subpop and then selects another. A run continues until there is at + * most one remaining thread performing updates. + * * See below for more details. - *

- * */ public class TSPExchangerTest { - static final int DEFAULT_MAX_THREADS = - (Runtime.getRuntime().availableProcessors() + 2); + static final int NCPUS = Runtime.getRuntime().availableProcessors(); + + /** Runs start with two threads, increasing by two through max */ + static final int DEFAULT_MAX_THREADS = Math.max(4, NCPUS + NCPUS/2); + + /** The number of replication runs per thread value */ + static final int DEFAULT_REPLICATIONS = 3; + + /** If true, print statistics in SNAPSHOT_RATE intervals */ + static boolean verbose = true; + static final long SNAPSHOT_RATE = 10000; // in milliseconds /** * The problem size. Each city is a random point. The goal is to @@ -42,30 +54,30 @@ public class TSPExchangerTest { */ static final int DEFAULT_CITIES = 144; - // Tuning parameters. + // Tuning parameters. /** - * The number of chromosomes per pool. Must be a power of two. + * The number of chromosomes per subpop. Must be a power of two. * * Smaller values lead to faster iterations but poorer quality * results */ - static final int DEFAULT_POOL_SIZE = 32; + static final int DEFAULT_SUBPOP_SIZE = 32; /** - * The number of iterations per task. Convergence appears + * The number of iterations per subpop. Convergence appears * to be roughly proportional to #cities-squared */ static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES; /** - * The number of pools. The total population is #pools * poolSize, + * The number of subpops. The total population is #subpops * subpopSize, * which should be roughly on the order of #cities-squared * * Smaller values lead to faster total runs but poorer quality * results */ - static final int DEFAULT_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE; + static final int DEFAULT_NSUBPOPS = DEFAULT_GENERATIONS / DEFAULT_SUBPOP_SIZE; /** * The minimum length for a random chromosome strand. @@ -74,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 / (poolSize >>> BREEDER_DECAY). + * with exponentially decaying probability + * 1 / (subpopSize >>> BREEDER_DECAY). * * Larger values usually cause faster convergence but poorer * quality results @@ -93,10 +105,10 @@ 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 - * 1 / (poolSize >>> DYER_DECAY) + * with exponentially decaying probability + * 1 / (subpopSize >>> DYER_DECAY) * * Larger values usually cause faster convergence but poorer * quality results @@ -104,31 +116,18 @@ public class TSPExchangerTest { static final int DYER_DECAY = 1; /** - * The probability mask for a task to give up running and - * resubmit itself. On each iteration, a task stops iterating - * and resubmits itself with probability 1 / (RESUBMIT_MASK+1). - * This avoids some tasks running to completion before others - * even start when there are more pools than threads. - * - * Must be 1 less than a power of two. - */ - static final int RESUBMIT_MASK = 63; - - static final boolean verbose = true; - static final long SNAPSHOT_RATE = 10000; // in milliseconds - - /** * 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; int nCities = DEFAULT_CITIES; - int poolSize = DEFAULT_POOL_SIZE; + int subpopSize = DEFAULT_SUBPOP_SIZE; int nGen = nCities * nCities; - int nPools = nCities * nCities / poolSize; + int nSubpops = nCities * nCities / subpopSize; + int nReps = DEFAULT_REPLICATIONS; try { int argc = 0; @@ -137,14 +136,20 @@ public class TSPExchangerTest { if (option.equals("-c")) { nCities = Integer.parseInt(args[argc]); nGen = nCities * nCities; - nPools = nCities * nCities / poolSize; + nSubpops = nCities * nCities / subpopSize; } else if (option.equals("-p")) - poolSize = Integer.parseInt(args[argc]); + subpopSize = Integer.parseInt(args[argc]); else if (option.equals("-g")) nGen = Integer.parseInt(args[argc]); else if (option.equals("-n")) - nPools = Integer.parseInt(args[argc]); + nSubpops = Integer.parseInt(args[argc]); + else if (option.equals("-q")) { + verbose = false; + argc--; + } + else if (option.equals("-r")) + nReps = Integer.parseInt(args[argc]); else maxThreads = Integer.parseInt(option); argc++; @@ -157,209 +162,261 @@ public class TSPExchangerTest { System.out.print("TSPExchangerTest"); System.out.print(" -c " + nCities); System.out.print(" -g " + nGen); - System.out.print(" -p " + poolSize); - System.out.print(" -n " + nPools); + System.out.print(" -p " + subpopSize); + System.out.print(" -n " + nSubpops); + System.out.print(" -r " + nReps); System.out.print(" max threads " + maxThreads); System.out.println(); cities = new CitySet(nCities); - for (int i = 2; i <= maxThreads; i += 2) - oneRun(i, nPools, poolSize, nGen); + if (false && NCPUS > 4) { + int h = NCPUS/2; + System.out.printf("Threads: %4d Warmup\n", h); + oneRun(h, nSubpops, subpopSize, nGen); + Thread.sleep(500); + } + + int maxt = (maxThreads < nSubpops) ? maxThreads : nSubpops; + for (int j = 0; j < nReps; ++j) { + for (int i = 2; i <= maxt; i += 2) { + System.out.printf("Threads: %4d Replication: %2d\n", i, j); + oneRun(i, nSubpops, subpopSize, nGen); + Thread.sleep(500); + } + } } static void reportUsageErrorAndDie() { System.out.print("usage: TSPExchangerTest"); System.out.print(" [-c #cities]"); - System.out.print(" [-p #poolSize]"); + System.out.print(" [-p #subpopSize]"); System.out.print(" [-g #generations]"); - System.out.print(" [-n #pools]"); + System.out.print(" [-n #subpops]"); + System.out.print(" [-r #replications]"); + System.out.print(" [-q ]"); System.out.print(" #threads]"); System.out.println(); System.exit(0); } /** - * Perform one run with the given parameters. Each run completes - * when all but one of the tasks has finished. The last remaining - * task may have no one left to exchange with, so the pool is - * abruptly terminated. + * Performs one run with the given parameters. Each run completes + * when there are fewer than 2 active threads. When there is + * only one remaining thread, it will have no one to exchange + * with, so it is terminated (via interrupt). */ - static void oneRun(int nThreads, int nPools, int poolSize, int nGen) + static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) throws InterruptedException { - Population p = new Population(nThreads, nPools, poolSize, nGen); + Population p = new Population(nThreads, nSubpops, subpopSize, nGen); ProgressMonitor mon = null; if (verbose) { + p.printSnapshot(0); mon = new ProgressMonitor(p); mon.start(); } - p.printSnapshot(0); long startTime = System.nanoTime(); p.start(); - p.awaitTasks(); + p.awaitDone(); long stopTime = System.nanoTime(); if (mon != null) mon.interrupt(); p.shutdown(); - Thread.sleep(100); + // Thread.sleep(100); long elapsed = stopTime - startTime; - long rate = elapsed / (nPools * nGen); - double secs = (double)elapsed / 1000000000.0; + double secs = (double) elapsed / 1000000000.0; p.printSnapshot(secs); - System.out.printf("%10d ns per transfer\n", rate); } - /** - * A Population creates the pools, tasks, and threads for a run + * A Population creates the subpops, subpops, and threads for a run * and has control methods to start, stop, and report progress. */ static final class Population { - final Task[] tasks; + final Worker[] threads; + final Subpop[] subpops; final Exchanger exchanger; - final ThreadPoolExecutor exec; final CountDownLatch done; final int nGen; - final int poolSize; + final int subpopSize; final int nThreads; - Population(int nThreads, int nPools, int poolSize, int nGen) { + Population(int nThreads, int nSubpops, int subpopSize, int nGen) { this.nThreads = nThreads; this.nGen = nGen; - this.poolSize = poolSize; + this.subpopSize = subpopSize; this.exchanger = new Exchanger(); - this.done = new CountDownLatch(nPools-1); - this.tasks = new Task[nPools]; - for (int i = 0; i < nPools; i++) - tasks[i] = new Task(this); - BlockingQueue tq = - new LinkedBlockingQueue(); - this.exec = new ThreadPoolExecutor(nThreads, nThreads, - 0L, TimeUnit.MILLISECONDS, - tq); - exec.prestartAllCoreThreads(); + this.done = new CountDownLatch(nThreads - 1); + + this.subpops = new Subpop[nSubpops]; + for (int i = 0; i < nSubpops; i++) + subpops[i] = new Subpop(this); + + this.threads = new Worker[nThreads]; + int maxExchanges = nGen * nSubpops / nThreads; + for (int i = 0; i < nThreads; ++i) { + threads[i] = new Worker(this, maxExchanges); + } + } - /** Start the tasks */ void start() { - for (int i = 0; i < tasks.length; i++) - exec.execute(tasks[i]); + for (int i = 0; i < nThreads; ++i) { + threads[i].start(); + } } /** Stop the tasks */ void shutdown() { - exec.shutdownNow(); + for (int i = 0; i < threads.length; ++ i) + threads[i].interrupt(); } - /** Called by task upon terminations */ - void taskDone() { + void threadDone() { done.countDown(); } - /** Wait for (all but one) task to complete */ - void awaitTasks() throws InterruptedException { + /** Wait for tasks to complete */ + void awaitDone() throws InterruptedException { done.await(); } - /** - * Called by a task to resubmit itself after completing - * fewer than nGen iterations. - */ - void resubmit(Task task) { - exec.execute(task); + int totalExchanges() { + int xs = 0; + for (int i = 0; i < threads.length; ++i) + xs += threads[i].exchanges; + return xs; } + /** + * Prints statistics, including best and worst tour lengths + * for points scaled in [0,1), scaled by the square root of + * number of points. 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 + */ void printSnapshot(double secs) { - int gens = 0; - double best = Double.MAX_VALUE; - double worst = 0; - for (int k = 0; k < tasks.length; ++k) { - gens += tasks[k].gen; - Chromosome[] cs = tasks[k].chromosomes; - float b = cs[0].fitness; - if (b < best) - best = b; - float w = cs[cs.length-1].fitness; - if (w > worst) - worst = w; - } - int avegen = (done.getCount() == 0)? nGen : gens / tasks.length; - System.out.printf("Time:%9.3f Best:%9.3f Worst:%9.3f Gen:%6d Threads:%4d\n", - secs, best, worst, avegen, nThreads); - } - - float averageFitness() { // currently unused - float total = 0; - int count = 0; - for (int k = 0; k < tasks.length; ++k) { - Chromosome[] cs = tasks[k].chromosomes; - for (int i = 0; i < cs.length; i++) - total += cs[i].fitness; - count += cs.length; + int xs = totalExchanges(); + 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) { + Chromosome[] cs = subpops[k].chromosomes; + if (cs[0].fitness < bestc.fitness) + bestc = cs[0]; + int w = cs[cs.length-1].fitness; + if (cs[cs.length-1].fitness > worstc.fitness) + worstc = cs[cs.length-1]; + } + double sqrtn = Math.sqrt(cities.length); + double best = bestc.unitTourLength() / sqrtn; + double worst = worstc.unitTourLength() / sqrtn; + System.out.printf("N:%4d T:%8.3f B:%6.3f W:%6.3f X:%9d R:%7d\n", + nThreads, secs, best, worst, xs, rate); + // exchanger.printStats(); + // System.out.print(" s: " + exchanger.aveSpins()); + // System.out.print(" p: " + exchanger.aveParks()); + } + } + + /** + * Worker threads perform updates on subpops. + */ + static final class Worker extends Thread { + final Population pop; + final int maxExchanges; + int exchanges; + final RNG rng = new RNG(); + + Worker(Population pop, int maxExchanges) { + this.pop = pop; + this.maxExchanges = maxExchanges; + } + + /** + * Repeatedly, find a subpop that is not being updated by + * another thread, and run a random number of updates on it. + */ + public void run() { + try { + int len = pop.subpops.length; + int pos = (rng.next() & 0x7FFFFFFF) % len; + while (exchanges < maxExchanges) { + Subpop s = pop.subpops[pos]; + AtomicBoolean busy = s.busy; + if (!busy.get() && busy.compareAndSet(false, true)) { + exchanges += s.runUpdates(); + busy.set(false); + pos = (rng.next() & 0x7FFFFFFF) % len; + } + else if (++pos >= len) + pos = 0; + } + pop.threadDone(); + } catch (InterruptedException fallthrough) { } - return total/(float)count; } } /** - * A Task updates its pool of chromosomes.. + * A Subpop maintains a set of chromosomes. */ - static final class Task implements Runnable { - /** The pool of chromosomes, kept in sorted order */ + static final class Subpop { + /** The chromosomes, kept in sorted order */ final Chromosome[] chromosomes; + /** The parent population */ final Population pop; - /** The common exchanger, same for all tasks */ + /** Reservation bit for worker threads */ + final AtomicBoolean busy; + /** The common exchanger, same for all subpops */ final Exchanger exchanger; /** The current strand being exchanged */ Strand strand; /** Bitset used in cross */ final int[] inTour; final RNG rng; - final int poolSize; - final int nGen; - int gen; + final int subpopSize; - Task(Population pop) { + Subpop(Population pop) { this.pop = pop; - this.nGen = pop.nGen; - this.gen = 0; - this.poolSize = pop.poolSize; + this.subpopSize = pop.subpopSize; this.exchanger = pop.exchanger; + this.busy = new AtomicBoolean(false); this.rng = new RNG(); int length = cities.length; this.strand = new Strand(length); this.inTour = new int[(length >>> 5) + 1]; - this.chromosomes = new Chromosome[poolSize]; - for (int j = 0; j < poolSize; ++j) + this.chromosomes = new Chromosome[subpopSize]; + for (int j = 0; j < subpopSize; ++j) chromosomes[j] = new Chromosome(length, rng); Arrays.sort(chromosomes); } /** - * Run one or more update cycles. + * Run a random number of updates. The number of updates is + * at least 1 and no more than subpopSize. This + * controls the granularity of multiplexing subpop updates on + * to threads. It is small enough to balance out updates + * across tasks, but large enough to avoid having runs + * dominated by subpop selection. It is randomized to avoid + * long runs where pairs of subpops exchange only with each + * other. It is hardwired because small variations of it + * don't matter much. + * + * @param g the first generation to run */ - public void run() { - try { - for (;;) { - update(); - if (++gen >= nGen) { - pop.taskDone(); - return; - } - if ((rng.next() & RESUBMIT_MASK) == 1) { - pop.resubmit(this); - return; - } - } - } catch (InterruptedException ie) { - pop.taskDone(); - } + int runUpdates() throws InterruptedException { + int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); + for (int i = 0; i < n; ++i) + update(); + return n; } /** - * Choose a breeder, exchange strand with another pool, and - * cross them to create new chromosome to replace a chosen + * Chooses a breeder, exchanges strand with another subpop, and + * crosses them to create new chromosome to replace a chosen * dyer. */ void update() throws InterruptedException { @@ -374,38 +431,38 @@ public class TSPExchangerTest { } /** - * Choose a breeder, with exponentially decreasing probability + * Chooses a breeder, with exponentially decreasing probability * starting at best. * @return index of selected breeder */ int chooseBreeder() { - int mask = (poolSize >>> BREEDER_DECAY) - 1; + int mask = (subpopSize >>> BREEDER_DECAY) - 1; int b = 0; while ((rng.next() & mask) != mask) { - if (++b >= poolSize) + if (++b >= subpopSize) b = 0; } return b; } /** - * Choose a chromosome that will be replaced, with - * exponentially decreasing probablility starting at - * worst, ignoring the excluded index + * Chooses a chromosome that will be replaced, with + * 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 */ int chooseDyer(int exclude) { - int mask = (poolSize >>> DYER_DECAY) - 1; - int d = poolSize - 1; + int mask = (subpopSize >>> DYER_DECAY) - 1; + int d = subpopSize - 1; while (d == exclude || (rng.next() & mask) != mask) { if (--d < 0) - d = poolSize - 1; + d = subpopSize - 1; } return d; } - /** + /** * Select a random strand of b's. * @param breeder the breeder */ @@ -426,7 +483,7 @@ public class TSPExchangerTest { } /** - * Copy current strand to start of c's, and then append all + * Copies current strand to start of c's, and then appends all * remaining b's that aren't in the strand. * @param breeder the breeder * @param child the child @@ -450,7 +507,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 @@ -459,20 +516,20 @@ 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 + * Fixes 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; - float oldFitness = c.fitness; + int oldFitness = c.fitness; c.recalcFitness(); - float newFitness = c.fitness; + int newFitness = c.fitness; if (newFitness < oldFitness) { int j = k; int p = j - 1; @@ -500,10 +557,10 @@ public class TSPExchangerTest { /** Index of cities in tour order */ final int[] alleles; /** Total tour length */ - float fitness; + int fitness; - /** - * Initialize to random tour + /** + * Initializes to random tour. */ Chromosome(int length, RNG random) { alleles = new int[length]; @@ -519,30 +576,49 @@ public class TSPExchangerTest { } public int compareTo(Object x) { // to enable sorting - float xf = ((Chromosome)x).fitness; - float f = fitness; - return ((f == xf)? 0 :((f < xf)? -1 : 1)); + int xf = ((Chromosome) x).fitness; + int f = fitness; + return ((f == xf) ? 0 :((f < xf) ? -1 : 1)); } void recalcFitness() { int[] a = alleles; int len = a.length; int p = a[0]; - float f = cities.distanceBetween(a[len-1], p); + long f = cities.distanceBetween(a[len-1], p); for (int i = 1; i < len; i++) { int n = a[i]; f += cities.distanceBetween(p, n); p = n; } - fitness = f; + fitness = (int) (f / len); + } + + /** + * Returns tour length for points scaled in [0, 1). + */ + double unitTourLength() { + int[] a = alleles; + int len = a.length; + int p = a[0]; + double f = cities.unitDistanceBetween(a[len-1], p); + for (int i = 1; i < len; i++) { + int n = a[i]; + f += cities.unitDistanceBetween(p, n); + p = n; + } + return f; } - void validate() { // Ensure that this is a valid tour. + /** + * Checks that this tour visits each city. + */ + 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"); } @@ -550,7 +626,7 @@ public class TSPExchangerTest { } /** - * A Strand is a random sub-sequence of a Chromosome. Each task + * A Strand is a random sub-sequence of a Chromosome. Each subpop * creates only one strand, and then trades it with others, * refilling it on each iteration. */ @@ -561,26 +637,20 @@ public class TSPExchangerTest { } /** - * A collection of (x,y) points that represent cities. Distances - * are scaled in [0,1) to simply 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 for + * A collection of (x,y) points that represent cities. */ static final class CitySet { - // Scale ints to doubles in [0,1) - static final double PSCALE = (double)0x80000000L; final int length; final int[] xPts; final int[] yPts; - final float[][] distances; + final int[][] distances; CitySet(int n) { this.length = n; this.xPts = new int[n]; this.yPts = new int[n]; - this.distances = new float[n][n]; + this.distances = new int[n][n]; RNG random = new RNG(); for (int i = 0; i < n; i++) { @@ -590,17 +660,39 @@ public class TSPExchangerTest { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { - double dX = (xPts[i] - xPts[j]) / PSCALE; - double dY = (yPts[i] - yPts[j]) / PSCALE; - distances[i][j] = (float)Math.hypot(dX, dY); + 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; } } } - // Retrieve the cached distance between a pair of cities - float distanceBetween(int i, int j) { + /** + * 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; + + /** + * 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; + return Math.hypot(dx, dy); + } + } /** @@ -612,7 +704,7 @@ public class TSPExchangerTest { int seed; RNG(int seed) { this.seed = seed; } - RNG() { this.seed = seedGenerator.nextInt(); } + RNG() { this.seed = seedGenerator.nextInt() | 1; } int next() { int x = seed;