001 /*
002 * Java Genetic Algorithm Library (jenetics-6.0.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 6.0
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 * Check if this chromosome represents still a valid permutation (or subset)
154 * of the given valid alleles.
155 */
156 @Override
157 public boolean isValid() {
158 if (_valid == null) {
159 final byte[] check = Bits.newArray(_validAlleles.length());
160 _valid = _genes.forAll(g -> !getAndSet(check, g.alleleIndex()));
161 }
162
163 return _valid;
164 }
165
166 /**
167 * Create a new, <em>random</em> chromosome.
168 */
169 @Override
170 public PermutationChromosome<T> newInstance() {
171 return of(_validAlleles, length());
172 }
173
174 @Override
175 public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
176 return new PermutationChromosome<>(genes);
177 }
178
179 @Override
180 public String toString() {
181 return _genes.stream()
182 .map(g -> g.allele().toString())
183 .collect(Collectors.joining("|"));
184 }
185
186 /**
187 * Create a new, random chromosome with the given valid alleles and the
188 * desired length.
189 * <p>
190 * The following example shows how to create a {@code PermutationChromosome}
191 * for encoding a sub-set problem (of a fixed {@code length}).
192 * <pre>{@code
193 * final ISeq<String> basicSet = ISeq.of("a", "b", "c", "d", "e", "f");
194 *
195 * // The chromosome has a length of 3 and will only contain values from the
196 * // given basic-set, with no duplicates.
197 * final PermutationChromosome<String> ch = PermutationChromosome.of(basicSet, 3);
198 * }</pre>
199 *
200 * @since 3.4
201 *
202 * @param <T> the allele type
203 * @param alleles the base-set of the valid alleles
204 * @param length the length of the created chromosomes
205 * @return a new chromosome with the given valid alleles and the desired
206 * length
207 * @throws IllegalArgumentException if {@code alleles.size() < length},
208 * {@code length <= 0} or {@code alleles.size()*length} will
209 * cause an integer overflow.
210 * @throws NullPointerException if one of the arguments is {@code null}
211 */
212 public static <T> PermutationChromosome<T> of(
213 final ISeq<? extends T> alleles,
214 final int length
215 ) {
216 Requires.positive(length);
217 if (length > alleles.size()) {
218 throw new IllegalArgumentException(format(
219 "The sub-set size must be be greater then the base-set: %d > %d",
220 length, alleles.size()
221 ));
222 }
223
224 final int[] subset = Arrays.shuffle(Combinatorics.subset(alleles.size(), length));
225 final ISeq<EnumGene<T>> genes = IntStream.of(subset)
226 .mapToObj(i -> EnumGene.<T>of(i, alleles))
227 .collect(ISeq.toISeq());
228
229 return new PermutationChromosome<>(genes, true);
230 }
231
232 /**
233 * Create a new, random chromosome with the given valid alleles.
234 *
235 * @param <T> the gene type of the chromosome
236 * @param alleles the valid alleles used for this permutation arrays.
237 * @return a new chromosome with the given alleles
238 * @throws IllegalArgumentException if the given allele sequence is empty.
239 */
240 public static <T> PermutationChromosome<T>
241 of(final ISeq<? extends T> alleles) {
242 return of(alleles, alleles.size());
243 }
244
245 /**
246 * Create a new, random chromosome with the given valid alleles.
247 *
248 * @since 2.0
249 *
250 * @param <T> the gene type of the chromosome
251 * @param alleles the valid alleles used for this permutation arrays.
252 * @return a new chromosome with the given alleles
253 * @throws IllegalArgumentException if the given allele array is empty.
254 * @throws NullPointerException if one of the alleles is {@code null}
255 */
256 @SafeVarargs
257 public static <T> PermutationChromosome<T> of(final T... alleles) {
258 return of(ISeq.of(alleles));
259 }
260
261 /**
262 * Create a integer permutation chromosome with the given length.
263 *
264 * @param length the chromosome length.
265 * @return a integer permutation chromosome with the given length.
266 * @throws IllegalArgumentException if {@code length <= 0}.
267 */
268 public static PermutationChromosome<Integer> ofInteger(final int length) {
269 return ofInteger(0, Requires.positive(length));
270 }
271
272 /**
273 * Create an integer permutation chromosome with the given range.
274 *
275 * @since 2.0
276 *
277 * @param start the start of the integer range (inclusively) of the returned
278 * chromosome.
279 * @param end the end of the integer range (exclusively) of the returned
280 * chromosome.
281 * @return a integer permutation chromosome with the given integer range
282 * values.
283 * @throws IllegalArgumentException if {@code start >= end} or
284 * {@code start <= 0}
285 */
286 public static PermutationChromosome<Integer>
287 ofInteger(final int start, final int end) {
288 if (end <= start) {
289 throw new IllegalArgumentException(format(
290 "end <= start: %d <= %d", end, start
291 ));
292 }
293
294 return ofInteger(IntRange.of(start, end), end - start);
295 }
296
297 /**
298 * Create an integer permutation chromosome with the given range and length
299 *
300 * @since 3.4
301 *
302 * @param range the value range
303 * @param length the chromosome length
304 * @return a new integer permutation chromosome
305 * @throws NullPointerException if the given {@code range} is {@code null}
306 * @throws IllegalArgumentException if
307 * {@code range.getMax() - range.getMin() < length},
308 * {@code length <= 0} or
309 * {@code (range.getMax() - range.getMin())*length} will cause an
310 * integer overflow.
311 */
312 public static PermutationChromosome<Integer>
313 ofInteger(final IntRange range, final int length) {
314 return of(
315 range.stream().boxed().collect(ISeq.toISeq()),
316 length
317 );
318 }
319
320 /* *************************************************************************
321 * Java object serialization
322 * ************************************************************************/
323
324 private Object writeReplace() {
325 return new Serial(Serial.PERMUTATION_CHROMOSOME, this);
326 }
327
328 private void readObject(final ObjectInputStream stream)
329 throws InvalidObjectException
330 {
331 throw new InvalidObjectException("Serialization proxy required.");
332 }
333
334 void write(final ObjectOutput out) throws IOException {
335 out.writeObject(_validAlleles);
336 for (EnumGene<?> gene : _genes) {
337 writeInt(gene.alleleIndex(), out);
338 }
339 }
340
341 @SuppressWarnings({"unchecked", "rawtypes"})
342 static PermutationChromosome read(final ObjectInput in)
343 throws IOException, ClassNotFoundException
344 {
345 final ISeq validAlleles = (ISeq)in.readObject();
346 final MSeq genes = MSeq.ofLength(validAlleles.length());
347 for (int i = 0, n = validAlleles.length(); i < n; ++i) {
348 genes.set(i, new EnumGene(readInt(in), validAlleles));
349 }
350
351 return new PermutationChromosome(genes.toISeq());
352 }
353
354 }
|