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