test/loops/TSPExchangerTest.java

/*
 * 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.
 */

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;

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;


    public static void main(String[] args) throws Exception {
        int maxThreads = DEFAULT_THREADS;
        int nCities = DEFAULT_CITIES;
        int pSize = DEFAULT_POPULATION;
        int nBreeders = DEFAULT_BREEDERS;
        int numGenerations = DEFAULT_GENERATIONS;

        // Parse and check args
        int argc = 0;
        try {
            while (argc < args.length) {
                String option = args[argc++];
                if (option.equals("-b"))
                    nBreeders = Integer.parseInt(args[argc]);
                else if (option.equals("-c"))
                    nCities = 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 
                    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);

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

    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]");
        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;

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

    static final class Population {
        final Chromosome[] individuals;
        final Exchanger<Chromosome> 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 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) {
            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(); 
            }
        }
        
        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;
        }

        void awaitMatingBarrier(int tid) {
            doneMating[tid] = true; // heuristically set before lock
            matingBarrierLock.lock();
            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;
                            }
                        }
                    }
                    try {
                        do { 
                            matingBarrier.await(); 
                        } while (matingBarrierCount >= 0);
                    } catch(InterruptedException ie) {}
                }
            } finally {
                matingBarrierLock.unlock();
            }
        }

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

        }

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

            }

            awaitMatingBarrier(tid);

            // Kill off dead guys
            for (int i = 0; i < nSub; i++) {
                individuals[dyers[firstSub + 1]] = children[i];
            }

            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
            alleles = new int[length];
            for (int i = 0; i < length; i++)
                alleles[i] = i;
            for (int i = length - 1; i > 0; i--) {
                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;
        }
        
        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;
        }
        
        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
     */
    static final class CitySet {
        final int XMAX = 1000;
        final int YMAX = 1000;
        final int length;
        final int xPts[];
        final int yPts[];
        final double distances[];
        
        CitySet(int n, LoopHelpers.SimpleRandom random) {
            this.length = n;
            xPts = new int[n];
            yPts = new int [n];
            for (int i = 0; i < n; i++) {
                xPts[i] = random.next() % XMAX;
                yPts[i] = random.next() % YMAX;
            }
            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);
                }
            }
        }
        
        // Retrieve the cached distance between a pair of cities
        double distanceBetween(int idx1, int idx2) {
            return distances[idx1 + idx2 * length];
        }
    }

    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;
        }
        
        public void run() {
            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);
                }
                b.await();
            } 
            catch (InterruptedException e) {
                e.printStackTrace(System.out);
                System.exit(0);
            }
            catch (BrokenBarrierException e) {
                e.printStackTrace(System.out);
                System.exit(0);
            }
        }
    }
}
Revision:	1.1
Committed:	Sun Aug 7 19:25:55 2005 UTC (18 years, 9 months ago) by dl
Branch:	MAIN
Log Message:	Add exchanger performance tests; update others
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Bill Scherer and Doug Lea with assistance from members
3			* of JCP JSR-166 Expert Group and released to the public domain. Use,
4			* modify, and redistribute this code in any way without
5			* acknowledgement.
6			*/
7
8			import java.util.concurrent.*;
9			import java.util.concurrent.atomic.*;
10			import java.util.concurrent.locks.*;
11
12			public class TSPExchangerTest {
13			// Set SLS true to use as default the settings in Scherer, Lea, and
14			// Scott paper. Otherwise smaller values are used to speed up testing
15			static final boolean SLS = false;
16
17			static final int DEFAULT_THREADS = SLS? 32: 8;
18			static final int DEFAULT_CITIES = SLS? 100: 50;
19			static final int DEFAULT_POPULATION = SLS? 1000: 500;
20			static final int DEFAULT_BREEDERS = SLS? 200: 100;
21			static final int DEFAULT_GENERATIONS = SLS? 20000: 10000;
22
23
24			public static void main(String[] args) throws Exception {
25			int maxThreads = DEFAULT_THREADS;
26			int nCities = DEFAULT_CITIES;
27			int pSize = DEFAULT_POPULATION;
28			int nBreeders = DEFAULT_BREEDERS;
29			int numGenerations = DEFAULT_GENERATIONS;
30
31			// Parse and check args
32			int argc = 0;
33			try {
34			while (argc < args.length) {
35			String option = args[argc++];
36			if (option.equals("-b"))
37			nBreeders = Integer.parseInt(args[argc]);
38			else if (option.equals("-c"))
39			nCities = Integer.parseInt(args[argc]);
40			else if (option.equals("-g"))
41			numGenerations = Integer.parseInt(args[argc]);
42			else if (option.equals("-p"))
43			pSize = Integer.parseInt(args[argc]);
44			else
45			maxThreads = Integer.parseInt(option);
46			argc++;
47			}
48			}
49			catch (NumberFormatException e) {
50			reportUsageErrorAndDie();
51			System.exit(0);
52			}
53			catch (Exception e) {
54			reportUsageErrorAndDie();
55			}
56
57			// Display runtime parameters
58			System.out.print("TSPExchangerTest -b " + nBreeders);
59			System.out.print(" -c " + nCities);
60			System.out.print(" -g " + numGenerations);
61			System.out.print(" -p " + pSize);
62			System.out.print(" max threads " + maxThreads);
63			System.out.println();
64
65			// warmup
66			System.out.print("Threads: " + 2 + "\t");
67			oneRun(2,
68			nCities,
69			pSize,
70			nBreeders,
71			numGenerations);
72			Thread.sleep(100);
73
74			int k = 4;
75			for (int i = 2; i <= maxThreads;) {
76			System.out.print("Threads: " + i + "\t");
77			oneRun(i,
78			nCities,
79			pSize,
80			nBreeders,
81			numGenerations);
82			Thread.sleep(100);
83			if (i == k) {
84			k = i << 1;
85			i = i + (i >>> 1);
86			}
87			else
88			i = k;
89			}
90			}
91
92			private static void reportUsageErrorAndDie() {
93			System.out.print("usage: TSPExchangerTest [-b #breeders] [-c #cities]");
94			System.out.println(" [-g #generations]");
95			System.out.println(" [-p population size] [ #threads]");
96			System.exit(0);
97			}
98
99			static void oneRun(int nThreads,
100			int nCities,
101			int pSize,
102			int nBreeders,
103			int numGenerations)
104			throws Exception {
105			CyclicBarrier runBarrier = new CyclicBarrier(nThreads + 1);
106			Population p = new Population(nCities, pSize, nBreeders, nThreads,
107			numGenerations, runBarrier);
108
109			// Run the test
110			long startTime = System.currentTimeMillis();
111			runBarrier.await(); // start 'em off
112			runBarrier.await(); // wait 'til they're done
113			long stopTime = System.currentTimeMillis();
114			long elapsed = stopTime - startTime;
115			long rate = (numGenerations * 1000) / elapsed;
116			double secs = (double)elapsed / 1000.0;
117
118			// Display results
119			System.out.print(LoopHelpers.rightJustify((int)p.bestFitness()) +
120			" fitness");
121			System.out.print(LoopHelpers.rightJustify(rate) + " gen/s \t");
122			System.out.print(secs + "s elapsed");
123			System.out.println();
124			}
125
126			static final class Population {
127			final Chromosome[] individuals;
128			final Exchanger<Chromosome> x;
129			final CitySet cities;
130			final int[] dyers;
131			final int[] breeders;
132			final CyclicBarrier generationBarrier;
133			final Thread[] threads;
134			final boolean[] doneMating;
135			final ReentrantLock matingBarrierLock;
136			final Condition matingBarrier;
137			final LoopHelpers.SimpleRandom[] rngs;
138			final int nThreads;
139			volatile int matingBarrierCount;
140
141			// action to run between each generation
142			class BarrierAction implements Runnable {
143			public void run() {
144			prepareToBreed();
145			resetMatingBarrier();
146			}
147			}
148
149			Population(int nCities,
150			int pSize,
151			int nBreeders,
152			int nThreads,
153			int nGen,
154			CyclicBarrier runBarrier) {
155			this.nThreads = nThreads;
156			// rngs[nThreads] is for global actions; others are per-thread
157			this.rngs = new LoopHelpers.SimpleRandom[nThreads+1];
158			for (int i = 0; i < rngs.length; ++i)
159			rngs[i] = new LoopHelpers.SimpleRandom();
160			this.cities = new CitySet(nCities, rngs[nThreads]);
161			this.individuals = new Chromosome[pSize];
162			for (int i = 0; i < individuals.length; i++)
163			individuals[i] = new Chromosome(cities, nCities,
164			rngs[nThreads]);
165			this.doneMating = new boolean[nThreads];
166			this.dyers = new int[nBreeders];
167			this.breeders = new int[nBreeders];
168
169			this.x = new Exchanger();
170
171			this.matingBarrierLock = new ReentrantLock();
172			this.matingBarrier = matingBarrierLock.newCondition();
173
174			BarrierAction ba = new BarrierAction();
175			this.generationBarrier = new CyclicBarrier(nThreads, ba);
176			ba.run(); // prepare for first generation
177
178			this.threads = new Thread[nThreads];
179			for (int i = 0; i < nThreads; i++) {
180			Runner r = new Runner(i, this, runBarrier, nGen);
181			threads[i] = new Thread(r);
182			threads[i].start();
183			}
184			}
185
186			double averageFitness() {
187			double total = 0;
188			for (int i = 0; i < individuals.length; i++)
189			total += individuals[i].fitness;
190			return total/(double)individuals.length;
191			}
192
193			double bestFitness() {
194			double best = individuals[0].fitness;
195			for (int i = 0; i < individuals.length; i++)
196			if (individuals[i].fitness < best)
197			best = individuals[i].fitness;
198			return best;
199			}
200
201			void resetMatingBarrier() {
202			matingBarrierCount = nThreads - 1;
203			}
204
205			void awaitMatingBarrier(int tid) {
206			doneMating[tid] = true; // heuristically set before lock
207			matingBarrierLock.lock();
208			try {
209			int m = matingBarrierCount--;
210			if (m < 1) {
211			for (int i = 0; i < doneMating.length; ++i)
212			doneMating[i] = false;
213			Thread.interrupted(); // clear
214			matingBarrier.signalAll();
215			} else {
216			doneMating[tid] = true;
217			if (m == 1 && nThreads > 2) {
218			for (int j = 0; j < doneMating.length; ++j) {
219			if (!doneMating[j]) {
220			threads[j].interrupt();
221			break;
222			}
223			}
224			}
225			try {
226			do {
227			matingBarrier.await();
228			} while (matingBarrierCount >= 0);
229			} catch(InterruptedException ie) {}
230			}
231			} finally {
232			matingBarrierLock.unlock();
233			}
234			}
235
236			void prepareToBreed() {
237
238			// Calculate statistics
239			double totalFitness = 0;
240			double worstFitness = 0;
241			double bestFitness = individuals[0].fitness;
242
243			for (int i = 0; i < individuals.length; i++) {
244			totalFitness += individuals[i].fitness;
245			if (individuals[i].fitness > worstFitness)
246			worstFitness = individuals[i].fitness;
247			if (individuals[i].fitness < bestFitness)
248			bestFitness = individuals[i].fitness;
249			}
250
251			double[] lifeNorm = new double[individuals.length];
252			double lifeNormTotal = 0;
253			double[] deathNorm = new double[individuals.length];
254			double deathNormTotal = 0;
255			for (int i = 0; i < individuals.length; i++) {
256			deathNorm[i] = (individuals[i].fitness - bestFitness)
257			/ (worstFitness - bestFitness + 1) + .05;
258			deathNorm[i] = (deathNorm[i] * deathNorm[i]);
259			lifeNorm[i] = 1.0 - deathNorm[i];
260			lifeNormTotal += lifeNorm[i];
261			deathNormTotal += deathNorm[i];
262			}
263
264			double deathScale = deathNormTotal / (double)0x7FFFFFFF;
265			double lifeScale = lifeNormTotal / (double)0x7FFFFFFF;
266
267			int nSub = breeders.length / nThreads;
268			LoopHelpers.SimpleRandom random = rngs[nThreads];
269
270			// Select breeders (need to be distinct)
271			for (int i = 0; i < nSub; i++) {
272			boolean newBreeder;
273			int lucky;
274			do {
275			newBreeder = true;
276			double choice = lifeScale * (double)random.next();
277			for (lucky = 0; lucky < individuals.length; lucky++) {
278			choice -= lifeNorm[lucky];
279			if (choice <= 0)
280			break;
281			}
282			for (int j = 0; j < i; j++)
283			if (breeders[j] == lucky)
284			newBreeder = false;
285			} while (!newBreeder);
286			breeders[i] = lucky;
287			}
288
289			// Select dead guys (need to be distinct)
290			for (int i = 0; i < nSub; i++) {
291			boolean newDead;
292			int victim;
293			do {
294			newDead = true;
295			double choice = deathScale * (double)random.next();
296			for (victim = 0; victim < individuals.length; victim++) {
297			choice -= deathNorm[victim];
298			if (choice <= 0)
299			break;
300			}
301			for (int j = 0; j < i; j++)
302			if (dyers[j] == victim)
303			newDead = false;
304			} while (!newDead);
305			dyers[i] = victim;
306			}
307
308			}
309
310
311			void nextGeneration(int tid, int matings)
312			throws InterruptedException, BrokenBarrierException {
313
314			int firstChild = ((individuals.length * tid) / nThreads);
315			int lastChild = ((individuals.length * (tid + 1)) / nThreads);
316			int nChildren = lastChild - firstChild;
317
318			int firstSub = ((breeders.length * tid) / nThreads);
319			int lastSub = ((breeders.length * (tid + 1)) / nThreads);
320			int nSub = lastSub - firstSub;
321
322			Chromosome[] children = new Chromosome[nChildren];
323
324			LoopHelpers.SimpleRandom random = rngs[tid];
325
326			for (int i = 0; i < nSub; i++) {
327			Chromosome parent = individuals[breeders[firstSub + i]];
328			Chromosome offspring = new Chromosome(parent);
329			int k = 0;
330			while (k < matings && matingBarrierCount > 0) {
331			try {
332			Chromosome other = x.exchange(offspring);
333			offspring = offspring.reproduceWith(other, random);
334			++k;
335			} catch (InterruptedException to) {
336			break;
337			}
338			}
339			if (k != 0)
340			children[i] = offspring;
341			else {
342			// No peers, so we mate with ourselves
343			for ( ; i < nSub - 1; i += 2) {
344			int cur = firstSub + i;
345			Chromosome bro = individuals[breeders[cur]];
346			Chromosome sis = individuals[breeders[cur + 1]];
347
348			children[i] = bro.breedWith(sis, matings, random);
349			children[i+1] = sis.breedWith(bro, matings, random);
350			}
351
352			// Not even a sibling, so we go to asexual reproduction
353			if (i < nSub)
354			children[i] = individuals[breeders[firstSub + 1]];
355			break;
356			}
357
358			}
359
360			awaitMatingBarrier(tid);
361
362			// Kill off dead guys
363			for (int i = 0; i < nSub; i++) {
364			individuals[dyers[firstSub + 1]] = children[i];
365			}
366
367			generationBarrier.await();
368			}
369			}
370
371			static final class Chromosome {
372			private final CitySet cities;
373			private final int[] alleles;
374			private final int length;
375			public double fitness; // immutable after publication
376
377			// Basic constructor - gets randomized genetic code
378			Chromosome(CitySet cities, int length,
379			LoopHelpers.SimpleRandom random) {
380			this.length = length;
381			this.cities = cities;
382			// Initialize alleles to a random shuffle
383			alleles = new int[length];
384			for (int i = 0; i < length; i++)
385			alleles[i] = i;
386			for (int i = length - 1; i > 0; i--) {
387			int tmp = alleles[i];
388			int idx = random.next() % length;
389			alleles[i] = alleles[idx];
390			alleles[idx] = tmp;
391			}
392			recalcFitness();
393			}
394
395			// Copy constructor - clones parent's genetic code
396			Chromosome(Chromosome clone) {
397			length = clone.length;
398			cities = clone.cities;
399			fitness = clone.fitness;
400			alleles = new int[length];
401			System.arraycopy(clone.alleles, 0, alleles, 0, length);
402			}
403
404			int getAllele(int offset) {
405			return alleles[offset % length];
406			}
407			void setAllele(int offset, int v) {
408			alleles[offset % length] = v;
409			}
410
411			void recalcFitness() {
412			fitness = cities.distanceBetween(alleles[0], alleles[length-1]);
413			for (int i = 1; i < length; i++) {
414			fitness += cities.distanceBetween(alleles[i-1], alleles[i]);
415			}
416			}
417
418			Chromosome breedWith(Chromosome partner, int n,
419			LoopHelpers.SimpleRandom random) {
420			Chromosome offspring = new Chromosome(this);
421			for (int i = 0; i < n; i++)
422			offspring = offspring.reproduceWith(partner, random);
423			return offspring;
424			}
425
426			Chromosome reproduceWith(Chromosome other,
427			LoopHelpers.SimpleRandom random) {
428			Chromosome child = new Chromosome(this);
429			int coStart = random.next() % length;
430			int coLen = 3;
431			while (1 == (random.next() & 1) && (coLen < length))
432			coLen++;
433			int cPos, pPos;
434
435			int join = other.getAllele(coStart);
436			child.alleles[0] = join;
437
438			for (pPos = 0; alleles[pPos] != join; pPos++)
439			;
440
441			for (cPos = 1; cPos < coLen; cPos++)
442			child.setAllele(cPos, other.getAllele(coStart + cPos));
443
444			for (int i = 0; i < length; i++) {
445			boolean found = false;
446			int allele = getAllele(pPos++);
447			for (int j = 0; j < coLen; j++) {
448			if (found = (child.getAllele(j) == allele))
449			break;
450			}
451			if (!found)
452			child.setAllele(cPos++, allele);
453			}
454
455			child.recalcFitness();
456			return child;
457			}
458
459			}
460			/**
461			* A collection of (x,y) points that represent cities
462			*/
463			static final class CitySet {
464			final int XMAX = 1000;
465			final int YMAX = 1000;
466			final int length;
467			final int xPts[];
468			final int yPts[];
469			final double distances[];
470
471			CitySet(int n, LoopHelpers.SimpleRandom random) {
472			this.length = n;
473			xPts = new int[n];
474			yPts = new int [n];
475			for (int i = 0; i < n; i++) {
476			xPts[i] = random.next() % XMAX;
477			yPts[i] = random.next() % YMAX;
478			}
479			distances = new double[n * n];
480			for (int i = 0; i < n; i++) {
481			for (int j = 0; j < n; j++) {
482			double dX = (double)(xPts[i] - xPts[j]);
483			double dY = (double)(yPts[i] - yPts[j]);
484			distances[i + j * n] = Math.hypot(dX, dY);
485			}
486			}
487			}
488
489			// Retrieve the cached distance between a pair of cities
490			double distanceBetween(int idx1, int idx2) {
491			return distances[idx1 + idx2 * length];
492			}
493			}
494
495			static final class Runner implements Runnable {
496			final Population pop;
497			final CyclicBarrier b;
498			final int nGen;
499			final int tid;
500			static final boolean verbose = false;
501
502			Runner(int tid, Population p, CyclicBarrier b, int n) {
503			this.tid = tid;
504			this.pop = p;
505			this.b = b;
506			this.nGen = n;
507			}
508
509			public void run() {
510			try {
511			b.await();
512			for (int i = 0; i < nGen; i++) {
513			if (verbose && 0 == tid && 0 == i % 1000) {
514			System.out.print("Gen " + i + " fitness:");
515			System.out.print(" best=" + (int)pop.bestFitness());
516			System.out.println("; avg=" + (int)pop.averageFitness());
517			}
518			int matings = (((nGen - i) * 2) / (nGen)) + 1;
519			pop.nextGeneration(tid, matings);
520			}
521			b.await();
522			}
523			catch (InterruptedException e) {
524			e.printStackTrace(System.out);
525			System.exit(0);
526			}
527			catch (BrokenBarrierException e) {
528			e.printStackTrace(System.out);
529			System.exit(0);
530			}
531			}
532			}
533			}