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.5 by jsr166, Mon Jan 5 05:50:48 2009 UTC vs.
Revision 1.6 by jsr166, Thu Oct 29 23:09:08 2009 UTC

# 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
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
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>
# 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 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 206 | Line 206 | public class TSPExchangerTest {
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 264 | Line 264 | public class TSPExchangerTest {
264  
265          void start() {
266              for (int i = 0; i < nThreads; ++i) {
267 <                threads[i].start();                
267 >                threads[i].start();
268              }
269          }
270  
# Line 285 | Line 285 | public class TSPExchangerTest {
285  
286          int totalExchanges() {
287              int xs = 0;
288 <            for (int i = 0; i < threads.length; ++i)
288 >            for (int i = 0; i < threads.length; ++i)
289                  xs += threads[i].exchanges;
290              return xs;
291          }
# Line 362 | Line 362 | public class TSPExchangerTest {
362      }
363  
364      /**
365 <     * A Subpop maintains a set of chromosomes..
365 >     * A Subpop maintains a set of chromosomes..
366       */
367      static final class Subpop {
368          /** The chromosomes, kept in sorted order */
# Line 406 | Line 406 | public class TSPExchangerTest {
406           * other.  It is hardwired because small variations of it
407           * don't matter much.
408           *
409 <         * @param g the first generation to run.
409 >         * @param g the first generation to run.
410           */
411          int runUpdates() throws InterruptedException {
412              int n = 1 + (rng.next() & ((subpopSize << 1) - 1));
# Line 463 | Line 463 | public class TSPExchangerTest {
463              return d;
464          }
465  
466 <        /**
466 >        /**
467           * Select a random strand of b's.
468           * @param breeder the breeder
469           */
# Line 508 | Line 508 | public class TSPExchangerTest {
508              int first = cs[0];
509              int j = 0;
510              int[] bs = breeder.alleles;
511 <            while (bs[j] != first)
511 >            while (bs[j] != first)
512                  ++j;
513  
514              // Append remaining b's that aren't already in tour
# Line 517 | Line 517 | public class TSPExchangerTest {
517                  int x = bs[j];
518                  if ((inTour[x >>> 5] & (1 << (x & 31))) == 0)
519                      cs[i++] = x;
520 <            }
520 >            }
521  
522          }
523  
524          /**
525           * Fix the sort order of a changed Chromosome c at position k
526           * @param c the chromosome
527 <         * @param k the index
527 >         * @param k the index
528           */
529          void fixOrder(Chromosome c, int k) {
530              Chromosome[] cs = chromosomes;
# Line 560 | Line 560 | public class TSPExchangerTest {
560          /** Total tour length */
561          int fitness;
562  
563 <        /**
563 >        /**
564           * Initialize to random tour
565           */
566          Chromosome(int length, RNG random) {
# Line 614 | Line 614 | public class TSPExchangerTest {
614          /**
615           * Check that this tour visits each city
616           */
617 <        void validate() {
617 >        void validate() {
618              int len = alleles.length;
619              boolean[] used = new boolean[len];
620 <            for (int i = 0; i < len; ++i)
620 >            for (int i = 0; i < len; ++i)
621                  used[alleles[i]] = true;
622 <            for (int i = 0; i < len; ++i)
622 >            for (int i = 0; i < len; ++i)
623                  if (!used[i])
624                      throw new Error("Bad tour");
625          }
# Line 638 | Line 638 | public class TSPExchangerTest {
638      }
639  
640      /**
641 <     * A collection of (x,y) points that represent cities.
641 >     * A collection of (x,y) points that represent cities.
642       */
643      static final class CitySet {
644  
# Line 665 | Line 665 | public class TSPExchangerTest {
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)?
668 >                    distances[i][j] = (ld >= Integer.MAX_VALUE)?
669                          Integer.MAX_VALUE : (int)ld;
670                  }
671              }
# Line 693 | Line 693 | public class TSPExchangerTest {
693              double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE;
694              return Math.hypot(dx, dy);
695          }
696 <            
696 >
697      }
698  
699      /**

Diff Legend

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