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