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