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.2 by dl, Sat Dec 10 20:08:51 2005 UTC vs.
Revision 1.19 by jsr166, Sun Sep 13 16:28:14 2015 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea and Bill Scherer with assistance from members
3		* of JCP JSR-166 Expert Group and released to the public domain, as
4	<	* explained at http://creativecommons.org/licenses/publicdomain
4	>	* explained at http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		import java.util.*;
#	Line 11 | Line 11 | import java.util.concurrent.locks.*;
11
12		/**
13		* A parallel Traveling Salesperson Problem (TSP) program based on a
14	<	* genetic algorithm using an Exchanger.  A population of chromosomes
15	<	* is distributed among "pools".  The chromosomes represent tours, and
16	<	* their fitness is the total tour length. Each chromosome is
17	<	* initialized as a random tour.  A Task is associated with each pool.
18	<	* Each task repeatedly does, for a fixed number of iterations
19	<	* (generations):
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 pool
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 pool
25	<	*   <li> Combine b and the received strand using crossing function to
26	<	*        create new chromosome c.
27	<	*   <li> Replace a chromosome in the pool with c.
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.
32	–	* <p>
33	–	*
37		*/
38		public class TSPExchangerTest {
39	<	static final int DEFAULT_MAX_THREADS  =
40	<	(Runtime.getRuntime().availableProcessors() + 2);
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
#	Line 42 | Line 54 | public class TSPExchangerTest {
54		*/
55		static final int DEFAULT_CITIES = 144;
56
57	<	// Tuning parameters.
57	>	// Tuning parameters.
58
59		/**
60	<	* The number of chromosomes per pool. Must be a power of two.
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_POOL_SIZE = 32;
65	>	static final int DEFAULT_SUBPOP_SIZE = 32;
66
67		/**
68	<	* The number of iterations per task. Convergence appears
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 pools. The total population is #pools * poolSize,
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_NPOOLS = DEFAULT_GENERATIONS / DEFAULT_POOL_SIZE;
80	>	static final int DEFAULT_NSUBPOPS = DEFAULT_GENERATIONS / DEFAULT_SUBPOP_SIZE;
81
82		/**
83		* The minimum length for a random chromosome strand.
#	Line 74 | Line 86 | public class TSPExchangerTest {
86		static final int MIN_STRAND_LENGTH = 3;
87
88		/**
89	<	* The probablility mask value for creating random strands,
89	>	* The probability mask value for creating random strands,
90		* that have lengths at least MIN_STRAND_LENGTH, and grow
91	<	* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1)
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	<	* Probablility control for selecting breeders.
97	>	* Probability control for selecting breeders.
98		* Breeders are selected starting at the best-fitness chromosome,
99	<	* with exponentially decaying probablility
100	<	* 1 / (poolSize >>> BREEDER_DECAY).
99	>	* with exponentially decaying probability
100	>	* 1 / (subpopSize >>> BREEDER_DECAY).
101		*
102		* Larger values usually cause faster convergence but poorer
103		* quality results
#	Line 93 | Line 105 | public class TSPExchangerTest {
105		static final int BREEDER_DECAY = 1;
106
107		/**
108	<	* Probablility control for selecting dyers.
108	>	* Probability control for selecting dyers.
109		* Dyers are selected starting at the worst-fitness chromosome,
110	<	* with exponentially decaying probablility
111	<	* 1 / (poolSize >>> DYER_DECAY)
110	>	* with exponentially decaying probability
111	>	* 1 / (subpopSize >>> DYER_DECAY)
112		*
113		* Larger values usually cause faster convergence but poorer
114		* quality results
#	Line 104 | Line 116 | public class TSPExchangerTest {
116		static final int DYER_DECAY = 1;
117
118		/**
107	–	* The probability mask for a task to give up running and
108	–	* resubmit itself. On each iteration, a task stops iterating
109	–	* and resubmits itself with probability 1 / (RESUBMIT_MASK+1).
110	–	* This avoids some tasks running to completion before others
111	–	* even start when there are more pools than threads.
112	–	*
113	–	* Must be 1 less than a power of two.
114	–	*/
115	–	static final int RESUBMIT_MASK = 63;
116	–
117	–	static final boolean verbose = true;
118	–	static final long SNAPSHOT_RATE = 10000; // in milliseconds
119	–
120	–	/**
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;
122	>	static CitySet cities;
123
124		public static void main(String[] args) throws Exception {
125		int maxThreads = DEFAULT_MAX_THREADS;
126		int nCities = DEFAULT_CITIES;
127	<	int poolSize = DEFAULT_POOL_SIZE;
127	>	int subpopSize = DEFAULT_SUBPOP_SIZE;
128		int nGen = nCities * nCities;
129	<	int nPools = nCities * nCities / poolSize;
129	>	int nSubpops = nCities * nCities / subpopSize;
130	>	int nReps = DEFAULT_REPLICATIONS;
131
132		try {
133		int argc = 0;
#	Line 137 | Line 136 | public class TSPExchangerTest {
136		if (option.equals("-c")) {
137		nCities = Integer.parseInt(args[argc]);
138		nGen = nCities * nCities;
139	<	nPools = nCities * nCities / poolSize;
139	>	nSubpops = nCities * nCities / subpopSize;
140		}
141		else if (option.equals("-p"))
142	<	poolSize = Integer.parseInt(args[argc]);
142	>	subpopSize = Integer.parseInt(args[argc]);
143		else if (option.equals("-g"))
144		nGen = Integer.parseInt(args[argc]);
145		else if (option.equals("-n"))
146	<	nPools = Integer.parseInt(args[argc]);
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++;
#	Line 157 | Line 162 | public class TSPExchangerTest {
162		System.out.print("TSPExchangerTest");
163		System.out.print(" -c " + nCities);
164		System.out.print(" -g " + nGen);
165	<	System.out.print(" -p " + poolSize);
166	<	System.out.print(" -n " + nPools);
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	<	for (int i = 2; i <= maxThreads; i += 2)
174	<	oneRun(i, nPools, poolSize, nGen);
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		static void reportUsageErrorAndDie() {
191		System.out.print("usage: TSPExchangerTest");
192		System.out.print(" [-c #cities]");
193	<	System.out.print(" [-p #poolSize]");
193	>	System.out.print(" [-p #subpopSize]");
194		System.out.print(" [-g #generations]");
195	<	System.out.print(" [-n #pools]");
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		/**
204	<	* Perform one run with the given parameters.  Each run completes
205	<	* when all but one of the tasks has finished.  The last remaining
206	<	* task may have no one left to exchange with, so the pool is
207	<	* abruptly terminated.
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 nPools, int poolSize, int nGen)
209	>	static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen)
210		throws InterruptedException {
211	<	Population p = new Population(nThreads, nPools, poolSize, nGen);
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		}
196	–	p.printSnapshot(0);
218		long startTime = System.nanoTime();
219		p.start();
220	<	p.awaitTasks();
220	>	p.awaitDone();
221		long stopTime = System.nanoTime();
222		if (mon != null)
223		mon.interrupt();
224		p.shutdown();
225	<	Thread.sleep(100);
225	>	//        Thread.sleep(100);
226
227		long elapsed = stopTime - startTime;
228	<	long rate = elapsed / (nPools * nGen);
208	<	double secs = (double)elapsed / 1000000000.0;
228	>	double secs = (double) elapsed / 1000000000.0;
229		p.printSnapshot(secs);
210	–	System.out.printf("%10d ns per transfer\n", rate);
230		}
231
213	–
232		/**
233	<	* A Population creates the pools, tasks, and threads for a run
233	>	* A Population creates the subpops, subpops, and threads for a run
234		* and has control methods to start, stop, and report progress.
235		*/
236		static final class Population {
237	<	final Task[] tasks;
237	>	final Worker[] threads;
238	>	final Subpop[] subpops;
239		final Exchanger<Strand> exchanger;
221	–	final ThreadPoolExecutor exec;
240		final CountDownLatch done;
241		final int nGen;
242	<	final int poolSize;
242	>	final int subpopSize;
243		final int nThreads;
244
245	<	Population(int nThreads, int nPools, int poolSize, int nGen) {
245	>	Population(int nThreads, int nSubpops, int subpopSize, int nGen) {
246		this.nThreads = nThreads;
247		this.nGen = nGen;
248	<	this.poolSize = poolSize;
248	>	this.subpopSize = subpopSize;
249		this.exchanger = new Exchanger<Strand>();
250	<	this.done = new CountDownLatch(nPools-1);
251	<	this.tasks = new Task[nPools];
252	<	for (int i = 0; i < nPools; i++)
253	<	tasks[i] = new Task(this);
254	<	BlockingQueue<Runnable> tq =
255	<	new LinkedBlockingQueue<Runnable>();
256	<	this.exec = new ThreadPoolExecutor(nThreads, nThreads,
257	<	0L, TimeUnit.MILLISECONDS,
258	<	tq);
259	<	exec.prestartAllCoreThreads();
250	>	this.done = new CountDownLatch(nThreads - 1);
251	>
252	>	this.subpops = new Subpop[nSubpops];
253	>	for (int i = 0; i < nSubpops; i++)
254	>	subpops[i] = new Subpop(this);
255	>
256	>	this.threads = new Worker[nThreads];
257	>	int maxExchanges = nGen * nSubpops / nThreads;
258	>	for (int i = 0; i < nThreads; ++i) {
259	>	threads[i] = new Worker(this, maxExchanges);
260	>	}
261	>
262		}
263
244	–	/** Start the tasks */
264		void start() {
265	<	for (int i = 0; i < tasks.length; i++)
266	<	exec.execute(tasks[i]);
265	>	for (int i = 0; i < nThreads; ++i) {
266	>	threads[i].start();
267	>	}
268		}
269
270		/** Stop the tasks */
271		void shutdown() {
272	<	exec.shutdownNow();
272	>	for (int i = 0; i < threads.length; ++ i)
273	>	threads[i].interrupt();
274		}
275
276	<	/** Called by task upon terminations */
256	<	void taskDone() {
276	>	void threadDone() {
277		done.countDown();
278		}
279
280	<	/** Wait for (all but one) task to complete */
281	<	void awaitTasks() throws InterruptedException {
280	>	/** Wait for tasks to complete */
281	>	void awaitDone() throws InterruptedException {
282		done.await();
283		}
284
285	<	/**
286	<	* Called by a task to resubmit itself after completing
287	<	* fewer than nGen iterations.
288	<	*/
289	<	void resubmit(Task task) {
270	<	exec.execute(task);
285	>	int totalExchanges() {
286	>	int xs = 0;
287	>	for (int i = 0; i < threads.length; ++i)
288	>	xs += threads[i].exchanges;
289	>	return xs;
290		}
291
292	+	/**
293	+	* Prints statistics, including best and worst tour lengths
294	+	* for points scaled in [0,1), scaled by the square root of
295	+	* number of points. This simplifies checking results.  The
296	+	* expected optimal TSP for random points is believed to be
297	+	* around 0.76 * sqrt(N). For papers discussing this, see
298	+	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
299	+	*/
300		void printSnapshot(double secs) {
301	<	int gens = 0;
302	<	double best = Double.MAX_VALUE;
303	<	double worst = 0;
304	<	for (int k = 0; k < tasks.length; ++k) {
305	<	gens += tasks[k].gen;
306	<	Chromosome[] cs = tasks[k].chromosomes;
307	<	float b = cs[0].fitness;
308	<	if (b < best)
309	<	best = b;
310	<	float w = cs[cs.length-1].fitness;
311	<	if (w > worst)
312	<	worst = w;
313	<	}
314	<	int avegen = (done.getCount() == 0)? nGen : gens / tasks.length;
315	<	System.out.printf("Time:%9.3f Best:%9.3f Worst:%9.3f Gen:%6d Threads:%4d\n",
316	<	secs, best, worst, avegen, nThreads);
317	<	}
318	<
319	<	float averageFitness() { // currently unused
320	<	float total = 0;
321	<	int count = 0;
322	<	for (int k = 0; k < tasks.length; ++k) {
323	<	Chromosome[] cs = tasks[k].chromosomes;
324	<	for (int i = 0; i < cs.length; i++)
325	<	total += cs[i].fitness;
326	<	count += cs.length;
301	>	int xs = totalExchanges();
302	>	long rate = (xs == 0) ? 0L : (long) ((secs * 1000000000.0) / xs);
303	>	Chromosome bestc = subpops[0].chromosomes[0];
304	>	Chromosome worstc = bestc;
305	>	for (int k = 0; k < subpops.length; ++k) {
306	>	Chromosome[] cs = subpops[k].chromosomes;
307	>	if (cs[0].fitness < bestc.fitness)
308	>	bestc = cs[0];
309	>	int w = cs[cs.length-1].fitness;
310	>	if (cs[cs.length-1].fitness > worstc.fitness)
311	>	worstc = cs[cs.length-1];
312	>	}
313	>	double sqrtn = Math.sqrt(cities.length);
314	>	double best = bestc.unitTourLength() / sqrtn;
315	>	double worst = worstc.unitTourLength() / sqrtn;
316	>	System.out.printf("N:%4d T:%8.3f B:%6.3f W:%6.3f X:%9d R:%7d\n",
317	>	nThreads, secs, best, worst, xs, rate);
318	>	//            exchanger.printStats();
319	>	//            System.out.print(" s: " + exchanger.aveSpins());
320	>	//            System.out.print(" p: " + exchanger.aveParks());
321	>	}
322	>	}
323	>
324	>	/**
325	>	* Worker threads perform updates on subpops.
326	>	*/
327	>	static final class Worker extends Thread {
328	>	final Population pop;
329	>	final int maxExchanges;
330	>	int exchanges;
331	>	final RNG rng = new RNG();
332	>
333	>	Worker(Population pop, int maxExchanges) {
334	>	this.pop = pop;
335	>	this.maxExchanges = maxExchanges;
336	>	}
337	>
338	>	/**
339	>	* Repeatedly, find a subpop that is not being updated by
340	>	* another thread, and run a random number of updates on it.
341	>	*/
342	>	public void run() {
343	>	try {
344	>	int len = pop.subpops.length;
345	>	int pos = (rng.next() & 0x7FFFFFFF) % len;
346	>	while (exchanges < maxExchanges) {
347	>	Subpop s = pop.subpops[pos];
348	>	AtomicBoolean busy = s.busy;
349	>	if (!busy.get() && busy.compareAndSet(false, true)) {
350	>	exchanges += s.runUpdates();
351	>	busy.set(false);
352	>	pos = (rng.next() & 0x7FFFFFFF) % len;
353	>	}
354	>	else if (++pos >= len)
355	>	pos = 0;
356	>	}
357	>	pop.threadDone();
358	>	} catch (InterruptedException fallthrough) {
359		}
301	–	return total/(float)count;
360		}
361		}
362
363		/**
364	<	* A Task updates its pool of chromosomes..
364	>	* A Subpop maintains a set of chromosomes.
365		*/
366	<	static final class Task implements Runnable {
367	<	/** The pool of chromosomes, kept in sorted order */
366	>	static final class Subpop {
367	>	/** The chromosomes, kept in sorted order */
368		final Chromosome[] chromosomes;
369	+	/** The parent population */
370		final Population pop;
371	<	/** The common exchanger, same for all tasks */
371	>	/** Reservation bit for worker threads */
372	>	final AtomicBoolean busy;
373	>	/** The common exchanger, same for all subpops */
374		final Exchanger<Strand> exchanger;
375		/** The current strand being exchanged */
376		Strand strand;
377		/** Bitset used in cross */
378		final int[] inTour;
379		final RNG rng;
380	<	final int poolSize;
320	<	final int nGen;
321	<	int gen;
380	>	final int subpopSize;
381
382	<	Task(Population pop) {
382	>	Subpop(Population pop) {
383		this.pop = pop;
384	<	this.nGen = pop.nGen;
326	<	this.gen = 0;
327	<	this.poolSize = pop.poolSize;
384	>	this.subpopSize = pop.subpopSize;
385		this.exchanger = pop.exchanger;
386	+	this.busy = new AtomicBoolean(false);
387		this.rng = new RNG();
388		int length = cities.length;
389		this.strand = new Strand(length);
390		this.inTour = new int[(length >>> 5) + 1];
391	<	this.chromosomes = new Chromosome[poolSize];
392	<	for (int j = 0; j < poolSize; ++j)
391	>	this.chromosomes = new Chromosome[subpopSize];
392	>	for (int j = 0; j < subpopSize; ++j)
393		chromosomes[j] = new Chromosome(length, rng);
394		Arrays.sort(chromosomes);
395		}
396
397		/**
398	<	* Run one or more update cycles.
398	>	* Run a random number of updates.  The number of updates is
399	>	* at least 1 and no more than subpopSize.  This
400	>	* controls the granularity of multiplexing subpop updates on
401	>	* to threads. It is small enough to balance out updates
402	>	* across tasks, but large enough to avoid having runs
403	>	* dominated by subpop selection. It is randomized to avoid
404	>	* long runs where pairs of subpops exchange only with each
405	>	* other.  It is hardwired because small variations of it
406	>	* don't matter much.
407	>	*
408	>	* @param g the first generation to run
409		*/
410	<	public void run() {
411	<	try {
412	<	for (;;) {
413	<	update();
414	<	if (++gen >= nGen) {
347	<	pop.taskDone();
348	<	return;
349	<	}
350	<	if ((rng.next() & RESUBMIT_MASK) == 1) {
351	<	pop.resubmit(this);
352	<	return;
353	<	}
354	<	}
355	<	} catch (InterruptedException ie) {
356	<	pop.taskDone();
357	<	}
410	>	int runUpdates() throws InterruptedException {
411	>	int n = 1 + (rng.next() & ((subpopSize << 1) - 1));
412	>	for (int i = 0; i < n; ++i)
413	>	update();
414	>	return n;
415		}
416
417		/**
418	<	* Choose a breeder, exchange strand with another pool, and
419	<	* cross them to create new chromosome to replace a chosen
418	>	* Chooses a breeder, exchanges strand with another subpop, and
419	>	* crosses them to create new chromosome to replace a chosen
420		* dyer.
421		*/
422		void update() throws InterruptedException {
#	Line 374 | Line 431 | public class TSPExchangerTest {
431		}
432
433		/**
434	<	* Choose a breeder, with exponentially decreasing probability
434	>	* Chooses a breeder, with exponentially decreasing probability
435		* starting at best.
436		* @return index of selected breeder
437		*/
438		int chooseBreeder() {
439	<	int mask = (poolSize >>> BREEDER_DECAY) - 1;
439	>	int mask = (subpopSize >>> BREEDER_DECAY) - 1;
440		int b = 0;
441		while ((rng.next() & mask) != mask) {
442	<	if (++b >= poolSize)
442	>	if (++b >= subpopSize)
443		b = 0;
444		}
445		return b;
446		}
447
448		/**
449	<	* Choose a chromosome that will be replaced, with
450	<	* exponentially decreasing probablility starting at
451	<	* worst, ignoring the excluded index
449	>	* Chooses a chromosome that will be replaced, with
450	>	* exponentially decreasing probability starting at
451	>	* worst, ignoring the excluded index.
452		* @param exclude index to ignore; use -1 to not exclude any
453		* @return index of selected dyer
454		*/
455		int chooseDyer(int exclude) {
456	<	int mask = (poolSize >>> DYER_DECAY)  - 1;
457	<	int d = poolSize - 1;
456	>	int mask = (subpopSize >>> DYER_DECAY)  - 1;
457	>	int d = subpopSize - 1;
458		while (d == exclude || (rng.next() & mask) != mask) {
459		if (--d < 0)
460	<	d = poolSize - 1;
460	>	d = subpopSize - 1;
461		}
462		return d;
463		}
464
465	<	/**
465	>	/**
466		* Select a random strand of b's.
467		* @param breeder the breeder
468		*/
#	Line 426 | Line 483 | public class TSPExchangerTest {
483		}
484
485		/**
486	<	* Copy current strand to start of c's, and then append all
486	>	* Copies current strand to start of c's, and then appends all
487		* remaining b's that aren't in the strand.
488		* @param breeder the breeder
489		* @param child the child
#	Line 450 | Line 507 | public class TSPExchangerTest {
507		int first = cs[0];
508		int j = 0;
509		int[] bs = breeder.alleles;
510	<	while (bs[j] != first)
510	>	while (bs[j] != first)
511		++j;
512
513		// Append remaining b's that aren't already in tour
#	Line 459 | Line 516 | public class TSPExchangerTest {
516		int x = bs[j];
517		if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
518		cs[i++] = x;
519	<	}
519	>	}
520
521		}
522
523		/**
524	<	* Fix the sort order of a changed Chromosome c at position k
524	>	* Fixes the sort order of a changed Chromosome c at position k.
525		* @param c the chromosome
526	<	* @param k the index
526	>	* @param k the index
527		*/
528		void fixOrder(Chromosome c, int k) {
529		Chromosome[] cs = chromosomes;
530	<	float oldFitness = c.fitness;
530	>	int oldFitness = c.fitness;
531		c.recalcFitness();
532	<	float newFitness = c.fitness;
532	>	int newFitness = c.fitness;
533		if (newFitness < oldFitness) {
534		int j = k;
535		int p = j - 1;
#	Line 500 | Line 557 | public class TSPExchangerTest {
557		/** Index of cities in tour order */
558		final int[] alleles;
559		/** Total tour length */
560	<	float fitness;
560	>	int fitness;
561
562	<	/**
563	<	* Initialize to random tour
562	>	/**
563	>	* Initializes to random tour.
564		*/
565		Chromosome(int length, RNG random) {
566		alleles = new int[length];
#	Line 519 | Line 576 | public class TSPExchangerTest {
576		}
577
578		public int compareTo(Object x) { // to enable sorting
579	<	float xf = ((Chromosome)x).fitness;
580	<	float f = fitness;
581	<	return ((f == xf)? 0 :((f < xf)? -1 : 1));
579	>	int xf = ((Chromosome) x).fitness;
580	>	int f = fitness;
581	>	return ((f == xf) ? 0 :((f < xf) ? -1 : 1));
582		}
583
584		void recalcFitness() {
585		int[] a = alleles;
586		int len = a.length;
587		int p = a[0];
588	<	float f = cities.distanceBetween(a[len-1], p);
588	>	long f = cities.distanceBetween(a[len-1], p);
589		for (int i = 1; i < len; i++) {
590		int n = a[i];
591		f += cities.distanceBetween(p, n);
592		p = n;
593		}
594	<	fitness = f;
594	>	fitness = (int) (f / len);
595	>	}
596	>
597	>	/**
598	>	* Returns tour length for points scaled in [0, 1).
599	>	*/
600	>	double unitTourLength() {
601	>	int[] a = alleles;
602	>	int len = a.length;
603	>	int p = a[0];
604	>	double f = cities.unitDistanceBetween(a[len-1], p);
605	>	for (int i = 1; i < len; i++) {
606	>	int n = a[i];
607	>	f += cities.unitDistanceBetween(p, n);
608	>	p = n;
609	>	}
610	>	return f;
611		}
612
613	<	void validate() { // Ensure that this is a valid tour.
613	>	/**
614	>	* Checks that this tour visits each city.
615	>	*/
616	>	void validate() {
617		int len = alleles.length;
618		boolean[] used = new boolean[len];
619	<	for (int i = 0; i < len; ++i)
619	>	for (int i = 0; i < len; ++i)
620		used[alleles[i]] = true;
621	<	for (int i = 0; i < len; ++i)
621	>	for (int i = 0; i < len; ++i)
622		if (!used[i])
623		throw new Error("Bad tour");
624		}
#	Line 550 | Line 626 | public class TSPExchangerTest {
626		}
627
628		/**
629	<	* A Strand is a random sub-sequence of a Chromosome.  Each task
629	>	* A Strand is a random sub-sequence of a Chromosome.  Each subpop
630		* creates only one strand, and then trades it with others,
631		* refilling it on each iteration.
632		*/
#	Line 561 | Line 637 | public class TSPExchangerTest {
637		}
638
639		/**
640	<	* A collection of (x,y) points that represent cities.  Distances
565	<	* are scaled in [0,1) to simply checking results.  The expected
566	<	* optimal TSP for random points is believed to be around 0.76 *
567	<	* sqrt(N). For papers discussing this, see
568	<	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html for
640	>	* A collection of (x,y) points that represent cities.
641		*/
642		static final class CitySet {
571	–	// Scale ints to doubles in [0,1)
572	–	static final double PSCALE = (double)0x80000000L;
643
644		final int length;
645		final int[] xPts;
646		final int[] yPts;
647	<	final float[][] distances;
647	>	final int[][] distances;
648
649		CitySet(int n) {
650		this.length = n;
651		this.xPts = new int[n];
652		this.yPts = new int[n];
653	<	this.distances = new float[n][n];
653	>	this.distances = new int[n][n];
654
655		RNG random = new RNG();
656		for (int i = 0; i < n; i++) {
#	Line 590 | Line 660 | public class TSPExchangerTest {
660
661		for (int i = 0; i < n; i++) {
662		for (int j = 0; j < n; j++) {
663	<	double dX = (xPts[i] - xPts[j]) / PSCALE;
664	<	double dY = (yPts[i] - yPts[j]) / PSCALE;
665	<	distances[i][j] = (float)Math.hypot(dX, dY);
663	>	double dx = (double) xPts[i] - (double) xPts[j];
664	>	double dy = (double) yPts[i] - (double) yPts[j];
665	>	double dd = Math.hypot(dx, dy) / 2.0;
666	>	long ld = Math.round(dd);
667	>	distances[i][j] = (ld >= Integer.MAX_VALUE) ?
668	>	Integer.MAX_VALUE : (int) ld;
669		}
670		}
671		}
672
673	<	// Retrieve the cached distance between a pair of cities
674	<	float distanceBetween(int i, int j) {
673	>	/**
674	>	* Returns the cached distance between a pair of cities.
675	>	*/
676	>	int distanceBetween(int i, int j) {
677		return distances[i][j];
678		}
679	+
680	+	// Scale ints to doubles in [0,1)
681	+	static final double PSCALE = (double) 0x80000000L;
682	+
683	+	/**
684	+	* Returns distance for points scaled in [0,1). This simplifies
685	+	* checking results.  The expected optimal TSP for random
686	+	* points is believed to be around 0.76 * sqrt(N). For papers
687	+	* discussing this, see
688	+	* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
689	+	*/
690	+	double unitDistanceBetween(int i, int j) {
691	+	double dx = ((double) xPts[i] - (double) xPts[j]) / PSCALE;
692	+	double dy = ((double) yPts[i] - (double) yPts[j]) / PSCALE;
693	+	return Math.hypot(dx, dy);
694	+	}
695	+
696		}
697
698		/**
#	Line 612 | Line 704 | public class TSPExchangerTest {
704
705		int seed;
706		RNG(int seed) { this.seed = seed; }
707	<	RNG()         { this.seed = seedGenerator.nextInt(); }
707	>	RNG()         { this.seed = seedGenerator.nextInt() | 1; }
708
709		int next() {
710		int x = seed;

Diff Legend

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