Clover coverage report - JGAP 3.1
Coverage timestamp: Mo Dez 11 2006 21:16:18 CET
file stats: LOC: 314   Methods: 10
NCLOC: 173   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
GreedyCrossover.java 93,8% 96,6% 90% 95,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;
 11   
 12    import java.util.*;
 13    import org.jgap.*;
 14   
 15    /**
 16    *
 17    * The Greedy Crossover is a specific type of crossover. It can only be is
 18    * applied if
 19    * <ul>
 20    * <li>
 21    * 1. All genes in the chromosome are different and
 22    * </li>
 23    * <li>
 24    * 2. The set of genes for both chromosomes is identical and only they order
 25    * in the chromosome can vary.
 26    * </li>
 27    * </ul>
 28    *
 29    * After the GreedyCrossover, these two conditions always remain true, so
 30    * it can be applied again and again.
 31    *
 32    * The algorithm throws an assertion error if the two initial chromosomes
 33    * does not satisfy these conditions.
 34    *
 35    *
 36    * Greedy crossover can be best explained in the terms of the
 37    * Traveling Salesman Problem:
 38    *
 39    * The algorithm selects the first city of one parent, compares the cities
 40    * leaving that city in both parents, and chooses the closer one to extend
 41    * the tour. If one city has already appeared in the tour, we choose the
 42    * other city. If both cities have already appeared, we randomly select a
 43    * non-selected city.
 44    *
 45    * See J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht.
 46    * <i>Genetic algorithms for the traveling salesman problem</i>.
 47    * In Proceedings of the Second International Conference on Genetic Algorithms.
 48    * Lawrence Eribaum Associates, Mahwah, NJ, 1985.
 49    * and also <a href="http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html">
 50    * Sushil J. Louis & Gong Li</a>}
 51    *
 52    * @author Audrius Meskauskas
 53    * @author <font size=-1>Neil Rotstan, Klaus Meffert (reused code
 54    * from {@link org.jgap.impl.CrossoverOperator CrossoverOperator})</font>
 55    * @since 2.0
 56    */
 57    public class GreedyCrossover
 58    extends BaseGeneticOperator {
 59    /** String containing the CVS revision. Read out via reflection!*/
 60    private static final String CVS_REVISION = "$Revision: 1.26 $";
 61   
 62    /** Switches assertions on/off. Must be true during tests and debugging. */
 63    boolean ASSERTIONS = true;
 64   
 65    private int m_startOffset = 1;
 66   
 67    /**
 68    * Default constructor for dynamic instantiation.<p>
 69    * Attention: The configuration used is the one set with the static method
 70    * Genotype.setConfiguration.
 71    * @throws InvalidConfigurationException
 72    *
 73    * @author Klaus Meffert
 74    * @since 2.6
 75    * @since 3.0 (since 2.0 without a_configuration)
 76    */
 77  0 public GreedyCrossover()
 78    throws InvalidConfigurationException {
 79  0 super(Genotype.getStaticConfiguration());
 80    }
 81   
 82    /**
 83    * Using the given configuration.
 84    * @param a_configuration the configuration to use
 85    * @throws InvalidConfigurationException
 86    *
 87    * @author Klaus Meffert
 88    * @since 3.0 (since 2.6 without a_configuration)
 89    */
 90  20 public GreedyCrossover(Configuration a_configuration)
 91    throws InvalidConfigurationException {
 92  20 super(a_configuration);
 93    }
 94   
 95    /**
 96    * Compute the distance between "cities", indicated by these two
 97    * given genes. The default method expects the genes to be a
 98    * IntegerGenes's and returns they absolute difference, that
 99    * makes sense only for tests.
 100    *
 101    * @param a_from Object
 102    * @param a_to Object
 103    * @return distance between the two given cities
 104    */
 105  15530 public double distance(final Object a_from, final Object a_to) {
 106  15530 IntegerGene from = (IntegerGene) a_from;
 107  15530 IntegerGene to = (IntegerGene) a_to;
 108  15530 return Math.abs(to.intValue() - from.intValue());
 109    }
 110   
 111  14 public void operate(final Population a_population,
 112    final List a_candidateChromosomes) {
 113  14 int size = Math.min(getConfiguration().getPopulationSize(),
 114    a_population.size());
 115  14 int numCrossovers = size / 2;
 116  14 RandomGenerator generator = getConfiguration().getRandomGenerator();
 117    // For each crossover, grab two random chromosomes and do what
 118    // Grefenstette et al say.
 119    // --------------------------------------------------------------
 120  14 for (int i = 0; i < numCrossovers; i++) {
 121  1308 IChromosome firstMate = (IChromosome)
 122    a_population.getChromosome(generator.
 123    nextInt(size)).clone();
 124  1308 IChromosome secondMate = (IChromosome)
 125    a_population.getChromosome(generator.
 126    nextInt(size)).clone();
 127  1308 operate(firstMate, secondMate);
 128    // Add the modified chromosomes to the candidate pool so that
 129    // they'll be considered for natural selection during the next
 130    // phase of evolution.
 131    // -----------------------------------------------------------
 132  1304 a_candidateChromosomes.add(firstMate);
 133  1304 a_candidateChromosomes.add(secondMate);
 134    }
 135    }
 136   
 137    /**
 138    * Performs a greedy crossover for the two given chromosoms.
 139    *
 140    * @param a_firstMate the first chromosome to crossover on
 141    * @param a_secondMate the second chromosome to crossover on
 142    * @throws Error if the gene set in the chromosomes is not identical
 143    *
 144    * @author Audrius Meskauskas
 145    * @since 2.1
 146    */
 147  1309 public void operate(final IChromosome a_firstMate,
 148    final IChromosome a_secondMate) {
 149  1309 Gene[] g1 = a_firstMate.getGenes();
 150  1309 Gene[] g2 = a_secondMate.getGenes();
 151  1309 Gene[] c1, c2;
 152  1309 try {
 153  1309 c1 = operate(g1, g2);
 154  1305 c2 = operate(g2, g1);
 155  1305 a_firstMate.setGenes(c1);
 156  1305 a_secondMate.setGenes(c2);
 157    }
 158    catch (InvalidConfigurationException cex) {
 159  0 throw new Error("Error occured while operating on:"
 160    + a_firstMate + " and "
 161    + a_secondMate
 162    + ". First " + m_startOffset + " genes were excluded "
 163    + "from crossover. Error message: "
 164    + cex.getMessage());
 165    }
 166    }
 167   
 168  2614 protected Gene[] operate(final Gene[] a_g1, final Gene[] a_g2) {
 169  2614 int n = a_g1.length;
 170  2614 LinkedList out = new LinkedList();
 171  2614 TreeSet not_picked = new TreeSet();
 172  2614 out.add(a_g1[m_startOffset]);
 173  2614 for (int j = m_startOffset + 1; j < n; j++) { // g[m_startOffset] picked
 174  13028 if (ASSERTIONS && not_picked.contains(a_g1[j])) {
 175  1 throw new Error("All genes must be different for "
 176    + getClass().getName()
 177    + ". The gene " + a_g1[j] + "[" + j
 178    + "] occurs more "
 179    + "than once in one of the chromosomes. ");
 180    }
 181  13027 not_picked.add(a_g1[j]);
 182    }
 183  2613 if (ASSERTIONS) {
 184  2613 if (a_g1.length != a_g2.length) {
 185  1 throw new Error("Chromosome sizes must be equal");
 186    }
 187  2612 for (int j = m_startOffset; j < n; j++) {
 188  15638 if (!not_picked.contains(a_g2[j])) {
 189  2612 if (!a_g1[m_startOffset].equals(a_g2[j])) {
 190  1 throw new Error("Chromosome gene sets must be identical."
 191    + " First gene set: " + a_g1
 192    + ", second gene set: " + a_g2);
 193    }
 194    }
 195    }
 196    }
 197  2611 while (not_picked.size() > 1) {
 198  10416 Gene last = (Gene) out.getLast();
 199  10416 Gene n1 = findNext(a_g1, last);
 200  10416 Gene n2 = findNext(a_g2, last);
 201  10416 Gene picked, other;
 202  10416 boolean pick1;
 203  10416 if (n1 == null) {
 204  1060 pick1 = false;
 205    }
 206  9356 else if (n2 == null) {
 207  1586 pick1 = true;
 208    }
 209    else {
 210  7770 pick1 = distance(last, n1) < distance(last, n2);
 211    }
 212  10416 if (pick1) {
 213  4320 picked = n1;
 214  4320 other = n2;
 215    }
 216    else {
 217  6096 picked = n2;
 218  6096 other = n1;
 219    }
 220  10416 if (out.contains(picked)) {
 221  1402 picked = other;
 222    }
 223  10416 if (picked == null || out /* still */.contains(picked)) {
 224    // select a non-selected // it is not random
 225  590 picked = (Gene) not_picked.first();
 226    }
 227  10416 out.add(picked);
 228  10416 not_picked.remove(picked);
 229    }
 230  2611 if (ASSERTIONS && not_picked.size() != 1) {
 231  1 throw new Error("Given Gene not correctly created (must have length > 1"
 232    + ")");
 233    }
 234  2610 out.add(not_picked.last());
 235  2610 Gene[] g = new Gene[n];
 236  2610 Iterator gi = out.iterator();
 237  2610 for (int i = 0; i < m_startOffset; i++) {
 238  2602 g[i] = a_g1[i];
 239    }
 240  2610 if (ASSERTIONS) {
 241  2610 if (out.size() != g.length - m_startOffset) {
 242  0 throw new Error("Unexpected internal error. "
 243    + "These two must be equal: " + out.size()
 244    + " and " + (g.length - m_startOffset) + ", g.length "
 245    + g.length + ", start offset " + m_startOffset);
 246    }
 247    }
 248  2610 for (int i = m_startOffset; i < g.length; i++) {
 249  15636 g[i] = (Gene) gi.next();
 250    }
 251  2610 return g;
 252    }
 253   
 254  20832 protected Gene findNext(final Gene[] a_g, final Gene a_x) {
 255  20832 for (int i = m_startOffset; i < a_g.length - 1; i++) {
 256  66577 if (a_g[i].equals(a_x)) {
 257  18004 return a_g[i + 1];
 258    }
 259    }
 260  2828 return null;
 261    }
 262   
 263    /**
 264    * Sets a number of genes at the start of chromosome, that are
 265    * excluded from the swapping. In the Salesman task, the first city
 266    * in the list should (where the salesman leaves from) probably should
 267    * not change as it is part of the list. The default value is 1.
 268    * @param a_offset the start offset to use
 269    */
 270  10 public void setStartOffset(int a_offset) {
 271  10 m_startOffset = a_offset;
 272    }
 273   
 274    /**
 275    * Gets a number of genes at the start of chromosome, that are
 276    * excluded from the swapping. In the Salesman task, the first city
 277    * in the list should (where the salesman leaves from) probably should
 278    * not change as it is part of the list. The default value is 1.
 279    * @return the start offset used
 280    */
 281  18 public int getStartOffset() {
 282  18 return m_startOffset;
 283    }
 284   
 285    /**
 286    * Compares the given GeneticOperator to this GeneticOperator.
 287    *
 288    * @param a_other the instance against which to compare this instance
 289    * @return a negative number if this instance is "less than" the given
 290    * instance, zero if they are equal to each other, and a positive number if
 291    * this is "greater than" the given instance
 292    *
 293    * @author Klaus Meffert
 294    * @since 2.6
 295    */
 296  6 public int compareTo(final Object a_other) {
 297  6 if (a_other == null) {
 298  1 return 1;
 299    }
 300  5 GreedyCrossover op = (GreedyCrossover) a_other;
 301  4 if (getStartOffset() < op.getStartOffset()) {
 302    // start offset less, meaning more to do --> return 1 for "is greater than"
 303  1 return 1;
 304    }
 305  3 else if (getStartOffset() > op.getStartOffset()) {
 306  1 return -1;
 307    }
 308    else {
 309    // Everything is equal. Return zero.
 310    // ---------------------------------
 311  2 return 0;
 312    }
 313    }
 314    }