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 */
17package org.apache.commons.math.genetics;
18
19import java.util.ArrayList;
20import 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: 903046 $ $Date: 2010-01-26 03:07:26 +0100 (mar. 26 janv. 2010) $
46 *
47 */
48public 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") // OK because of instanceof checks
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}
118