001 /*
002 * Java Genetic Algorithm Library (jenetics-5.1.0).
003 * Copyright (c) 2007-2019 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.Iterator;
040 import java.util.ListIterator;
041 import java.util.stream.IntStream;
042
043 import io.jenetics.internal.util.bit;
044 import io.jenetics.internal.util.require;
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 5.0
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 int _length;
077
078 /**
079 * The boolean array which holds the {@link BitGene}s.
080 */
081 protected byte[] _genes;
082
083 // Wraps the genes byte array into a Seq<BitGene>.
084 private 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 bit.copy(bits, start, end),
110 min(bits.length << 3, end) - start,
111 0.0
112 );
113 _p = (double)bit.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)bit.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 = bit.newArray(value.length());
137 for (int i = value.length(); --i >= 0;) {
138 final char c = value.charAt(i);
139 if (c == '1') {
140 bit.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 3.9
163 *
164 * @return the one probability of this chromosome.
165 */
166 public double getOneProbability() {
167 return _p;
168 }
169
170 @Override
171 public BitGene getGene() {
172 assert _genes != null;
173 assert _genes.length > 0;
174 return BitGene.of(bit.get(_genes, 0));
175 }
176
177 /**
178 * Return the value of the first gene of this chromosome.
179 *
180 * @since 4.2
181 *
182 * @return the first value of this chromosome.
183 */
184 public boolean booleanValue() {
185 return bit.get(_genes, 0);
186 }
187
188 @Override
189 public BitGene getGene(final int index) {
190 rangeCheck(index);
191 assert _genes != null;
192 return BitGene.of(bit.get(_genes, index));
193 }
194
195 /**
196 * Return the value on the specified index.
197 *
198 * @since 4.2
199 *
200 * @param index the gene index
201 * @return the wanted gene value
202 * @throws IndexOutOfBoundsException if the index is out of range
203 * (index < 1 || index >= length()).
204 */
205 public boolean booleanValue(final int index) {
206 rangeCheck(index);
207 return bit.get(_genes, index);
208 }
209
210 @Override
211 public ISeq<BitGene> toSeq() {
212 return _seq;
213 }
214
215 @Override
216 public int length() {
217 return _length;
218 }
219
220 /**
221 * Returns the number of bits set to true in this {@code BitChromosome}.
222 *
223 * @return the number of bits set to true in this {@code BitChromosome}
224 */
225 public int bitCount() {
226 return bit.count(_genes);
227 }
228
229 @Override
230 public Iterator<BitGene> iterator() {
231 return _seq.iterator();
232 }
233
234 /**
235 * Return a list iterator over the bit-genes of this chromosome.
236 *
237 * @return a list iterator over the bit-genes of this chromosome
238 */
239 public ListIterator<BitGene> listIterator() {
240 return _seq.listIterator();
241 }
242
243 /**
244 * Return the long value this BitChromosome represents.
245 *
246 * @return long value this BitChromosome represents.
247 */
248 @Override
249 public int intValue() {
250 return (int)longValue();
251 }
252
253 /**
254 * Return the long value this BitChromosome represents.
255 *
256 * @return long value this BitChromosome represents.
257 */
258 @Override
259 public long longValue() {
260 return toBigInteger().longValue();
261 }
262
263 /**
264 * Return the float value this BitChromosome represents.
265 *
266 * @return float value this BitChromosome represents.
267 */
268 @Override
269 public float floatValue() {
270 return (float)longValue();
271 }
272
273 /**
274 * Return the double value this BitChromosome represents.
275 *
276 * @return double value this BitChromosome represents.
277 */
278 @Override
279 public double doubleValue() {
280 return longValue();
281 }
282
283 /**
284 * Return always {@code true}.
285 *
286 * @return {@code true}, always
287 */
288 @Override
289 public boolean isValid() {
290 return true;
291 }
292
293 /**
294 * Return the {@code BigInteger} value this {@code BitChromosome} represents.
295 *
296 * @return {@code BigInteger} value this {@code BitChromosome} represents.
297 */
298 public BigInteger toBigInteger() {
299 return new BigInteger(_genes);
300 }
301
302 /**
303 * Returns the two's-complement binary representation of this
304 * large integer. The output array is in <i>big-endian</i>
305 * byte-order: the most significant byte is at the offset position.
306 *
307 * <p>Note: This representation is consistent with {@code java.lang.BigInteger
308 * } byte array representation and can be used for conversion
309 * between the two classes.</p>
310 *
311 * @param bytes the bytes to hold the binary representation
312 * (two's-complement) of this large integer.
313 * @return the number of bytes written.
314 * @throws IndexOutOfBoundsException
315 * if {@code bytes.length < (int)Math.ceil(length()/8.0)}
316 * @throws NullPointerException it the give array is {@code null}.
317 */
318 public int toByteArray(final byte[] bytes) {
319 if (bytes.length < _genes.length) {
320 throw new IndexOutOfBoundsException();
321 }
322
323 System.arraycopy(_genes, 0, bytes, 0, _genes.length);
324 return _genes.length;
325 }
326
327 /**
328 * @return a byte array which represents this {@code BitChromosome}. The
329 * length of the array is {@code (int)Math.ceil(length()/8.0)}.
330 *
331 * @see #toByteArray(byte[])
332 */
333 public byte[] toByteArray() {
334 final byte[] data = new byte[_genes.length];
335 toByteArray(data);
336 return data;
337 }
338
339 /**
340 * Return the corresponding BitSet of this BitChromosome.
341 *
342 * @return The corresponding BitSet of this BitChromosome.
343 */
344 public BitSet toBitSet() {
345 final BitSet set = new BitSet(length());
346 for (int i = 0, n = length(); i < n; ++i) {
347 set.set(i, getGene(i).getBit());
348 }
349 return set;
350 }
351
352 /**
353 * Return the indexes of the <i>ones</i> of this bit-chromosome as stream.
354 *
355 * @since 3.0
356 *
357 * @return the indexes of the <i>ones</i> of this bit-chromosome
358 */
359 public IntStream ones() {
360 return IntStream.range(0, length())
361 .filter(index -> bit.get(_genes, index));
362 }
363
364 /**
365 * Return the indexes of the <i>zeros</i> of this bit-chromosome as stream.
366 *
367 * @since 3.0
368 *
369 * @return the indexes of the <i>zeros</i> of this bit-chromosome
370 */
371 public IntStream zeros() {
372 return IntStream.range(0, length())
373 .filter(index -> !bit.get(_genes, index));
374 }
375
376 @Override
377 public BitChromosome newInstance(final ISeq<BitGene> genes) {
378 requireNonNull(genes, "Genes");
379 if (genes.isEmpty()) {
380 throw new IllegalArgumentException(
381 "The genes sequence must contain at least one gene."
382 );
383 }
384
385 final BitChromosome chromosome = new BitChromosome(
386 bit.newArray(genes.length()), genes.length()
387 );
388 int ones = 0;
389
390 if (genes instanceof BitGeneISeq) {
391 final BitGeneISeq iseq = (BitGeneISeq)genes;
392 iseq.copyTo(chromosome._genes);
393 ones = bit.count(chromosome._genes);
394 } else {
395 for (int i = genes.length(); --i >= 0;) {
396 if (genes.get(i).booleanValue()) {
397 bit.set(chromosome._genes, i);
398 ++ones;
399 }
400 }
401 }
402
403 chromosome._p = (double)ones/(double)genes.length();
404 return chromosome;
405 }
406
407 @Override
408 public BitChromosome newInstance() {
409 return of(_length, _p);
410 }
411
412 /**
413 * Return the BitChromosome as String. A TRUE is represented by a 1 and
414 * a FALSE by a 0. The returned string can be used to create a new
415 * chromosome with the {@link #of(CharSequence)} constructor.
416 *
417 * @return String representation (containing only '1' and '0') of the
418 * BitChromosome.
419 */
420 public String toCanonicalString() {
421 return stream()
422 .map(g -> g.booleanValue() ? "1" : "0")
423 .collect(joining());
424 }
425
426 @Override
427 public int compareTo(final BitChromosome that) {
428 return toBigInteger().compareTo(that.toBigInteger());
429 }
430
431 /**
432 * Invert the ones and zeros of this bit chromosome.
433 *
434 * @return a new BitChromosome with inverted ones and zeros.
435 */
436 public BitChromosome invert() {
437 final byte[] data = _genes.clone();
438 bit.invert(data);
439 return new BitChromosome(data, _length, 1.0 - _p);
440 }
441
442 /**
443 * Construct a new BitChromosome with the given _length.
444 *
445 * @param length Length of the BitChromosome, number of bits.
446 * @param p Probability of the TRUEs in 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 * @throws IllegalArgumentException if {@code p} is not a valid probability.
451 */
452 public static BitChromosome of(final int length, final double p) {
453 return new BitChromosome(bit.newArray(length, p), length, p);
454 }
455
456 /**
457 * Constructing a new BitChromosome with the given _length. The TRUEs and
458 * FALSE in the {@code Chromosome} are equally distributed.
459 *
460 * @param length Length of the BitChromosome.
461 * @return a new {@code BitChromosome} with the given parameter
462 * @throws NegativeArraySizeException if the {@code _length} is smaller
463 * than one.
464 */
465 public static BitChromosome of(final int length) {
466 return new BitChromosome(bit.newArray(length, 0.5), length, 0.5);
467 }
468
469 /**
470 * Create a new {@code BitChromosome} with the given parameters.
471 *
472 * @param length length of the BitChromosome.
473 * @param bits the bit-set which initializes the chromosome
474 * @return a new {@code BitChromosome} with the given parameter
475 * @throws NegativeArraySizeException if the {@code length} is smaller
476 * than one.
477 * @throws NullPointerException if the {@code bitSet} is
478 * {@code null}.
479 */
480 public static BitChromosome of(final BitSet bits, final int length) {
481 final byte[] bytes = bit.newArray(length);
482 for (int i = 0; i < length; ++i) {
483 if (bits.get(i)) {
484 bit.set(bytes, i);
485 }
486 }
487 final double p = (double)bit.count(bytes)/(double)length;
488
489 return new BitChromosome(bytes, length, p);
490 }
491
492 /**
493 * Create a new {@code BitChromosome} with the given parameters.
494 *
495 * @param length length of the BitChromosome.
496 * @param bits the bit-set which initializes the chromosome
497 * @param p Probability of the TRUEs in the BitChromosome.
498 * @return a new {@code BitChromosome} with the given parameter
499 * @throws NegativeArraySizeException if the {@code length} is smaller than
500 * one.
501 * @throws NullPointerException if the {@code bitSet} is {@code null}.
502 * @throws IllegalArgumentException if {@code p} is not a valid probability.
503 */
504 public static BitChromosome of(
505 final BitSet bits,
506 final int length,
507 final double p
508 ) {
509 final byte[] bytes = bit.newArray(length);
510 for (int i = 0; i < length; ++i) {
511 if (bits.get(i)) {
512 bit.set(bytes, i);
513 }
514 }
515
516 return new BitChromosome(bytes, length, require.probability(p));
517 }
518
519 /**
520 * Constructing a new BitChromosome from a given BitSet.
521 * The BitSet is copied while construction. The length of the constructed
522 * BitChromosome will be {@code bitSet.length()} ({@link BitSet#length}).
523 *
524 * @param bits the bit-set which initializes the chromosome
525 * @return a new {@code BitChromosome} with the given parameter
526 * @throws NullPointerException if the {@code bitSet} is
527 * {@code null}.
528 */
529 public static BitChromosome of(final BitSet bits) {
530 return new BitChromosome(bits.toByteArray(), -1);
531 }
532
533 /**
534 * Create a new {@code BitChromosome} from the given big integer value.
535 *
536 * @param value the value of the created {@code BitChromosome}
537 * @return a new {@code BitChromosome} with the given parameter
538 * @throws NullPointerException if the given {@code value} is {@code null}.
539 */
540 public static BitChromosome of(final BigInteger value) {
541 return new BitChromosome(value.toByteArray(), -1);
542 }
543
544 /**
545 * Create a new {@code BitChromosome} from the given big integer value and
546 * ones probability.
547 *
548 * @param value the value of the created {@code 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 given {@code value} is {@code null}.
552 * @throws IllegalArgumentException if {@code p} is not a valid probability.
553 */
554 public static BitChromosome of(final BigInteger value, final double p) {
555 final byte[] bits = value.toByteArray();
556 return new BitChromosome(bits, bits.length*8, require.probability(p));
557 }
558
559 /**
560 * Create a new {@code BitChromosome} from the given character sequence
561 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
562 * method.
563 *
564 * @param value the input string.
565 * @return a new {@code BitChromosome} with the given parameter
566 * @throws NullPointerException if the {@code value} is {@code null}.
567 * @throws IllegalArgumentException if the length of the character sequence
568 * is zero or contains other characters than '0' or '1'.
569 */
570 public static BitChromosome of(final CharSequence value) {
571 return new BitChromosome(toByteArray(requireNonNull(value, "Input")), -1);
572 }
573
574 /**
575 * Create a new {@code BitChromosome} from the given character sequence
576 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
577 * method.
578 *
579 * @param value the input string.
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 {@code value} is {@code null}.
583 * @throws IllegalArgumentException if the length of the character sequence
584 * is zero or contains other characters than '0' or '1'.
585 * @throws IllegalArgumentException if {@code p} is not a valid probability.
586 */
587 public static BitChromosome of(final CharSequence value, final double p) {
588 final byte[] bits = toByteArray(requireNonNull(value, "Input"));
589 return new BitChromosome(bits, bits.length*8, require.probability(p));
590 }
591
592 /**
593 * Create a new {@code BitChromosome} from the given character sequence
594 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
595 * method.
596 *
597 * @param value the input string.
598 * @param length length of the BitChromosome
599 * @param p Probability of the TRUEs in the BitChromosome.
600 * @return a new {@code BitChromosome} with the given parameter
601 * @throws NullPointerException if the {@code value} is {@code null}.
602 * @throws IllegalArgumentException if the length of the character sequence
603 * is zero or contains other characters than '0' or '1'.
604 * @throws IllegalArgumentException if {@code p} is not a valid probability.
605 */
606 public static BitChromosome of(
607 final CharSequence value,
608 final int length,
609 final double p
610 ) {
611 final byte[] bits = toByteArray(requireNonNull(value, "Input"));
612 return new BitChromosome(bits, length, require.probability(p));
613 }
614
615 @Override
616 public int hashCode() {
617 return hash(_genes, hash(getClass()));
618 }
619
620 @Override
621 public boolean equals(final Object obj) {
622 return obj == this ||
623 obj != null &&
624 getClass() == obj.getClass() &&
625 length() == ((BitChromosome)obj).length() &&
626 Arrays.equals(_genes, ((BitChromosome)obj)._genes);
627 }
628
629 @Override
630 public String toString() {
631 return bit.toByteString(_genes);
632 }
633
634
635 /* *************************************************************************
636 * Java object serialization
637 * ************************************************************************/
638
639 private Object writeReplace() {
640 return new Serial(Serial.BIT_CHROMOSOME, this);
641 }
642
643 private void readObject(final ObjectInputStream stream)
644 throws InvalidObjectException
645 {
646 throw new InvalidObjectException("Serialization proxy required.");
647 }
648
649 void write(final DataOutput out) throws IOException {
650 writeInt(_length, out);
651 out.writeDouble(_p);
652 writeInt(_genes.length, out);
653 out.write(_genes);
654 }
655
656 static BitChromosome read(final DataInput in) throws IOException {
657 final int length = readInt(in);
658 final double p = in.readDouble();
659 final byte[] genes = new byte[readInt(in)];
660 in.readFully(genes);
661
662 return new BitChromosome(genes, length, p);
663 }
664
665 }
|