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

Diff Legend

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