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.Math.min;
023 import static java.lang.String.format;
024 import static java.util.Objects.requireNonNull;
025 import static java.util.stream.Collectors.joining;
026
027 import java.io.IOException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.io.Serializable;
031 import java.math.BigInteger;
032 import java.util.BitSet;
033 import java.util.Iterator;
034 import java.util.ListIterator;
035 import java.util.stream.IntStream;
036
037 import javax.xml.bind.annotation.XmlAccessType;
038 import javax.xml.bind.annotation.XmlAccessorType;
039 import javax.xml.bind.annotation.XmlAttribute;
040 import javax.xml.bind.annotation.XmlRootElement;
041 import javax.xml.bind.annotation.XmlType;
042 import javax.xml.bind.annotation.XmlValue;
043 import javax.xml.bind.annotation.adapters.XmlAdapter;
044 import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;
045
046 import org.jenetics.internal.util.Equality;
047 import org.jenetics.internal.util.Hash;
048 import org.jenetics.internal.util.bit;
049 import org.jenetics.internal.util.require;
050
051 import org.jenetics.util.ISeq;
052
053 /**
054 * Implementation of the <i>classical</i> BitChromosome.
055 *
056 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
057 * @since 1.0
058 * @version 3.4
059 */
060 @XmlJavaTypeAdapter(BitChromosome.Model.Adapter.class)
061 public class BitChromosome extends Number
062 implements
063 Chromosome<BitGene>,
064 Comparable<BitChromosome>,
065 Serializable
066 {
067 private static final long serialVersionUID = 2L;
068
069
070 /**
071 * The ones probability of the randomly generated Chromosome.
072 */
073 protected double _p;
074
075 /**
076 * The length of the chromosomes (number of bits).
077 */
078 protected int _length;
079
080 /**
081 * The boolean array which holds the {@link BitGene}s.
082 */
083 protected byte[] _genes;
084
085 // Wraps the genes byte array into a Seq<BitGene>.
086 private transient BitGeneISeq _seq;
087
088 // Private primary constructor.
089 private BitChromosome(final byte[] bits, final int length, final double p) {
090 _genes = bits;
091 _length = length;
092 _p = p;
093 _seq = BitGeneMSeq.of(_genes, length).toISeq();
094 }
095
096 /**
097 * Create a new bit chromosome from the given bit (byte) array.
098 *
099 * @param bits the bit values of the new chromosome gene.
100 * @param start the initial (bit) index of the range to be copied, inclusive
101 * @param end the final (bit) index of the range to be copied, exclusive.
102 * (This index may lie outside the array.)
103 * @throws java.lang.ArrayIndexOutOfBoundsException if {@code start < 0} or
104 * {@code start > bits.length*8}
105 * @throws java.lang.IllegalArgumentException if {@code start > end}
106 * @throws java.lang.NullPointerException if the {@code bits} array is
107 * {@code null}.
108 */
109 public BitChromosome(final byte[] bits, final int start, final int end) {
110 this(
111 bit.copy(bits, start, end),
112 min(bits.length << 3, end) - start,
113 0.0
114 );
115 _p = (double)bit.count(_genes)/(double)_length;
116 }
117
118 /**
119 * Create a new {@code BitChromosome} from the given {@code byte} array.
120 * This is a shortcut for {@code new BitChromosome(bits, 0, bits.length*8)}.
121 *
122 * @param bits the {@code byte} array.
123 */
124 public BitChromosome(final byte[] bits) {
125 this(bits, 0, bits.length << 3);
126 }
127
128 private BitChromosome(final byte[] bits, final int length) {
129 this(
130 bits,
131 length == -1 ? bits.length*8 : length,
132 (double)bit.count(bits)/
133 (double)(length == -1 ? bits.length*8 : length)
134 );
135 }
136
137 private static byte[] toByteArray(final CharSequence value) {
138 final byte[] bytes = bit.newArray(value.length());
139 for (int i = value.length(); --i >= 0;) {
140 final char c = value.charAt(i);
141 if (c == '1') {
142 bit.set(bytes, i);
143 } else if (c != '0') {
144 throw new IllegalArgumentException(format(
145 "Illegal character '%s' at position %d", c, i
146 ));
147 }
148 }
149
150 return bytes;
151 }
152
153 private void rangeCheck(final int index) {
154 if (index < 0 || index >= _length) {
155 throw new IndexOutOfBoundsException(
156 "Index: " + index + ", Length: " + _length
157 );
158 }
159 }
160
161 /**
162 * Return the one probability of this chromosome.
163 *
164 * @since 3.9
165 *
166 * @return the one probability of this chromosome.
167 */
168 public double getOneProbability() {
169 return _p;
170 }
171
172 @Override
173 public BitGene getGene() {
174 assert _genes != null;
175 assert _genes.length > 0;
176 return BitGene.of(bit.get(_genes, 0));
177 }
178
179 /**
180 * Return the value of the first gene of this chromosome.
181 *
182 * @since 2.0
183 * @return the first value of this chromosome.
184 */
185 public boolean get() {
186 return bit.get(_genes, 0);
187 }
188
189 @Override
190 public BitGene getGene(final int index) {
191 rangeCheck(index);
192 assert _genes != null;
193 return BitGene.of(bit.get(_genes, index));
194 }
195
196 /**
197 * Return the value on the specified index.
198 *
199 * @since 2.0
200 * @param index the gene index
201 * @return the wanted gene value
202 * @throws IndexOutOfBoundsException if the index is out of range
203 * (index < 1 || index >= length()).
204 */
205 public boolean get(final int index) {
206 rangeCheck(index);
207 return bit.get(_genes, index);
208 }
209
210 @Override
211 public ISeq<BitGene> toSeq() {
212 return _seq;
213 }
214
215 @Override
216 public int length() {
217 return _length;
218 }
219
220 /**
221 * Returns the number of bits set to true in this {@code BitChromosome}.
222 *
223 * @return the number of bits set to true in this {@code BitChromosome}
224 */
225 public int bitCount() {
226 return bit.count(_genes);
227 }
228
229 @Override
230 public Iterator<BitGene> iterator() {
231 return _seq.iterator();
232 }
233
234 public ListIterator<BitGene> listIterator() {
235 return _seq.listIterator();
236 }
237
238 /**
239 * Return the long value this BitChromosome represents.
240 *
241 * @return long value this BitChromosome represents.
242 */
243 @Override
244 public int intValue() {
245 return (int)longValue();
246 }
247
248 /**
249 * Return the long value this BitChromosome represents.
250 *
251 * @return long value this BitChromosome represents.
252 */
253 @Override
254 public long longValue() {
255 return toBigInteger().longValue();
256 }
257
258 /**
259 * Return the float value this BitChromosome represents.
260 *
261 * @return float value this BitChromosome represents.
262 */
263 @Override
264 public float floatValue() {
265 return (float)longValue();
266 }
267
268 /**
269 * Return the double value this BitChromosome represents.
270 *
271 * @return double value this BitChromosome represents.
272 */
273 @Override
274 public double doubleValue() {
275 return longValue();
276 }
277
278 @Override
279 public boolean isValid() {
280 return true;
281 }
282
283 /**
284 * Return the {@code BigInteger} value this {@code BitChromosome} represents.
285 *
286 * @return {@code BigInteger} value this {@code BitChromosome} represents.
287 */
288 public BigInteger toBigInteger() {
289 return new BigInteger(_genes);
290 }
291
292 /**
293 * Returns the two's-complement binary representation of this
294 * large integer. The output array is in <i>big-endian</i>
295 * byte-order: the most significant byte is at the offset position.
296 *
297 * <p>Note: This representation is consistent with {@code java.lang.BigInteger
298 * } byte array representation and can be used for conversion
299 * between the two classes.</p>
300 *
301 * @param bytes the bytes to hold the binary representation
302 * (two's-complement) of this large integer.
303 * @return the number of bytes written.
304 * @throws IndexOutOfBoundsException
305 * if {@code bytes.length < (int)Math.ceil(length()/8.0)}
306 * @throws NullPointerException it the give array is {@code null}.
307 */
308 public int toByteArray(final byte[] bytes) {
309 if (bytes.length < _genes.length) {
310 throw new IndexOutOfBoundsException();
311 }
312
313 System.arraycopy(_genes, 0, bytes, 0, _genes.length);
314 return _genes.length;
315 }
316
317 /**
318 * @return a byte array which represents this {@code BitChromosome}. The
319 * length of the array is {@code (int)Math.ceil(length()/8.0)}.
320 *
321 * @see #toByteArray(byte[])
322 */
323 public byte[] toByteArray() {
324 final byte[] data = new byte[_genes.length];
325 toByteArray(data);
326 return data;
327 }
328
329 /**
330 * Return the corresponding BitSet of this BitChromosome.
331 *
332 * @return The corresponding BitSet of this BitChromosome.
333 */
334 public BitSet toBitSet() {
335 final BitSet set = new BitSet(length());
336 for (int i = 0, n = length(); i < n; ++i) {
337 set.set(i, getGene(i).getBit());
338 }
339 return set;
340 }
341
342 /**
343 * Return the indexes of the <i>ones</i> of this bit-chromosome as stream.
344 *
345 * @since 3.0
346 *
347 * @return the indexes of the <i>ones</i> of this bit-chromosome
348 */
349 public IntStream ones() {
350 return IntStream.range(0, length())
351 .filter(index -> bit.get(_genes, index));
352 }
353
354 /**
355 * Return the indexes of the <i>zeros</i> of this bit-chromosome as stream.
356 *
357 * @since 3.0
358 *
359 * @return the indexes of the <i>zeros</i> of this bit-chromosome
360 */
361 public IntStream zeros() {
362 return IntStream.range(0, length())
363 .filter(index -> !bit.get(_genes, index));
364 }
365
366 @Override
367 public BitChromosome newInstance(final ISeq<BitGene> genes) {
368 requireNonNull(genes, "Genes");
369 if (genes.isEmpty()) {
370 throw new IllegalArgumentException(
371 "The genes sequence must contain at least one gene."
372 );
373 }
374
375 final BitChromosome chromosome = new BitChromosome(
376 bit.newArray(genes.length()), genes.length()
377 );
378 int ones = 0;
379
380 if (genes instanceof BitGeneISeq) {
381 final BitGeneISeq iseq = (BitGeneISeq)genes;
382 iseq.copyTo(chromosome._genes);
383 ones = bit.count(chromosome._genes);
384 } else {
385 for (int i = genes.length(); --i >= 0;) {
386 if (genes.get(i).booleanValue()) {
387 bit.set(chromosome._genes, i);
388 ++ones;
389 }
390 }
391 }
392
393 chromosome._p = (double)ones/(double)genes.length();
394 return chromosome;
395 }
396
397 @Override
398 public BitChromosome newInstance() {
399 return of(_length, _p);
400 }
401
402 /**
403 * Return the BitChromosome as String. A TRUE is represented by a 1 and
404 * a FALSE by a 0. The returned string can be used to create a new
405 * chromosome with the {@link #of(CharSequence)} constructor.
406 *
407 * @return String representation (containing only '1' and '0') of the
408 * BitChromosome.
409 */
410 public String toCanonicalString() {
411 return toSeq().stream()
412 .map(g -> g.booleanValue() ? "1" : "0")
413 .collect(joining());
414 }
415
416 @Override
417 public int compareTo(final BitChromosome that) {
418 return toBigInteger().compareTo(that.toBigInteger());
419 }
420
421 /**
422 * Invert the ones and zeros of this bit chromosome.
423 *
424 * @return a new BitChromosome with inverted ones and zeros.
425 */
426 public BitChromosome invert() {
427 final byte[] data = _genes.clone();
428 bit.invert(data);
429 return new BitChromosome(data, _length, 1.0 - _p);
430 }
431
432 /**
433 * Construct a new BitChromosome with the given _length.
434 *
435 * @param length Length of the BitChromosome, number of bits.
436 * @param p Probability of the TRUEs in the BitChromosome.
437 * @return a new {@code BitChromosome} with the given parameter
438 * @throws NegativeArraySizeException if the {@code length} is smaller
439 * than one.
440 * @throws IllegalArgumentException if {@code p} is not a valid probability.
441 */
442 public static BitChromosome of(final int length, final double p) {
443 return new BitChromosome(bit.newArray(length, p), length, p);
444 }
445
446 /**
447 * Constructing a new BitChromosome with the given _length. The TRUEs and
448 * FALSE in the {@code Chromosome} are equally distributed.
449 *
450 * @param length Length of the BitChromosome.
451 * @return a new {@code BitChromosome} with the given parameter
452 * @throws NegativeArraySizeException if the {@code _length} is smaller
453 * than one.
454 */
455 public static BitChromosome of(final int length) {
456 return new BitChromosome(bit.newArray(length, 0.5), length, 0.5);
457 }
458
459 /**
460 * Create a new {@code BitChromosome} with the given parameters.
461 *
462 * @param length length of the BitChromosome.
463 * @param bits the bit-set which initializes the chromosome
464 * @return a new {@code BitChromosome} with the given parameter
465 * @throws NegativeArraySizeException if the {@code length} is smaller
466 * than one.
467 * @throws NullPointerException if the {@code bitSet} is
468 * {@code null}.
469 */
470 public static BitChromosome of(final BitSet bits, final int length) {
471 final byte[] bytes = bit.newArray(length);
472 for (int i = 0; i < length; ++i) {
473 if (bits.get(i)) {
474 bit.set(bytes, i);
475 }
476 }
477 final double p = (double)bit.count(bytes)/(double)length;
478
479 return new BitChromosome(bytes, length, p);
480 }
481
482 /**
483 * Create a new {@code BitChromosome} with the given parameters.
484 *
485 * @param length length of the BitChromosome.
486 * @param bits the bit-set which initializes the chromosome
487 * @param p Probability of the TRUEs in the BitChromosome.
488 * @return a new {@code BitChromosome} with the given parameter
489 * @throws NegativeArraySizeException if the {@code length} is smaller than
490 * one.
491 * @throws NullPointerException if the {@code bitSet} is {@code null}.
492 * @throws IllegalArgumentException if {@code p} is not a valid probability.
493 */
494 public static BitChromosome of(
495 final BitSet bits,
496 final int length,
497 final double p
498 ) {
499 final byte[] bytes = bit.newArray(length);
500 for (int i = 0; i < length; ++i) {
501 if (bits.get(i)) {
502 bit.set(bytes, i);
503 }
504 }
505
506 return new BitChromosome(bytes, length, require.probability(p));
507 }
508
509 /**
510 * Constructing a new BitChromosome from a given BitSet.
511 * The BitSet is copied while construction. The length of the constructed
512 * BitChromosome will be {@code bitSet.length()} ({@link BitSet#length}).
513 *
514 * @param bits the bit-set which initializes the chromosome
515 * @return a new {@code BitChromosome} with the given parameter
516 * @throws NullPointerException if the {@code bitSet} is
517 * {@code null}.
518 */
519 public static BitChromosome of(final BitSet bits) {
520 return new BitChromosome(bits.toByteArray(), -1);
521 }
522
523 /**
524 * Create a new {@code BitChromosome} from the given big integer value.
525 *
526 * @param value the value of the created {@code BitChromosome}
527 * @return a new {@code BitChromosome} with the given parameter
528 * @throws NullPointerException if the given {@code value} is {@code null}.
529 */
530 public static BitChromosome of(final BigInteger value) {
531 return new BitChromosome(value.toByteArray(), -1);
532 }
533
534 /**
535 * Create a new {@code BitChromosome} from the given big integer value and
536 * ones probability.
537 *
538 * @param value the value of the created {@code BitChromosome}
539 * @param p Probability of the TRUEs in the BitChromosome.
540 * @return a new {@code BitChromosome} with the given parameter
541 * @throws NullPointerException if the given {@code value} is {@code null}.
542 * @throws IllegalArgumentException if {@code p} is not a valid probability.
543 */
544 public static BitChromosome of(final BigInteger value, final double p) {
545 final byte[] bits = value.toByteArray();
546 return new BitChromosome(bits, bits.length*8, require.probability(p));
547 }
548
549 /**
550 * Create a new {@code BitChromosome} from the given character sequence
551 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
552 * method.
553 *
554 * @param value the input string.
555 * @return a new {@code BitChromosome} with the given parameter
556 * @throws NullPointerException if the {@code value} is {@code null}.
557 * @throws IllegalArgumentException if the length of the character sequence
558 * is zero or contains other characters than '0' or '1'.
559 */
560 public static BitChromosome of(final CharSequence value) {
561 return new BitChromosome(toByteArray(requireNonNull(value, "Input")), -1);
562 }
563
564 /**
565 * Create a new {@code BitChromosome} from the given character sequence
566 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
567 * method.
568 *
569 * @param value the input string.
570 * @param p Probability of the TRUEs in the BitChromosome.
571 * @return a new {@code BitChromosome} with the given parameter
572 * @throws NullPointerException if the {@code value} is {@code null}.
573 * @throws IllegalArgumentException if the length of the character sequence
574 * is zero or contains other characters than '0' or '1'.
575 * @throws IllegalArgumentException if {@code p} is not a valid probability.
576 */
577 public static BitChromosome of(final CharSequence value, final double p) {
578 final byte[] bits = toByteArray(requireNonNull(value, "Input"));
579 return new BitChromosome(bits, bits.length*8, require.probability(p));
580 }
581
582 /**
583 * Create a new {@code BitChromosome} from the given character sequence
584 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
585 * method.
586 *
587 * @param value the input string.
588 * @param length length of the BitChromosome
589 * @param p Probability of the TRUEs in the BitChromosome.
590 * @return a new {@code BitChromosome} with the given parameter
591 * @throws NullPointerException if the {@code value} is {@code null}.
592 * @throws IllegalArgumentException if the length of the character sequence
593 * is zero or contains other characters than '0' or '1'.
594 * @throws IllegalArgumentException if {@code p} is not a valid probability.
595 */
596 public static BitChromosome of(
597 final CharSequence value,
598 final int length,
599 final double p
600 ) {
601 final byte[] bits = toByteArray(requireNonNull(value, "Input"));
602 return new BitChromosome(bits, length, require.probability(p));
603 }
604
605 @Override
606 public int hashCode() {
607 return Hash.of(getClass()).and(_genes).value();
608 }
609
610 @Override
611 public boolean equals(final Object obj) {
612 return Equality.of(this, obj).test(c -> {
613 boolean equals = length() == c.length();
614 for (int i = 0, n = length(); equals && i < n; ++i) {
615 equals = getGene(i) == c.getGene(i);
616 }
617 return equals;
618 });
619 }
620
621 @Override
622 public String toString() {
623 return bit.toByteString(_genes);
624 }
625
626 /* *************************************************************************
627 * Java object serialization
628 * ************************************************************************/
629
630 private void writeObject(final ObjectOutputStream out)
631 throws IOException
632 {
633 out.defaultWriteObject();
634
635 out.writeInt(_length);
636 out.writeDouble(_p);
637 out.writeInt(_genes.length);
638 out.write(_genes);
639 }
640
641 private void readObject(final ObjectInputStream in)
642 throws IOException, ClassNotFoundException
643 {
644 in.defaultReadObject();
645
646 _length = in.readInt();
647 _p = in.readDouble();
648
649 final int bytes = in.readInt();
650 _genes = new byte[bytes];
651 in.readFully(_genes);
652
653 _seq = BitGeneISeq.of(_genes, _length);
654 }
655
656 /* *************************************************************************
657 * JAXB object serialization
658 * ************************************************************************/
659
660 @XmlRootElement(name = "bit-chromosome")
661 @XmlType(name = "org.jenetics.BitChromosome")
662 @XmlAccessorType(XmlAccessType.FIELD)
663 final static class Model {
664
665 @XmlAttribute(name = "length", required = true)
666 public int length;
667
668 @XmlAttribute(name = "ones-probability", required = true)
669 public double probability;
670
671 @XmlValue
672 public String value;
673
674 public final static class Adapter
675 extends XmlAdapter<Model, BitChromosome>
676 {
677 @Override
678 public Model marshal(final BitChromosome chromosome) {
679 final Model model = new Model();
680 model.length = chromosome._length;
681 model.probability = chromosome._p;
682 model.value = chromosome.toCanonicalString();
683 return model;
684 }
685
686 @Override
687 public BitChromosome unmarshal(final Model model) {
688 return new BitChromosome(
689 toByteArray(model.value),
690 model.length,
691 model.probability
692 );
693 }
694 }
695 }
696
697 }
|