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