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.5 by jsr166, Mon Jan 5 05:50:48 2009 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 14 | Line 14 | import java.util.concurrent.locks.*;
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	<	*
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.
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.
#	Line 39 | Line 39 | public class TSPExchangerTest {
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);
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;
#	Line 54 | 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 subpop. Must be a power of two.
#	Line 62 | Line 62 | public class TSPExchangerTest {
62		* Smaller values lead to faster iterations but poorer quality
63		* results
64		*/
65	<	static final int DEFAULT_SUBPOP_SIZE = 32;
65	>	static final int DEFAULT_SUBPOP_SIZE = 32;
66
67		/**
68		* The number of iterations per subpop. Convergence appears
#	Line 88 | Line 88 | public class TSPExchangerTest {
88		/**
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;
#	Line 97 | Line 97 | public class TSPExchangerTest {
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).
100	>	* 1 / (subpopSize >>> BREEDER_DECAY).
101		*
102		* Larger values usually cause faster convergence but poorer
103		* quality results
#	Line 119 | Line 119 | public class TSPExchangerTest {
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;
#	Line 201 | Line 201 | public class TSPExchangerTest {
201		}
202
203		/**
204	<	* Perform one run with the given parameters.  Each run complete
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)
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;
#	Line 225 | Line 225 | public class TSPExchangerTest {
225		//        Thread.sleep(100);
226
227		long elapsed = stopTime - startTime;
228	<	double secs = (double)elapsed / 1000000000.0;
228	>	double secs = (double) elapsed / 1000000000.0;
229		p.printSnapshot(secs);
230		}
231
232	–
232		/**
233		* A Population creates the subpops, subpops, and threads for a run
234		* and has control methods to start, stop, and report progress.
#	Line 264 | Line 263 | public class TSPExchangerTest {
263
264		void start() {
265		for (int i = 0; i < nThreads; ++i) {
266	<	threads[i].start();
266	>	threads[i].start();
267		}
268		}
269
#	Line 285 | Line 284 | public class TSPExchangerTest {
284
285		int totalExchanges() {
286		int xs = 0;
287	<	for (int i = 0; i < threads.length; ++i)
287	>	for (int i = 0; i < threads.length; ++i)
288		xs += threads[i].exchanges;
289		return xs;
290		}
#	Line 300 | Line 299 | public class TSPExchangerTest {
299		*/
300		void printSnapshot(double secs) {
301		int xs = totalExchanges();
302	<	long rate = (xs == 0)? 0L : (long)((secs * 1000000000.0) / xs);
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) {
#	Line 362 | Line 361 | public class TSPExchangerTest {
361		}
362
363		/**
364	<	* A Subpop maintains a set of chromosomes..
364	>	* A Subpop maintains a set of chromosomes.
365		*/
366		static final class Subpop {
367		/** The chromosomes, kept in sorted order */
#	Line 406 | Line 405 | public class TSPExchangerTest {
405		* other.  It is hardwired because small variations of it
406		* don't matter much.
407		*
408	<	* @param g the first generation to run.
408	>	* @param g the first generation to run
409		*/
410		int runUpdates() throws InterruptedException {
411		int n = 1 + (rng.next() & ((subpopSize << 1) - 1));
#	Line 416 | Line 415 | public class TSPExchangerTest {
415		}
416
417		/**
418	<	* Choose a breeder, exchange strand with another subpop, 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 432 | 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		*/
#	Line 447 | Line 446 | public class TSPExchangerTest {
446		}
447
448		/**
449	<	* Choose a chromosome that will be replaced, with
449	>	* Chooses a chromosome that will be replaced, with
450		* exponentially decreasing probability starting at
451	<	* worst, ignoring the excluded index
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		*/
#	Line 463 | Line 462 | public class TSPExchangerTest {
462		return d;
463		}
464
465	<	/**
465	>	/**
466		* Select a random strand of b's.
467		* @param breeder the breeder
468		*/
#	Line 484 | 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 508 | 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 517 | 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;
#	Line 560 | Line 559 | public class TSPExchangerTest {
559		/** Total tour length */
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 577 | Line 576 | public class TSPExchangerTest {
576		}
577
578		public int compareTo(Object x) { // to enable sorting
579	<	int xf = ((Chromosome)x).fitness;
579	>	int xf = ((Chromosome) x).fitness;
580		int f = fitness;
581	<	return ((f == xf)? 0 :((f < xf)? -1 : 1));
581	>	return ((f == xf) ? 0 :((f < xf) ? -1 : 1));
582		}
583
584		void recalcFitness() {
#	Line 592 | Line 591 | public class TSPExchangerTest {
591		f += cities.distanceBetween(p, n);
592		p = n;
593		}
594	<	fitness = (int)(f / len);
594	>	fitness = (int) (f / len);
595		}
596
597		/**
598	<	* Return tour length for points scaled in [0, 1).
598	>	* Returns tour length for points scaled in [0, 1).
599		*/
600		double unitTourLength() {
601		int[] a = alleles;
#	Line 612 | Line 611 | public class TSPExchangerTest {
611		}
612
613		/**
614	<	* Check that this tour visits each city
614	>	* Checks that this tour visits each city.
615		*/
616	<	void validate() {
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 638 | Line 637 | public class TSPExchangerTest {
637		}
638
639		/**
640	<	* A collection of (x,y) points that represent cities.
640	>	* A collection of (x,y) points that represent cities.
641		*/
642		static final class CitySet {
643
#	Line 661 | 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 = (double)xPts[i] - (double)xPts[j];
664	<	double dy = (double)yPts[i] - (double)yPts[j];
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;
667	>	distances[i][j] = (ld >= Integer.MAX_VALUE) ?
668	>	Integer.MAX_VALUE : (int) ld;
669		}
670		}
671		}
672
673		/**
674	<	*  Returns the cached distance between a pair of cities
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;
681	>	static final double PSCALE = (double) 0x80000000L;
682
683		/**
684	<	* Return distance for points scaled in [0,1). This simplifies
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;
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	<
695	>
696		}
697
698		/**
#	Line 705 | Line 704 | public class TSPExchangerTest {
704
705		int seed;
706		RNG(int seed) { this.seed = seed; }
707	<	RNG()         { this.seed = seedGenerator.nextInt() | 1;  }
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