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
#	Content
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	}