001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licencing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package examples.salesman;
011:
012: import org.jgap.*;
013: import org.jgap.impl.*;
014: import org.jgap.impl.salesman.*;
015:
016: /**
017: * Explains how to use JGAP extensions, needed to solve the task group,
018: * known as the <i>Problem of the travelling salesman</i>. The extensions are
019: * defined in {@link org.jgap.impl.salesman org.jgap.impl.salesman}
020: *
021: * <font size=-1><p>
022: * The traveling salesman problem is the following: given a finite number of
023: * 'cities' along with the cost of travel between each pair of them, find the
024: * cheapest way of visiting all the cities and returning to your starting point.
025: * </p></font>
026: *
027: * Also see
028: * <ul>
029: * <li>J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
030: * <i>Genetic algorithms for the traveling salesman problem</i>.
031: * In Proceedings of the Second International Conference on Genetice
032: * Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985.
033: * </li>
034: * <li>
035: * <a href="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
036: * Sushil J. Louis & Gong Li</a> (very clear explanatory material)
037: * </li>
038: * <li>
039: * <a href="http://www.tsp.gatech.edu www.tsp.gatech.edu">
040: * <i>Travelling salesman</i> web site</a>
041: * </li>
042: * </ul>
043: *
044: * This simple test and example shows how to use the Salesman class.
045: * The distance between the cities is assumed to be equal
046: * to the difference of the assigned numbers. So, the
047: * optimal solution is obviously 1 2 3 4 ... n or reverse,
048: * but the system does not know this. To get the useful application, you
049: * need to override at least the distance function. Also, it is recommended
050: * to define a new type of gene, corresponding the data about your "city".
051: * For example, it can contain the city X and Y co-ordinates, used by
052: * the distance function.
053: *
054: * @author Audrius Meskauskas
055: * @since 2.0
056: */
057: public class TravellingSalesman extends Salesman {
058: /** String containing the CVS revision. Read out via reflection!*/
059: private static final String CVS_REVISION = "$Revision: 1.12 $";
060:
061: /** The number of cities to visit*/
062: public static final int CITIES = 7;
063:
064: /**
065: * Create an array of the given number of integer genes. The first gene is
066: * always 0, this is the city where the salesman starts the journey.
067: *
068: * @param a_initial_data ignored
069: * @return Chromosome
070: *
071: * @author Audrius Meskauskas
072: * @since 2.0
073: */
074: public IChromosome createSampleChromosome(Object a_initial_data) {
075: try {
076: Gene[] genes = new Gene[CITIES];
077: for (int i = 0; i < genes.length; i++) {
078: genes[i] = new IntegerGene(getConfiguration(), 0,
079: CITIES - 1);
080: genes[i].setAllele(new Integer(i));
081: }
082: IChromosome sample = new Chromosome(getConfiguration(),
083: genes);
084: System.out.println("Optimal way " + sample);
085: System.out.println("Score "
086: + (Integer.MAX_VALUE / 2 - getConfiguration()
087: .getFitnessFunction().getFitnessValue(
088: sample)));
089: shuffle(genes);
090: System.out.println("Sample chromosome " + sample);
091: System.out.println("Score "
092: + (Integer.MAX_VALUE / 2 - getConfiguration()
093: .getFitnessFunction().getFitnessValue(
094: sample)));
095: return sample;
096: } catch (InvalidConfigurationException iex) {
097: throw new IllegalStateException(iex.getMessage());
098: }
099: }
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[] 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
145: .getFitnessValue()));
146: } catch (Exception ex) {
147: ex.printStackTrace();
148: }
149: }
150: }
|