001/* 002 * Java Genetic Algorithm Library (jenetics-7.0.0). 003 * Copyright (c) 2007-2022 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 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 * Invert the ones and zeros of this bit chromosome. 368 * 369 * @return a new BitChromosome with inverted ones and zeros. 370 */ 371 public BitChromosome invert() { 372 final var array = _genes.copy(); 373 array.invert(); 374 return new BitChromosome(array, 1.0 - _p); 375 } 376 377 @Override 378 public int hashCode() { 379 return _genes.hashCode(); 380 } 381 382 @Override 383 public boolean equals(final Object obj) { 384 return obj == this || 385 obj instanceof BitChromosome other && 386 _genes.equals(other._genes); 387 } 388 389 @Override 390 public String toString() { 391 return _genes.toByteString(); 392 } 393 394 395 /* ************************************************************************* 396 * Static factory methods. 397 **************************************************************************/ 398 399 /** 400 * Constructing a new BitChromosome with the given {@code length} and 401 * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are 402 * equally distributed with one-probability of {@code p}. 403 * 404 * @param length Length of the BitChromosome, number of bits. 405 * @param p Probability of the TRUEs in the BitChromosome. 406 * @return a new {@code BitChromosome} with the given parameter 407 * @throws NegativeArraySizeException if the {@code length} is smaller 408 * than one. 409 * @throws IllegalArgumentException if {@code p} is not a valid probability. 410 */ 411 public static BitChromosome of(final int length, final double p) { 412 return new BitChromosome(BitArray.ofLength(length, p), p); 413 } 414 415 /** 416 * Constructing a new BitChromosome with the given {@code length} and 417 * randomly set bits. The TRUEs and FALSE in the {@code Chromosome} are 418 * equally distributed with one-probability of 0.5. 419 * 420 * @param length Length of the BitChromosome. 421 * @return a new {@code BitChromosome} with the given parameter 422 * @throws NegativeArraySizeException if the {@code length} is smaller 423 * than one. 424 */ 425 public static BitChromosome of(final int length) { 426 return of(length, DEFAULT_PROBABILITY); 427 } 428 429 /** 430 * Create a new {@code BitChromosome} with the given parameters. 431 * 432 * @param length length of the BitChromosome. 433 * @param bits the bit-set which initializes the chromosome 434 * @param p Probability of the TRUEs in the BitChromosome. 435 * @return a new {@code BitChromosome} with the given parameter 436 * @throws NegativeArraySizeException if the {@code length} is smaller than 437 * one. 438 * @throws NullPointerException if the {@code bitSet} is {@code null}. 439 * @throws IllegalArgumentException if {@code p} is not a valid probability. 440 */ 441 public static BitChromosome of( 442 final BitSet bits, 443 final int length, 444 final double p 445 ) { 446 final var array = BitArray.ofLength(length); 447 for (int i = 0; i < length; ++i) { 448 if (bits.get(i)) { 449 array.set(i, true); 450 } 451 } 452 453 return new BitChromosome(array, probability(p)); 454 } 455 456 /** 457 * Create a new {@code BitChromosome} with the given parameters. The 458 * {@link #oneProbability()} of the chromosome is set to {@code 0.5}. 459 * 460 * @param length length of the BitChromosome. 461 * @param bits the bit-set which initializes the chromosome 462 * @return a new {@code BitChromosome} with the given parameter 463 * @throws NegativeArraySizeException if the {@code length} is smaller 464 * than one. 465 * @throws NullPointerException if the {@code bitSet} is 466 * {@code null}. 467 */ 468 public static BitChromosome of(final BitSet bits, final int length) { 469 return of(bits, length, DEFAULT_PROBABILITY); 470 } 471 472 /** 473 * Constructing a new BitChromosome from a given BitSet. The length of the 474 * constructed {@code BitChromosome} will be ({@link BitSet#length}). 475 * 476 * @see #of(BitSet, int, double) 477 * @see #of(BitSet, int) 478 * 479 * @param bits the bit-set which initializes the chromosome 480 * @return a new {@code BitChromosome} with the given parameter 481 * @throws NullPointerException if the {@code bitSet} is 482 * {@code null}. 483 */ 484 public static BitChromosome of(final BitSet bits) { 485 return of(bits, bits.length()); 486 } 487 488 /** 489 * Create a new {@code BitChromosome} from the given big integer value and 490 * ones probability. 491 * 492 * @param value the value of the created {@code BitChromosome} 493 * @param length length of the BitChromosome 494 * @param p Probability of the TRUEs in the BitChromosome. 495 * @return a new {@code BitChromosome} with the given parameter 496 * @throws NullPointerException if the given {@code value} is {@code null}. 497 * @throws IllegalArgumentException if {@code p} is not a valid probability. 498 */ 499 public static BitChromosome of( 500 final BigInteger value, 501 final int length, 502 final double p 503 ) { 504 final var array = BitArray.of(value, length); 505 return new BitChromosome(array, probability(p)); 506 } 507 508 /** 509 * Create a new {@code BitChromosome} from the given big integer value and 510 * ones probability. The {@link #oneProbability()} of the chromosome is set 511 * to {@code 0.5}. 512 * 513 * @since 7.0 514 * 515 * @param value the value of the created {@code BitChromosome} 516 * @param length length of the BitChromosome 517 * @return a new {@code BitChromosome} with the given parameter 518 * @throws NullPointerException if the given {@code value} is {@code null}. 519 * @throws IllegalArgumentException if {@code p} is not a valid probability. 520 */ 521 public static BitChromosome of( 522 final BigInteger value, 523 final int length 524 ) { 525 return of(value, length, DEFAULT_PROBABILITY); 526 } 527 528 529 /** 530 * Create a new {@code BitChromosome} from the given big integer value. The 531 * {@link #oneProbability()} of the chromosome is set to {@code 0.5}. 532 * 533 * @param value the value of the created {@code BitChromosome} 534 * @return a new {@code BitChromosome} with the given parameter 535 * @throws NullPointerException if the given {@code value} is {@code null}. 536 */ 537 public static BitChromosome of(final BigInteger value) { 538 final var array = BitArray.of(value); 539 return new BitChromosome(array, DEFAULT_PROBABILITY); 540 } 541 542 /** 543 * Create a new {@code BitChromosome} from the given character sequence 544 * containing '0' and '1'; as created with the {@link #toCanonicalString()} 545 * method. 546 * 547 * @param value the input string. 548 * @param length length of the BitChromosome 549 * @param p Probability of the TRUEs in the BitChromosome. 550 * @return a new {@code BitChromosome} with the given parameter 551 * @throws NullPointerException if the {@code value} is {@code null}. 552 * @throws IllegalArgumentException if the length of the character sequence 553 * is zero or contains other characters than '0' or '1'. 554 * @throws IllegalArgumentException if {@code p} is not a valid probability. 555 */ 556 public static BitChromosome of( 557 final CharSequence value, 558 final int length, 559 final double p 560 ) { 561 final var array = BitArray.of(value, length); 562 return new BitChromosome(array, probability(p)); 563 } 564 565 /** 566 * Create a new {@code BitChromosome} from the given character sequence 567 * containing '0' and '1'; as created with the {@link #toCanonicalString()} 568 * method. 569 * 570 * @param value the input string. 571 * @param p Probability of the TRUEs in the BitChromosome. 572 * @return a new {@code BitChromosome} with the given parameter 573 * @throws NullPointerException if the {@code value} is {@code null}. 574 * @throws IllegalArgumentException if the length of the character sequence 575 * is zero or contains other characters than '0' or '1'. 576 * @throws IllegalArgumentException if {@code p} is not a valid probability. 577 */ 578 public static BitChromosome of(final CharSequence value, final double p) { 579 return of(value, value.length(), 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. The {@link #oneProbability()} of the chromosome is set to 586 * {@code 0.5}. 587 * 588 * @param value the input string. 589 * @return a new {@code BitChromosome} with the given parameter 590 * @throws NullPointerException if the {@code value} is {@code null}. 591 * @throws IllegalArgumentException if the length of the character sequence 592 * is zero or contains other characters than '0' or '1'. 593 */ 594 public static BitChromosome of(final CharSequence value) { 595 return of(value, value.length(), DEFAULT_PROBABILITY); 596 } 597 598 599 /* ************************************************************************* 600 * Java object serialization 601 * ************************************************************************/ 602 603 @Serial 604 private Object writeReplace() { 605 return new SerialProxy(SerialProxy.BIT_CHROMOSOME, this); 606 } 607 608 @Serial 609 private void readObject(final ObjectInputStream stream) 610 throws InvalidObjectException 611 { 612 throw new InvalidObjectException("Serialization proxy required."); 613 } 614 615 void write(final DataOutput out) throws IOException { 616 writeBytes(toByteArray(), out); 617 writeInt(length(), out); 618 out.writeDouble(oneProbability()); 619 } 620 621 static BitChromosome read(final DataInput in) throws IOException { 622 final var bytes = readBytes(in); 623 final var length = readInt(in); 624 final var p = in.readDouble(); 625 final var genes = BitArray.of(bytes,0, length); 626 627 return new BitChromosome(genes, p); 628 } 629 630}