View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.genetics;
18  
19  import java.util.ArrayList;
20  import java.util.List;
21  
22  
23  /**
24   * One point crossover policy. A random crossover point is selected and the
25   * first part from each parent is copied to the corresponding child, and the
26   * second parts are copied crosswise.
27   * 
28   * Example:
29   * <pre>
30   * -C- denotes a crossover point
31   *                   -C-                                -C-
32   * p1 = (1 0 1 0 0 1  | 0 1 1)    X    p2 = (0 1 1 0 1 0  | 1 1 1)
33   *         \------------/ \-----/              \------------/ \-----/
34   *            ||         (*)                       ||        (**)
35   *            VV         (**)                      VV        (*)
36   *      /------------\ /-----\              /------------\ /-----\
37   * c1 = (1 0 1 0 0 1  | 1 1 1)    X    p2 = (0 1 1 0 1 0  | 0 1 1)
38   * </pre>
39   * 
40   * This policy works only on {@link AbstractListChromosome}, and therefore it 
41   * is parametrized by T. Moreover, the chromosomes must have same lengths.
42   * 
43   * @param <T> generic type of the {@link AbstractListChromosome}s for crossover
44   * @since 2.0
45   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
46   * 
47   */
48  public class OnePointCrossover<T> implements CrossoverPolicy {
49      
50      /**
51       * Performs one point crossover. A random crossover point is selected and the
52       * first part from each parent is copied to the corresponding child, and the
53       * second parts are copied crosswise.
54       * 
55       * Example:
56       * -C- denotes a crossover point
57       *                   -C-                                -C-
58       * p1 = (1 0 1 0 0 1  | 0 1 1)    X    p2 = (0 1 1 0 1 0  | 1 1 1)
59       *         \------------/ \-----/              \------------/ \-----/
60       *            ||         (*)                       ||        (**)
61       *            VV         (**)                      VV        (*)
62       *      /------------\ /-----\              /------------\ /-----\
63       * c1 = (1 0 1 0 0 1  | 1 1 1)    X    p2 = (0 1 1 0 1 0  | 0 1 1)
64       * 
65       * @param first first parent (p1)
66       * @param second second parent (p2)
67       * @return pair of two children (c1,c2)
68       */
69      @SuppressWarnings("unchecked")
70      public ChromosomePair crossover(Chromosome first, Chromosome second) {
71          if (! (first instanceof AbstractListChromosome && second instanceof AbstractListChromosome)) {
72              throw new IllegalArgumentException("One point crossover works on FixedLengthChromosomes only.");
73          }
74          return crossover((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second);
75      }
76  
77  
78      /**
79       * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover.
80       * 
81       * @param first the first chromosome.
82       * @param second the second chromosome.
83       * @return the pair of new chromosomes that resulted from the crossover.
84       */
85      private ChromosomePair crossover(AbstractListChromosome<T> first, AbstractListChromosome<T> second) {
86          int length = first.getLength();
87          if (length != second.getLength()) 
88              throw new IllegalArgumentException("Both chromosomes must have same lengths.");
89          
90          // array representations of the parents
91          List<T> parent1Rep = first.getRepresentation();
92          List<T> parent2Rep = second.getRepresentation();
93          // and of the children
94          ArrayList<T> child1Rep = new ArrayList<T> (first.getLength());
95          ArrayList<T> child2Rep = new ArrayList<T> (second.getLength());
96          
97          // select a crossover point at random (0 and length makes no sense)
98          int crossoverIndex = 1 + (GeneticAlgorithm.getRandomGenerator().nextInt(length-2));
99  
100         // copy the first part
101         for (int i = 0; i < crossoverIndex; i++) {
102             child1Rep.add(parent1Rep.get(i));
103             child2Rep.add(parent2Rep.get(i));
104         }
105         // and switch the second part
106         for (int i = crossoverIndex; i < length; i++) {
107             child1Rep.add(parent2Rep.get(i));
108             child2Rep.add(parent1Rep.get(i));
109         }
110         
111         return new ChromosomePair(
112                 first.newFixedLengthChromosome(child1Rep),
113                 second.newFixedLengthChromosome(child2Rep)
114                 );
115     }
116 
117 }