001/* 002 * Java Genetic Algorithm Library (jenetics-8.2.0). 003 * Copyright (c) 2007-2025 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 */ 020package io.jenetics; 021 022import static java.lang.Math.min; 023import static java.util.Objects.requireNonNull; 024import static io.jenetics.internal.util.Requires.probability; 025import static io.jenetics.internal.util.SerialIO.readBytes; 026import static io.jenetics.internal.util.SerialIO.readInt; 027import static io.jenetics.internal.util.SerialIO.writeBytes; 028import static io.jenetics.internal.util.SerialIO.writeInt; 029 030import java.io.DataInput; 031import java.io.DataOutput; 032import java.io.IOException; 033import java.io.InvalidObjectException; 034import java.io.ObjectInputStream; 035import java.io.Serial; 036import java.io.Serializable; 037import java.math.BigInteger; 038import java.util.BitSet; 039import java.util.function.Function; 040import java.util.stream.IntStream; 041 042import io.jenetics.internal.collection.BitArray; 043import 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 */ 065public 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 one's 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 one's 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 instanceof BitChromosome other && 472 _genes.equals(other._genes); 473 } 474 475 @Override 476 public String toString() { 477 return _genes.toByteString(); 478 } 479 480 481 /* ************************************************************************* 482 * Static factory methods. 483 **************************************************************************/ 484 485 /** 486 * Constructing a new BitChromosome with the given {@code length} and 487 * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are 488 * equally distributed with one-probability of {@code p}. 489 * 490 * @param length Length of the BitChromosome, number of bits. 491 * @param p Probability of the TRUEs in the BitChromosome. 492 * @return a new {@code BitChromosome} with the given parameter 493 * @throws NegativeArraySizeException if the {@code length} is smaller 494 * than one. 495 * @throws IllegalArgumentException if {@code p} is not a valid probability. 496 */ 497 public static BitChromosome of(final int length, final double p) { 498 return new BitChromosome(BitArray.ofLength(length, p), p); 499 } 500 501 /** 502 * Constructing a new BitChromosome with the given {@code length} and 503 * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are 504 * equally distributed with one-probability of 0.5. 505 * 506 * @param length Length of the BitChromosome. 507 * @return a new {@code BitChromosome} with the given parameter 508 * @throws NegativeArraySizeException if the {@code length} is smaller 509 * than one. 510 */ 511 public static BitChromosome of(final int length) { 512 return of(length, DEFAULT_PROBABILITY); 513 } 514 515 /** 516 * Create a new {@code BitChromosome} with the given parameters. 517 * 518 * @param length length of the BitChromosome. 519 * @param bits the bit-set which initializes the chromosome 520 * @param p Probability of the TRUEs in the BitChromosome. 521 * @return a new {@code BitChromosome} with the given parameter 522 * @throws NegativeArraySizeException if the {@code length} is smaller than 523 * one. 524 * @throws NullPointerException if the {@code bitSet} is {@code null}. 525 * @throws IllegalArgumentException if {@code p} is not a valid probability. 526 */ 527 public static BitChromosome of( 528 final BitSet bits, 529 final int length, 530 final double p 531 ) { 532 final var array = BitArray.ofLength(length); 533 for (int i = 0; i < length; ++i) { 534 if (bits.get(i)) { 535 array.set(i, true); 536 } 537 } 538 539 return new BitChromosome(array, probability(p)); 540 } 541 542 /** 543 * Create a new {@code BitChromosome} with the given parameters. The 544 * {@link #oneProbability()} of the chromosome is set to {@code 0.5}. 545 * 546 * @param length length of the BitChromosome. 547 * @param bits the bit-set which initializes the chromosome 548 * @return a new {@code BitChromosome} with the given parameter 549 * @throws NegativeArraySizeException if the {@code length} is smaller 550 * than one. 551 * @throws NullPointerException if the {@code bitSet} is 552 * {@code null}. 553 */ 554 public static BitChromosome of(final BitSet bits, final int length) { 555 return of(bits, length, DEFAULT_PROBABILITY); 556 } 557 558 /** 559 * Constructing a new BitChromosome from a given BitSet. The length of the 560 * constructed {@code BitChromosome} will be ({@link BitSet#length}). 561 * 562 * @see #of(BitSet, int, double) 563 * @see #of(BitSet, int) 564 * 565 * @param bits the bit-set which initializes the chromosome 566 * @return a new {@code BitChromosome} with the given parameter 567 * @throws NullPointerException if the {@code bitSet} is 568 * {@code null}. 569 */ 570 public static BitChromosome of(final BitSet bits) { 571 return of(bits, bits.length()); 572 } 573 574 /** 575 * Create a new {@code BitChromosome} from the given big integer value and 576 * ones' probability. 577 * 578 * @param value the value of the created {@code BitChromosome} 579 * @param length length of the BitChromosome 580 * @param p Probability of the TRUEs in the BitChromosome. 581 * @return a new {@code BitChromosome} with the given parameter 582 * @throws NullPointerException if the given {@code value} is {@code null}. 583 * @throws IllegalArgumentException if {@code p} is not a valid probability. 584 */ 585 public static BitChromosome of( 586 final BigInteger value, 587 final int length, 588 final double p 589 ) { 590 final var array = BitArray.of(value, length); 591 return new BitChromosome(array, probability(p)); 592 } 593 594 /** 595 * Create a new {@code BitChromosome} from the given big integer value and 596 * ones' probability. The {@link #oneProbability()} of the chromosome is set 597 * to {@code 0.5}. 598 * 599 * @since 7.0 600 * 601 * @param value the value of the created {@code BitChromosome} 602 * @param length length of the BitChromosome 603 * @return a new {@code BitChromosome} with the given parameter 604 * @throws NullPointerException if the given {@code value} is {@code null}. 605 * @throws IllegalArgumentException if {@code p} is not a valid probability. 606 */ 607 public static BitChromosome of( 608 final BigInteger value, 609 final int length 610 ) { 611 return of(value, length, DEFAULT_PROBABILITY); 612 } 613 614 615 /** 616 * Create a new {@code BitChromosome} from the given big integer value. The 617 * {@link #oneProbability()} of the chromosome is set to {@code 0.5}. 618 * 619 * @param value the value of the created {@code BitChromosome} 620 * @return a new {@code BitChromosome} with the given parameter 621 * @throws NullPointerException if the given {@code value} is {@code null}. 622 */ 623 public static BitChromosome of(final BigInteger value) { 624 final var array = BitArray.of(value); 625 return new BitChromosome(array, DEFAULT_PROBABILITY); 626 } 627 628 /** 629 * Create a new {@code BitChromosome} from the given character sequence 630 * containing '0' and '1'; as created with the {@link #toCanonicalString()} 631 * method. 632 * 633 * @param value the input string. 634 * @param length length of the BitChromosome 635 * @param p Probability of the TRUEs in the BitChromosome. 636 * @return a new {@code BitChromosome} with the given parameter 637 * @throws NullPointerException if the {@code value} is {@code null}. 638 * @throws IllegalArgumentException if the length of the character sequence 639 * is zero or contains other characters than '0' or '1'. 640 * @throws IllegalArgumentException if {@code p} is not a valid probability. 641 */ 642 public static BitChromosome of( 643 final CharSequence value, 644 final int length, 645 final double p 646 ) { 647 final var array = BitArray.of(value, length); 648 return new BitChromosome(array, probability(p)); 649 } 650 651 /** 652 * Create a new {@code BitChromosome} from the given character sequence 653 * containing '0' and '1'; as created with the {@link #toCanonicalString()} 654 * method. 655 * 656 * @param value the input string. 657 * @param p Probability of the TRUEs in the BitChromosome. 658 * @return a new {@code BitChromosome} with the given parameter 659 * @throws NullPointerException if the {@code value} is {@code null}. 660 * @throws IllegalArgumentException if the length of the character sequence 661 * is zero or contains other characters than '0' or '1'. 662 * @throws IllegalArgumentException if {@code p} is not a valid probability. 663 */ 664 public static BitChromosome of(final CharSequence value, final double p) { 665 return of(value, value.length(), p); 666 } 667 668 /** 669 * Create a new {@code BitChromosome} from the given character sequence 670 * containing '0' and '1'; as created with the {@link #toCanonicalString()} 671 * method. The {@link #oneProbability()} of the chromosome is set to 672 * {@code 0.5}. 673 * 674 * @param value the input string. 675 * @return a new {@code BitChromosome} with the given parameter 676 * @throws NullPointerException if the {@code value} is {@code null}. 677 * @throws IllegalArgumentException if the length of the character sequence 678 * is zero or contains other characters than '0' or '1'. 679 */ 680 public static BitChromosome of(final CharSequence value) { 681 return of(value, value.length(), DEFAULT_PROBABILITY); 682 } 683 684 685 /* ************************************************************************* 686 * Java object serialization 687 * ************************************************************************/ 688 689 @Serial 690 private Object writeReplace() { 691 return new SerialProxy(SerialProxy.BIT_CHROMOSOME, this); 692 } 693 694 @Serial 695 private void readObject(final ObjectInputStream stream) 696 throws InvalidObjectException 697 { 698 throw new InvalidObjectException("Serialization proxy required."); 699 } 700 701 void write(final DataOutput out) throws IOException { 702 writeBytes(toByteArray(), out); 703 writeInt(length(), out); 704 out.writeDouble(oneProbability()); 705 } 706 707 static BitChromosome read(final DataInput in) throws IOException { 708 final var bytes = readBytes(in); 709 final var length = readInt(in); 710 final var p = in.readDouble(); 711 final var genes = BitArray.of(bytes,0, length); 712 713 return new BitChromosome(genes, p); 714 } 715 716}