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