001 /*
002 * Java Genetic Algorithm Library (jenetics-3.9.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@gmx.at)
019 */
020 package org.jenetics;
021
022 import static java.lang.String.format;
023 import static org.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.List;
030 import java.util.function.Function;
031 import java.util.stream.Collectors;
032 import java.util.stream.IntStream;
033
034 import javax.xml.bind.annotation.XmlAccessType;
035 import javax.xml.bind.annotation.XmlAccessorType;
036 import javax.xml.bind.annotation.XmlAttribute;
037 import javax.xml.bind.annotation.XmlElement;
038 import javax.xml.bind.annotation.XmlElementWrapper;
039 import javax.xml.bind.annotation.XmlList;
040 import javax.xml.bind.annotation.XmlRootElement;
041 import javax.xml.bind.annotation.XmlType;
042 import javax.xml.bind.annotation.adapters.XmlAdapter;
043 import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;
044
045 import org.jenetics.internal.math.base;
046 import org.jenetics.internal.util.Equality;
047 import org.jenetics.internal.util.Hash;
048 import org.jenetics.internal.util.array;
049 import org.jenetics.internal.util.bit;
050 import org.jenetics.internal.util.jaxb;
051 import org.jenetics.internal.util.require;
052
053 import org.jenetics.util.ISeq;
054 import org.jenetics.util.IntRange;
055 import org.jenetics.util.MSeq;
056 import org.jenetics.util.Seq;
057
058 /**
059 * This chromosome can be used to model permutations of a given (sub) set of
060 * alleles.
061 *
062 * <pre>{@code
063 * final ISeq<String> alleles = ISeq.of("one", "two", "three", "four", "five");
064 *
065 * // Create a new randomly permuted chromosome from the given alleles.
066 * final PermutationChromosome<String> ch1 = PermutationChromosome.of(alleles);
067 * System.out.println(ch1);
068 * System.out.println(ch1.newInstance());
069 *
070 * // Create a new randomly permuted chromosome from a subset of the given alleles.
071 * final PermutationChromosome<String> ch2 = PermutationChromosome.of(alleles, 3);
072 * System.out.println(ch2);
073 * System.out.println(ch2.newInstance());
074 *
075 * // Console output:
076 * // > three|two|one|five|four
077 * // > two|one|four|five|three
078 * // > three|one|five
079 * // > five|three|one
080 * }</pre>
081 *
082 * Usable {@link Alterer} for this chromosome:
083 * <ul>
084 * <li>{@link PartiallyMatchedCrossover}</li>
085 * <li>{@link SwapMutator}</li>
086 * </ul>
087 * <p>
088 * <em><b>Implementation note 1:</b>
089 * The factory methods of the {@link AbstractChromosome} has been overridden so
090 * that no invalid permutation will be created.
091 * </em>
092 *
093 * <p>
094 * <em><b>Implementation note 2:</b>
095 * This class uses an algorithm for choosing subsets which is based on a
096 * FORTRAN77 version, originally implemented by Albert Nijenhuis, Herbert Wilf.
097 * The actual Java implementation is based on the C++ version by John Burkardt.
098 * </em>
099 * <br>
100 * <em><a href="https://people.sc.fsu.edu/~burkardt/c_src/subset/subset.html">
101 * Reference:</a></em>
102 * Albert Nijenhuis, Herbert Wilf,
103 * Combinatorial Algorithms for Computers and Calculators,
104 * Second Edition,
105 * Academic Press, 1978,
106 * ISBN: 0-12-519260-6,
107 * LC: QA164.N54.
108 * </p>
109 *
110 *
111 * @see PartiallyMatchedCrossover
112 * @see SwapMutator
113 *
114 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
115 * @since 1.0
116 * @version 3.4
117 */
118 @XmlJavaTypeAdapter(PermutationChromosome.Model.Adapter.class)
119 public final class PermutationChromosome<T>
120 extends AbstractChromosome<EnumGene<T>>
121 implements Serializable
122 {
123 private static final long serialVersionUID = 2L;
124
125 private ISeq<T> _validAlleles;
126
127 // Private primary constructor.
128 private PermutationChromosome(
129 final ISeq<EnumGene<T>> genes,
130 final Boolean valid
131 ) {
132 super(genes);
133
134 assert !genes.isEmpty();
135 _validAlleles = genes.get(0).getValidAlleles();
136 _valid = valid;
137 }
138
139 /**
140 * Create a new {@code PermutationChromosome} from the given {@code genes}.
141 * If the given {@code genes} sequence contains duplicate entries, the
142 * created {@code PermutationChromosome} will be invalid
143 * ({@code ch.isValid() == false}).
144 *
145 * @param genes the enum genes the new chromosome consists of
146 * @throws NullPointerException if the given {@code genes} are null
147 * @throws IllegalArgumentException if the given {@code genes} sequence is
148 * empty
149 */
150 public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
151 this(genes, null);
152 }
153
154 /**
155 * Return the sequence of valid alleles of this chromosome.
156 *
157 * @return the sequence of valid alleles of this chromosome
158 */
159 public ISeq<T> getValidAlleles() {
160 return _validAlleles;
161 }
162
163 /**
164 * Check if this chromosome represents still a valid permutation (or subset)
165 * of the given valid alleles.
166 */
167 @Override
168 public boolean isValid() {
169 if (_valid == null) {
170 final byte[] check = bit.newArray(_validAlleles.length());
171 _valid = _genes.forAll(g -> !getAndSet(check, g.getAlleleIndex()));
172 }
173
174 return _valid;
175 }
176
177 /**
178 * Create a new, <em>random</em> chromosome.
179 */
180 @Override
181 public PermutationChromosome<T> newInstance() {
182 return of(_validAlleles, length());
183 }
184
185 @Override
186 public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
187 return new PermutationChromosome<>(genes);
188 }
189
190 @Override
191 public int hashCode() {
192 return Hash.of(getClass())
193 .and(super.hashCode())
194 .value();
195 }
196
197 @Override
198 public boolean equals(final Object obj) {
199 return Equality.of(this, obj).test(super::equals);
200 }
201
202 @Override
203 public String toString() {
204 return _genes.asList().stream()
205 .map(g -> g.getAllele().toString())
206 .collect(Collectors.joining("|"));
207 }
208
209 /**
210 * Create a new, random chromosome with the given valid alleles and the
211 * desired length.
212 * <p>
213 * The following example shows how to create a {@code PermutationChromosome}
214 * for encoding a sub-set problem (of a fixed {@code length}).
215 * <pre>{@code
216 * final ISeq<String> basicSet = ISeq.of("a", "b", "c", "d", "e", "f");
217 *
218 * // The chromosome has a length of 3 and will only contain values from the
219 * // given basic-set, with no duplicates.
220 * final PermutationChromosome<String> ch = PermutationChromosome.of(basicSet, 3);
221 * }</pre>
222 *
223 * @since 3.4
224 *
225 * @param <T> the allele type
226 * @param alleles the base-set of the valid alleles
227 * @param length the length of the created chromosomes
228 * @return a new chromosome with the given valid alleles and the desired
229 * length
230 * @throws IllegalArgumentException if {@code alleles.size() < length},
231 * {@code length <= 0} or {@code alleles.size()*length} will
232 * cause an integer overflow.
233 * @throws NullPointerException if one of the arguments is {@code null}
234 */
235 public static <T> PermutationChromosome<T> of(
236 final ISeq<? extends T> alleles,
237 final int length
238 ) {
239 require.positive(length);
240 if (length > alleles.size()) {
241 throw new IllegalArgumentException(format(
242 "The sub-set size must be be greater then the base-set: %d > %d",
243 length, alleles.size()
244 ));
245 }
246
247 final int[] subset = array.shuffle(base.subset(alleles.size(), length));
248 final ISeq<EnumGene<T>> genes = IntStream.of(subset)
249 .mapToObj(i -> EnumGene.<T>of(i, alleles))
250 .collect(ISeq.toISeq());
251
252 return new PermutationChromosome<>(genes, true);
253 }
254
255 /**
256 * Create a new, random chromosome with the given valid alleles.
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 sequence is empty.
262 */
263 public static <T> PermutationChromosome<T>
264 of(final ISeq<? extends T> alleles) {
265 return of(alleles, alleles.size());
266 }
267
268 /**
269 * Create a new, random chromosome with the given valid alleles.
270 *
271 * @since 2.0
272 *
273 * @param <T> the gene type of the chromosome
274 * @param alleles the valid alleles used for this permutation arrays.
275 * @return a new chromosome with the given alleles
276 * @throws IllegalArgumentException if the given allele array is empty.
277 * @throws NullPointerException if one of the alleles is {@code null}
278 */
279 @SafeVarargs
280 public static <T> PermutationChromosome<T> of(final T... alleles) {
281 return of(ISeq.of(alleles));
282 }
283
284 /**
285 * Create a integer permutation chromosome with the given length.
286 *
287 * @param length the chromosome length.
288 * @return a integer permutation chromosome with the given length.
289 * @throws IllegalArgumentException if {@code length <= 0}.
290 */
291 public static PermutationChromosome<Integer> ofInteger(final int length) {
292 return ofInteger(0, require.positive(length));
293 }
294
295 /**
296 * Create an integer permutation chromosome with the given range.
297 *
298 * @since 2.0
299 *
300 * @param start the start of the integer range (inclusively) of the returned
301 * chromosome.
302 * @param end the end of the integer range (exclusively) of the returned
303 * chromosome.
304 * @return a integer permutation chromosome with the given integer range
305 * values.
306 * @throws IllegalArgumentException if {@code start >= end} or
307 * {@code start <= 0}
308 */
309 public static PermutationChromosome<Integer>
310 ofInteger(final int start, final int end) {
311 if (end <= start) {
312 throw new IllegalArgumentException(format(
313 "end <= start: %d <= %d", end, start
314 ));
315 }
316
317 return ofInteger(IntRange.of(start, end), end - start);
318 }
319
320 /**
321 * Create an integer permutation chromosome with the given range and length
322 *
323 * @since 3.4
324 *
325 * @param range the value range
326 * @param length the chromosome length
327 * @return a new integer permutation chromosome
328 * @throws NullPointerException if the given {@code range} is {@code null}
329 * @throws IllegalArgumentException if
330 * {@code range.getMax() - range.getMin() < length},
331 * {@code length <= 0} or
332 * {@code (range.getMax() - range.getMin())*length} will cause an
333 * integer overflow.
334 */
335 public static PermutationChromosome<Integer>
336 ofInteger(final IntRange range, final int length) {
337 return of(
338 range.stream()
339 .mapToObj(i -> i)
340 .collect(ISeq.toISeq()),
341 length
342 );
343 }
344
345 /* *************************************************************************
346 * Java object serialization
347 * ************************************************************************/
348
349 private void writeObject(final ObjectOutputStream out)
350 throws IOException
351 {
352 out.defaultWriteObject();
353
354 out.writeObject(_validAlleles);
355 for (EnumGene<?> gene : _genes) {
356 out.writeInt(gene.getAlleleIndex());
357 }
358 }
359
360 @SuppressWarnings("unchecked")
361 private void readObject(final ObjectInputStream in)
362 throws IOException, ClassNotFoundException
363 {
364 in.defaultReadObject();
365
366 _validAlleles = (ISeq<T>)in.readObject();
367
368 final MSeq<EnumGene<T>> genes = MSeq.ofLength(_validAlleles.length());
369 for (int i = 0; i < _validAlleles.length(); ++i) {
370 genes.set(i, new EnumGene<>(in.readInt(), _validAlleles));
371 }
372
373 _genes = genes.toISeq();
374 }
375
376 /* *************************************************************************
377 * JAXB object serialization
378 * ************************************************************************/
379
380 @XmlRootElement(name = "permutation-chromosome")
381 @XmlType(name = "org.jenetics.PermutationChromosome")
382 @XmlAccessorType(XmlAccessType.FIELD)
383 @SuppressWarnings({"unchecked", "rawtypes"})
384 static final class Model {
385
386 @XmlAttribute
387 public int length;
388
389 @XmlElementWrapper(name = "valid-alleles")
390 @XmlElement(name = "allele")
391 public List<Object> alleles;
392
393 @XmlList
394 @XmlElement(name = "order")
395 public List<Integer> order;
396
397 public static final class Adapter
398 extends XmlAdapter<Model, PermutationChromosome> {
399 @Override
400 public Model marshal(final PermutationChromosome pc)
401 throws Exception {
402 final Model model = new Model();
403 model.length = pc.length();
404 model.alleles = pc.getValidAlleles()
405 .map(jaxb.Marshaller(pc.getValidAlleles().get(0)))
406 .asList();
407 model.order = ((Seq<EnumGene<?>>)pc.toSeq())
408 .map(EnumGene::getAlleleIndex)
409 .asList();
410
411 return model;
412 }
413
414 @Override
415 public PermutationChromosome unmarshal(final Model model)
416 throws Exception {
417 final ISeq alleles = ISeq.of(model.alleles)
418 .map(jaxb.Unmarshaller(model.alleles.get(0)));
419
420 return new PermutationChromosome(
421 ISeq.of(model.order).map(Gene(alleles))
422 );
423 }
424 }
425
426 private static Function<Integer, EnumGene<Object>>
427 Gene(final ISeq<Object> alleles) {
428 return value -> new EnumGene<>(value, alleles);
429 }
430 }
431 }
|