--- jsr166/src/test/loops/TSPExchangerTest.java 2005/08/07 19:25:55 1.1
+++ jsr166/src/test/loops/TSPExchangerTest.java 2005/12/10 20:08:51 1.2
@@ -1,533 +1,641 @@
/*
- * Written by Bill Scherer and Doug Lea with assistance from members
- * of JCP JSR-166 Expert Group and released to the public domain. Use,
- * modify, and redistribute this code in any way without
- * acknowledgement.
+ * 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
*/
+import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
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):
+ *
+ *
+ * - Select a breeder b from the pool
+ *
- Create a strand of its tour with a random starting point and length
+ *
- Offer the strand to the exchanger, receiving a strand from
+ * another pool
+ *
- Combine b and the received strand using crossing function to
+ * create new chromosome c.
+ *
- Replace a chromosome in the pool with c.
+ *
+ *
+ * See below for more details.
+ *
+ *
+ */
public class TSPExchangerTest {
- // Set SLS true to use as default the settings in Scherer, Lea, and
- // Scott paper. Otherwise smaller values are used to speed up testing
- static final boolean SLS = false;
-
- static final int DEFAULT_THREADS = SLS? 32: 8;
- static final int DEFAULT_CITIES = SLS? 100: 50;
- static final int DEFAULT_POPULATION = SLS? 1000: 500;
- static final int DEFAULT_BREEDERS = SLS? 200: 100;
- static final int DEFAULT_GENERATIONS = SLS? 20000: 10000;
+ static final int DEFAULT_MAX_THREADS =
+ (Runtime.getRuntime().availableProcessors() + 2);
+
+ /**
+ * The problem size. Each city is a random point. The goal is to
+ * find a tour among them with smallest total Euclidean distance.
+ */
+ static final int DEFAULT_CITIES = 144;
+
+ // Tuning parameters.
+
+ /**
+ * The number of chromosomes per pool. Must be a power of two.
+ *
+ * Smaller values lead to faster iterations but poorer quality
+ * results
+ */
+ static final int DEFAULT_POOL_SIZE = 32;
+ /**
+ * The number of iterations per task. 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,
+ * 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;
+
+ /**
+ * The minimum length for a random chromosome strand.
+ * Must be at least 1.
+ */
+ static final int MIN_STRAND_LENGTH = 3;
+
+ /**
+ * The probablility 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)
+ * Must be 1 less than a power of two.
+ */
+ static final int RANDOM_STRAND_MASK = 7;
+
+ /**
+ * Probablility control for selecting breeders.
+ * Breeders are selected starting at the best-fitness chromosome,
+ * with exponentially decaying probablility
+ * 1 / (poolSize >>> BREEDER_DECAY).
+ *
+ * Larger values usually cause faster convergence but poorer
+ * quality results
+ */
+ static final int BREEDER_DECAY = 1;
+
+ /**
+ * Probablility control for selecting dyers.
+ * Dyers are selected starting at the worst-fitness chromosome,
+ * with exponentially decaying probablility
+ * 1 / (poolSize >>> DYER_DECAY)
+ *
+ * Larger values usually cause faster convergence but poorer
+ * quality results
+ */
+ 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;
public static void main(String[] args) throws Exception {
- int maxThreads = DEFAULT_THREADS;
+ int maxThreads = DEFAULT_MAX_THREADS;
int nCities = DEFAULT_CITIES;
- int pSize = DEFAULT_POPULATION;
- int nBreeders = DEFAULT_BREEDERS;
- int numGenerations = DEFAULT_GENERATIONS;
+ int poolSize = DEFAULT_POOL_SIZE;
+ int nGen = nCities * nCities;
+ int nPools = nCities * nCities / poolSize;
- // Parse and check args
- int argc = 0;
try {
+ int argc = 0;
while (argc < args.length) {
String option = args[argc++];
- if (option.equals("-b"))
- nBreeders = Integer.parseInt(args[argc]);
- else if (option.equals("-c"))
+ if (option.equals("-c")) {
nCities = Integer.parseInt(args[argc]);
+ nGen = nCities * nCities;
+ nPools = nCities * nCities / poolSize;
+ }
+ else if (option.equals("-p"))
+ poolSize = Integer.parseInt(args[argc]);
else if (option.equals("-g"))
- numGenerations = Integer.parseInt(args[argc]);
- else if (option.equals("-p"))
- pSize = Integer.parseInt(args[argc]);
- else
+ nGen = Integer.parseInt(args[argc]);
+ else if (option.equals("-n"))
+ nPools = Integer.parseInt(args[argc]);
+ else
maxThreads = Integer.parseInt(option);
argc++;
}
}
- catch (NumberFormatException e) {
- reportUsageErrorAndDie();
- System.exit(0);
- }
catch (Exception e) {
reportUsageErrorAndDie();
}
- // Display runtime parameters
- System.out.print("TSPExchangerTest -b " + nBreeders);
- System.out.print(" -c " + nCities);
- System.out.print(" -g " + numGenerations);
- System.out.print(" -p " + pSize);
- System.out.print(" max threads " + maxThreads);
- System.out.println();
-
- // warmup
- System.out.print("Threads: " + 2 + "\t");
- oneRun(2,
- nCities,
- pSize,
- nBreeders,
- numGenerations);
- Thread.sleep(100);
+ 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(" max threads " + maxThreads);
+ System.out.println();
- int k = 4;
- for (int i = 2; i <= maxThreads;) {
- System.out.print("Threads: " + i + "\t");
- oneRun(i,
- nCities,
- pSize,
- nBreeders,
- numGenerations);
- Thread.sleep(100);
- if (i == k) {
- k = i << 1;
- i = i + (i >>> 1);
- }
- else
- i = k;
- }
+ cities = new CitySet(nCities);
+
+ for (int i = 2; i <= maxThreads; i += 2)
+ oneRun(i, nPools, poolSize, nGen);
}
- private static void reportUsageErrorAndDie() {
- System.out.print("usage: TSPExchangerTest [-b #breeders] [-c #cities]");
- System.out.println(" [-g #generations]");
- System.out.println(" [-p population size] [ #threads]");
+ static void reportUsageErrorAndDie() {
+ System.out.print("usage: TSPExchangerTest");
+ System.out.print(" [-c #cities]");
+ System.out.print(" [-p #poolSize]");
+ System.out.print(" [-g #generations]");
+ System.out.print(" [-n #pools]");
+ System.out.print(" #threads]");
+ System.out.println();
System.exit(0);
}
- static void oneRun(int nThreads,
- int nCities,
- int pSize,
- int nBreeders,
- int numGenerations)
- throws Exception {
- CyclicBarrier runBarrier = new CyclicBarrier(nThreads + 1);
- Population p = new Population(nCities, pSize, nBreeders, nThreads,
- numGenerations, runBarrier);
-
- // Run the test
- long startTime = System.currentTimeMillis();
- runBarrier.await(); // start 'em off
- runBarrier.await(); // wait 'til they're done
- long stopTime = System.currentTimeMillis();
- long elapsed = stopTime - startTime;
- long rate = (numGenerations * 1000) / elapsed;
- double secs = (double)elapsed / 1000.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.
+ */
+ static void oneRun(int nThreads, int nPools, int poolSize, int nGen)
+ throws InterruptedException {
+ Population p = new Population(nThreads, nPools, poolSize, nGen);
+ ProgressMonitor mon = null;
+ if (verbose) {
+ mon = new ProgressMonitor(p);
+ mon.start();
+ }
+ p.printSnapshot(0);
+ long startTime = System.nanoTime();
+ p.start();
+ p.awaitTasks();
+ long stopTime = System.nanoTime();
+ if (mon != null)
+ mon.interrupt();
+ p.shutdown();
+ Thread.sleep(100);
- // Display results
- System.out.print(LoopHelpers.rightJustify((int)p.bestFitness()) +
- " fitness");
- System.out.print(LoopHelpers.rightJustify(rate) + " gen/s \t");
- System.out.print(secs + "s elapsed");
- System.out.println();
+ long elapsed = stopTime - startTime;
+ long rate = elapsed / (nPools * nGen);
+ 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
+ * and has control methods to start, stop, and report progress.
+ */
static final class Population {
- final Chromosome[] individuals;
- final Exchanger x;
- final CitySet cities;
- final int[] dyers;
- final int[] breeders;
- final CyclicBarrier generationBarrier;
- final Thread[] threads;
- final boolean[] doneMating;
- final ReentrantLock matingBarrierLock;
- final Condition matingBarrier;
- final LoopHelpers.SimpleRandom[] rngs;
+ final Task[] tasks;
+ final Exchanger exchanger;
+ final ThreadPoolExecutor exec;
+ final CountDownLatch done;
+ final int nGen;
+ final int poolSize;
final int nThreads;
- volatile int matingBarrierCount;
- // action to run between each generation
- class BarrierAction implements Runnable {
- public void run() {
- prepareToBreed();
- resetMatingBarrier();
- }
- }
-
- Population(int nCities,
- int pSize,
- int nBreeders,
- int nThreads,
- int nGen,
- CyclicBarrier runBarrier) {
+ Population(int nThreads, int nPools, int poolSize, int nGen) {
this.nThreads = nThreads;
- // rngs[nThreads] is for global actions; others are per-thread
- this.rngs = new LoopHelpers.SimpleRandom[nThreads+1];
- for (int i = 0; i < rngs.length; ++i)
- rngs[i] = new LoopHelpers.SimpleRandom();
- this.cities = new CitySet(nCities, rngs[nThreads]);
- this.individuals = new Chromosome[pSize];
- for (int i = 0; i < individuals.length; i++)
- individuals[i] = new Chromosome(cities, nCities,
- rngs[nThreads]);
- this.doneMating = new boolean[nThreads];
- this.dyers = new int[nBreeders];
- this.breeders = new int[nBreeders];
-
- this.x = new Exchanger();
-
- this.matingBarrierLock = new ReentrantLock();
- this.matingBarrier = matingBarrierLock.newCondition();
-
- BarrierAction ba = new BarrierAction();
- this.generationBarrier = new CyclicBarrier(nThreads, ba);
- ba.run(); // prepare for first generation
-
- this.threads = new Thread[nThreads];
- for (int i = 0; i < nThreads; i++) {
- Runner r = new Runner(i, this, runBarrier, nGen);
- threads[i] = new Thread(r);
- threads[i].start();
+ this.nGen = nGen;
+ this.poolSize = poolSize;
+ 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();
+ }
+
+ /** Start the tasks */
+ void start() {
+ for (int i = 0; i < tasks.length; i++)
+ exec.execute(tasks[i]);
+ }
+
+ /** Stop the tasks */
+ void shutdown() {
+ exec.shutdownNow();
+ }
+
+ /** Called by task upon terminations */
+ void taskDone() {
+ done.countDown();
+ }
+
+ /** Wait for (all but one) task to complete */
+ void awaitTasks() throws InterruptedException {
+ done.await();
+ }
+
+ /**
+ * Called by a task to resubmit itself after completing
+ * fewer than nGen iterations.
+ */
+ void resubmit(Task task) {
+ exec.execute(task);
+ }
+
+ 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;
}
+ return total/(float)count;
}
-
- double averageFitness() {
- double total = 0;
- for (int i = 0; i < individuals.length; i++)
- total += individuals[i].fitness;
- return total/(double)individuals.length;
- }
-
- double bestFitness() {
- double best = individuals[0].fitness;
- for (int i = 0; i < individuals.length; i++)
- if (individuals[i].fitness < best)
- best = individuals[i].fitness;
- return best;
- }
+ }
- void resetMatingBarrier() {
- matingBarrierCount = nThreads - 1;
- }
+ /**
+ * A Task updates its pool of chromosomes..
+ */
+ static final class Task implements Runnable {
+ /** The pool of chromosomes, kept in sorted order */
+ final Chromosome[] chromosomes;
+ final Population pop;
+ /** The common exchanger, same for all tasks */
+ 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;
- void awaitMatingBarrier(int tid) {
- doneMating[tid] = true; // heuristically set before lock
- matingBarrierLock.lock();
+ Task(Population pop) {
+ this.pop = pop;
+ this.nGen = pop.nGen;
+ this.gen = 0;
+ this.poolSize = pop.poolSize;
+ this.exchanger = pop.exchanger;
+ 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)
+ chromosomes[j] = new Chromosome(length, rng);
+ Arrays.sort(chromosomes);
+ }
+
+ /**
+ * Run one or more update cycles.
+ */
+ public void run() {
try {
- int m = matingBarrierCount--;
- if (m < 1) {
- for (int i = 0; i < doneMating.length; ++i)
- doneMating[i] = false;
- Thread.interrupted(); // clear
- matingBarrier.signalAll();
- } else {
- doneMating[tid] = true;
- if (m == 1 && nThreads > 2) {
- for (int j = 0; j < doneMating.length; ++j) {
- if (!doneMating[j]) {
- threads[j].interrupt();
- break;
- }
- }
+ for (;;) {
+ update();
+ if (++gen >= nGen) {
+ pop.taskDone();
+ return;
}
- try {
- do {
- matingBarrier.await();
- } while (matingBarrierCount >= 0);
- } catch(InterruptedException ie) {}
+ if ((rng.next() & RESUBMIT_MASK) == 1) {
+ pop.resubmit(this);
+ return;
+ }
}
- } finally {
- matingBarrierLock.unlock();
+ } catch (InterruptedException ie) {
+ pop.taskDone();
}
}
- void prepareToBreed() {
-
- // Calculate statistics
- double totalFitness = 0;
- double worstFitness = 0;
- double bestFitness = individuals[0].fitness;
-
- for (int i = 0; i < individuals.length; i++) {
- totalFitness += individuals[i].fitness;
- if (individuals[i].fitness > worstFitness)
- worstFitness = individuals[i].fitness;
- if (individuals[i].fitness < bestFitness)
- bestFitness = individuals[i].fitness;
- }
-
- double[] lifeNorm = new double[individuals.length];
- double lifeNormTotal = 0;
- double[] deathNorm = new double[individuals.length];
- double deathNormTotal = 0;
- for (int i = 0; i < individuals.length; i++) {
- deathNorm[i] = (individuals[i].fitness - bestFitness)
- / (worstFitness - bestFitness + 1) + .05;
- deathNorm[i] = (deathNorm[i] * deathNorm[i]);
- lifeNorm[i] = 1.0 - deathNorm[i];
- lifeNormTotal += lifeNorm[i];
- deathNormTotal += deathNorm[i];
- }
-
- double deathScale = deathNormTotal / (double)0x7FFFFFFF;
- double lifeScale = lifeNormTotal / (double)0x7FFFFFFF;
-
- int nSub = breeders.length / nThreads;
- LoopHelpers.SimpleRandom random = rngs[nThreads];
-
- // Select breeders (need to be distinct)
- for (int i = 0; i < nSub; i++) {
- boolean newBreeder;
- int lucky;
- do {
- newBreeder = true;
- double choice = lifeScale * (double)random.next();
- for (lucky = 0; lucky < individuals.length; lucky++) {
- choice -= lifeNorm[lucky];
- if (choice <= 0)
- break;
- }
- for (int j = 0; j < i; j++)
- if (breeders[j] == lucky)
- newBreeder = false;
- } while (!newBreeder);
- breeders[i] = lucky;
- }
-
- // Select dead guys (need to be distinct)
- for (int i = 0; i < nSub; i++) {
- boolean newDead;
- int victim;
- do {
- newDead = true;
- double choice = deathScale * (double)random.next();
- for (victim = 0; victim < individuals.length; victim++) {
- choice -= deathNorm[victim];
- if (choice <= 0)
- break;
- }
- for (int j = 0; j < i; j++)
- if (dyers[j] == victim)
- newDead = false;
- } while (!newDead);
- dyers[i] = victim;
- }
+ /**
+ * Choose a breeder, exchange strand with another pool, and
+ * cross them to create new chromosome to replace a chosen
+ * dyer.
+ */
+ void update() throws InterruptedException {
+ int b = chooseBreeder();
+ int d = chooseDyer(b);
+ Chromosome breeder = chromosomes[b];
+ Chromosome child = chromosomes[d];
+ chooseStrand(breeder);
+ strand = exchanger.exchange(strand);
+ cross(breeder, child);
+ fixOrder(child, d);
+ }
+
+ /**
+ * Choose a breeder, with exponentially decreasing probability
+ * starting at best.
+ * @return index of selected breeder
+ */
+ int chooseBreeder() {
+ int mask = (poolSize >>> BREEDER_DECAY) - 1;
+ int b = 0;
+ while ((rng.next() & mask) != mask) {
+ if (++b >= poolSize)
+ b = 0;
+ }
+ return b;
+ }
+
+ /**
+ * Choose a chromosome that will be replaced, with
+ * exponentially decreasing probablility 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;
+ while (d == exclude || (rng.next() & mask) != mask) {
+ if (--d < 0)
+ d = poolSize - 1;
+ }
+ return d;
+ }
+
+ /**
+ * Select a random strand of b's.
+ * @param breeder the breeder
+ */
+ void chooseStrand(Chromosome breeder) {
+ int[] bs = breeder.alleles;
+ int length = bs.length;
+ int strandLength = MIN_STRAND_LENGTH;
+ while (strandLength < length &&
+ (rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK)
+ strandLength++;
+ strand.strandLength = strandLength;
+ int[] ss = strand.alleles;
+ int k = (rng.next() & 0x7FFFFFFF) % length;
+ for (int i = 0; i < strandLength; ++i) {
+ ss[i] = bs[k];
+ if (++k >= length) k = 0;
+ }
+ }
+
+ /**
+ * Copy current strand to start of c's, and then append all
+ * remaining b's that aren't in the strand.
+ * @param breeder the breeder
+ * @param child the child
+ */
+ void cross(Chromosome breeder, Chromosome child) {
+ for (int k = 0; k < inTour.length; ++k) // clear bitset
+ inTour[k] = 0;
+
+ // Copy current strand to c
+ int[] cs = child.alleles;
+ int ssize = strand.strandLength;
+ int[] ss = strand.alleles;
+ int i;
+ for (i = 0; i < ssize; ++i) {
+ int x = ss[i];
+ cs[i] = x;
+ inTour[x >>> 5] |= 1 << (x & 31); // record in bit set
+ }
+
+ // Find index of matching origin in b
+ int first = cs[0];
+ int j = 0;
+ int[] bs = breeder.alleles;
+ while (bs[j] != first)
+ ++j;
+
+ // Append remaining b's that aren't already in tour
+ while (i < cs.length) {
+ if (++j >= bs.length) j = 0;
+ int x = bs[j];
+ if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
+ cs[i++] = x;
+ }
}
-
- void nextGeneration(int tid, int matings)
- throws InterruptedException, BrokenBarrierException {
-
- int firstChild = ((individuals.length * tid) / nThreads);
- int lastChild = ((individuals.length * (tid + 1)) / nThreads);
- int nChildren = lastChild - firstChild;
-
- int firstSub = ((breeders.length * tid) / nThreads);
- int lastSub = ((breeders.length * (tid + 1)) / nThreads);
- int nSub = lastSub - firstSub;
-
- Chromosome[] children = new Chromosome[nChildren];
-
- LoopHelpers.SimpleRandom random = rngs[tid];
-
- for (int i = 0; i < nSub; i++) {
- Chromosome parent = individuals[breeders[firstSub + i]];
- Chromosome offspring = new Chromosome(parent);
- int k = 0;
- while (k < matings && matingBarrierCount > 0) {
- try {
- Chromosome other = x.exchange(offspring);
- offspring = offspring.reproduceWith(other, random);
- ++k;
- } catch (InterruptedException to) {
- break;
- }
+ /**
+ * Fix the sort order of a changed Chromosome c at position k
+ * @param c the chromosome
+ * @param k the index
+ */
+ void fixOrder(Chromosome c, int k) {
+ Chromosome[] cs = chromosomes;
+ float oldFitness = c.fitness;
+ c.recalcFitness();
+ float newFitness = c.fitness;
+ if (newFitness < oldFitness) {
+ int j = k;
+ int p = j - 1;
+ while (p >= 0 && cs[p].fitness > newFitness) {
+ cs[j] = cs[p];
+ j = p--;
}
- if (k != 0)
- children[i] = offspring;
- else {
- // No peers, so we mate with ourselves
- for ( ; i < nSub - 1; i += 2) {
- int cur = firstSub + i;
- Chromosome bro = individuals[breeders[cur]];
- Chromosome sis = individuals[breeders[cur + 1]];
-
- children[i] = bro.breedWith(sis, matings, random);
- children[i+1] = sis.breedWith(bro, matings, random);
- }
-
- // Not even a sibling, so we go to asexual reproduction
- if (i < nSub)
- children[i] = individuals[breeders[firstSub + 1]];
- break;
+ cs[j] = c;
+ } else if (newFitness > oldFitness) {
+ int j = k;
+ int n = j + 1;
+ while (n < cs.length && cs[n].fitness < newFitness) {
+ cs[j] = cs[n];
+ j = n++;
}
-
- }
-
- awaitMatingBarrier(tid);
-
- // Kill off dead guys
- for (int i = 0; i < nSub; i++) {
- individuals[dyers[firstSub + 1]] = children[i];
+ cs[j] = c;
}
-
- generationBarrier.await();
}
}
- static final class Chromosome {
- private final CitySet cities;
- private final int[] alleles;
- private final int length;
- public double fitness; // immutable after publication
-
- // Basic constructor - gets randomized genetic code
- Chromosome(CitySet cities, int length,
- LoopHelpers.SimpleRandom random) {
- this.length = length;
- this.cities = cities;
- // Initialize alleles to a random shuffle
+ /**
+ * A Chromosome is a candidate TSP tour.
+ */
+ static final class Chromosome implements Comparable {
+ /** Index of cities in tour order */
+ final int[] alleles;
+ /** Total tour length */
+ float fitness;
+
+ /**
+ * Initialize to random tour
+ */
+ Chromosome(int length, RNG random) {
alleles = new int[length];
for (int i = 0; i < length; i++)
alleles[i] = i;
for (int i = length - 1; i > 0; i--) {
+ int idx = (random.next() & 0x7FFFFFFF) % alleles.length;
int tmp = alleles[i];
- int idx = random.next() % length;
alleles[i] = alleles[idx];
alleles[idx] = tmp;
}
recalcFitness();
}
-
- // Copy constructor - clones parent's genetic code
- Chromosome(Chromosome clone) {
- length = clone.length;
- cities = clone.cities;
- fitness = clone.fitness;
- alleles = new int[length];
- System.arraycopy(clone.alleles, 0, alleles, 0, length);
- }
-
- int getAllele(int offset) {
- return alleles[offset % length];
- }
- void setAllele(int offset, int v) {
- alleles[offset % length] = v;
+
+ public int compareTo(Object x) { // to enable sorting
+ float xf = ((Chromosome)x).fitness;
+ float f = fitness;
+ return ((f == xf)? 0 :((f < xf)? -1 : 1));
}
-
+
void recalcFitness() {
- fitness = cities.distanceBetween(alleles[0], alleles[length-1]);
- for (int i = 1; i < length; i++) {
- fitness += cities.distanceBetween(alleles[i-1], alleles[i]);
- }
- }
-
- Chromosome breedWith(Chromosome partner, int n,
- LoopHelpers.SimpleRandom random) {
- Chromosome offspring = new Chromosome(this);
- for (int i = 0; i < n; i++)
- offspring = offspring.reproduceWith(partner, random);
- return offspring;
+ int[] a = alleles;
+ int len = a.length;
+ int p = a[0];
+ float 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;
+ }
+
+ void validate() { // Ensure that this is a valid tour.
+ int len = alleles.length;
+ boolean[] used = new boolean[len];
+ for (int i = 0; i < len; ++i)
+ used[alleles[i]] = true;
+ for (int i = 0; i < len; ++i)
+ if (!used[i])
+ throw new Error("Bad tour");
}
-
- Chromosome reproduceWith(Chromosome other,
- LoopHelpers.SimpleRandom random) {
- Chromosome child = new Chromosome(this);
- int coStart = random.next() % length;
- int coLen = 3;
- while (1 == (random.next() & 1) && (coLen < length))
- coLen++;
- int cPos, pPos;
-
- int join = other.getAllele(coStart);
- child.alleles[0] = join;
-
- for (pPos = 0; alleles[pPos] != join; pPos++)
- ;
-
- for (cPos = 1; cPos < coLen; cPos++)
- child.setAllele(cPos, other.getAllele(coStart + cPos));
-
- for (int i = 0; i < length; i++) {
- boolean found = false;
- int allele = getAllele(pPos++);
- for (int j = 0; j < coLen; j++) {
- if (found = (child.getAllele(j) == allele))
- break;
- }
- if (!found)
- child.setAllele(cPos++, allele);
- }
-
- child.recalcFitness();
- return child;
- }
-
+
}
+
/**
- * A collection of (x,y) points that represent cities
+ * A Strand is a random sub-sequence of a Chromosome. Each task
+ * creates only one strand, and then trades it with others,
+ * refilling it on each iteration.
+ */
+ static final class Strand {
+ final int[] alleles;
+ int strandLength;
+ Strand(int length) { alleles = new int[length]; }
+ }
+
+ /**
+ * 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
*/
static final class CitySet {
- final int XMAX = 1000;
- final int YMAX = 1000;
+ // Scale ints to doubles in [0,1)
+ static final double PSCALE = (double)0x80000000L;
+
final int length;
- final int xPts[];
- final int yPts[];
- final double distances[];
-
- CitySet(int n, LoopHelpers.SimpleRandom random) {
+ final int[] xPts;
+ final int[] yPts;
+ final float[][] distances;
+
+ CitySet(int n) {
this.length = n;
- xPts = new int[n];
- yPts = new int [n];
+ this.xPts = new int[n];
+ this.yPts = new int[n];
+ this.distances = new float[n][n];
+
+ RNG random = new RNG();
for (int i = 0; i < n; i++) {
- xPts[i] = random.next() % XMAX;
- yPts[i] = random.next() % YMAX;
+ xPts[i] = (random.next() & 0x7FFFFFFF);
+ yPts[i] = (random.next() & 0x7FFFFFFF);
}
- distances = new double[n * n];
+
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
- double dX = (double)(xPts[i] - xPts[j]);
- double dY = (double)(yPts[i] - yPts[j]);
- distances[i + j * n] = Math.hypot(dX, dY);
+ double dX = (xPts[i] - xPts[j]) / PSCALE;
+ double dY = (yPts[i] - yPts[j]) / PSCALE;
+ distances[i][j] = (float)Math.hypot(dX, dY);
}
}
}
-
+
// Retrieve the cached distance between a pair of cities
- double distanceBetween(int idx1, int idx2) {
- return distances[idx1 + idx2 * length];
+ float distanceBetween(int i, int j) {
+ return distances[i][j];
}
}
- static final class Runner implements Runnable {
- final Population pop;
- final CyclicBarrier b;
- final int nGen;
- final int tid;
- static final boolean verbose = false;
-
- Runner(int tid, Population p, CyclicBarrier b, int n) {
- this.tid = tid;
- this.pop = p;
- this.b = b;
- this.nGen = n;
+ /**
+ * Cheap XorShift random number generator
+ */
+ static final class RNG {
+ /** Seed generator for XorShift RNGs */
+ static final Random seedGenerator = new Random();
+
+ int seed;
+ RNG(int seed) { this.seed = seed; }
+ RNG() { this.seed = seedGenerator.nextInt(); }
+
+ int next() {
+ int x = seed;
+ x ^= x << 6;
+ x ^= x >>> 21;
+ x ^= x << 7;
+ seed = x;
+ return x;
}
-
+ }
+
+ static final class ProgressMonitor extends Thread {
+ final Population pop;
+ ProgressMonitor(Population p) { pop = p; }
public void run() {
+ double time = 0;
try {
- b.await();
- for (int i = 0; i < nGen; i++) {
- if (verbose && 0 == tid && 0 == i % 1000) {
- System.out.print("Gen " + i + " fitness:");
- System.out.print(" best=" + (int)pop.bestFitness());
- System.out.println("; avg=" + (int)pop.averageFitness());
- }
- int matings = (((nGen - i) * 2) / (nGen)) + 1;
- pop.nextGeneration(tid, matings);
+ while (!Thread.interrupted()) {
+ sleep(SNAPSHOT_RATE);
+ time += SNAPSHOT_RATE;
+ pop.printSnapshot(time / 1000.0);
}
- b.await();
- }
- catch (InterruptedException e) {
- e.printStackTrace(System.out);
- System.exit(0);
- }
- catch (BrokenBarrierException e) {
- e.printStackTrace(System.out);
- System.exit(0);
- }
+ } catch (InterruptedException ie) {}
}
}
}