001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.math3.genetics; 018 019 import java.util.ArrayList; 020 import java.util.List; 021 022 import org.apache.commons.math3.exception.DimensionMismatchException; 023 import org.apache.commons.math3.exception.MathIllegalArgumentException; 024 import org.apache.commons.math3.exception.NotStrictlyPositiveException; 025 import org.apache.commons.math3.exception.NumberIsTooLargeException; 026 import org.apache.commons.math3.exception.util.LocalizedFormats; 027 import org.apache.commons.math3.random.RandomGenerator; 028 029 /** 030 * N-point crossover policy. For each iteration a random crossover point is 031 * selected and the first part from each parent is copied to the corresponding 032 * child, and the second parts are copied crosswise. 033 * 034 * Example (2-point crossover): 035 * <pre> 036 * -C- denotes a crossover point 037 * -C- -C- -C- -C- 038 * p1 = (1 0 | 1 0 0 1 | 0 1 1) X p2 = (0 1 | 1 0 1 0 | 1 1 1) 039 * \----/ \-------/ \-----/ \----/ \--------/ \-----/ 040 * || (*) || || (**) || 041 * VV (**) VV VV (*) VV 042 * /----\ /--------\ /-----\ /----\ /--------\ /-----\ 043 * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1) 044 * </pre> 045 * 046 * This policy works only on {@link AbstractListChromosome}, and therefore it 047 * is parameterized by T. Moreover, the chromosomes must have same lengths. 048 * 049 * @param <T> generic type of the {@link AbstractListChromosome}s for crossover 050 * @since 3.1 051 * @version $Id: NPointCrossover.java 1385297 2012-09-16 16:05:57Z tn $ 052 */ 053 public class NPointCrossover<T> implements CrossoverPolicy { 054 055 /** The number of crossover points. */ 056 private final int crossoverPoints; 057 058 /** 059 * Creates a new {@link NPointCrossover} policy using the given number of points. 060 * <p> 061 * <b>Note</b>: the number of crossover points must be < <code>chromosome length - 1</code>. 062 * This condition can only be checked at runtime, as the chromosome length is not known in advance. 063 * 064 * @param crossoverPoints the number of crossover points 065 * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive 066 */ 067 public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException { 068 if (crossoverPoints <= 0) { 069 throw new NotStrictlyPositiveException(crossoverPoints); 070 } 071 this.crossoverPoints = crossoverPoints; 072 } 073 074 /** 075 * Returns the number of crossover points used by this {@link CrossoverPolicy}. 076 * 077 * @return the number of crossover points 078 */ 079 public int getCrossoverPoints() { 080 return crossoverPoints; 081 } 082 083 /** 084 * Performs a N-point crossover. N random crossover points are selected and are used 085 * to divide the parent chromosomes into segments. The segments are copied in alternate 086 * order from the two parents to the corresponding child chromosomes. 087 * 088 * Example (2-point crossover): 089 * <pre> 090 * -C- denotes a crossover point 091 * -C- -C- -C- -C- 092 * p1 = (1 0 | 1 0 0 1 | 0 1 1) X p2 = (0 1 | 1 0 1 0 | 1 1 1) 093 * \----/ \-------/ \-----/ \----/ \--------/ \-----/ 094 * || (*) || || (**) || 095 * VV (**) VV VV (*) VV 096 * /----\ /--------\ /-----\ /----\ /--------\ /-----\ 097 * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1) 098 * </pre> 099 * 100 * @param first first parent (p1) 101 * @param second second parent (p2) 102 * @return pair of two children (c1,c2) 103 * @throws MathIllegalArgumentException iff one of the chromosomes is 104 * not an instance of {@link AbstractListChromosome} 105 * @throws DimensionMismatchException if the length of the two chromosomes is different 106 */ 107 @SuppressWarnings("unchecked") // OK because of instanceof checks 108 public ChromosomePair crossover(final Chromosome first, final Chromosome second) 109 throws DimensionMismatchException, MathIllegalArgumentException { 110 111 if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { 112 throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); 113 } 114 return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second); 115 } 116 117 /** 118 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover. 119 * 120 * @param first the first chromosome 121 * @param second the second chromosome 122 * @return the pair of new chromosomes that resulted from the crossover 123 * @throws DimensionMismatchException if the length of the two chromosomes is different 124 * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes 125 */ 126 private ChromosomePair mate(final AbstractListChromosome<T> first, 127 final AbstractListChromosome<T> second) 128 throws DimensionMismatchException, NumberIsTooLargeException { 129 130 final int length = first.getLength(); 131 if (length != second.getLength()) { 132 throw new DimensionMismatchException(second.getLength(), length); 133 } 134 if (crossoverPoints >= length) { 135 throw new NumberIsTooLargeException(crossoverPoints, length, false); 136 } 137 138 // array representations of the parents 139 final List<T> parent1Rep = first.getRepresentation(); 140 final List<T> parent2Rep = second.getRepresentation(); 141 // and of the children 142 final ArrayList<T> child1Rep = new ArrayList<T>(first.getLength()); 143 final ArrayList<T> child2Rep = new ArrayList<T>(second.getLength()); 144 145 final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); 146 147 ArrayList<T> c1 = child1Rep; 148 ArrayList<T> c2 = child2Rep; 149 150 int remainingPoints = crossoverPoints; 151 int lastIndex = 0; 152 for (int i = 0; i < crossoverPoints; i++, remainingPoints--) { 153 // select the next crossover point at random 154 final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints); 155 156 // copy the current segment 157 for (int j = lastIndex; j < crossoverIndex; j++) { 158 c1.add(parent1Rep.get(j)); 159 c2.add(parent2Rep.get(j)); 160 } 161 162 // swap the children for the next segment 163 ArrayList<T> tmp = c1; 164 c1 = c2; 165 c2 = tmp; 166 167 lastIndex = crossoverIndex; 168 } 169 170 // copy the last segment 171 for (int j = lastIndex; j < length; j++) { 172 c1.add(parent1Rep.get(j)); 173 c2.add(parent2Rep.get(j)); 174 } 175 176 return new ChromosomePair(first.newFixedLengthChromosome(child1Rep), 177 second.newFixedLengthChromosome(child2Rep)); 178 } 179 }