KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgap > impl > salesman > TravellingSalesmanTest


1 /*
2  * This file is part of JGAP.
3  *
4  * JGAP offers a dual license model containing the LGPL as well as the MPL.
5  *
6  * For licencing information please see the file license.txt included with JGAP
7  * or have a look at the top of class org.jgap.Chromosome which representatively
8  * includes the JGAP license policy applicable for any file delivered with JGAP.
9  */
10 package org.jgap.impl.salesman;
11
12 import org.jgap.*;
13 import org.jgap.impl.*;
14 import junit.framework.*;
15
16 /**
17  * Test JGAP's travelling salesman implementation.
18  *
19  * @author Audrius Meskauskas
20  * @author Klaus Meffert
21  * @since 2.0
22  */
23 public class TravellingSalesmanTest
24     extends JGAPTestCase {
25   /** String containing the CVS revision. Read out via reflection!*/
26   private final static String JavaDoc CVS_REVISION = "$Revision: 1.13 $";
27
28   public static Test suite() {
29     TestSuite suite = new TestSuite(TravellingSalesmanTest.class);
30     return suite;
31   }
32
33   public void setUp() {
34     super.setUp();
35     Configuration.reset();
36   }
37
38   public void tearDown()
39       throws Exception JavaDoc {
40     super.tearDown();
41   }
42
43   /**
44    * @throws Exception
45    *
46    * @author Audrius Meskauskas
47    * @since 2.0
48    */
49   public void testSampleTravellingSalesmanApp()
50       throws Exception JavaDoc {
51     // With 7 cities, should find the best solution with score 7
52 int oks = 0;
53     for (int i = 0; i < 7; i++) {
54       TravellingSalesmanForTest t = new TravellingSalesmanForTest();
55       IChromosome optimal = t.findOptimalPath(null);
56       if (Integer.MAX_VALUE / 2 - optimal.getFitnessValue() <= 7) {
57         oks++;
58       }
59       Configuration.reset();
60     }
61     if (oks < 6) {
62       fail("Less than 6 cities computed correctly!");
63     }
64   }
65
66   /**
67    * @throws Exception
68    *
69    * @author Klaus Meffert
70    * @since 3.0
71    */
72   public void testSetAcceptableCost_0() throws Exception JavaDoc {
73     TravellingSalesmanForTest t = new TravellingSalesmanForTest();
74     assertEquals(-1, t.getAcceptableCost());
75     t.setAcceptableCost(47);
76     assertEquals(47, t.getAcceptableCost());
77   }
78
79   /**
80    * @throws Exception
81    *
82    * @author Klaus Meffert
83    * @since 3.0
84    */
85   public void testSetStartOffset_0() throws Exception JavaDoc {
86     TravellingSalesmanForTest t = new TravellingSalesmanForTest();
87     assertEquals(1, t.getStartOffset());
88     t.setStartOffset(47);
89     assertEquals(47, t.getStartOffset());
90   }
91
92   /**
93    * Explains how to use JGap extensions, needed to solve the task group,
94    * known as the <i>Problem of the travelling salesman</i>. The extensions are
95    * defined in {@link org.jgap.impl.salesman org.jgap.impl.salesman}
96    *
97    * <font size=-1><p>
98    * The traveling salesman problem is the following: given a finite number of
99    * 'cities' along with the
100    * cost of travel between each pair of them, find the cheapest way of visiting
101    * all the cities and returning to your starting point.
102    * </p></font>
103    *
104    * See
105    * <ul>
106    * <li>J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
107    * <i>Genetic algorithms for the traveling salesman problem</i>.
108    * In Proceedings of the Second International Conference on Genetic
109    * Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985.
110    * </li>
111    * <li>
112    * <a HREF="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
113    * Sushil J. Louis & Gong Li</a> (very clear explanatory material)
114    * </li>
115    * <li>
116    * <a HREF="http://www.tsp.gatech.edu www.tsp.gatech.edu">
117    * <i>Travelling salesman</i> web site</a>
118    * </li>
119    * </ul>
120    *
121    * This simple test and example shows how to use the Salesman class.
122    * The distance between the cities is assumed to be equal
123    * to the difference of the assigned numbers. So, the
124    * optimal solution is obviously 1 2 3 4 ... n or reverse,
125    * but the system does not know this. To get the useful application, you
126    * need to override at least the distance function. Also, it is recommended
127    * to define a new type of gene, corresponding the data about your "city".
128    * For example, it can contain the city X and Y co-ordinates, used by
129    * the distance function.
130    *
131    * @author Audrius Meskauskas
132    * @version 1.0
133    */
134   public class TravellingSalesmanForTest
135       extends Salesman {
136     /** The number of cities to visit, 7 by default. */
137     public static final int CITIES = 7;
138
139     /**
140      * Create an array of the given number of integer genes. The first gene is
141      * always 0, this is a city where the salesman starts the journey.
142      *
143      * @param a_initial_data Object
144      * @return Chromosome
145      */
146     public IChromosome createSampleChromosome(Object JavaDoc a_initial_data) {
147       try {
148         Gene[] genes = new Gene[CITIES];
149         for (int i = 0; i < genes.length; i++) {
150           genes[i] = new IntegerGene(getConfiguration(), 0, CITIES - 1);
151           genes[i].setAllele(new Integer JavaDoc(i));
152         }
153         IChromosome sample = new Chromosome(getConfiguration(), genes);
154 // System.out.println("Optimal way "+sample);
155 // System.out.println("Fitness "+
156 // (Integer.MAX_VALUE/2-m_conf.getFitnessFunction()
157 // .getFitnessValue(sample)));
158 shuffle(genes);
159 // System.out.println("Sample chromosome "+sample);
160 // System.out.println("Fitness "+
161 // (Integer.MAX_VALUE/2-m_conf.getFitnessFunction()
162 // .getFitnessValue(sample)));
163 return sample;
164       }
165       catch (InvalidConfigurationException iex) {
166         throw new IllegalStateException JavaDoc(iex.getMessage());
167       }
168     }
169
170     /**
171      * Distance is equal to the difference between city numbers,
172      * except the distance between the last and first cities that
173      * is equal to 1. In this way, we ensure that the optimal
174      * soultion is 0 1 2 3 .. n - easy to check.
175      * @param a_from Gene
176      * @param a_to Gene
177      * @return double
178      */
179     public double distance(Gene a_from, Gene a_to) {
180       IntegerGene a = (IntegerGene) a_from;
181       IntegerGene b = (IntegerGene) a_to;
182       int A = a.intValue();
183       int B = b.intValue();
184       if (A == 0 && B == CITIES - 1) {
185         return 1;
186       }
187       if (B == 0 && A == CITIES - 1) {
188         return 1;
189       }
190       return Math.abs(A - B);
191     }
192
193   }
194 }
195
Popular Tags