ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/loops/TSPExchangerTest.java
(Generate patch)

Comparing jsr166/src/test/loops/TSPExchangerTest.java (file contents):
Revision 1.10 by jsr166, Tue Nov 3 01:04:02 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 18 | Line 18 | import java.util.concurrent.locks.*;
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 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).
# Line 229 | Line 229 | public class TSPExchangerTest {
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 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 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 522 | Line 521 | public class TSPExchangerTest {
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
527           */
# Line 561 | Line 560 | public class TSPExchangerTest {
560          int fitness;
561  
562          /**
563 <         * Initialize to random tour
563 >         * Initializes to random tour.
564           */
565          Chromosome(int length, RNG random) {
566              alleles = new int[length];
# Line 596 | Line 595 | public class TSPExchangerTest {
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() {
617              int len = alleles.length;
# Line 672 | Line 671 | public class TSPExchangerTest {
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];
# Line 682 | Line 681 | public class TSPExchangerTest {
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
# 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