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