001 /*
002 * Java Genetic Algorithm Library (jenetics-1.5.0).
003 * Copyright (c) 2007-2013 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.String.format;
023 import static java.util.Objects.requireNonNull;
024 import static org.jenetics.util.object.checkProbability;
025 import static org.jenetics.util.object.hashCodeOf;
026
027 import java.io.IOException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.util.BitSet;
031 import java.util.Iterator;
032 import java.util.ListIterator;
033
034 import javolution.text.Text;
035 import javolution.xml.XMLFormat;
036 import javolution.xml.XMLSerializable;
037 import javolution.xml.stream.XMLStreamException;
038
039 import org.jscience.mathematics.number.LargeInteger;
040 import org.jscience.mathematics.number.Number;
041
042 import org.jenetics.util.ISeq;
043 import org.jenetics.util.bit;
044
045 /**
046 * Implementation of the <i>classical</i> BitChromosome.
047 *
048 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
049 * @since 1.0
050 * @version 1.5 — <em>$Date: 2013-12-05 $</em>
051 */
052 public class BitChromosome extends Number<BitChromosome>
053 implements
054 Chromosome<BitGene>,
055 XMLSerializable
056 {
057 private static final long serialVersionUID = 1L;
058
059
060 /**
061 * The one's probability of the randomly generated Chromosome.
062 */
063 protected double _p;
064
065 /**
066 * The length of the chromosomes (number of bits).
067 */
068 protected int _length;
069
070 /**
071 * The boolean array which holds the {@link BitGene}s.
072 */
073 protected byte[] _genes;
074 private transient BitGeneArray _seq;
075
076
077 private BitChromosome(final byte[] bits, final int length, final double p) {
078 if (bits.length != bit.toByteLength(length)) {
079 throw new IllegalArgumentException(String.format(
080 "The byte array must has at least a length of " +
081 "%d to contain %d bits.",
082 bit.toByteLength(length), length
083 ));
084 }
085
086 _length = length;
087 _p = checkProbability(p);
088 _genes = bits;
089 _seq = new BitGeneArray(_genes, 0, _length);
090
091 }
092
093 private BitChromosome(final byte[] bits, final int length) {
094 this(
095 bits,
096 length == -1 ? bits.length*8 : length,
097 (double)bit.count(bits)/
098 (double)(length == -1 ? bits.length*8 : length)
099 );
100 }
101
102 /**
103 * Create a new {@code BitChromosome} from the given {@code byte} array.
104 *
105 * @param bits the {@code byte} array.
106 */
107 public BitChromosome(final byte[] bits) {
108 this(bits.clone(), bits.length*8);
109 }
110
111 /**
112 * Construct a new BitChromosome with the given _length.
113 *
114 * @param length Length of the BitChromosome, number of bits.
115 * @param p Probability of the TRUEs in the BitChromosome.
116 * @throws NegativeArraySizeException if the {@code length} is smaller
117 * than one.
118 * @throws IllegalArgumentException if {@code p} is not a valid probability.
119 */
120 public BitChromosome(final int length, final double p) {
121 this(bit.newArray(length, p), length, p);
122 }
123
124 /**
125 * Constructing a new BitChromosome with the given _length. The TRUEs and
126 * FALSE in the {@code Chromosome} are equally distributed.
127 *
128 * @param length Length of the BitChromosome.
129 * @throws NegativeArraySizeException if the {@code _length} is smaller
130 * than one.
131 */
132 public BitChromosome(final int length) {
133 this(length, 0.5);
134 }
135
136 /**
137 * @param length Length of the BitChromosome.
138 * @param bits the bit-set which initializes the chromosome
139 * @throws NegativeArraySizeException if the {@code length} is smaller
140 * than one.
141 * @throws NullPointerException if the {@code bitSet} is
142 * {@code null}.
143 */
144 public BitChromosome(final int length, final BitSet bits) {
145 this(toByteArray(requireNonNull(bits, "BitSet"), length));
146 }
147
148 private static byte[] toByteArray(final BitSet bits, final int length) {
149 final byte[] bytes = bit.newArray(length);
150 for (int i = 0; i < length; ++i) {
151 if (bits.get(i)) {
152 bit.set(bytes, i);
153 }
154 }
155 return bytes;
156 }
157
158 /**
159 * Constructing a new BitChromosome from a given BitSet.
160 * The BitSet is copied while construction. The length of the constructed
161 * BitChromosome will be {@code bitSet.length()}
162 * (@see BitSet#length).
163 *
164 * @param bits the bit-set which initializes the chromosome
165 * @throws NullPointerException if the {@code bitSet} is
166 * {@code null}.
167 */
168 public BitChromosome (final BitSet bits) {
169 this(bits.toByteArray(), -1);
170 }
171
172 /**
173 * Create a new {@code BitChromosome} from the given large integer value.
174 *
175 * @param value the value of the created {@code BitChromosome}
176 * @throws NullPointerException if the given {@code value} is {@code null}.
177 */
178 public BitChromosome(final LargeInteger value) {
179 this(bit.toByteArray(value), -1);
180 }
181
182 /**
183 * Create a new {@code BitChromosome} from the given character sequence
184 * containing '0' and '1'; as created with the {@link #toCanonicalString()}
185 * method.
186 *
187 * @param value the input string.
188 * @throws NullPointerException if the {@code value} is {@code null}.
189 * @throws IllegalArgumentException if the length of the character sequence
190 * is zero or contains other characters than '0' or '1'.
191 */
192 public BitChromosome (final CharSequence value) {
193 this(toByteArray(requireNonNull(value, "Input")), -1);
194 }
195
196 private static byte[] toByteArray(final CharSequence value) {
197 final byte[] bytes = bit.newArray(value.length());
198 for (int i = value.length(); --i >= 0;) {
199 final char c = value.charAt(i);
200 if (c == '1') {
201 bit.set(bytes, i);
202 } else if (c != '0') {
203 throw new IllegalArgumentException(format(
204 "Illegal character '%s' at position %d", c, i
205 ));
206 }
207 }
208
209 return bytes;
210 }
211
212 private void rangeCheck(final int index) {
213 assert(_length >= 0);
214 if (index < 0 || index >= _length) {
215 throw new IndexOutOfBoundsException(
216 "Index: " + index + ", Length: " + _length
217 );
218 }
219 }
220
221 @Override
222 public BitGene getGene() {
223 assert (_genes != null);
224 assert (_genes.length > 0);
225 return BitGene.valueOf(bit.get(_genes, 0));
226 }
227
228 @Override
229 public BitGene getGene(final int index) {
230 rangeCheck(index);
231 assert(_genes != null);
232 return BitGene.valueOf(bit.get(_genes, index));
233 }
234
235 @Override
236 public ISeq<BitGene> toSeq() {
237 return _seq.toISeq();
238 }
239
240 @Override
241 public int length() {
242 return _length;
243 }
244
245 /**
246 * Returns the number of bits set to true in this {@code BitChromosome}.
247 *
248 * @return the number of bits set to true in this {@code BitChromosome}
249 */
250 public int bitCount() {
251 return bit.count(_genes);
252 }
253
254 @Override
255 public Iterator<BitGene> iterator() {
256 return _seq.iterator();
257 }
258
259 public ListIterator<BitGene> listIterator() {
260 return _seq.listIterator();
261 }
262
263 /**
264 * Return the long value this BitChromosome represents.
265 *
266 * @return Long value this BitChromosome represents.
267 */
268 @Override
269 public long longValue() {
270 return toLargeInteger().longValue();
271 }
272
273 /**
274 * Return the double value this BitChromosome represents.
275 *
276 * @return Double value this BitChromosome represents.
277 */
278 @Override
279 public double doubleValue() {
280 return longValue();
281 }
282
283 @Override
284 public boolean isValid() {
285 return true;
286 }
287
288 /**
289 * Return the LargeInteger value this BitChromosome represents.
290 *
291 * @return LargeInteger value this BitChromosome represents.
292 */
293 public LargeInteger toLargeInteger() {
294 return bit.toLargeInteger(_genes);
295 }
296
297 /**
298 * Returns the two's-complement binary representation of this
299 * large integer. The output array is in <i>big-endian</i>
300 * byte-order: the most significant byte is at the offset position.
301 *
302 * <p>Note: This representation is consistent with {@code java.lang.BigInteger
303 * } byte array representation and can be used for conversion
304 * between the two classes.</p>
305 *
306 * @param bytes the bytes to hold the binary representation
307 * (two's-complement) of this large integer.
308 * @return the number of bytes written.
309 * @throws IndexOutOfBoundsException
310 * if {@code bytes.length < (int)Math.ceil(length()/8.0)}
311 * @throws NullPointerException it the give array is {@code null}.
312 */
313 public int toByteArray(final byte[] bytes) {
314 if (bytes.length < _genes.length) {
315 throw new IndexOutOfBoundsException();
316 }
317
318 System.arraycopy(_genes, 0, bytes, 0, _genes.length);
319
320 return _genes.length;
321 }
322
323 /**
324 * @return a byte array which represents this {@code BitChromosome}. The
325 * length of the array is {@code (int)Math.ceil(length()/8.0)}.
326 *
327 * @see #toByteArray(byte[])
328 */
329 public byte[] toByteArray() {
330 final byte[] data = new byte[_genes.length];
331 toByteArray(data);
332 return data;
333 }
334
335 /**
336 * Return the corresponding BitSet of this BitChromosome.
337 *
338 * @return The corresponding BitSet of this BitChromosome.
339 */
340 public BitSet toBitSet() {
341 final BitSet set = new BitSet(length());
342 for (int i = 0, n = length(); i < n; ++i) {
343 set.set(i, getGene(i).getBit());
344 }
345 return set;
346 }
347
348 @Override
349 public BitChromosome newInstance(final ISeq<BitGene> genes) {
350 requireNonNull(genes, "Genes");
351
352 final BitChromosome chromosome = new BitChromosome(
353 bit.newArray(genes.length()), genes.length()
354 );
355 int ones = 0;
356
357 if (genes instanceof BitGeneArray.BitGeneISeq) {
358 final BitGeneArray.BitGeneISeq iseq = (BitGeneArray.BitGeneISeq)genes;
359 iseq.copyTo(chromosome._genes);
360 ones = bit.count(chromosome._genes);
361 } else {
362 for (int i = genes.length(); --i >= 0;) {
363 if (genes.get(i).booleanValue()) {
364 ++ones;
365 }
366 bit.set(chromosome._genes, i, genes.get(i).booleanValue());
367 }
368 }
369
370 chromosome._p = (double)ones/(double)genes.length();
371 return chromosome;
372 }
373
374 @Override
375 public BitChromosome newInstance() {
376 return new BitChromosome(_length, _p);
377 }
378
379 /**
380 * Return the BitChromosome as String. A TRUE is represented by a 1 and
381 * a FALSE by a 0. The returned string can be used to create a new
382 * chromosome with the {@link #BitChromosome(CharSequence)} constructor.
383 *
384 * @return String representation (containing only '1' and '0') of the
385 * BitChromosome.
386 */
387 public String toCanonicalString() {
388 final StringBuilder out = new StringBuilder(length());
389 for (int i = 0; i < _length; ++i) {
390 out.append(bit.get(_genes, i) ? '1' : '0');
391 }
392 return out.toString();
393 }
394
395 @Override
396 public int compareTo(final BitChromosome that) {
397 return toLargeInteger().compareTo(that.toLargeInteger());
398 }
399
400 @Override
401 public boolean isLargerThan(final BitChromosome that) {
402 return toLargeInteger().isLargerThan(that.toLargeInteger());
403 }
404
405 public LargeInteger sqrt() {
406 return toLargeInteger().sqrt();
407 }
408
409 @Override
410 public BitChromosome plus(final BitChromosome that) {
411 return new BitChromosome(toLargeInteger().plus(that.toLargeInteger()));
412 }
413
414 @Override
415 public BitChromosome opposite() {
416 return new BitChromosome(toLargeInteger().opposite());
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 BitChromosome copy = copy();
426 bit.invert(copy._genes);
427 return copy;
428 }
429
430 @Override
431 public BitChromosome times(final BitChromosome that) {
432 return new BitChromosome(toLargeInteger().times(that.toLargeInteger()));
433 }
434
435 @Override
436 public int hashCode() {
437 return hashCodeOf(getClass()).and(_genes).value();
438 }
439
440 @Override
441 public boolean equals(final Object o) {
442 if (o == this) {
443 return true;
444 }
445 if (o == null || getClass() != o.getClass()) {
446 return false;
447 }
448
449 final BitChromosome c = (BitChromosome)o;
450 boolean equals = length() == c.length();
451 for (int i = 0, n = length(); equals && i < n; ++i) {
452 equals = getGene(i) == c.getGene(i);
453 }
454 return equals;
455 }
456
457 @Override
458 public Text toText() {
459 return Text.valueOf(bit.toByteString(toByteArray()));
460 }
461
462 @Override
463 public BitChromosome copy() {
464 final BitChromosome chromosome = new BitChromosome(_length, _p);
465 System.arraycopy(_genes, 0, chromosome._genes, 0, chromosome._genes.length);
466 return chromosome;
467 }
468
469 /* *************************************************************************
470 * XML object serialization
471 * ************************************************************************/
472
473 static final XMLFormat<BitChromosome>
474 XML = new XMLFormat<BitChromosome>(BitChromosome.class)
475 {
476 private static final String LENGTH = "length";
477 private static final String PROBABILITY = "probability";
478
479 @Override
480 public BitChromosome newInstance(
481 final Class<BitChromosome> cls, final InputElement xml
482 )
483 throws XMLStreamException
484 {
485 final int length = xml.getAttribute(LENGTH, 1);
486 final double probability = xml.getAttribute(PROBABILITY, 0.5);
487 final byte[] data = bit.fromByteString(xml.getText().toString());
488 final BitChromosome chromosome = new BitChromosome(data);
489 chromosome._p = probability;
490 chromosome._length = length;
491 return chromosome;
492 }
493 @Override
494 public void write(final BitChromosome chromosome, final OutputElement xml)
495 throws XMLStreamException
496 {
497 xml.setAttribute(LENGTH, chromosome._length);
498 xml.setAttribute(PROBABILITY, chromosome._p);
499 xml.addText(bit.toByteString(chromosome.toByteArray()));
500 }
501 @Override
502 public void read(final InputElement element, final BitChromosome gene) {
503 }
504 };
505
506 /* *************************************************************************
507 * Java object serialization
508 * ************************************************************************/
509
510 private void writeObject(final ObjectOutputStream out)
511 throws IOException
512 {
513 out.defaultWriteObject();
514
515 out.writeInt(_length);
516 out.writeDouble(_p);
517 out.writeInt(_genes.length);
518 out.write(_genes);
519 }
520
521 private void readObject(final ObjectInputStream in)
522 throws IOException, ClassNotFoundException
523 {
524 in.defaultReadObject();
525
526 _length = in.readInt();
527 _p = in.readDouble();
528
529 final int bytes = in.readInt();
530 _genes = new byte[bytes];
531 in.readFully(_genes);
532
533 _seq = new BitGeneArray(_genes, 0, _length);
534 }
535
536 }
537
538
|