Clover coverage report - JGAP 3.1
Coverage timestamp: Mo Dez 11 2006 21:16:18 CET
file stats: LOC: 321   Methods: 13
NCLOC: 107   Classes: 1
0 - Aktuelle Promotion 728x090
 
 Source file Conditionals Statements Methods TOTAL
Salesman.java 83,3% 96,2% 84,6% 92,2%
coverage coverage
 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  7 public FitnessFunction createFitnessFunction(final Object a_initial_data) {
 103  7 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  7 public Configuration createConfiguration(final Object a_initial_data)
 121    throws InvalidConfigurationException {
 122    // This is copied from DefaultConfiguration.
 123    // -----------------------------------------
 124  7 Configuration config = new Configuration();
 125  7 BestChromosomesSelector bestChromsSelector =
 126    new BestChromosomesSelector(config, 1.0d);
 127  7 bestChromsSelector.setDoubletteChromosomesAllowed(false);
 128  7 config.addNaturalSelector(bestChromsSelector, true);
 129  7 config.setRandomGenerator(new StockRandomGenerator());
 130  7 config.setMinimumPopSizePercent(0);
 131  7 config.setEventManager(new EventManager());
 132  7 config.setFitnessEvaluator(new DefaultFitnessEvaluator());
 133  7 config.setChromosomePool(new ChromosomePool());
 134    // These are different:
 135    // --------------------
 136  7 config.addGeneticOperator(new GreedyCrossover(config));
 137  7 config.addGeneticOperator(new SwappingMutationOperator(config, 20));
 138  7 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  9 public int getAcceptableCost() {
 153  9 return m_acceptableCost;
 154    }
 155   
 156  1 public void setAcceptableCost(final int a_acceptableCost) {
 157  1 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  7 public int getMaxEvolution() {
 167  7 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  0 public void setMaxEvolution(final int a_maxEvolution) {
 178  0 m_maxEvolution = a_maxEvolution;
 179    }
 180   
 181    /**
 182    * @return population size for this solution
 183    *
 184    * @since 2.0
 185    */
 186  7 public int getPopulationSize() {
 187  7 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  0 public void setPopulationSize(final int a_populationSize) {
 198  0 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  7 public IChromosome findOptimalPath(final Object a_initial_data)
 217    throws Exception {
 218  7 m_config = createConfiguration(a_initial_data);
 219  7 FitnessFunction myFunc = createFitnessFunction(a_initial_data);
 220  7 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  7 IChromosome sampleChromosome = createSampleChromosome(a_initial_data);
 227  7 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  7 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  7 IChromosome[] chromosomes =
 243    new IChromosome[m_config.getPopulationSize()];
 244  7 Gene[] samplegenes = sampleChromosome.getGenes();
 245  7 for (int i = 0; i < chromosomes.length; i++) {
 246  3584 Gene[] genes = new Gene[samplegenes.length];
 247  3584 for (int k = 0; k < genes.length; k++) {
 248  25088 genes[k] = samplegenes[k].newGene();
 249  25088 genes[k].setAllele(samplegenes[k].getAllele());
 250    }
 251  3584 shuffle(genes);
 252  3584 chromosomes[i] = new Chromosome(m_config, genes);
 253    }
 254  7 Genotype population = new Genotype(m_config,
 255    new Population(m_config, chromosomes));
 256  7 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  7 Evolution:
 261  7 for (int i = 0; i < getMaxEvolution(); i++) {
 262  7 population.evolve();
 263  7 best = population.getFittestChromosome();
 264  7 if (best.getFitnessValue() >= getAcceptableCost()) {
 265  7 break Evolution;
 266    }
 267    }
 268    // Return the best solution we found.
 269    // ----------------------------------
 270  7 return best;
 271    }
 272   
 273  3591 protected void shuffle(final Gene[] a_genes) {
 274  3591 Gene t;
 275    // shuffle:
 276  3591 for (int r = 0; r < 10 * a_genes.length; r++) {
 277  251370 for (int i = m_startOffset; i < a_genes.length; i++) {
 278  1508220 int p = m_startOffset
 279    + m_config.getRandomGenerator().
 280    nextInt(a_genes.length - m_startOffset);
 281  1508220 t = a_genes[i];
 282  1508220 a_genes[i] = a_genes[p];
 283  1508220 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  1 public void setStartOffset(final int a_offset) {
 301  1 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  2 public int getStartOffset() {
 315  2 return m_startOffset;
 316    }
 317   
 318  56 public Configuration getConfiguration() {
 319  56 return m_config;
 320    }
 321    }