001 /*
002 * Java Genetic Algorithm Library (jenetics-5.2.0).
003 * Copyright (c) 2007-2020 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@gmail.com)
019 */
020 package io.jenetics;
021
022 import static java.lang.String.format;
023 import static io.jenetics.internal.util.Bits.getAndSet;
024 import static io.jenetics.internal.util.SerialIO.readInt;
025 import static io.jenetics.internal.util.SerialIO.writeInt;
026
027 import java.io.IOException;
028 import java.io.InvalidObjectException;
029 import java.io.ObjectInput;
030 import java.io.ObjectInputStream;
031 import java.io.ObjectOutput;
032 import java.io.Serializable;
033 import java.util.stream.Collectors;
034 import java.util.stream.IntStream;
035
036 import io.jenetics.internal.math.Combinatorics;
037 import io.jenetics.internal.util.Arrays;
038 import io.jenetics.internal.util.Bits;
039 import io.jenetics.internal.util.Requires;
040 import io.jenetics.util.ISeq;
041 import io.jenetics.util.IntRange;
042 import io.jenetics.util.MSeq;
043
044 /**
045 * This chromosome can be used to model permutations of a given (sub) set of
046 * alleles.
047 *
048 * <pre>{@code
049 * final ISeq<String> alleles = ISeq.of("one", "two", "three", "four", "five");
050 *
051 * // Create a new randomly permuted chromosome from the given alleles.
052 * final PermutationChromosome<String> ch1 = PermutationChromosome.of(alleles);
053 * System.out.println(ch1);
054 * System.out.println(ch1.newInstance());
055 *
056 * // Create a new randomly permuted chromosome from a subset of the given alleles.
057 * final PermutationChromosome<String> ch2 = PermutationChromosome.of(alleles, 3);
058 * System.out.println(ch2);
059 * System.out.println(ch2.newInstance());
060 *
061 * // Console output:
062 * // > three|two|one|five|four
063 * // > two|one|four|five|three
064 * // > three|one|five
065 * // > five|three|one
066 * }</pre>
067 *
068 * Usable {@link Alterer} for this chromosome:
069 * <ul>
070 * <li>{@link PartiallyMatchedCrossover}</li>
071 * <li>{@link SwapMutator}</li>
072 * </ul>
073 * <p>
074 * <em><b>Implementation note 1:</b>
075 * The factory methods of the {@link AbstractChromosome} has been overridden so
076 * that no invalid permutation will be created.
077 * </em>
078 *
079 * <p>
080 * <em><b>Implementation note 2:</b>
081 * This class uses an algorithm for choosing subsets which is based on a
082 * FORTRAN77 version, originally implemented by Albert Nijenhuis, Herbert Wilf.
083 * The actual Java implementation is based on the C++ version by John Burkardt.
084 * </em>
085 * <br>
086 * <em><a href="https://people.sc.fsu.edu/~burkardt/c_src/subset/subset.html">
087 * Reference:</a></em>
088 * Albert Nijenhuis, Herbert Wilf,
089 * Combinatorial Algorithms for Computers and Calculators,
090 * Second Edition,
091 * Academic Press, 1978,
092 * ISBN: 0-12-519260-6,
093 * LC: QA164.N54.
094 * </p>
095 *
096 *
097 * @see EnumGene
098 * @see PartiallyMatchedCrossover
099 * @see SwapMutator
100 *
101 * @implNote
102 * This class is immutable and thread-safe.
103 *
104 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
105 * @since 1.0
106 * @version 5.2
107 */
108 public final class PermutationChromosome<T>
109 extends AbstractChromosome<EnumGene<T>>
110 implements Serializable
111 {
112 private static final long serialVersionUID = 2L;
113
114 private final ISeq<T> _validAlleles;
115
116 // Private primary constructor.
117 private PermutationChromosome(
118 final ISeq<EnumGene<T>> genes,
119 final Boolean valid
120 ) {
121 super(genes);
122
123 assert !genes.isEmpty();
124 _validAlleles = genes.get(0).validAlleles();
125 _valid = valid;
126 }
127
128 /**
129 * Create a new {@code PermutationChromosome} from the given {@code genes}.
130 * If the given {@code genes} sequence contains duplicate entries, the
131 * created {@code PermutationChromosome} will be invalid
132 * ({@code ch.isValid() == false}).
133 *
134 * @param genes the enum genes the new chromosome consists of
135 * @throws NullPointerException if the given {@code genes} are null
136 * @throws IllegalArgumentException if the given {@code genes} sequence is
137 * empty
138 */
139 public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
140 this(genes, null);
141 }
142
143 /**
144 * Return the sequence of valid alleles of this chromosome.
145 *
146 * @return the sequence of valid alleles of this chromosome
147 */
148 public ISeq<T> validAlleles() {
149 return _validAlleles;
150 }
151
152 /**
153 * Return the sequence of valid alleles of this chromosome.
154 *
155 * @return the sequence of valid alleles of this chromosome
156 * @deprecated Use {@link #validAlleles()} instead
157 */
158 @Deprecated
159 public ISeq<T> getValidAlleles() {
160 return _validAlleles;
161 }
162
163 /**
164 * Check if this chromosome represents still a valid permutation (or subset)
165 * of the given valid alleles.
166 */
167 @Override
168 public boolean isValid() {
169 if (_valid == null) {
170 final byte[] check = Bits.newArray(_validAlleles.length());
171 _valid = _genes.forAll(g -> !getAndSet(check, g.alleleIndex()));
172 }
173
174 return _valid;
175 }
176
177 /**
178 * Create a new, <em>random</em> chromosome.
179 */
180 @Override
181 public PermutationChromosome<T> newInstance() {
182 return of(_validAlleles, length());
183 }
184
185 @Override
186 public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
187 return new PermutationChromosome<>(genes);
188 }
189
190 @Override
191 public String toString() {
192 return _genes.asList().stream()
193 .map(g -> g.allele().toString())
194 .collect(Collectors.joining("|"));
195 }
196
197 /**
198 * Create a new, random chromosome with the given valid alleles and the
199 * desired length.
200 * <p>
201 * The following example shows how to create a {@code PermutationChromosome}
202 * for encoding a sub-set problem (of a fixed {@code length}).
203 * <pre>{@code
204 * final ISeq<String> basicSet = ISeq.of("a", "b", "c", "d", "e", "f");
205 *
206 * // The chromosome has a length of 3 and will only contain values from the
207 * // given basic-set, with no duplicates.
208 * final PermutationChromosome<String> ch = PermutationChromosome.of(basicSet, 3);
209 * }</pre>
210 *
211 * @since 3.4
212 *
213 * @param <T> the allele type
214 * @param alleles the base-set of the valid alleles
215 * @param length the length of the created chromosomes
216 * @return a new chromosome with the given valid alleles and the desired
217 * length
218 * @throws IllegalArgumentException if {@code alleles.size() < length},
219 * {@code length <= 0} or {@code alleles.size()*length} will
220 * cause an integer overflow.
221 * @throws NullPointerException if one of the arguments is {@code null}
222 */
223 public static <T> PermutationChromosome<T> of(
224 final ISeq<? extends T> alleles,
225 final int length
226 ) {
227 Requires.positive(length);
228 if (length > alleles.size()) {
229 throw new IllegalArgumentException(format(
230 "The sub-set size must be be greater then the base-set: %d > %d",
231 length, alleles.size()
232 ));
233 }
234
235 final int[] subset = Arrays.shuffle(Combinatorics.subset(alleles.size(), length));
236 final ISeq<EnumGene<T>> genes = IntStream.of(subset)
237 .mapToObj(i -> EnumGene.<T>of(i, alleles))
238 .collect(ISeq.toISeq());
239
240 return new PermutationChromosome<>(genes, true);
241 }
242
243 /**
244 * Create a new, random chromosome with the given valid alleles.
245 *
246 * @param <T> the gene type of the chromosome
247 * @param alleles the valid alleles used for this permutation arrays.
248 * @return a new chromosome with the given alleles
249 * @throws IllegalArgumentException if the given allele sequence is empty.
250 */
251 public static <T> PermutationChromosome<T>
252 of(final ISeq<? extends T> alleles) {
253 return of(alleles, alleles.size());
254 }
255
256 /**
257 * Create a new, random chromosome with the given valid alleles.
258 *
259 * @since 2.0
260 *
261 * @param <T> the gene type of the chromosome
262 * @param alleles the valid alleles used for this permutation arrays.
263 * @return a new chromosome with the given alleles
264 * @throws IllegalArgumentException if the given allele array is empty.
265 * @throws NullPointerException if one of the alleles is {@code null}
266 */
267 @SafeVarargs
268 public static <T> PermutationChromosome<T> of(final T... alleles) {
269 return of(ISeq.of(alleles));
270 }
271
272 /**
273 * Create a integer permutation chromosome with the given length.
274 *
275 * @param length the chromosome length.
276 * @return a integer permutation chromosome with the given length.
277 * @throws IllegalArgumentException if {@code length <= 0}.
278 */
279 public static PermutationChromosome<Integer> ofInteger(final int length) {
280 return ofInteger(0, Requires.positive(length));
281 }
282
283 /**
284 * Create an integer permutation chromosome with the given range.
285 *
286 * @since 2.0
287 *
288 * @param start the start of the integer range (inclusively) of the returned
289 * chromosome.
290 * @param end the end of the integer range (exclusively) of the returned
291 * chromosome.
292 * @return a integer permutation chromosome with the given integer range
293 * values.
294 * @throws IllegalArgumentException if {@code start >= end} or
295 * {@code start <= 0}
296 */
297 public static PermutationChromosome<Integer>
298 ofInteger(final int start, final int end) {
299 if (end <= start) {
300 throw new IllegalArgumentException(format(
301 "end <= start: %d <= %d", end, start
302 ));
303 }
304
305 return ofInteger(IntRange.of(start, end), end - start);
306 }
307
308 /**
309 * Create an integer permutation chromosome with the given range and length
310 *
311 * @since 3.4
312 *
313 * @param range the value range
314 * @param length the chromosome length
315 * @return a new integer permutation chromosome
316 * @throws NullPointerException if the given {@code range} is {@code null}
317 * @throws IllegalArgumentException if
318 * {@code range.getMax() - range.getMin() < length},
319 * {@code length <= 0} or
320 * {@code (range.getMax() - range.getMin())*length} will cause an
321 * integer overflow.
322 */
323 public static PermutationChromosome<Integer>
324 ofInteger(final IntRange range, final int length) {
325 return of(
326 range.stream().boxed()
327 .collect(ISeq.toISeq()),
328 length
329 );
330 }
331
332 /* *************************************************************************
333 * Java object serialization
334 * ************************************************************************/
335
336 private Object writeReplace() {
337 return new Serial(Serial.PERMUTATION_CHROMOSOME, this);
338 }
339
340 private void readObject(final ObjectInputStream stream)
341 throws InvalidObjectException
342 {
343 throw new InvalidObjectException("Serialization proxy required.");
344 }
345
346 void write(final ObjectOutput out) throws IOException {
347 out.writeObject(_validAlleles);
348 for (EnumGene<?> gene : _genes) {
349 writeInt(gene.alleleIndex(), out);
350 }
351 }
352
353 @SuppressWarnings({"unchecked", "rawtypes"})
354 static PermutationChromosome read(final ObjectInput in)
355 throws IOException, ClassNotFoundException
356 {
357 final ISeq validAlleles = (ISeq)in.readObject();
358 final MSeq genes = MSeq.ofLength(validAlleles.length());
359 for (int i = 0, n = validAlleles.length(); i < n; ++i) {
360 genes.set(i, new EnumGene(readInt(in), validAlleles));
361 }
362
363 return new PermutationChromosome(genes.toISeq());
364 }
365
366 }
|