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