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