MultiPointCrossover.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.5.0).
003  * Copyright (c) 2007-2013 Franz Wilhelmstötter
004  *
005  * Licensed under the Apache License, Version 2.0 (the "License");
006  * you may not use this file except in compliance with the License.
007  * 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  * Author:
018  *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019  */
020 package org.jenetics;
021 
022 import static java.lang.Math.min;
023 import static java.lang.String.format;
024 import static org.jenetics.util.object.hashCodeOf;
025 
026 import java.util.Random;
027 
028 import org.jenetics.util.MSeq;
029 import org.jenetics.util.RandomRegistry;
030 import org.jenetics.util.math;
031 
032 /**
033  <strong><p>Multiple point crossover</p></strong>
034  *
035  * If the {@code MultiPointCrossover} is created with one crossover point, it
036  * behaves exactly like the {@link SinglePointCrossover}. The following picture
037  * shows how the {@code MultiPointCrossover} works with two crossover points,
038  * defined at index 1 and 4.
039  <p><div align="center">
040  *    <img src="doc-files/2PointCrossover.svg" width="400" alt="2-point crossover">
041  </div></p>
042  *
043  * If the number of crossover points is odd, the crossover looks like in the
044  * following figure.
045  *
046  <p><div align="center">
047  *    <img src="doc-files/3PointCrossover.svg" width="400" alt="3-point crossover">
048  </div></p>
049  *
050  @see SinglePointCrossover
051  *
052  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
053  @since 1.2
054  @version 1.2 &mdash; <em>$Date: 2013-11-28 $ </em>
055  */
056 public class MultiPointCrossover<G extends Gene<?, G>> extends Crossover<G> {
057 
058     private final int _n;
059 
060     /**
061      * Create a new crossover instance.
062      *
063      @param probability the recombination probability.
064      @param n the number of crossover points.
065      @throws IllegalArgumentException if the {@code probability} is not in the
066      *         valid range of {@code [0, 1]} or {@code n &lt; 1}.
067      */
068     public MultiPointCrossover(final double probability, final int n) {
069         super(probability);
070         if (n < 1) {
071             throw new IllegalArgumentException(format(
072                 "n must be at least 1 but was %d.", n
073             ));
074         }
075         _n = n;
076     }
077 
078     /**
079      * Create a new crossover instance with two crossover points.
080      *
081      @param probability the recombination probability.
082      @throws IllegalArgumentException if the {@code probability} is not in the
083      *         valid range of {@code [0, 1]}.
084      */
085     public MultiPointCrossover(final double probability) {
086         this(probability, 2);
087     }
088 
089     /**
090      * Create a new crossover instance with default crossover probability of
091      * 0.05.
092      *
093      @param n the number of crossover points.
094      @throws IllegalArgumentException if {@code n &lt; 1}.
095      */
096     public MultiPointCrossover(final int n) {
097         this(0.05, n);
098     }
099 
100     /**
101      * Create a new crossover instance with two crossover points and crossover
102      * probability 0.05.
103      */
104     public MultiPointCrossover() {
105         this(0.052);
106     }
107 
108     /**
109      * Return the number of crossover points.
110      *
111      @return the number of crossover points.
112      */
113     public int getN() {
114         return _n;
115     }
116 
117     @Override
118     protected int crossover(final MSeq<G> that, final MSeq<G> other) {
119         assert (that.length() == other.length());
120 
121         final int n = that.length();
122         final int k = min(n, _n);
123 
124         final Random random = RandomRegistry.getRandom();
125         final int[] points = k > ? math.subset(n, k, randomnew int[0];
126 
127         crossover(that, other, points);
128         return 2;
129     }
130 
131     // Package private for testing purpose.
132     static <T> void crossover(
133         final MSeq<T> that,
134         final MSeq<T> other,
135         final int[] indexes
136     ) {
137 
138         for (int i = 0; i < indexes.length - 1; i += 2) {
139             final int start = indexes[i];
140             final int end = indexes[i + 1];
141             that.swap(start, end, other, start);
142         }
143         if (indexes.length%== 1) {
144             final int index = indexes[indexes.length - 1];
145             that.swap(index, that.length(), other, index);
146         }
147     }
148 
149     @Override
150     public int hashCode() {
151         return hashCodeOf(getClass()).
152                 and(super.hashCode()).
153                 and(_n).value();
154     }
155 
156     @Override
157     public boolean equals(final Object obj) {
158         if (obj == this) {
159             return true;
160         }
161         if (obj == null || obj.getClass() != getClass()) {
162             return false;
163         }
164 
165         final MultiPointCrossover<?> mpc = (MultiPointCrossover<?>)obj;
166         return _n == mpc._n && super.equals(obj);
167     }
168 
169     @Override
170     public String toString() {
171         return format(
172             "%s[p=%f, n=%d]",
173             getClass().getSimpleName(), _probability, _n
174         );
175     }
176 
177     //public static <G extends Gene<?, G>> MultiPointCrossover<G> zip() {
178     //    return new MultiPointCrossover<>(Integer.MAX_VALUE);
179     //}
180 
181 }
182 
183 
184 
185 
186 
187 
188 
189 
190