PermutationChromosome.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-7.0.0).
003  * Copyright (c) 2007-2022 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  <pre>{@code
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  * }</pre>
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 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      <pre>{@code
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      * }</pre>
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(alleles.size(), length, rnd);
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 outthrows 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 }