test/loops/TSPExchangerTest.java

/*
 * 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):
 *
 * <ol>
 *   <li> Select a breeder b from the pool
 *   <li> Create a strand of its tour with a random starting point and length
 *   <li> Offer the strand to the exchanger, receiving a strand from 
 *        another pool
 *   <li> Combine b and the received strand using crossing function to 
 *        create new chromosome c.
 *   <li> Replace a chromosome in the pool with c.
 * </ol>
 *
 * See below for more details.
 * <p>
 * 
 */
public class TSPExchangerTest {
    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_MAX_THREADS;
        int nCities = DEFAULT_CITIES;
        int poolSize = DEFAULT_POOL_SIZE;
        int nGen = nCities * nCities;
        int nPools = nCities * nCities / poolSize;

        try {
            int argc = 0;
            while (argc < args.length) {
                String option = args[argc++];
                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"))
                    nGen = Integer.parseInt(args[argc]);
                else if (option.equals("-n"))
                    nPools = Integer.parseInt(args[argc]);
                else
                    maxThreads = Integer.parseInt(option);
                argc++;
            }
        }
        catch (Exception e) {
            reportUsageErrorAndDie();
        }

        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();

        cities = new CitySet(nCities);

        for (int i = 2; i <= maxThreads; i += 2) 
            oneRun(i, nPools, poolSize, nGen);
    }

    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);
    }

    /**
     * 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);

        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 Task[] tasks;
        final Exchanger<Strand> exchanger;
        final ThreadPoolExecutor exec;
        final CountDownLatch done;
        final int nGen;
        final int poolSize;
        final int nThreads;

        Population(int nThreads, int nPools, int poolSize, int nGen) {
            this.nThreads = nThreads;
            this.nGen = nGen;
            this.poolSize = poolSize;
            this.exchanger = new Exchanger<Strand>();
            this.done = new CountDownLatch(nPools-1);
            this.tasks = new Task[nPools];
            for (int i = 0; i < nPools; i++) 
                tasks[i] = new Task(this);
            BlockingQueue<Runnable> tq = 
                new LinkedBlockingQueue<Runnable>();
            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;
        }
    }

    /**
     * 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<Strand> 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;

        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 {
                for (;;) {
                    update();
                    if (++gen >= nGen) {
                        pop.taskDone();
                        return;
                    }
                    if ((rng.next() & RESUBMIT_MASK) == 1) {
                        pop.resubmit(this);
                        return;
                    } 
                }
            } catch (InterruptedException ie) {
                pop.taskDone();
            }
        }

        /**
         * 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;
            } 

        }

        /**
         * 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--;
                }
                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++;
                }
                cs[j] = c;
            }
        }
    }

    /**
     * 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];
                alleles[i] = alleles[idx];
                alleles[idx] = tmp;
            }
            recalcFitness();
        }

        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() {
            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");
        }

    }

    /**
     * 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 {
        // 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;

        CitySet(int n) {
            this.length = 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() & 0x7FFFFFFF);
                yPts[i] = (random.next() & 0x7FFFFFFF);
            }

            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);
                }
            }
        }

        // Retrieve the cached distance between a pair of cities
        float distanceBetween(int i, int j) {
            return distances[i][j];
        }
    }

    /**
     * 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 {
                while (!Thread.interrupted()) {
                    sleep(SNAPSHOT_RATE);
                    time += SNAPSHOT_RATE;
                    pop.printSnapshot(time / 1000.0);
                }
            } catch (InterruptedException ie) {}
        }
    }
}
Revision:	1.2
Committed:	Sat Dec 10 20:08:51 2005 UTC (18 years, 5 months ago) by dl
Branch:	MAIN
Changes since 1.1:	+546 -438 lines
Log Message:	Improved tests
#	Content
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
5	*/
6
7	import java.util.*;
8	import java.util.concurrent.*;
9	import java.util.concurrent.atomic.*;
10	import java.util.concurrent.locks.*;
11
12	/**
13	* A parallel Traveling Salesperson Problem (TSP) program based on a
14	* genetic algorithm using an Exchanger. A population of chromosomes
15	* is distributed among "pools". The chromosomes represent tours, and
16	* their fitness is the total tour length. Each chromosome is
17	* initialized as a random tour. A Task is associated with each pool.
18	* Each task repeatedly does, for a fixed number of iterations
19	* (generations):
20	*
21	* <ol>
22	* <li> Select a breeder b from the pool
23	* <li> Create a strand of its tour with a random starting point and length
24	* <li> Offer the strand to the exchanger, receiving a strand from
25	* another pool
26	* <li> Combine b and the received strand using crossing function to
27	* create new chromosome c.
28	* <li> Replace a chromosome in the pool with c.
29	* </ol>
30	*
31	* See below for more details.
32	* <p>
33	*
34	*/
35	public class TSPExchangerTest {
36	static final int DEFAULT_MAX_THREADS =
37	(Runtime.getRuntime().availableProcessors() + 2);
38
39	/**
40	* The problem size. Each city is a random point. The goal is to
41	* find a tour among them with smallest total Euclidean distance.
42	*/
43	static final int DEFAULT_CITIES = 144;
44
45	// Tuning parameters.
46
47	/**
48	* The number of chromosomes per pool. Must be a power of two.
49	*
50	* Smaller values lead to faster iterations but poorer quality
51	* results
52	*/
53	static final int DEFAULT_POOL_SIZE = 32;
54
55	/**
56	* The number of iterations per task. Convergence appears
57	* to be roughly proportional to #cities-squared
58	*/
59	static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES;
60
61	/**
62	* The number of pools. The total population is #pools * poolSize,
63	* which should be roughly on the order of #cities-squared
64	*
65	* Smaller values lead to faster total runs but poorer quality
66	* results
67	*/
68	static final int DEFAULT_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE;
69
70	/**
71	* The minimum length for a random chromosome strand.
72	* Must be at least 1.
73	*/
74	static final int MIN_STRAND_LENGTH = 3;
75
76	/**
77	* The probablility mask value for creating random strands,
78	* that have lengths at least MIN_STRAND_LENGTH, and grow
79	* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1)
80	* Must be 1 less than a power of two.
81	*/
82	static final int RANDOM_STRAND_MASK = 7;
83
84	/**
85	* Probablility control for selecting breeders.
86	* Breeders are selected starting at the best-fitness chromosome,
87	* with exponentially decaying probablility
88	* 1 / (poolSize >>> BREEDER_DECAY).
89	*
90	* Larger values usually cause faster convergence but poorer
91	* quality results
92	*/
93	static final int BREEDER_DECAY = 1;
94
95	/**
96	* Probablility control for selecting dyers.
97	* Dyers are selected starting at the worst-fitness chromosome,
98	* with exponentially decaying probablility
99	* 1 / (poolSize >>> DYER_DECAY)
100	*
101	* Larger values usually cause faster convergence but poorer
102	* quality results
103	*/
104	static final int DYER_DECAY = 1;
105
106	/**
107	* The probability mask for a task to give up running and
108	* resubmit itself. On each iteration, a task stops iterating
109	* and resubmits itself with probability 1 / (RESUBMIT_MASK+1).
110	* This avoids some tasks running to completion before others
111	* even start when there are more pools than threads.
112	*
113	* Must be 1 less than a power of two.
114	*/
115	static final int RESUBMIT_MASK = 63;
116
117	static final boolean verbose = true;
118	static final long SNAPSHOT_RATE = 10000; // in milliseconds
119
120	/**
121	* The set of cities. Created once per program run, to
122	* make it easier to compare solutions across different runs.
123	*/
124	static CitySet cities;
125
126	public static void main(String[] args) throws Exception {
127	int maxThreads = DEFAULT_MAX_THREADS;
128	int nCities = DEFAULT_CITIES;
129	int poolSize = DEFAULT_POOL_SIZE;
130	int nGen = nCities * nCities;
131	int nPools = nCities * nCities / poolSize;
132
133	try {
134	int argc = 0;
135	while (argc < args.length) {
136	String option = args[argc++];
137	if (option.equals("-c")) {
138	nCities = Integer.parseInt(args[argc]);
139	nGen = nCities * nCities;
140	nPools = nCities * nCities / poolSize;
141	}
142	else if (option.equals("-p"))
143	poolSize = Integer.parseInt(args[argc]);
144	else if (option.equals("-g"))
145	nGen = Integer.parseInt(args[argc]);
146	else if (option.equals("-n"))
147	nPools = Integer.parseInt(args[argc]);
148	else
149	maxThreads = Integer.parseInt(option);
150	argc++;
151	}
152	}
153	catch (Exception e) {
154	reportUsageErrorAndDie();
155	}
156
157	System.out.print("TSPExchangerTest");
158	System.out.print(" -c " + nCities);
159	System.out.print(" -g " + nGen);
160	System.out.print(" -p " + poolSize);
161	System.out.print(" -n " + nPools);
162	System.out.print(" max threads " + maxThreads);
163	System.out.println();
164
165	cities = new CitySet(nCities);
166
167	for (int i = 2; i <= maxThreads; i += 2)
168	oneRun(i, nPools, poolSize, nGen);
169	}
170
171	static void reportUsageErrorAndDie() {
172	System.out.print("usage: TSPExchangerTest");
173	System.out.print(" [-c #cities]");
174	System.out.print(" [-p #poolSize]");
175	System.out.print(" [-g #generations]");
176	System.out.print(" [-n #pools]");
177	System.out.print(" #threads]");
178	System.out.println();
179	System.exit(0);
180	}
181
182	/**
183	* Perform one run with the given parameters. Each run completes
184	* when all but one of the tasks has finished. The last remaining
185	* task may have no one left to exchange with, so the pool is
186	* abruptly terminated.
187	*/
188	static void oneRun(int nThreads, int nPools, int poolSize, int nGen)
189	throws InterruptedException {
190	Population p = new Population(nThreads, nPools, poolSize, nGen);
191	ProgressMonitor mon = null;
192	if (verbose) {
193	mon = new ProgressMonitor(p);
194	mon.start();
195	}
196	p.printSnapshot(0);
197	long startTime = System.nanoTime();
198	p.start();
199	p.awaitTasks();
200	long stopTime = System.nanoTime();
201	if (mon != null)
202	mon.interrupt();
203	p.shutdown();
204	Thread.sleep(100);
205
206	long elapsed = stopTime - startTime;
207	long rate = elapsed / (nPools * nGen);
208	double secs = (double)elapsed / 1000000000.0;
209	p.printSnapshot(secs);
210	System.out.printf("%10d ns per transfer\n", rate);
211	}
212
213
214	/**
215	* A Population creates the pools, tasks, and threads for a run
216	* and has control methods to start, stop, and report progress.
217	*/
218	static final class Population {
219	final Task[] tasks;
220	final Exchanger<Strand> exchanger;
221	final ThreadPoolExecutor exec;
222	final CountDownLatch done;
223	final int nGen;
224	final int poolSize;
225	final int nThreads;
226
227	Population(int nThreads, int nPools, int poolSize, int nGen) {
228	this.nThreads = nThreads;
229	this.nGen = nGen;
230	this.poolSize = poolSize;
231	this.exchanger = new Exchanger<Strand>();
232	this.done = new CountDownLatch(nPools-1);
233	this.tasks = new Task[nPools];
234	for (int i = 0; i < nPools; i++)
235	tasks[i] = new Task(this);
236	BlockingQueue<Runnable> tq =
237	new LinkedBlockingQueue<Runnable>();
238	this.exec = new ThreadPoolExecutor(nThreads, nThreads,
239	0L, TimeUnit.MILLISECONDS,
240	tq);
241	exec.prestartAllCoreThreads();
242	}
243
244	/** Start the tasks */
245	void start() {
246	for (int i = 0; i < tasks.length; i++)
247	exec.execute(tasks[i]);
248	}
249
250	/** Stop the tasks */
251	void shutdown() {
252	exec.shutdownNow();
253	}
254
255	/** Called by task upon terminations */
256	void taskDone() {
257	done.countDown();
258	}
259
260	/** Wait for (all but one) task to complete */
261	void awaitTasks() throws InterruptedException {
262	done.await();
263	}
264
265	/**
266	* Called by a task to resubmit itself after completing
267	* fewer than nGen iterations.
268	*/
269	void resubmit(Task task) {
270	exec.execute(task);
271	}
272
273	void printSnapshot(double secs) {
274	int gens = 0;
275	double best = Double.MAX_VALUE;
276	double worst = 0;
277	for (int k = 0; k < tasks.length; ++k) {
278	gens += tasks[k].gen;
279	Chromosome[] cs = tasks[k].chromosomes;
280	float b = cs[0].fitness;
281	if (b < best)
282	best = b;
283	float w = cs[cs.length-1].fitness;
284	if (w > worst)
285	worst = w;
286	}
287	int avegen = (done.getCount() == 0)? nGen : gens / tasks.length;
288	System.out.printf("Time:%9.3f Best:%9.3f Worst:%9.3f Gen:%6d Threads:%4d\n",
289	secs, best, worst, avegen, nThreads);
290	}
291
292	float averageFitness() { // currently unused
293	float total = 0;
294	int count = 0;
295	for (int k = 0; k < tasks.length; ++k) {
296	Chromosome[] cs = tasks[k].chromosomes;
297	for (int i = 0; i < cs.length; i++)
298	total += cs[i].fitness;
299	count += cs.length;
300	}
301	return total/(float)count;
302	}
303	}
304
305	/**
306	* A Task updates its pool of chromosomes..
307	*/
308	static final class Task implements Runnable {
309	/** The pool of chromosomes, kept in sorted order */
310	final Chromosome[] chromosomes;
311	final Population pop;
312	/** The common exchanger, same for all tasks */
313	final Exchanger<Strand> exchanger;
314	/** The current strand being exchanged */
315	Strand strand;
316	/** Bitset used in cross */
317	final int[] inTour;
318	final RNG rng;
319	final int poolSize;
320	final int nGen;
321	int gen;
322
323	Task(Population pop) {
324	this.pop = pop;
325	this.nGen = pop.nGen;
326	this.gen = 0;
327	this.poolSize = pop.poolSize;
328	this.exchanger = pop.exchanger;
329	this.rng = new RNG();
330	int length = cities.length;
331	this.strand = new Strand(length);
332	this.inTour = new int[(length >>> 5) + 1];
333	this.chromosomes = new Chromosome[poolSize];
334	for (int j = 0; j < poolSize; ++j)
335	chromosomes[j] = new Chromosome(length, rng);
336	Arrays.sort(chromosomes);
337	}
338
339	/**
340	* Run one or more update cycles.
341	*/
342	public void run() {
343	try {
344	for (;;) {
345	update();
346	if (++gen >= nGen) {
347	pop.taskDone();
348	return;
349	}
350	if ((rng.next() & RESUBMIT_MASK) == 1) {
351	pop.resubmit(this);
352	return;
353	}
354	}
355	} catch (InterruptedException ie) {
356	pop.taskDone();
357	}
358	}
359
360	/**
361	* Choose a breeder, exchange strand with another pool, and
362	* cross them to create new chromosome to replace a chosen
363	* dyer.
364	*/
365	void update() throws InterruptedException {
366	int b = chooseBreeder();
367	int d = chooseDyer(b);
368	Chromosome breeder = chromosomes[b];
369	Chromosome child = chromosomes[d];
370	chooseStrand(breeder);
371	strand = exchanger.exchange(strand);
372	cross(breeder, child);
373	fixOrder(child, d);
374	}
375
376	/**
377	* Choose a breeder, with exponentially decreasing probability
378	* starting at best.
379	* @return index of selected breeder
380	*/
381	int chooseBreeder() {
382	int mask = (poolSize >>> BREEDER_DECAY) - 1;
383	int b = 0;
384	while ((rng.next() & mask) != mask) {
385	if (++b >= poolSize)
386	b = 0;
387	}
388	return b;
389	}
390
391	/**
392	* Choose a chromosome that will be replaced, with
393	* exponentially decreasing probablility starting at
394	* worst, ignoring the excluded index
395	* @param exclude index to ignore; use -1 to not exclude any
396	* @return index of selected dyer
397	*/
398	int chooseDyer(int exclude) {
399	int mask = (poolSize >>> DYER_DECAY) - 1;
400	int d = poolSize - 1;
401	while (d == exclude \|\| (rng.next() & mask) != mask) {
402	if (--d < 0)
403	d = poolSize - 1;
404	}
405	return d;
406	}
407
408	/**
409	* Select a random strand of b's.
410	* @param breeder the breeder
411	*/
412	void chooseStrand(Chromosome breeder) {
413	int[] bs = breeder.alleles;
414	int length = bs.length;
415	int strandLength = MIN_STRAND_LENGTH;
416	while (strandLength < length &&
417	(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK)
418	strandLength++;
419	strand.strandLength = strandLength;
420	int[] ss = strand.alleles;
421	int k = (rng.next() & 0x7FFFFFFF) % length;
422	for (int i = 0; i < strandLength; ++i) {
423	ss[i] = bs[k];
424	if (++k >= length) k = 0;
425	}
426	}
427
428	/**
429	* Copy current strand to start of c's, and then append all
430	* remaining b's that aren't in the strand.
431	* @param breeder the breeder
432	* @param child the child
433	*/
434	void cross(Chromosome breeder, Chromosome child) {
435	for (int k = 0; k < inTour.length; ++k) // clear bitset
436	inTour[k] = 0;
437
438	// Copy current strand to c
439	int[] cs = child.alleles;
440	int ssize = strand.strandLength;
441	int[] ss = strand.alleles;
442	int i;
443	for (i = 0; i < ssize; ++i) {
444	int x = ss[i];
445	cs[i] = x;
446	inTour[x >>> 5] \|= 1 << (x & 31); // record in bit set
447	}
448
449	// Find index of matching origin in b
450	int first = cs[0];
451	int j = 0;
452	int[] bs = breeder.alleles;
453	while (bs[j] != first)
454	++j;
455
456	// Append remaining b's that aren't already in tour
457	while (i < cs.length) {
458	if (++j >= bs.length) j = 0;
459	int x = bs[j];
460	if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
461	cs[i++] = x;
462	}
463
464	}
465
466	/**
467	* Fix the sort order of a changed Chromosome c at position k
468	* @param c the chromosome
469	* @param k the index
470	*/
471	void fixOrder(Chromosome c, int k) {
472	Chromosome[] cs = chromosomes;
473	float oldFitness = c.fitness;
474	c.recalcFitness();
475	float newFitness = c.fitness;
476	if (newFitness < oldFitness) {
477	int j = k;
478	int p = j - 1;
479	while (p >= 0 && cs[p].fitness > newFitness) {
480	cs[j] = cs[p];
481	j = p--;
482	}
483	cs[j] = c;
484	} else if (newFitness > oldFitness) {
485	int j = k;
486	int n = j + 1;
487	while (n < cs.length && cs[n].fitness < newFitness) {
488	cs[j] = cs[n];
489	j = n++;
490	}
491	cs[j] = c;
492	}
493	}
494	}
495
496	/**
497	* A Chromosome is a candidate TSP tour.
498	*/
499	static final class Chromosome implements Comparable {
500	/** Index of cities in tour order */
501	final int[] alleles;
502	/** Total tour length */
503	float fitness;
504
505	/**
506	* Initialize to random tour
507	*/
508	Chromosome(int length, RNG random) {
509	alleles = new int[length];
510	for (int i = 0; i < length; i++)
511	alleles[i] = i;
512	for (int i = length - 1; i > 0; i--) {
513	int idx = (random.next() & 0x7FFFFFFF) % alleles.length;
514	int tmp = alleles[i];
515	alleles[i] = alleles[idx];
516	alleles[idx] = tmp;
517	}
518	recalcFitness();
519	}
520
521	public int compareTo(Object x) { // to enable sorting
522	float xf = ((Chromosome)x).fitness;
523	float f = fitness;
524	return ((f == xf)? 0 :((f < xf)? -1 : 1));
525	}
526
527	void recalcFitness() {
528	int[] a = alleles;
529	int len = a.length;
530	int p = a[0];
531	float f = cities.distanceBetween(a[len-1], p);
532	for (int i = 1; i < len; i++) {
533	int n = a[i];
534	f += cities.distanceBetween(p, n);
535	p = n;
536	}
537	fitness = f;
538	}
539
540	void validate() { // Ensure that this is a valid tour.
541	int len = alleles.length;
542	boolean[] used = new boolean[len];
543	for (int i = 0; i < len; ++i)
544	used[alleles[i]] = true;
545	for (int i = 0; i < len; ++i)
546	if (!used[i])
547	throw new Error("Bad tour");
548	}
549
550	}
551
552	/**
553	* A Strand is a random sub-sequence of a Chromosome. Each task
554	* creates only one strand, and then trades it with others,
555	* refilling it on each iteration.
556	*/
557	static final class Strand {
558	final int[] alleles;
559	int strandLength;
560	Strand(int length) { alleles = new int[length]; }
561	}
562
563	/**
564	* A collection of (x,y) points that represent cities. Distances
565	* are scaled in [0,1) to simply checking results. The expected
566	* optimal TSP for random points is believed to be around 0.76 *
567	* sqrt(N). For papers discussing this, see
568	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html for
569	*/
570	static final class CitySet {
571	// Scale ints to doubles in [0,1)
572	static final double PSCALE = (double)0x80000000L;
573
574	final int length;
575	final int[] xPts;
576	final int[] yPts;
577	final float[][] distances;
578
579	CitySet(int n) {
580	this.length = n;
581	this.xPts = new int[n];
582	this.yPts = new int[n];
583	this.distances = new float[n][n];
584
585	RNG random = new RNG();
586	for (int i = 0; i < n; i++) {
587	xPts[i] = (random.next() & 0x7FFFFFFF);
588	yPts[i] = (random.next() & 0x7FFFFFFF);
589	}
590
591	for (int i = 0; i < n; i++) {
592	for (int j = 0; j < n; j++) {
593	double dX = (xPts[i] - xPts[j]) / PSCALE;
594	double dY = (yPts[i] - yPts[j]) / PSCALE;
595	distances[i][j] = (float)Math.hypot(dX, dY);
596	}
597	}
598	}
599
600	// Retrieve the cached distance between a pair of cities
601	float distanceBetween(int i, int j) {
602	return distances[i][j];
603	}
604	}
605
606	/**
607	* Cheap XorShift random number generator
608	*/
609	static final class RNG {
610	/** Seed generator for XorShift RNGs */
611	static final Random seedGenerator = new Random();
612
613	int seed;
614	RNG(int seed) { this.seed = seed; }
615	RNG() { this.seed = seedGenerator.nextInt(); }
616
617	int next() {
618	int x = seed;
619	x ^= x << 6;
620	x ^= x >>> 21;
621	x ^= x << 7;
622	seed = x;
623	return x;
624	}
625	}
626
627	static final class ProgressMonitor extends Thread {
628	final Population pop;
629	ProgressMonitor(Population p) { pop = p; }
630	public void run() {
631	double time = 0;
632	try {
633	while (!Thread.interrupted()) {
634	sleep(SNAPSHOT_RATE);
635	time += SNAPSHOT_RATE;
636	pop.printSnapshot(time / 1000.0);
637	}
638	} catch (InterruptedException ie) {}
639	}
640	}
641	}