001 /*
002 * Java Genetic Algorithm Library (jenetics-4.0.0).
003 * Copyright (c) 2007-2017 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 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
101 * @since 1.0
102 * @version 4.0
103 */
104 public final class PermutationChromosome<T>
105 extends AbstractChromosome<EnumGene<T>>
106 implements Serializable
107 {
108 private static final long serialVersionUID = 2L;
109
110 private ISeq<T> _validAlleles;
111
112 // Private primary constructor.
113 private PermutationChromosome(
114 final ISeq<EnumGene<T>> genes,
115 final Boolean valid
116 ) {
117 super(genes);
118
119 assert !genes.isEmpty();
120 _validAlleles = genes.get(0).getValidAlleles();
121 _valid = valid;
122 }
123
124 /**
125 * Create a new {@code PermutationChromosome} from the given {@code genes}.
126 * If the given {@code genes} sequence contains duplicate entries, the
127 * created {@code PermutationChromosome} will be invalid
128 * ({@code ch.isValid() == false}).
129 *
130 * @param genes the enum genes the new chromosome consists of
131 * @throws NullPointerException if the given {@code genes} are null
132 * @throws IllegalArgumentException if the given {@code genes} sequence is
133 * empty
134 */
135 public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
136 this(genes, null);
137 }
138
139 /**
140 * Return the sequence of valid alleles of this chromosome.
141 *
142 * @return the sequence of valid alleles of this chromosome
143 */
144 public ISeq<T> getValidAlleles() {
145 return _validAlleles;
146 }
147
148 /**
149 * Check if this chromosome represents still a valid permutation (or subset)
150 * of the given valid alleles.
151 */
152 @Override
153 public boolean isValid() {
154 if (_valid == null) {
155 final byte[] check = bit.newArray(_validAlleles.length());
156 _valid = _genes.forAll(g -> !getAndSet(check, g.getAlleleIndex()));
157 }
158
159 return _valid;
160 }
161
162 /**
163 * Create a new, <em>random</em> chromosome.
164 */
165 @Override
166 public PermutationChromosome<T> newInstance() {
167 return of(_validAlleles, length());
168 }
169
170 @Override
171 public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
172 return new PermutationChromosome<>(genes);
173 }
174
175 @Override
176 public int hashCode() {
177 return Hash.of(getClass())
178 .and(super.hashCode())
179 .value();
180 }
181
182 @Override
183 public boolean equals(final Object obj) {
184 return Equality.of(this, obj).test(super::equals);
185 }
186
187 @Override
188 public String toString() {
189 return _genes.asList().stream()
190 .map(g -> g.getAllele().toString())
191 .collect(Collectors.joining("|"));
192 }
193
194 /**
195 * Create a new, random chromosome with the given valid alleles and the
196 * desired length.
197 * <p>
198 * The following example shows how to create a {@code PermutationChromosome}
199 * for encoding a sub-set problem (of a fixed {@code length}).
200 * <pre>{@code
201 * final ISeq<String> basicSet = ISeq.of("a", "b", "c", "d", "e", "f");
202 *
203 * // The chromosome has a length of 3 and will only contain values from the
204 * // given basic-set, with no duplicates.
205 * final PermutationChromosome<String> ch = PermutationChromosome.of(basicSet, 3);
206 * }</pre>
207 *
208 * @since 3.4
209 *
210 * @param <T> the allele type
211 * @param alleles the base-set of the valid alleles
212 * @param length the length of the created chromosomes
213 * @return a new chromosome with the given valid alleles and the desired
214 * length
215 * @throws IllegalArgumentException if {@code alleles.size() < length},
216 * {@code length <= 0} or {@code alleles.size()*length} will
217 * cause an integer overflow.
218 * @throws NullPointerException if one of the arguments is {@code null}
219 */
220 public static <T> PermutationChromosome<T> of(
221 final ISeq<? extends T> alleles,
222 final int length
223 ) {
224 require.positive(length);
225 if (length > alleles.size()) {
226 throw new IllegalArgumentException(format(
227 "The sub-set size must be be greater then the base-set: %d > %d",
228 length, alleles.size()
229 ));
230 }
231
232 final int[] subset = array.shuffle(comb.subset(alleles.size(), length));
233 final ISeq<EnumGene<T>> genes = IntStream.of(subset)
234 .mapToObj(i -> EnumGene.<T>of(i, alleles))
235 .collect(ISeq.toISeq());
236
237 return new PermutationChromosome<>(genes, true);
238 }
239
240 /**
241 * Create a new, random chromosome with the given valid alleles.
242 *
243 * @param <T> the gene type of the chromosome
244 * @param alleles the valid alleles used for this permutation arrays.
245 * @return a new chromosome with the given alleles
246 * @throws IllegalArgumentException if the given allele sequence is empty.
247 */
248 public static <T> PermutationChromosome<T>
249 of(final ISeq<? extends T> alleles) {
250 return of(alleles, alleles.size());
251 }
252
253 /**
254 * Create a new, random chromosome with the given valid alleles.
255 *
256 * @since 2.0
257 *
258 * @param <T> the gene type of the chromosome
259 * @param alleles the valid alleles used for this permutation arrays.
260 * @return a new chromosome with the given alleles
261 * @throws IllegalArgumentException if the given allele array is empty.
262 * @throws NullPointerException if one of the alleles is {@code null}
263 */
264 @SafeVarargs
265 public static <T> PermutationChromosome<T> of(final T... alleles) {
266 return of(ISeq.of(alleles));
267 }
268
269 /**
270 * Create a integer permutation chromosome with the given length.
271 *
272 * @param length the chromosome length.
273 * @return a integer permutation chromosome with the given length.
274 * @throws IllegalArgumentException if {@code length <= 0}.
275 */
276 public static PermutationChromosome<Integer> ofInteger(final int length) {
277 return ofInteger(0, require.positive(length));
278 }
279
280 /**
281 * Create an integer permutation chromosome with the given range.
282 *
283 * @since 2.0
284 *
285 * @param start the start of the integer range (inclusively) of the returned
286 * chromosome.
287 * @param end the end of the integer range (exclusively) of the returned
288 * chromosome.
289 * @return a integer permutation chromosome with the given integer range
290 * values.
291 * @throws IllegalArgumentException if {@code start >= end} or
292 * {@code start <= 0}
293 */
294 public static PermutationChromosome<Integer>
295 ofInteger(final int start, final int end) {
296 if (end <= start) {
297 throw new IllegalArgumentException(format(
298 "end <= start: %d <= %d", end, start
299 ));
300 }
301
302 return ofInteger(IntRange.of(start, end), end - start);
303 }
304
305 /**
306 * Create an integer permutation chromosome with the given range and length
307 *
308 * @since 3.4
309 *
310 * @param range the value range
311 * @param length the chromosome length
312 * @return a new integer permutation chromosome
313 * @throws NullPointerException if the given {@code range} is {@code null}
314 * @throws IllegalArgumentException if
315 * {@code range.getMax() - range.getMin() < length},
316 * {@code length <= 0} or
317 * {@code (range.getMax() - range.getMin())*length} will cause an
318 * integer overflow.
319 */
320 public static PermutationChromosome<Integer>
321 ofInteger(final IntRange range, final int length) {
322 return of(
323 range.stream()
324 .boxed()
325 .collect(ISeq.toISeq()),
326 length
327 );
328 }
329
330 /* *************************************************************************
331 * Java object serialization
332 * ************************************************************************/
333
334 private void writeObject(final ObjectOutputStream out)
335 throws IOException
336 {
337 out.defaultWriteObject();
338
339 out.writeObject(_validAlleles);
340 for (EnumGene<?> gene : _genes) {
341 out.writeInt(gene.getAlleleIndex());
342 }
343 }
344
345 @SuppressWarnings("unchecked")
346 private void readObject(final ObjectInputStream in)
347 throws IOException, ClassNotFoundException
348 {
349 in.defaultReadObject();
350
351 _validAlleles = (ISeq<T>)in.readObject();
352
353 final MSeq<EnumGene<T>> genes = MSeq.ofLength(_validAlleles.length());
354 for (int i = 0; i < _validAlleles.length(); ++i) {
355 genes.set(i, new EnumGene<>(in.readInt(), _validAlleles));
356 }
357
358 reflect.setField(this, "_genes", genes.toISeq());
359 }
360
361 }
|