KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > salesman > TravellingSalesman


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 examples.salesman;
11
12 import org.jgap.*;
13 import org.jgap.impl.*;
14 import org.jgap.impl.salesman.*;
15
16 /**
17  * Explains how to use JGAP extensions, needed to solve the task group,
18  * known as the <i>Problem of the travelling salesman</i>. The extensions are
19  * defined in {@link org.jgap.impl.salesman org.jgap.impl.salesman}
20  *
21  * <font size=-1><p>
22  * The traveling salesman problem is the following: given a finite number of
23  * 'cities' along with the cost of travel between each pair of them, find the
24  * cheapest way of visiting all the cities and returning to your starting point.
25  * </p></font>
26  *
27  * Also see
28  * <ul>
29  * <li>J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
30  * <i>Genetic algorithms for the traveling salesman problem</i>.
31  * In Proceedings of the Second International Conference on Genetice
32  * Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985.
33  * </li>
34  * <li>
35  * <a HREF="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
36  * Sushil J. Louis & Gong Li</a> (very clear explanatory material)
37  * </li>
38  * <li>
39  * <a HREF="http://www.tsp.gatech.edu www.tsp.gatech.edu">
40  * <i>Travelling salesman</i> web site</a>
41  * </li>
42  * </ul>
43  *
44  * This simple test and example shows how to use the Salesman class.
45  * The distance between the cities is assumed to be equal
46  * to the difference of the assigned numbers. So, the
47  * optimal solution is obviously 1 2 3 4 ... n or reverse,
48  * but the system does not know this. To get the useful application, you
49  * need to override at least the distance function. Also, it is recommended
50  * to define a new type of gene, corresponding the data about your "city".
51  * For example, it can contain the city X and Y co-ordinates, used by
52  * the distance function.
53  *
54  * @author Audrius Meskauskas
55  * @since 2.0
56  */
57 public class TravellingSalesman
58     extends Salesman {
59   /** String containing the CVS revision. Read out via reflection!*/
60   private static final String JavaDoc CVS_REVISION = "$Revision: 1.12 $";
61
62   /** The number of cities to visit*/
63   public static final int CITIES = 7;
64
65   /**
66    * Create an array of the given number of integer genes. The first gene is
67    * always 0, this is the city where the salesman starts the journey.
68    *
69    * @param a_initial_data ignored
70    * @return Chromosome
71    *
72    * @author Audrius Meskauskas
73    * @since 2.0
74    */
75   public IChromosome createSampleChromosome(Object JavaDoc a_initial_data) {
76     try {
77       Gene[] genes = new Gene[CITIES];
78       for (int i = 0; i < genes.length; i++) {
79         genes[i] = new IntegerGene(getConfiguration(), 0, CITIES - 1);
80         genes[i].setAllele(new Integer JavaDoc(i));
81       }
82       IChromosome sample = new Chromosome(getConfiguration(), genes);
83       System.out.println("Optimal way " + sample);
84       System.out.println("Score " +
85                          (Integer.MAX_VALUE / 2 -
86                           getConfiguration().getFitnessFunction()
87                           .getFitnessValue(sample)));
88       shuffle(genes);
89       System.out.println("Sample chromosome " + sample);
90       System.out.println("Score " +
91                          (Integer.MAX_VALUE / 2 -
92                           getConfiguration().getFitnessFunction()
93                           .getFitnessValue(sample)));
94       return sample;
95     }
96     catch (InvalidConfigurationException iex) {
97       throw new IllegalStateException JavaDoc(iex.getMessage());
98     }
99   }
100
101   /**
102    * Distance is equal to the difference between city numbers, except the
103    * distance between the last and first cities that is equal to 1. In this
104    * way, we ensure that the optimal solution is 0 1 2 3 .. n - easy to check.
105    *
106    * @param a_from first gene, representing a city
107    * @param a_to second gene, representing a city
108    * @return the distance between two cities represented as genes
109
110    * @author Audrius Meskauskas
111    * @since 2.0
112    */
113   public double distance(Gene a_from, Gene a_to) {
114     IntegerGene a = (IntegerGene) a_from;
115     IntegerGene b = (IntegerGene) a_to;
116     int A = a.intValue();
117     int B = b.intValue();
118     if (A == 0 && B == CITIES - 1) {
119       return 1;
120     }
121     if (B == 0 && A == CITIES - 1) {
122       return 1;
123     }
124     return Math.abs(A - B);
125   }
126
127   /**
128    * Solve a sample task with the number of cities, defined in a CITIES
129    * constant. Print the known optimal way, sample chromosome and found
130    * solution.
131    *
132    * @param args not relevant here
133    *
134    * @author Audrius Meskauskas
135    * @since 2.0
136    */
137   public static void main(String JavaDoc[] args) {
138     try {
139       TravellingSalesman t = new TravellingSalesman();
140       IChromosome optimal = t.findOptimalPath(null);
141       System.out.println("Solution: ");
142       System.out.println(optimal);
143       System.out.println("Score " +
144                          (Integer.MAX_VALUE / 2 - optimal.getFitnessValue()));
145     }
146     catch (Exception JavaDoc ex) {
147       ex.printStackTrace();
148     }
149   }
150 }
151
Popular Tags