Salesman


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 org.jgap.event.*;
15  
16  /**
17   * The class solves the travelling salesman problem.
18   * The traveling salesman problem, or TSP for short, is this: given a finite
19   *  number of 'cities' along with the cost of travel between each pair of
20   * them, find the cheapest way of visiting all the cities and returning to
21   * your starting point.)
22   *
23   * @author Audrius Meskauskas
24   * @author <font size="-1">Neil Rotstan, Klaus Meffert (reused code fragments)
25   * </font>
26   * @since 2.0
27   *
28   *
29   * @see
30   *  <ul>
31   *   <li>J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
32   *     <i>Genetic algorithms for the traveling salesman problem</i>.
33   *     In Proceedings of the Second International Conference on Genetic
34   *     Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985.
35   *   </li>
36   *   <li>
37   *    <a HREF="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
38   *      Sushil J. Louis & Gong Li</a> (explanatory material)
39   *   </li>
40   *   <li>
41   *     <a HREF="http://www.tsp.gatech.edu www.tsp.gatech.edu">TPS web site</a>
42   *  </li>
43   * </ul>
44   */
45  public abstract class Salesman
46      implements java.io.Serializable   {
47    /** String containing the CVS revision. Read out via reflection!*/
48    private final static String   CVS_REVISION = "$Revision: 1.19 $";
49  
50    private Configuration m_config;
51  
52    private int m_maxEvolution = 128;
53  
54    private int m_populationSize = 512;
55  
56    private int m_acceptableCost = -1;
57  
58    /**
59     * Override this method to compute the distance between "cities",
60     * indicated by these two given genes. The algorithm is not dependent
61     * on the used type of genes.
62     *
63     * @param a_from first gene, representing a city
64     * @param a_to second gene, representing a city
65     * @return the distance between two cities represented as genes
66     *
67     * @author Audrius Meskauskas
68     * @since 2.0
69     */
70    public abstract double distance(Gene a_from, Gene a_to);
71  
72    /**
73     * Override this method to create a single sample chromosome, representing
74     * al list of "cities". Each gene corresponds a single "city" and
75     * can appear only once. By default, the first gene corresponds
76     * a "city" where the salesman starts the journey.
77     * It never changes its position. This can be changed by setting other
78     * start offset with setStartOffset( ).  Other genes will be shuffled to
79     * create the initial random population.
80     *
81     * @param a_initial_data the same object as was passed to findOptimalPath.
82     * It can be used to specify the task more precisely if the class is
83     * used for solving multiple tasks
84     * @return a sample chromosome
85     *
86     * @author Audrius Meskauskas
87     * @since 2.0
88     */
89    public abstract IChromosome createSampleChromosome(Object   a_initial_data);
90  
91    /**
92     * Return the fitness function to use.
93     *
94     * @param a_initial_data the same object as was passed to findOptimalPath.
95     * It can be used to specify the task more precisely if the class is
96     * used for solving multiple tasks
97     * @return an applicable fitness function
98     *
99     * @author Audrius Meskauskas
100    * @since 2.0
101    */
102   public FitnessFunction createFitnessFunction(final Object   a_initial_data) {
103     return new SalesmanFitnessFunction(this);
104   }
105 
106   /**
107    * Create a configuration. The configuration should not contain
108    * operators for odrinary crossover and mutations, as they make
109    * chromosoms invalid in this task. The special operators
110    * SwappingMutationOperator and GreedyCrossober should be used instead.
111    *
112    * @param a_initial_data the same object as was passed to findOptimalPath.
113    * It can be used to specify the task more precisely if the class is
114    * used for solving multiple tasks
115    * @return created configuration
116    *
117    * @author Audrius Meskauskas
118    * @since 2.0
119    */
120   public Configuration createConfiguration(final Object   a_initial_data)
121       throws InvalidConfigurationException {
122     // This is copied from DefaultConfiguration.
123       // -----------------------------------------
124       Configuration config = new Configuration();
125       BestChromosomesSelector bestChromsSelector =
126           new BestChromosomesSelector(config, 1.0d);
127       bestChromsSelector.setDoubletteChromosomesAllowed(false);
128       config.addNaturalSelector(bestChromsSelector, true);
129       config.setRandomGenerator(new StockRandomGenerator());
130       config.setMinimumPopSizePercent(0);
131       config.setEventManager(new EventManager());
132       config.setFitnessEvaluator(new DefaultFitnessEvaluator());
133       config.setChromosomePool(new ChromosomePool());
134       // These are different:
135       // --------------------
136       config.addGeneticOperator(new GreedyCrossover(config));
137       config.addGeneticOperator(new SwappingMutationOperator(config, 20));
138       return config;
139   }
140 
141   /**
142    * The solution process breaks after the total path length drops below this
143    * limit. The default value (-1) will never be achieved, and evolution stops
144    * after getMaxEvolution() iterations.
145    *
146    * @return satisfying cost allowed to conditionally stop before an optimal
147    * solution has been found
148    *
149    * @author Audrius Meskauskas
150    * @since 2.0
151    */
152   public int getAcceptableCost() {
153     return m_acceptableCost;
154   }
155 
156   public void setAcceptableCost(final int a_acceptableCost) {
157     m_acceptableCost = a_acceptableCost;
158   }
159 
160   /**
161    * @return maximal number of iterations for population to evolve
162    *
163    * @author Audrius Meskauskas
164    * @since 2.0
165    */
166   public int getMaxEvolution() {
167     return m_maxEvolution;
168   }
169 
170   /** Set the maximal number of iterations for population to evolve
171    * (default 512).
172    * @param a_maxEvolution sic
173    *
174    * @author Audrius Meskauskas
175    * @since 2.0
176    */
177   public void setMaxEvolution(final int a_maxEvolution) {
178     m_maxEvolution = a_maxEvolution;
179   }
180 
181   /**
182    * @return population size for this solution
183    *
184    * @since 2.0
185    */
186   public int getPopulationSize() {
187     return m_populationSize;
188   }
189 
190   /**
191    * Set an population size for this solution (default 512)
192    *
193    * @param a_populationSize sic
194    *
195    * @since 2.0
196    */
197   public void setPopulationSize(final int a_populationSize) {
198     m_populationSize = a_populationSize;
199   }
200 
201   /**
202    * Executes the genetic algorithm to determine the
203    * optimal path between the cities.
204    *
205    * @param a_initial_data can be a record with fields, specifying the
206    * task more precisely if the class is used to solve multiple tasks.
207    * It is passed to createFitnessFunction, createSampleChromosome and
208    * createConfiguration
209    *
210    * @throws Exception
211    * @return chromosome representing the optimal path between cities
212    *
213    * @author Audrius Meskauskas
214    * @since 2.0
215    */
216   public IChromosome findOptimalPath(final Object   a_initial_data)
217       throws Exception   {
218     m_config = createConfiguration(a_initial_data);
219     FitnessFunction myFunc = createFitnessFunction(a_initial_data);
220     m_config.setFitnessFunction(myFunc);
221     // Now we need to tell the Configuration object how we want our
222     // Chromosomes to be setup. We do that by actually creating a
223     // sample Chromosome and then setting it on the Configuration
224     // object.
225     // --------------------------------------------------------------
226     IChromosome sampleChromosome = createSampleChromosome(a_initial_data);
227     m_config.setSampleChromosome(sampleChromosome);
228     // Finally, we need to tell the Configuration object how many
229     // Chromosomes we want in our population. The more Chromosomes,
230     // the larger number of potential solutions (which is good for
231     // finding the answer), but the longer it will take to evolve
232     // the population (which could be seen as bad). We'll just set
233     // the population size to 500 here.
234     // ------------------------------------------------------------
235     m_config.setPopulationSize(getPopulationSize());
236     // Create random initial population of Chromosomes.
237     // ------------------------------------------------
238 
239     // As we cannot allow the normal mutations if this task,
240     // we need multiple calls to createSampleChromosome.
241     // -----------------------------------------------------
242     IChromosome[] chromosomes =
243         new IChromosome[m_config.getPopulationSize()];
244     Gene[] samplegenes = sampleChromosome.getGenes();
245     for (int i = 0; i < chromosomes.length; i++) {
246       Gene[] genes = new Gene[samplegenes.length];
247       for (int k = 0; k < genes.length; k++) {
248         genes[k] = samplegenes[k].newGene();
249         genes[k].setAllele(samplegenes[k].getAllele());
250       }
251       shuffle(genes);
252       chromosomes[i] = new Chromosome(m_config, genes);
253     }
254     Genotype population = new Genotype(m_config,
255                                        new Population(m_config, chromosomes));
256     IChromosome best = null;
257     // Evolve the population. Since we don't know what the best answer
258     // is going to be, we just evolve the max number of times.
259     // ---------------------------------------------------------------
260     Evolution:
261         for (int i = 0; i < getMaxEvolution(); i++) {
262       population.evolve();
263       best = population.getFittestChromosome();
264       if (best.getFitnessValue() >= getAcceptableCost()) {
265         break Evolution;
266       }
267     }
268     // Return the best solution we found.
269     // ----------------------------------
270     return best;
271   }
272 
273   protected void shuffle(final Gene[] a_genes) {
274     Gene t;
275     // shuffle:
276     for (int r = 0; r < 10 * a_genes.length; r++) {
277       for (int i = m_startOffset; i < a_genes.length; i++) {
278         int p = m_startOffset
279             + m_config.getRandomGenerator().
280             nextInt(a_genes.length - m_startOffset);
281         t = a_genes[i];
282         a_genes[i] = a_genes[p];
283         a_genes[p] = t;
284       }
285     }
286   }
287 
288   private int m_startOffset = 1;
289 
290   /**
291    * Sets a number of genes at the start of chromosome, that are
292    * excluded from the swapping. In the Salesman task, the first city
293    * in the list should (where the salesman leaves from) probably should
294    * not change as it is part of the list. The default value is 1.
295    *
296    * @param a_offset start offset for chromosome
297    *
298    * @since 2.0
299    */
300   public void setStartOffset(final int a_offset) {
301     m_startOffset = a_offset;
302   }
303 
304   /**
305    * Gets a number of genes at the start of chromosome, that are
306    * excluded from the swapping. In the Salesman task, the first city
307    * in the list should (where the salesman leaves from) probably should
308    * not change as it is part of the list. The default value is 1.
309    *
310    * @return start offset for chromosome
311    *
312    * @since 2.0
313    */
314   public int getStartOffset() {
315     return m_startOffset;
316   }
317 
318   public Configuration getConfiguration() {
319     return m_config;
320   }
321 }
322
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags