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