GreedyCrossover


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    public GreedyCrossover()
78        throws InvalidConfigurationException {
79      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    public GreedyCrossover(Configuration a_configuration)
91        throws InvalidConfigurationException {
92      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   public double distance(final Object   a_from, final Object   a_to) {
106     IntegerGene from = (IntegerGene) a_from;
107     IntegerGene to = (IntegerGene) a_to;
108     return Math.abs(to.intValue() - from.intValue());
109   }
110 
111   public void operate(final Population a_population,
112                       final List a_candidateChromosomes) {
113     int size = Math.min(getConfiguration().getPopulationSize(),
114                         a_population.size());
115     int numCrossovers = size / 2;
116     RandomGenerator generator = getConfiguration().getRandomGenerator();
117     // For each crossover, grab two random chromosomes and do what
118     // Grefenstette et al say.
119     // --------------------------------------------------------------
120     for (int i = 0; i < numCrossovers; i++) {
121       IChromosome firstMate = (IChromosome)
122           a_population.getChromosome(generator.
123                                      nextInt(size)).clone();
124       IChromosome secondMate = (IChromosome)
125           a_population.getChromosome(generator.
126                                      nextInt(size)).clone();
127       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       a_candidateChromosomes.add(firstMate);
133       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   public void operate(final IChromosome a_firstMate,
148                       final IChromosome a_secondMate) {
149     Gene[] g1 = a_firstMate.getGenes();
150     Gene[] g2 = a_secondMate.getGenes();
151     Gene[] c1, c2;
152     try {
153       c1 = operate(g1, g2);
154       c2 = operate(g2, g1);
155       a_firstMate.setGenes(c1);
156       a_secondMate.setGenes(c2);
157     }
158     catch (InvalidConfigurationException cex) {
159       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   protected Gene[] operate(final Gene[] a_g1, final Gene[] a_g2) {
169     int n = a_g1.length;
170     LinkedList out = new LinkedList();
171     TreeSet not_picked = new TreeSet();
172     out.add(a_g1[m_startOffset]);
173     for (int j = m_startOffset + 1; j < n; j++) { // g[m_startOffset] picked
174       if (ASSERTIONS && not_picked.contains(a_g1[j])) {
175         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       not_picked.add(a_g1[j]);
182     }
183     if (ASSERTIONS) {
184       if (a_g1.length != a_g2.length) {
185         throw new Error  ("Chromosome sizes must be equal");
186       }
187       for (int j = m_startOffset; j < n; j++) {
188         if (!not_picked.contains(a_g2[j])) {
189           if (!a_g1[m_startOffset].equals(a_g2[j])) {
190             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     while (not_picked.size() > 1) {
198       Gene last = (Gene) out.getLast();
199       Gene n1 = findNext(a_g1, last);
200       Gene n2 = findNext(a_g2, last);
201       Gene picked, other;
202       boolean pick1;
203       if (n1 == null) {
204         pick1 = false;
205       }
206       else if (n2 == null) {
207         pick1 = true;
208       }
209       else {
210         pick1 = distance(last, n1) < distance(last, n2);
211       }
212       if (pick1) {
213         picked = n1;
214         other = n2;
215       }
216       else {
217         picked = n2;
218         other = n1;
219       }
220       if (out.contains(picked)) {
221         picked = other;
222       }
223       if (picked == null || out /* still */.contains(picked)) {
224         // select a non-selected // it is not random
225         picked = (Gene) not_picked.first();
226       }
227       out.add(picked);
228       not_picked.remove(picked);
229     }
230     if (ASSERTIONS && not_picked.size() != 1) {
231       throw new Error  ("Given Gene not correctly created (must have length > 1"
232                       + ")");
233     }
234     out.add(not_picked.last());
235     Gene[] g = new Gene[n];
236     Iterator gi = out.iterator();
237     for (int i = 0; i < m_startOffset; i++) {
238       g[i] = a_g1[i];
239     }
240     if (ASSERTIONS) {
241       if (out.size() != g.length - m_startOffset) {
242         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     for (int i = m_startOffset; i < g.length; i++) {
249       g[i] = (Gene) gi.next();
250     }
251     return g;
252   }
253 
254   protected Gene findNext(final Gene[] a_g, final Gene a_x) {
255     for (int i = m_startOffset; i < a_g.length - 1; i++) {
256       if (a_g[i].equals(a_x)) {
257         return a_g[i + 1];
258       }
259     }
260     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   public void setStartOffset(int a_offset) {
271     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   public int getStartOffset() {
282     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   public int compareTo(final Object   a_other) {
297     if (a_other == null) {
298       return 1;
299     }
300     GreedyCrossover op = (GreedyCrossover) a_other;
301     if (getStartOffset() < op.getStartOffset()) {
302       // start offset less, meaning more to do --> return 1 for "is greater than"
303       return 1;
304     }
305     else if (getStartOffset() > op.getStartOffset()) {
306       return -1;
307     }
308     else {
309       // Everything is equal. Return zero.
310       // ---------------------------------
311       return 0;
312     }
313   }
314 }
315
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags