ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/TSPExchangerTest.java

Comparing jsr166/src/test/loops/TSPExchangerTest.java (file contents):
Revision 1.1 by dl, Sun Aug 7 19:25:55 2005 UTC vs.
Revision 1.16 by jsr166, Thu Aug 8 18:39:10 2013 UTC

#	Line 1 | Line 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.
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/publicdomain/zero/1.0/
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 is
15	+	* distributed among "subpops".  Each chromosomes represents a tour,
16	+	* and its fitness is the total tour length.
17	+	*
18	+	* A set of worker threads perform updates on subpops. The basic
19	+	* update step is:
20	+	* <ol>
21	+	*   <li> Select a breeder b from the subpop
22	+	*   <li> Create a strand of its tour with a random starting point and length
23	+	*   <li> Offer the strand to the exchanger, receiving a strand from
24	+	*        another subpop
25	+	*   <li> Combine b and the received strand using crossing function to
26	+	*        create new chromosome c.
27	+	*   <li> Replace a chromosome in the subpop with c.
28	+	* </ol>
29	+	*
30	+	* This continues for a given number of generations per subpop.
31	+	* Because there are normally more subpops than threads, each worker
32	+	* thread performs small (randomly sized) run of updates for one
33	+	* subpop and then selects another. A run continues until there is at
34	+	* most one remaining thread performing updates.
35	+	*
36	+	* See below for more details.
37	+	*/
38		public class TSPExchangerTest {
39	<	// Set SLS true to use as default the settings in Scherer, Lea, and
40	<	// Scott paper. Otherwise smaller values are used to speed up testing
41	<	static final boolean SLS = false;
42	<
43	<	static final int DEFAULT_THREADS      = SLS?    32:     8;
44	<	static final int DEFAULT_CITIES       = SLS?   100:    50;
45	<	static final int DEFAULT_POPULATION   = SLS?  1000:   500;
46	<	static final int DEFAULT_BREEDERS     = SLS?   200:   100;
47	<	static final int DEFAULT_GENERATIONS  = SLS? 20000: 10000;
39	>	static final int NCPUS = Runtime.getRuntime().availableProcessors();
40	>
41	>	/** Runs start with two threads, increasing by two through max */
42	>	static final int DEFAULT_MAX_THREADS  = Math.max(4, NCPUS + NCPUS/2);
43	>
44	>	/** The number of replication runs per thread value */
45	>	static final int DEFAULT_REPLICATIONS = 3;
46	>
47	>	/** If true, print statistics in SNAPSHOT_RATE intervals */
48	>	static boolean verbose = true;
49	>	static final long SNAPSHOT_RATE = 10000; // in milliseconds
50	>
51	>	/**
52	>	* The problem size. Each city is a random point. The goal is to
53	>	* find a tour among them with smallest total Euclidean distance.
54	>	*/
55	>	static final int DEFAULT_CITIES = 144;
56	>
57	>	// Tuning parameters.
58	>
59	>	/**
60	>	* The number of chromosomes per subpop. Must be a power of two.
61	>	*
62	>	* Smaller values lead to faster iterations but poorer quality
63	>	* results
64	>	*/
65	>	static final int DEFAULT_SUBPOP_SIZE = 32;
66	>
67	>	/**
68	>	* The number of iterations per subpop. Convergence appears
69	>	* to be roughly proportional to #cities-squared
70	>	*/
71	>	static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES;
72
73	+	/**
74	+	* The number of subpops. The total population is #subpops * subpopSize,
75	+	* which should be roughly on the order of #cities-squared
76	+	*
77	+	* Smaller values lead to faster total runs but poorer quality
78	+	* results
79	+	*/
80	+	static final int DEFAULT_NSUBPOPS = DEFAULT_GENERATIONS / DEFAULT_SUBPOP_SIZE;
81	+
82	+	/**
83	+	* The minimum length for a random chromosome strand.
84	+	* Must be at least 1.
85	+	*/
86	+	static final int MIN_STRAND_LENGTH = 3;
87	+
88	+	/**
89	+	* The probability mask value for creating random strands,
90	+	* that have lengths at least MIN_STRAND_LENGTH, and grow
91	+	* with exponential decay 2^(-(1/(RANDOM_STRAND_MASK + 1)
92	+	* Must be 1 less than a power of two.
93	+	*/
94	+	static final int RANDOM_STRAND_MASK = 7;
95	+
96	+	/**
97	+	* Probability control for selecting breeders.
98	+	* Breeders are selected starting at the best-fitness chromosome,
99	+	* with exponentially decaying probability
100	+	* 1 / (subpopSize >>> BREEDER_DECAY).
101	+	*
102	+	* Larger values usually cause faster convergence but poorer
103	+	* quality results
104	+	*/
105	+	static final int BREEDER_DECAY = 1;
106	+
107	+	/**
108	+	* Probability control for selecting dyers.
109	+	* Dyers are selected starting at the worst-fitness chromosome,
110	+	* with exponentially decaying probability
111	+	* 1 / (subpopSize >>> DYER_DECAY)
112	+	*
113	+	* Larger values usually cause faster convergence but poorer
114	+	* quality results
115	+	*/
116	+	static final int DYER_DECAY = 1;
117	+
118	+	/**
119	+	* The set of cities. Created once per program run, to
120	+	* make it easier to compare solutions across different runs.
121	+	*/
122	+	static CitySet cities;
123
124		public static void main(String[] args) throws Exception {
125	<	int maxThreads = DEFAULT_THREADS;
125	>	int maxThreads = DEFAULT_MAX_THREADS;
126		int nCities = DEFAULT_CITIES;
127	<	int pSize = DEFAULT_POPULATION;
128	<	int nBreeders = DEFAULT_BREEDERS;
129	<	int numGenerations = DEFAULT_GENERATIONS;
127	>	int subpopSize = DEFAULT_SUBPOP_SIZE;
128	>	int nGen = nCities * nCities;
129	>	int nSubpops = nCities * nCities / subpopSize;
130	>	int nReps = DEFAULT_REPLICATIONS;
131
31	–	// Parse and check args
32	–	int argc = 0;
132		try {
133	+	int argc = 0;
134		while (argc < args.length) {
135		String option = args[argc++];
136	<	if (option.equals("-b"))
37	<	nBreeders = Integer.parseInt(args[argc]);
38	<	else if (option.equals("-c"))
136	>	if (option.equals("-c")) {
137		nCities = Integer.parseInt(args[argc]);
138	+	nGen = nCities * nCities;
139	+	nSubpops = nCities * nCities / subpopSize;
140	+	}
141	+	else if (option.equals("-p"))
142	+	subpopSize = Integer.parseInt(args[argc]);
143		else if (option.equals("-g"))
144	<	numGenerations = Integer.parseInt(args[argc]);
145	<	else if (option.equals("-p"))
146	<	pSize = Integer.parseInt(args[argc]);
147	<	else
144	>	nGen = Integer.parseInt(args[argc]);
145	>	else if (option.equals("-n"))
146	>	nSubpops = Integer.parseInt(args[argc]);
147	>	else if (option.equals("-q")) {
148	>	verbose = false;
149	>	argc--;
150	>	}
151	>	else if (option.equals("-r"))
152	>	nReps = Integer.parseInt(args[argc]);
153	>	else
154		maxThreads = Integer.parseInt(option);
155		argc++;
156		}
157		}
49	–	catch (NumberFormatException e) {
50	–	reportUsageErrorAndDie();
51	–	System.exit(0);
52	–	}
158		catch (Exception e) {
159		reportUsageErrorAndDie();
160		}
161
162	<	// Display runtime parameters
163	<	System.out.print("TSPExchangerTest -b " + nBreeders);
164	<	System.out.print(" -c " + nCities);
165	<	System.out.print(" -g " + numGenerations);
166	<	System.out.print(" -p " + pSize);
167	<	System.out.print(" max threads " + maxThreads);
168	<	System.out.println();
169	<
170	<	// warmup
171	<	System.out.print("Threads: " + 2 + "\t");
172	<	oneRun(2,
173	<	nCities,
174	<	pSize,
175	<	nBreeders,
176	<	numGenerations);
177	<	Thread.sleep(100);
178	<
179	<	int k = 4;
180	<	for (int i = 2; i <= maxThreads;) {
181	<	System.out.print("Threads: " + i + "\t");
182	<	oneRun(i,
183	<	nCities,
184	<	pSize,
185	<	nBreeders,
186	<	numGenerations);
82	<	Thread.sleep(100);
83	<	if (i == k) {
84	<	k = i << 1;
85	<	i = i + (i >>> 1);
86	<	}
87	<	else
88	<	i = k;
162	>	System.out.print("TSPExchangerTest");
163	>	System.out.print(" -c " + nCities);
164	>	System.out.print(" -g " + nGen);
165	>	System.out.print(" -p " + subpopSize);
166	>	System.out.print(" -n " + nSubpops);
167	>	System.out.print(" -r " + nReps);
168	>	System.out.print(" max threads " + maxThreads);
169	>	System.out.println();
170	>
171	>	cities = new CitySet(nCities);
172	>
173	>	if (false && NCPUS > 4) {
174	>	int h = NCPUS/2;
175	>	System.out.printf("Threads: %4d Warmup\n", h);
176	>	oneRun(h, nSubpops, subpopSize, nGen);
177	>	Thread.sleep(500);
178	>	}
179	>
180	>	int maxt = (maxThreads < nSubpops) ? maxThreads : nSubpops;
181	>	for (int j = 0; j < nReps; ++j) {
182	>	for (int i = 2; i <= maxt; i += 2) {
183	>	System.out.printf("Threads: %4d Replication: %2d\n", i, j);
184	>	oneRun(i, nSubpops, subpopSize, nGen);
185	>	Thread.sleep(500);
186	>	}
187		}
188		}
189
190	<	private static void reportUsageErrorAndDie() {
191	<	System.out.print("usage: TSPExchangerTest [-b #breeders] [-c #cities]");
192	<	System.out.println(" [-g #generations]");
193	<	System.out.println(" [-p population size] [ #threads]");
190	>	static void reportUsageErrorAndDie() {
191	>	System.out.print("usage: TSPExchangerTest");
192	>	System.out.print(" [-c #cities]");
193	>	System.out.print(" [-p #subpopSize]");
194	>	System.out.print(" [-g #generations]");
195	>	System.out.print(" [-n #subpops]");
196	>	System.out.print(" [-r #replications]");
197	>	System.out.print(" [-q <quiet>]");
198	>	System.out.print(" #threads]");
199	>	System.out.println();
200		System.exit(0);
201		}
202
203	<	static void oneRun(int nThreads,
204	<	int nCities,
205	<	int pSize,
206	<	int nBreeders,
207	<	int numGenerations)
208	<	throws Exception {
209	<	CyclicBarrier runBarrier = new CyclicBarrier(nThreads + 1);
210	<	Population p = new Population(nCities, pSize, nBreeders, nThreads,
211	<	numGenerations, runBarrier);
212	<
213	<	// Run the test
214	<	long startTime = System.currentTimeMillis();
215	<	runBarrier.await(); // start 'em off
216	<	runBarrier.await(); // wait 'til they're done
217	<	long stopTime = System.currentTimeMillis();
218	<	long elapsed = stopTime - startTime;
219	<	long rate = (numGenerations * 1000) / elapsed;
220	<	double secs = (double)elapsed / 1000.0;
203	>	/**
204	>	* Performs one run with the given parameters.  Each run completes
205	>	* when there are fewer than 2 active threads.  When there is
206	>	* only one remaining thread, it will have no one to exchange
207	>	* with, so it is terminated (via interrupt).
208	>	*/
209	>	static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen)
210	>	throws InterruptedException {
211	>	Population p = new Population(nThreads, nSubpops, subpopSize, nGen);
212	>	ProgressMonitor mon = null;
213	>	if (verbose) {
214	>	p.printSnapshot(0);
215	>	mon = new ProgressMonitor(p);
216	>	mon.start();
217	>	}
218	>	long startTime = System.nanoTime();
219	>	p.start();
220	>	p.awaitDone();
221	>	long stopTime = System.nanoTime();
222	>	if (mon != null)
223	>	mon.interrupt();
224	>	p.shutdown();
225	>	//        Thread.sleep(100);
226
227	<	// Display results
228	<	System.out.print(LoopHelpers.rightJustify((int)p.bestFitness()) +
229	<	" fitness");
121	<	System.out.print(LoopHelpers.rightJustify(rate) + " gen/s \t");
122	<	System.out.print(secs + "s elapsed");
123	<	System.out.println();
227	>	long elapsed = stopTime - startTime;
228	>	double secs = (double) elapsed / 1000000000.0;
229	>	p.printSnapshot(secs);
230		}
231
232	+
233	+	/**
234	+	* A Population creates the subpops, subpops, and threads for a run
235	+	* and has control methods to start, stop, and report progress.
236	+	*/
237		static final class Population {
238	<	final Chromosome[] individuals;
239	<	final Exchanger<Chromosome> x;
240	<	final CitySet cities;
241	<	final int[] dyers;
242	<	final int[] breeders;
243	<	final CyclicBarrier generationBarrier;
133	<	final Thread[] threads;
134	<	final boolean[] doneMating;
135	<	final ReentrantLock matingBarrierLock;
136	<	final Condition matingBarrier;
137	<	final LoopHelpers.SimpleRandom[] rngs;
238	>	final Worker[] threads;
239	>	final Subpop[] subpops;
240	>	final Exchanger<Strand> exchanger;
241	>	final CountDownLatch done;
242	>	final int nGen;
243	>	final int subpopSize;
244		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	–	}
245
246	<	Population(int nCities,
150	<	int pSize,
151	<	int nBreeders,
152	<	int nThreads,
153	<	int nGen,
154	<	CyclicBarrier runBarrier) {
246	>	Population(int nThreads, int nSubpops, int subpopSize, int nGen) {
247		this.nThreads = nThreads;
248	<	// rngs[nThreads] is for global actions; others are per-thread
249	<	this.rngs = new LoopHelpers.SimpleRandom[nThreads+1];
250	<	for (int i = 0; i < rngs.length; ++i)
251	<	rngs[i] = new LoopHelpers.SimpleRandom();
252	<	this.cities = new CitySet(nCities, rngs[nThreads]);
253	<	this.individuals = new Chromosome[pSize];
254	<	for (int i = 0; i < individuals.length; i++)
255	<	individuals[i] = new Chromosome(cities, nCities,
256	<	rngs[nThreads]);
257	<	this.doneMating = new boolean[nThreads];
258	<	this.dyers = new int[nBreeders];
259	<	this.breeders = new int[nBreeders];
260	<
261	<	this.x = new Exchanger();
262	<
263	<	this.matingBarrierLock = new ReentrantLock();
264	<	this.matingBarrier = matingBarrierLock.newCondition();
265	<
266	<	BarrierAction ba = new BarrierAction();
267	<	this.generationBarrier = new CyclicBarrier(nThreads, ba);
268	<	ba.run(); // prepare for first generation
269	<
270	<	this.threads = new Thread[nThreads];
271	<	for (int i = 0; i < nThreads; i++) {
272	<	Runner r = new Runner(i, this, runBarrier, nGen);
273	<	threads[i] = new Thread(r);
274	<	threads[i].start();
275	<	}
276	<	}
277	<
278	<	double averageFitness() {
279	<	double total = 0;
280	<	for (int i = 0; i < individuals.length; i++)
281	<	total += individuals[i].fitness;
282	<	return total/(double)individuals.length;
283	<	}
284	<
285	<	double bestFitness() {
286	<	double best = individuals[0].fitness;
287	<	for (int i = 0; i < individuals.length; i++)
288	<	if (individuals[i].fitness < best)
289	<	best = individuals[i].fitness;
290	<	return best;
291	<	}
292	<
293	<	void resetMatingBarrier() {
294	<	matingBarrierCount = nThreads - 1;
295	<	}
296	<
297	<	void awaitMatingBarrier(int tid) {
298	<	doneMating[tid] = true; // heuristically set before lock
299	<	matingBarrierLock.lock();
300	<	try {
301	<	int m = matingBarrierCount--;
302	<	if (m < 1) {
303	<	for (int i = 0; i < doneMating.length; ++i)
304	<	doneMating[i] = false;
305	<	Thread.interrupted(); // clear
306	<	matingBarrier.signalAll();
307	<	} else {
308	<	doneMating[tid] = true;
309	<	if (m == 1 && nThreads > 2) {
310	<	for (int j = 0; j < doneMating.length; ++j) {
311	<	if (!doneMating[j]) {
312	<	threads[j].interrupt();
313	<	break;
314	<	}
315	<	}
316	<	}
317	<	try {
318	<	do {
319	<	matingBarrier.await();
320	<	} while (matingBarrierCount >= 0);
321	<	} catch(InterruptedException ie) {}
230	<	}
231	<	} finally {
232	<	matingBarrierLock.unlock();
233	<	}
248	>	this.nGen = nGen;
249	>	this.subpopSize = subpopSize;
250	>	this.exchanger = new Exchanger<Strand>();
251	>	this.done = new CountDownLatch(nThreads - 1);
252	>
253	>	this.subpops = new Subpop[nSubpops];
254	>	for (int i = 0; i < nSubpops; i++)
255	>	subpops[i] = new Subpop(this);
256	>
257	>	this.threads = new Worker[nThreads];
258	>	int maxExchanges = nGen * nSubpops / nThreads;
259	>	for (int i = 0; i < nThreads; ++i) {
260	>	threads[i] = new Worker(this, maxExchanges);
261	>	}
262	>
263	>	}
264	>
265	>	void start() {
266	>	for (int i = 0; i < nThreads; ++i) {
267	>	threads[i].start();
268	>	}
269	>	}
270	>
271	>	/** Stop the tasks */
272	>	void shutdown() {
273	>	for (int i = 0; i < threads.length; ++ i)
274	>	threads[i].interrupt();
275	>	}
276	>
277	>	void threadDone() {
278	>	done.countDown();
279	>	}
280	>
281	>	/** Wait for tasks to complete */
282	>	void awaitDone() throws InterruptedException {
283	>	done.await();
284	>	}
285	>
286	>	int totalExchanges() {
287	>	int xs = 0;
288	>	for (int i = 0; i < threads.length; ++i)
289	>	xs += threads[i].exchanges;
290	>	return xs;
291	>	}
292	>
293	>	/**
294	>	* Prints statistics, including best and worst tour lengths
295	>	* for points scaled in [0,1), scaled by the square root of
296	>	* number of points. This simplifies checking results.  The
297	>	* expected optimal TSP for random points is believed to be
298	>	* around 0.76 * sqrt(N). For papers discussing this, see
299	>	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
300	>	*/
301	>	void printSnapshot(double secs) {
302	>	int xs = totalExchanges();
303	>	long rate = (xs == 0) ? 0L : (long) ((secs * 1000000000.0) / xs);
304	>	Chromosome bestc = subpops[0].chromosomes[0];
305	>	Chromosome worstc = bestc;
306	>	for (int k = 0; k < subpops.length; ++k) {
307	>	Chromosome[] cs = subpops[k].chromosomes;
308	>	if (cs[0].fitness < bestc.fitness)
309	>	bestc = cs[0];
310	>	int w = cs[cs.length-1].fitness;
311	>	if (cs[cs.length-1].fitness > worstc.fitness)
312	>	worstc = cs[cs.length-1];
313	>	}
314	>	double sqrtn = Math.sqrt(cities.length);
315	>	double best = bestc.unitTourLength() / sqrtn;
316	>	double worst = worstc.unitTourLength() / sqrtn;
317	>	System.out.printf("N:%4d T:%8.3f B:%6.3f W:%6.3f X:%9d R:%7d\n",
318	>	nThreads, secs, best, worst, xs, rate);
319	>	//            exchanger.printStats();
320	>	//            System.out.print(" s: " + exchanger.aveSpins());
321	>	//            System.out.print(" p: " + exchanger.aveParks());
322		}
323	+	}
324
325	<	void prepareToBreed() {
325	>	/**
326	>	* Worker threads perform updates on subpops.
327	>	*/
328	>	static final class Worker extends Thread {
329	>	final Population pop;
330	>	final int maxExchanges;
331	>	int exchanges;
332	>	final RNG rng = new RNG();
333	>
334	>	Worker(Population pop, int maxExchanges) {
335	>	this.pop = pop;
336	>	this.maxExchanges = maxExchanges;
337	>	}
338
339	<	// Calculate statistics
340	<	double totalFitness = 0;
341	<	double worstFitness = 0;
342	<	double bestFitness = individuals[0].fitness;
343	<
344	<	for (int i = 0; i < individuals.length; i++) {
345	<	totalFitness += individuals[i].fitness;
346	<	if (individuals[i].fitness > worstFitness)
347	<	worstFitness = individuals[i].fitness;
348	<	if (individuals[i].fitness < bestFitness)
349	<	bestFitness = individuals[i].fitness;
350	<	}
351	<
352	<	double[] lifeNorm = new double[individuals.length];
353	<	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;
339	>	/**
340	>	* Repeatedly, find a subpop that is not being updated by
341	>	* another thread, and run a random number of updates on it.
342	>	*/
343	>	public void run() {
344	>	try {
345	>	int len = pop.subpops.length;
346	>	int pos = (rng.next() & 0x7FFFFFFF) % len;
347	>	while (exchanges < maxExchanges) {
348	>	Subpop s = pop.subpops[pos];
349	>	AtomicBoolean busy = s.busy;
350	>	if (!busy.get() && busy.compareAndSet(false, true)) {
351	>	exchanges += s.runUpdates();
352	>	busy.set(false);
353	>	pos = (rng.next() & 0x7FFFFFFF) % len;
354		}
355	<	for (int j = 0; j < i; j++)
356	<	if (dyers[j] == victim)
357	<	newDead = false;
358	<	} while (!newDead);
359	<	dyers[i] = victim;
355	>	else if (++pos >= len)
356	>	pos = 0;
357	>	}
358	>	pop.threadDone();
359	>	} catch (InterruptedException fallthrough) {
360		}
307	–
361		}
362	+	}
363
364	<
365	<	void nextGeneration(int tid, int matings)
366	<	throws InterruptedException, BrokenBarrierException {
367	<
368	<	int firstChild = ((individuals.length * tid) / nThreads);
369	<	int lastChild = ((individuals.length * (tid + 1)) / nThreads);
370	<	int nChildren =  lastChild - firstChild;
371	<
372	<	int firstSub = ((breeders.length * tid) / nThreads);
373	<	int lastSub = ((breeders.length * (tid + 1)) / nThreads);
374	<	int nSub = lastSub - firstSub;
375	<
376	<	Chromosome[] children = new Chromosome[nChildren];
377	<
378	<	LoopHelpers.SimpleRandom random = rngs[tid];
379	<
380	<	for (int i = 0; i < nSub; i++) {
381	<	Chromosome parent = individuals[breeders[firstSub + i]];
382	<	Chromosome offspring = new Chromosome(parent);
383	<	int k = 0;
384	<	while (k < matings && matingBarrierCount > 0) {
385	<	try {
386	<	Chromosome other = x.exchange(offspring);
387	<	offspring = offspring.reproduceWith(other, random);
388	<	++k;
389	<	} catch (InterruptedException to) {
390	<	break;
391	<	}
364	>	/**
365	>	* A Subpop maintains a set of chromosomes.
366	>	*/
367	>	static final class Subpop {
368	>	/** The chromosomes, kept in sorted order */
369	>	final Chromosome[] chromosomes;
370	>	/** The parent population */
371	>	final Population pop;
372	>	/** Reservation bit for worker threads */
373	>	final AtomicBoolean busy;
374	>	/** The common exchanger, same for all subpops */
375	>	final Exchanger<Strand> exchanger;
376	>	/** The current strand being exchanged */
377	>	Strand strand;
378	>	/** Bitset used in cross */
379	>	final int[] inTour;
380	>	final RNG rng;
381	>	final int subpopSize;
382	>
383	>	Subpop(Population pop) {
384	>	this.pop = pop;
385	>	this.subpopSize = pop.subpopSize;
386	>	this.exchanger = pop.exchanger;
387	>	this.busy = new AtomicBoolean(false);
388	>	this.rng = new RNG();
389	>	int length = cities.length;
390	>	this.strand = new Strand(length);
391	>	this.inTour = new int[(length >>> 5) + 1];
392	>	this.chromosomes = new Chromosome[subpopSize];
393	>	for (int j = 0; j < subpopSize; ++j)
394	>	chromosomes[j] = new Chromosome(length, rng);
395	>	Arrays.sort(chromosomes);
396	>	}
397	>
398	>	/**
399	>	* Run a random number of updates.  The number of updates is
400	>	* at least 1 and no more than subpopSize.  This
401	>	* controls the granularity of multiplexing subpop updates on
402	>	* to threads. It is small enough to balance out updates
403	>	* across tasks, but large enough to avoid having runs
404	>	* dominated by subpop selection. It is randomized to avoid
405	>	* long runs where pairs of subpops exchange only with each
406	>	* other.  It is hardwired because small variations of it
407	>	* don't matter much.
408	>	*
409	>	* @param g the first generation to run
410	>	*/
411	>	int runUpdates() throws InterruptedException {
412	>	int n = 1 + (rng.next() & ((subpopSize << 1) - 1));
413	>	for (int i = 0; i < n; ++i)
414	>	update();
415	>	return n;
416	>	}
417	>
418	>	/**
419	>	* Chooses a breeder, exchanges strand with another subpop, and
420	>	* crosses them to create new chromosome to replace a chosen
421	>	* dyer.
422	>	*/
423	>	void update() throws InterruptedException {
424	>	int b = chooseBreeder();
425	>	int d = chooseDyer(b);
426	>	Chromosome breeder = chromosomes[b];
427	>	Chromosome child = chromosomes[d];
428	>	chooseStrand(breeder);
429	>	strand = exchanger.exchange(strand);
430	>	cross(breeder, child);
431	>	fixOrder(child, d);
432	>	}
433	>
434	>	/**
435	>	* Chooses a breeder, with exponentially decreasing probability
436	>	* starting at best.
437	>	* @return index of selected breeder
438	>	*/
439	>	int chooseBreeder() {
440	>	int mask = (subpopSize >>> BREEDER_DECAY) - 1;
441	>	int b = 0;
442	>	while ((rng.next() & mask) != mask) {
443	>	if (++b >= subpopSize)
444	>	b = 0;
445	>	}
446	>	return b;
447	>	}
448	>
449	>	/**
450	>	* Chooses a chromosome that will be replaced, with
451	>	* exponentially decreasing probability starting at
452	>	* worst, ignoring the excluded index.
453	>	* @param exclude index to ignore; use -1 to not exclude any
454	>	* @return index of selected dyer
455	>	*/
456	>	int chooseDyer(int exclude) {
457	>	int mask = (subpopSize >>> DYER_DECAY)  - 1;
458	>	int d = subpopSize - 1;
459	>	while (d == exclude || (rng.next() & mask) != mask) {
460	>	if (--d < 0)
461	>	d = subpopSize - 1;
462	>	}
463	>	return d;
464	>	}
465	>
466	>	/**
467	>	* Select a random strand of b's.
468	>	* @param breeder the breeder
469	>	*/
470	>	void chooseStrand(Chromosome breeder) {
471	>	int[] bs = breeder.alleles;
472	>	int length = bs.length;
473	>	int strandLength = MIN_STRAND_LENGTH;
474	>	while (strandLength < length &&
475	>	(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK)
476	>	strandLength++;
477	>	strand.strandLength = strandLength;
478	>	int[] ss = strand.alleles;
479	>	int k = (rng.next() & 0x7FFFFFFF) % length;
480	>	for (int i = 0; i < strandLength; ++i) {
481	>	ss[i] = bs[k];
482	>	if (++k >= length) k = 0;
483	>	}
484	>	}
485	>
486	>	/**
487	>	* Copies current strand to start of c's, and then appends all
488	>	* remaining b's that aren't in the strand.
489	>	* @param breeder the breeder
490	>	* @param child the child
491	>	*/
492	>	void cross(Chromosome breeder, Chromosome child) {
493	>	for (int k = 0; k < inTour.length; ++k) // clear bitset
494	>	inTour[k] = 0;
495	>
496	>	// Copy current strand to c
497	>	int[] cs = child.alleles;
498	>	int ssize = strand.strandLength;
499	>	int[] ss = strand.alleles;
500	>	int i;
501	>	for (i = 0; i < ssize; ++i) {
502	>	int x = ss[i];
503	>	cs[i] = x;
504	>	inTour[x >>> 5] |= 1 << (x & 31); // record in bit set
505	>	}
506	>
507	>	// Find index of matching origin in b
508	>	int first = cs[0];
509	>	int j = 0;
510	>	int[] bs = breeder.alleles;
511	>	while (bs[j] != first)
512	>	++j;
513	>
514	>	// Append remaining b's that aren't already in tour
515	>	while (i < cs.length) {
516	>	if (++j >= bs.length) j = 0;
517	>	int x = bs[j];
518	>	if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
519	>	cs[i++] = x;
520	>	}
521	>
522	>	}
523	>
524	>	/**
525	>	* Fixes the sort order of a changed Chromosome c at position k.
526	>	* @param c the chromosome
527	>	* @param k the index
528	>	*/
529	>	void fixOrder(Chromosome c, int k) {
530	>	Chromosome[] cs = chromosomes;
531	>	int oldFitness = c.fitness;
532	>	c.recalcFitness();
533	>	int newFitness = c.fitness;
534	>	if (newFitness < oldFitness) {
535	>	int j = k;
536	>	int p = j - 1;
537	>	while (p >= 0 && cs[p].fitness > newFitness) {
538	>	cs[j] = cs[p];
539	>	j = p--;
540		}
541	<	if (k != 0)
542	<	children[i] = offspring;
543	<	else {
544	<	// No peers, so we mate with ourselves
545	<	for ( ; i < nSub - 1; i += 2) {
546	<	int cur = firstSub + i;
547	<	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;
541	>	cs[j] = c;
542	>	} else if (newFitness > oldFitness) {
543	>	int j = k;
544	>	int n = j + 1;
545	>	while (n < cs.length && cs[n].fitness < newFitness) {
546	>	cs[j] = cs[n];
547	>	j = n++;
548		}
549	<
549	>	cs[j] = c;
550		}
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();
551		}
552		}
553
554	<	static final class Chromosome {
555	<	private final CitySet cities;
556	<	private final int[] alleles;
557	<	private final int length;
558	<	public  double fitness; // immutable after publication
559	<
560	<	// Basic constructor - gets randomized genetic code
561	<	Chromosome(CitySet cities, int length,
562	<	LoopHelpers.SimpleRandom random) {
563	<	this.length = length;
564	<	this.cities = cities;
565	<	// Initialize alleles to a random shuffle
554	>	/**
555	>	* A Chromosome is a candidate TSP tour.
556	>	*/
557	>	static final class Chromosome implements Comparable {
558	>	/** Index of cities in tour order */
559	>	final int[] alleles;
560	>	/** Total tour length */
561	>	int fitness;
562	>
563	>	/**
564	>	* Initializes to random tour.
565	>	*/
566	>	Chromosome(int length, RNG random) {
567		alleles = new int[length];
568		for (int i = 0; i < length; i++)
569		alleles[i] = i;
570		for (int i = length - 1; i > 0; i--) {
571	+	int idx = (random.next() & 0x7FFFFFFF) % alleles.length;
572		int tmp = alleles[i];
388	–	int idx = random.next() % length;
573		alleles[i] = alleles[idx];
574		alleles[idx] = tmp;
575		}
576		recalcFitness();
577		}
578	<
579	<	// Copy constructor - clones parent's genetic code
580	<	Chromosome(Chromosome clone) {
581	<	length = clone.length;
582	<	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;
578	>
579	>	public int compareTo(Object x) { // to enable sorting
580	>	int xf = ((Chromosome) x).fitness;
581	>	int f = fitness;
582	>	return ((f == xf) ? 0 :((f < xf) ? -1 : 1));
583		}
584	<
584	>
585		void recalcFitness() {
586	<	fitness = cities.distanceBetween(alleles[0], alleles[length-1]);
587	<	for (int i = 1; i < length; i++) {
588	<	fitness += cities.distanceBetween(alleles[i-1], alleles[i]);
589	<	}
590	<	}
591	<
592	<	Chromosome breedWith(Chromosome partner, int n,
593	<	LoopHelpers.SimpleRandom random) {
594	<	Chromosome offspring = new Chromosome(this);
595	<	for (int i = 0; i < n; i++)
596	<	offspring = offspring.reproduceWith(partner, random);
597	<	return offspring;
598	<	}
599	<
600	<	Chromosome reproduceWith(Chromosome other,
601	<	LoopHelpers.SimpleRandom random) {
602	<	Chromosome child = new Chromosome(this);
603	<	int coStart = random.next() % length;
604	<	int coLen = 3;
605	<	while (1 == (random.next() & 1) && (coLen < length))
606	<	coLen++;
607	<	int cPos, pPos;
608	<
609	<	int join = other.getAllele(coStart);
610	<	child.alleles[0] = join;
611	<
612	<	for (pPos = 0; alleles[pPos] != join; pPos++)
613	<	;
614	<
615	<	for (cPos = 1; cPos < coLen; cPos++)
616	<	child.setAllele(cPos, other.getAllele(coStart + cPos));
617	<
618	<	for (int i = 0; i < length; i++) {
619	<	boolean found = false;
620	<	int allele = getAllele(pPos++);
621	<	for (int j = 0; j < coLen; j++) {
622	<	if (found = (child.getAllele(j) == allele))
623	<	break;
624	<	}
451	<	if (!found)
452	<	child.setAllele(cPos++, allele);
453	<	}
454	<
455	<	child.recalcFitness();
456	<	return child;
586	>	int[] a = alleles;
587	>	int len = a.length;
588	>	int p = a[0];
589	>	long f = cities.distanceBetween(a[len-1], p);
590	>	for (int i = 1; i < len; i++) {
591	>	int n = a[i];
592	>	f += cities.distanceBetween(p, n);
593	>	p = n;
594	>	}
595	>	fitness = (int) (f / len);
596	>	}
597	>
598	>	/**
599	>	* Returns tour length for points scaled in [0, 1).
600	>	*/
601	>	double unitTourLength() {
602	>	int[] a = alleles;
603	>	int len = a.length;
604	>	int p = a[0];
605	>	double f = cities.unitDistanceBetween(a[len-1], p);
606	>	for (int i = 1; i < len; i++) {
607	>	int n = a[i];
608	>	f += cities.unitDistanceBetween(p, n);
609	>	p = n;
610	>	}
611	>	return f;
612	>	}
613	>
614	>	/**
615	>	* Checks that this tour visits each city.
616	>	*/
617	>	void validate() {
618	>	int len = alleles.length;
619	>	boolean[] used = new boolean[len];
620	>	for (int i = 0; i < len; ++i)
621	>	used[alleles[i]] = true;
622	>	for (int i = 0; i < len; ++i)
623	>	if (!used[i])
624	>	throw new Error("Bad tour");
625		}
626	<
626	>
627		}
628	+
629		/**
630	<	* A collection of (x,y) points that represent cities
630	>	* A Strand is a random sub-sequence of a Chromosome.  Each subpop
631	>	* creates only one strand, and then trades it with others,
632	>	* refilling it on each iteration.
633	>	*/
634	>	static final class Strand {
635	>	final int[] alleles;
636	>	int strandLength;
637	>	Strand(int length) { alleles = new int[length]; }
638	>	}
639	>
640	>	/**
641	>	* A collection of (x,y) points that represent cities.
642		*/
643		static final class CitySet {
644	<	final int XMAX = 1000;
465	<	final int YMAX = 1000;
644	>
645		final int length;
646	<	final int xPts[];
647	<	final int yPts[];
648	<	final double distances[];
649	<
650	<	CitySet(int n, LoopHelpers.SimpleRandom random) {
646	>	final int[] xPts;
647	>	final int[] yPts;
648	>	final int[][] distances;
649	>
650	>	CitySet(int n) {
651		this.length = n;
652	<	xPts = new int[n];
653	<	yPts = new int [n];
652	>	this.xPts = new int[n];
653	>	this.yPts = new int[n];
654	>	this.distances = new int[n][n];
655	>
656	>	RNG random = new RNG();
657		for (int i = 0; i < n; i++) {
658	<	xPts[i] = random.next() % XMAX;
659	<	yPts[i] = random.next() % YMAX;
658	>	xPts[i] = (random.next() & 0x7FFFFFFF);
659	>	yPts[i] = (random.next() & 0x7FFFFFFF);
660		}
661	<	distances = new double[n * n];
661	>
662		for (int i = 0; i < n; i++) {
663		for (int j = 0; j < n; j++) {
664	<	double dX = (double)(xPts[i] - xPts[j]);
665	<	double dY = (double)(yPts[i] - yPts[j]);
666	<	distances[i + j * n] = Math.hypot(dX, dY);
664	>	double dx = (double) xPts[i] - (double) xPts[j];
665	>	double dy = (double) yPts[i] - (double) yPts[j];
666	>	double dd = Math.hypot(dx, dy) / 2.0;
667	>	long ld = Math.round(dd);
668	>	distances[i][j] = (ld >= Integer.MAX_VALUE) ?
669	>	Integer.MAX_VALUE : (int) ld;
670		}
671		}
672		}
673	<
674	<	// Retrieve the cached distance between a pair of cities
675	<	double distanceBetween(int idx1, int idx2) {
676	<	return distances[idx1 + idx2 * length];
673	>
674	>	/**
675	>	* Returns the cached distance between a pair of cities.
676	>	*/
677	>	int distanceBetween(int i, int j) {
678	>	return distances[i][j];
679	>	}
680	>
681	>	// Scale ints to doubles in [0,1)
682	>	static final double PSCALE = (double) 0x80000000L;
683	>
684	>	/**
685	>	* Returns distance for points scaled in [0,1). This simplifies
686	>	* checking results.  The expected optimal TSP for random
687	>	* points is believed to be around 0.76 * sqrt(N). For papers
688	>	* discussing this, see
689	>	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
690	>	*/
691	>	double unitDistanceBetween(int i, int j) {
692	>	double dx = ((double) xPts[i] - (double) xPts[j]) / PSCALE;
693	>	double dy = ((double) yPts[i] - (double) yPts[j]) / PSCALE;
694	>	return Math.hypot(dx, dy);
695		}
696	+
697		}
698
699	<	static final class Runner implements Runnable {
700	<	final Population pop;
701	<	final CyclicBarrier b;
702	<	final int nGen;
703	<	final int tid;
704	<	static final boolean verbose = false;
705	<
706	<	Runner(int tid, Population p, CyclicBarrier b, int n) {
707	<	this.tid = tid;
708	<	this.pop = p;
709	<	this.b = b;
710	<	this.nGen = n;
699	>	/**
700	>	* Cheap XorShift random number generator
701	>	*/
702	>	static final class RNG {
703	>	/** Seed generator for XorShift RNGs */
704	>	static final Random seedGenerator = new Random();
705	>
706	>	int seed;
707	>	RNG(int seed) { this.seed = seed; }
708	>	RNG()         { this.seed = seedGenerator.nextInt() | 1; }
709	>
710	>	int next() {
711	>	int x = seed;
712	>	x ^= x << 6;
713	>	x ^= x >>> 21;
714	>	x ^= x << 7;
715	>	seed = x;
716	>	return x;
717		}
718	<
718	>	}
719	>
720	>	static final class ProgressMonitor extends Thread {
721	>	final Population pop;
722	>	ProgressMonitor(Population p) { pop = p; }
723		public void run() {
724	+	double time = 0;
725		try {
726	<	b.await();
727	<	for (int i = 0; i < nGen; i++) {
728	<	if (verbose && 0 == tid && 0 == i % 1000) {
729	<	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);
726	>	while (!Thread.interrupted()) {
727	>	sleep(SNAPSHOT_RATE);
728	>	time += SNAPSHOT_RATE;
729	>	pop.printSnapshot(time / 1000.0);
730		}
731	<	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	<	}
731	>	} catch (InterruptedException ie) {}
732		}
733		}
734		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines