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 */ 017package org.apache.commons.math3.genetics; 018 019import java.util.ArrayList; 020import java.util.List; 021 022import org.apache.commons.math3.exception.DimensionMismatchException; 023import org.apache.commons.math3.exception.MathIllegalArgumentException; 024import org.apache.commons.math3.exception.NotStrictlyPositiveException; 025import org.apache.commons.math3.exception.NumberIsTooLargeException; 026import org.apache.commons.math3.exception.util.LocalizedFormats; 027import 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 */ 052public class NPointCrossover<T> implements CrossoverPolicy { 053 054 /** The number of crossover points. */ 055 private final int crossoverPoints; 056 057 /** 058 * Creates a new {@link NPointCrossover} policy using the given number of points. 059 * <p> 060 * <b>Note</b>: the number of crossover points must be < <code>chromosome length - 1</code>. 061 * This condition can only be checked at runtime, as the chromosome length is not known in advance. 062 * 063 * @param crossoverPoints the number of crossover points 064 * @throws NotStrictlyPositiveException if the number of {@code crossoverPoints} is not strictly positive 065 */ 066 public NPointCrossover(final int crossoverPoints) throws NotStrictlyPositiveException { 067 if (crossoverPoints <= 0) { 068 throw new NotStrictlyPositiveException(crossoverPoints); 069 } 070 this.crossoverPoints = crossoverPoints; 071 } 072 073 /** 074 * Returns the number of crossover points used by this {@link CrossoverPolicy}. 075 * 076 * @return the number of crossover points 077 */ 078 public int getCrossoverPoints() { 079 return crossoverPoints; 080 } 081 082 /** 083 * Performs a N-point crossover. N random crossover points are selected and are used 084 * to divide the parent chromosomes into segments. The segments are copied in alternate 085 * order from the two parents to the corresponding child chromosomes. 086 * 087 * Example (2-point crossover): 088 * <pre> 089 * -C- denotes a crossover point 090 * -C- -C- -C- -C- 091 * p1 = (1 0 | 1 0 0 1 | 0 1 1) X p2 = (0 1 | 1 0 1 0 | 1 1 1) 092 * \----/ \-------/ \-----/ \----/ \--------/ \-----/ 093 * || (*) || || (**) || 094 * VV (**) VV VV (*) VV 095 * /----\ /--------\ /-----\ /----\ /--------\ /-----\ 096 * c1 = (1 0 | 1 0 1 0 | 0 1 1) X c2 = (0 1 | 1 0 0 1 | 0 1 1) 097 * </pre> 098 * 099 * @param first first parent (p1) 100 * @param second second parent (p2) 101 * @return pair of two children (c1,c2) 102 * @throws MathIllegalArgumentException iff one of the chromosomes is 103 * not an instance of {@link AbstractListChromosome} 104 * @throws DimensionMismatchException if the length of the two chromosomes is different 105 */ 106 @SuppressWarnings("unchecked") // OK because of instanceof checks 107 public ChromosomePair crossover(final Chromosome first, final Chromosome second) 108 throws DimensionMismatchException, MathIllegalArgumentException { 109 110 if (!(first instanceof AbstractListChromosome<?> && second instanceof AbstractListChromosome<?>)) { 111 throw new MathIllegalArgumentException(LocalizedFormats.INVALID_FIXED_LENGTH_CHROMOSOME); 112 } 113 return mate((AbstractListChromosome<T>) first, (AbstractListChromosome<T>) second); 114 } 115 116 /** 117 * Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the actual crossover. 118 * 119 * @param first the first chromosome 120 * @param second the second chromosome 121 * @return the pair of new chromosomes that resulted from the crossover 122 * @throws DimensionMismatchException if the length of the two chromosomes is different 123 * @throws NumberIsTooLargeException if the number of crossoverPoints is too large for the actual chromosomes 124 */ 125 private ChromosomePair mate(final AbstractListChromosome<T> first, 126 final AbstractListChromosome<T> second) 127 throws DimensionMismatchException, NumberIsTooLargeException { 128 129 final int length = first.getLength(); 130 if (length != second.getLength()) { 131 throw new DimensionMismatchException(second.getLength(), length); 132 } 133 if (crossoverPoints >= length) { 134 throw new NumberIsTooLargeException(crossoverPoints, length, false); 135 } 136 137 // array representations of the parents 138 final List<T> parent1Rep = first.getRepresentation(); 139 final List<T> parent2Rep = second.getRepresentation(); 140 // and of the children 141 final List<T> child1Rep = new ArrayList<T>(length); 142 final List<T> child2Rep = new ArrayList<T>(length); 143 144 final RandomGenerator random = GeneticAlgorithm.getRandomGenerator(); 145 146 List<T> c1 = child1Rep; 147 List<T> c2 = child2Rep; 148 149 int remainingPoints = crossoverPoints; 150 int lastIndex = 0; 151 for (int i = 0; i < crossoverPoints; i++, remainingPoints--) { 152 // select the next crossover point at random 153 final int crossoverIndex = 1 + lastIndex + random.nextInt(length - lastIndex - remainingPoints); 154 155 // copy the current segment 156 for (int j = lastIndex; j < crossoverIndex; j++) { 157 c1.add(parent1Rep.get(j)); 158 c2.add(parent2Rep.get(j)); 159 } 160 161 // swap the children for the next segment 162 List<T> tmp = c1; 163 c1 = c2; 164 c2 = tmp; 165 166 lastIndex = crossoverIndex; 167 } 168 169 // copy the last segment 170 for (int j = lastIndex; j < length; j++) { 171 c1.add(parent1Rep.get(j)); 172 c2.add(parent2Rep.get(j)); 173 } 174 175 return new ChromosomePair(first.newFixedLengthChromosome(child1Rep), 176 second.newFixedLengthChromosome(child2Rep)); 177 } 178}