001/* 002 * Java Genetic Algorithm Library (jenetics-8.1.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 */ 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 == 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}