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