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