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