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