001 /*
002 * Java Genetic Algorithm Library (jenetics-4.1.0).
003 * Copyright (c) 2007-2018 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.Equality;
034 import io.jenetics.internal.util.Hash;
035 import io.jenetics.internal.util.array;
036 import io.jenetics.internal.util.bit;
037 import io.jenetics.internal.util.reflect;
038 import io.jenetics.internal.util.require;
039 import io.jenetics.util.ISeq;
040 import io.jenetics.util.IntRange;
041 import io.jenetics.util.MSeq;
042
043 /**
044 * This chromosome can be used to model permutations of a given (sub) set of
045 * alleles.
046 *
047 * <pre>{@code
048 * final ISeq<String> alleles = ISeq.of("one", "two", "three", "four", "five");
049 *
050 * // Create a new randomly permuted chromosome from the given alleles.
051 * final PermutationChromosome<String> ch1 = PermutationChromosome.of(alleles);
052 * System.out.println(ch1);
053 * System.out.println(ch1.newInstance());
054 *
055 * // Create a new randomly permuted chromosome from a subset of the given alleles.
056 * final PermutationChromosome<String> ch2 = PermutationChromosome.of(alleles, 3);
057 * System.out.println(ch2);
058 * System.out.println(ch2.newInstance());
059 *
060 * // Console output:
061 * // > three|two|one|five|four
062 * // > two|one|four|five|three
063 * // > three|one|five
064 * // > five|three|one
065 * }</pre>
066 *
067 * Usable {@link Alterer} for this chromosome:
068 * <ul>
069 * <li>{@link PartiallyMatchedCrossover}</li>
070 * <li>{@link SwapMutator}</li>
071 * </ul>
072 * <p>
073 * <em><b>Implementation note 1:</b>
074 * The factory methods of the {@link AbstractChromosome} has been overridden so
075 * that no invalid permutation will be created.
076 * </em>
077 *
078 * <p>
079 * <em><b>Implementation note 2:</b>
080 * This class uses an algorithm for choosing subsets which is based on a
081 * FORTRAN77 version, originally implemented by Albert Nijenhuis, Herbert Wilf.
082 * The actual Java implementation is based on the C++ version by John Burkardt.
083 * </em>
084 * <br>
085 * <em><a href="https://people.sc.fsu.edu/~burkardt/c_src/subset/subset.html">
086 * Reference:</a></em>
087 * Albert Nijenhuis, Herbert Wilf,
088 * Combinatorial Algorithms for Computers and Calculators,
089 * Second Edition,
090 * Academic Press, 1978,
091 * ISBN: 0-12-519260-6,
092 * LC: QA164.N54.
093 * </p>
094 *
095 *
096 * @see EnumGene
097 * @see PartiallyMatchedCrossover
098 * @see SwapMutator
099 *
100 * @implSpec
101 * This class is immutable and thread-safe.
102 *
103 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
104 * @since 1.0
105 * @version 4.0
106 */
107 public final class PermutationChromosome<T>
108 extends AbstractChromosome<EnumGene<T>>
109 implements Serializable
110 {
111 private static final long serialVersionUID = 2L;
112
113 private ISeq<T> _validAlleles;
114
115 // Private primary constructor.
116 private PermutationChromosome(
117 final ISeq<EnumGene<T>> genes,
118 final Boolean valid
119 ) {
120 super(genes);
121
122 assert !genes.isEmpty();
123 _validAlleles = genes.get(0).getValidAlleles();
124 _valid = valid;
125 }
126
127 /**
128 * Create a new {@code PermutationChromosome} from the given {@code genes}.
129 * If the given {@code genes} sequence contains duplicate entries, the
130 * created {@code PermutationChromosome} will be invalid
131 * ({@code ch.isValid() == false}).
132 *
133 * @param genes the enum genes the new chromosome consists of
134 * @throws NullPointerException if the given {@code genes} are null
135 * @throws IllegalArgumentException if the given {@code genes} sequence is
136 * empty
137 */
138 public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
139 this(genes, null);
140 }
141
142 /**
143 * Return the sequence of valid alleles of this chromosome.
144 *
145 * @return the sequence of valid alleles of this chromosome
146 */
147 public ISeq<T> getValidAlleles() {
148 return _validAlleles;
149 }
150
151 /**
152 * Check if this chromosome represents still a valid permutation (or subset)
153 * of the given valid alleles.
154 */
155 @Override
156 public boolean isValid() {
157 if (_valid == null) {
158 final byte[] check = bit.newArray(_validAlleles.length());
159 _valid = _genes.forAll(g -> !getAndSet(check, g.getAlleleIndex()));
160 }
161
162 return _valid;
163 }
164
165 /**
166 * Create a new, <em>random</em> chromosome.
167 */
168 @Override
169 public PermutationChromosome<T> newInstance() {
170 return of(_validAlleles, length());
171 }
172
173 @Override
174 public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
175 return new PermutationChromosome<>(genes);
176 }
177
178 @Override
179 public int hashCode() {
180 return Hash.of(getClass())
181 .and(super.hashCode())
182 .value();
183 }
184
185 @Override
186 public boolean equals(final Object obj) {
187 return Equality.of(this, obj).test(super::equals);
188 }
189
190 @Override
191 public String toString() {
192 return _genes.asList().stream()
193 .map(g -> g.getAllele().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 require.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 = array.shuffle(comb.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, require.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()
327 .boxed()
328 .collect(ISeq.toISeq()),
329 length
330 );
331 }
332
333 /* *************************************************************************
334 * Java object serialization
335 * ************************************************************************/
336
337 private void writeObject(final ObjectOutputStream out)
338 throws IOException
339 {
340 out.defaultWriteObject();
341
342 out.writeObject(_validAlleles);
343 for (EnumGene<?> gene : _genes) {
344 out.writeInt(gene.getAlleleIndex());
345 }
346 }
347
348 @SuppressWarnings("unchecked")
349 private void readObject(final ObjectInputStream in)
350 throws IOException, ClassNotFoundException
351 {
352 in.defaultReadObject();
353
354 _validAlleles = (ISeq<T>)in.readObject();
355
356 final MSeq<EnumGene<T>> genes = MSeq.ofLength(_validAlleles.length());
357 for (int i = 0; i < _validAlleles.length(); ++i) {
358 genes.set(i, new EnumGene<>(in.readInt(), _validAlleles));
359 }
360
361 reflect.setField(this, "_genes", genes.toISeq());
362 }
363
364 }
|