001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package org.jgap.impl;
011:
012: import java.util.*;
013: import org.jgap.*;
014:
015: /**
016: * A Gene implementation that supports two possible values (alleles, 1 and 0)
017: * with a fixed length of alleles.
018: * <p>
019: * NOTE: Since this Gene implementation only supports two different
020: * values (1 and 0), there's only a 50% chance that invocation
021: * of the setToRandomValue() method will actually change the value of
022: * this Gene (if it has a value). As a result, it may be desirable to
023: * use a higher overall mutation rate when this Gene implementation
024: * is in use.
025: * <p>
026: * Partly adapted stuff from the JAGA (Java API for Genetic Algorithms)
027: * package (see <a href="http://www.jaga.org">jaga</a>).
028: *
029: * @author Klaus Meffert
030: * @since 2.0
031: */
032: public class FixedBinaryGene extends BaseGene implements
033: IPersistentRepresentation {
034: /** String containing the CVS revision. Read out via reflection!*/
035: private final static String CVS_REVISION = "$Revision: 1.39 $";
036:
037: private int m_length;
038:
039: private int[] m_value;
040:
041: private static final int WORD_LEN_BITS = 32;
042:
043: /**
044: *
045: * @param a_config the configuration to use
046: * @param a_length the fixed length of the gene
047: * @throws InvalidConfigurationException
048: *
049: * @author Klaus Meffert
050: * @since 2.0
051: */
052: public FixedBinaryGene(final Configuration a_config,
053: final int a_length) throws InvalidConfigurationException {
054: super (a_config);
055: if (a_length < 1) {
056: throw new IllegalArgumentException(
057: "Length must be greater than zero!");
058: }
059: m_length = a_length;
060: int bufSize = m_length / WORD_LEN_BITS;
061: if (0 != m_length % WORD_LEN_BITS) {
062: ++bufSize;
063: }
064: m_value = new int[bufSize];
065: for (int i = 0; i < bufSize; i++) {
066: m_value[i] = 0;
067: }
068: }
069:
070: protected Gene newGeneInternal() {
071: try {
072: FixedBinaryGene result = new FixedBinaryGene(
073: getConfiguration(), m_length);
074: return result;
075: } catch (InvalidConfigurationException iex) {
076: throw new IllegalStateException(iex.getMessage());
077: }
078: }
079:
080: public FixedBinaryGene(final Configuration a_config,
081: final FixedBinaryGene a_toCopy)
082: throws InvalidConfigurationException {
083: super (a_config);
084: m_length = a_toCopy.getLength();
085: int bufSize = m_length / WORD_LEN_BITS;
086: if (0 != m_length % WORD_LEN_BITS) {
087: ++bufSize;
088: }
089: m_value = new int[bufSize];
090: System.arraycopy(a_toCopy.getValue(), 0, m_value, 0,
091: m_value.length);
092: }
093:
094: protected int[] getValue() {
095: return m_value;
096: }
097:
098: public int getLength() {
099: return m_length;
100: }
101:
102: public Object clone() {
103: try {
104: return new FixedBinaryGene(getConfiguration(), this );
105: } catch (InvalidConfigurationException iex) {
106: throw new IllegalStateException(iex.getMessage());
107: }
108: }
109:
110: public void setAllele(final Object a_newValue) {
111: if (a_newValue == null) {
112: throw new IllegalArgumentException(
113: "Allele must not be null!");
114: }
115: if (((int[]) a_newValue).length != getLength()) {
116: throw new IllegalArgumentException(
117: "Length of allele must be equal to"
118: + " fixed length set (" + getLength() + ")");
119: }
120: if (getConstraintChecker() != null) {
121: if (!getConstraintChecker().verify(this , a_newValue, null,
122: -1)) {
123: return;
124: }
125: }
126: int[] bits = (int[]) a_newValue;
127: for (int i = 0; i < bits.length; i++) {
128: setBit(i, bits[i]);
129: }
130: }
131:
132: public Object getAllele() {
133: int[] bits = new int[getLength()];
134: for (int i = 0; i < getLength(); i++) {
135: if (getBit(i)) {
136: bits[i] = 1;
137: } else {
138: bits[i] = 0;
139: }
140: }
141: return bits;
142: }
143:
144: public int[] getIntValues() {
145: return m_value;
146: }
147:
148: public boolean getBit(final int a_index) {
149: checkIndex(a_index);
150: return getUnchecked(a_index);
151: }
152:
153: public void setBit(final int a_index, final boolean a_value) {
154: checkIndex(a_index);
155: setUnchecked(a_index, a_value);
156: }
157:
158: public void setBit(final int a_index, final int a_value) {
159: if (a_value > 0) {
160: if (a_value != 1) {
161: throw new IllegalArgumentException(
162: "Only values 0 and 1 are valid!");
163: }
164: setBit(a_index, true);
165: } else {
166: if (a_value != 0) {
167: throw new IllegalArgumentException(
168: "Only values 0 and 1 are valid!");
169: }
170: setBit(a_index, false);
171: }
172: }
173:
174: public void setBit(final int a_from, final int a_to,
175: final boolean a_value) {
176: checkSubLength(a_from, a_to);
177: for (int i = a_from; i < a_to; i++) {
178: setUnchecked(i, a_value);
179: }
180: }
181:
182: public void setBit(final int a_from, final int a_to,
183: final FixedBinaryGene a_values) {
184: if (a_values.getLength() == 0) {
185: throw new IllegalArgumentException(
186: "Length of values must be > 0");
187: }
188: checkSubLength(a_from, a_to);
189: int iV = 0;
190: for (int i = a_from; i <= a_to; i++, iV++) {
191: if (iV >= a_values.getLength()) {
192: iV = 0;
193: }
194: setUnchecked(i, a_values.getUnchecked(iV));
195: }
196: }
197:
198: public FixedBinaryGene substring(final int a_from, final int a_to) {
199: try {
200: int len = checkSubLength(a_from, a_to);
201: FixedBinaryGene substring = new FixedBinaryGene(
202: getConfiguration(), len);
203: for (int i = a_from; i <= a_to; i++) {
204: substring.setUnchecked(i - a_from, getUnchecked(i));
205: }
206: return substring;
207: } catch (InvalidConfigurationException iex) {
208: throw new IllegalStateException(iex.getMessage());
209: }
210: }
211:
212: public void flip(final int a_index) {
213: checkIndex(a_index);
214: int segment = a_index / WORD_LEN_BITS;
215: int offset = a_index % WORD_LEN_BITS;
216: int mask = 0x1 << (WORD_LEN_BITS - offset - 1);
217: m_value[segment] ^= mask;
218: }
219:
220: protected int checkSubLength(final int a_from, final int a_to) {
221: checkIndex(a_from);
222: checkIndex(a_to);
223: int sublen = a_to - a_from + 1;
224: if (0 >= sublen) {
225: throw new IllegalArgumentException(
226: "must have 'from' <= 'to', but has " + a_from
227: + " > " + a_to);
228: }
229: return sublen;
230: }
231:
232: protected void checkIndex(final int a_index) {
233: if (a_index < 0 || a_index >= getLength()) {
234: throw new IndexOutOfBoundsException("index is " + a_index
235: + ", but must be in [0, " + (getLength() - 1) + "]");
236: }
237: }
238:
239: protected boolean getUnchecked(final int a_index) {
240: int segment = a_index / WORD_LEN_BITS;
241: int offset = a_index % WORD_LEN_BITS;
242: int mask = 0x1 << (WORD_LEN_BITS - offset - 1);
243: return 0 != (m_value[segment] & mask);
244: }
245:
246: public void setUnchecked(final int a_index, final boolean a_value) {
247: int segment = a_index / WORD_LEN_BITS;
248: int offset = a_index % WORD_LEN_BITS;
249: int mask = 0x1 << (WORD_LEN_BITS - offset - 1);
250: if (a_value) {
251: m_value[segment] |= mask;
252: } else {
253: m_value[segment] &= ~mask;
254: }
255: }
256:
257: public String getPersistentRepresentation() {
258: return toString();
259: }
260:
261: /**
262: * Sets the value and internal state of this Gene from the string
263: * representation returned by a previous invocation of the
264: * getPersistentRepresentation() method. This is an optional method but,
265: * if not implemented, XML persistence and possibly other features will not
266: * be available. An UnsupportedOperationException should be thrown if no
267: * implementation is provided.
268: *
269: * @param a_representation the string representation retrieved from a
270: * prior call to the getPersistentRepresentation() method
271: *
272: * @throws UnsupportedRepresentationException if this Gene implementation
273: * does not support the given string representation
274: *
275: * @author Klaus Meffert
276: * @since 2.0
277: */
278: public void setValueFromPersistentRepresentation(
279: String a_representation)
280: throws UnsupportedRepresentationException {
281: if (a_representation != null) {
282: if (isValidRepresentation(a_representation)) {
283: a_representation = a_representation.substring(1,
284: a_representation.length() - 1);
285: StringTokenizer st = new StringTokenizer(
286: a_representation, ",");
287: int index = 0;
288: while (st.hasMoreTokens()) {
289: int i = Integer.parseInt(st.nextToken());
290: setBit(index++, i);
291: }
292: if (index < getLength()) {
293: throw new UnsupportedRepresentationException(
294: "Invalid gene representation: "
295: + a_representation);
296: }
297: } else {
298: throw new UnsupportedRepresentationException(
299: "Invalid gene representation: "
300: + a_representation);
301: }
302: } else {
303: throw new UnsupportedRepresentationException(
304: "The input parameter must not be null!");
305: }
306: }
307:
308: /**
309: * Verifies if the String is a valid representation of this Gene type
310: * in general (bit values will not be checked)
311: * @param a_representation the representation to check
312: * @return true: representation is valid in general
313: * @author Klaus Meffert
314: * @since 2.0
315: */
316: private boolean isValidRepresentation(final String a_representation) {
317: if (!a_representation.startsWith("[")
318: || !a_representation.endsWith("]")) {
319: return false;
320: }
321: return true;
322: }
323:
324: public void setToRandomValue(final RandomGenerator a_numberGenerator) {
325: if (a_numberGenerator == null) {
326: throw new IllegalArgumentException(
327: "Random Generator must not be null!");
328: }
329: int len = getLength();
330: for (int i = 0; i < len; i++) {
331: setBit(i, a_numberGenerator.nextBoolean());
332: }
333: }
334:
335: /**
336: * @return String representation
337: *
338: * @author Klaus Meffert
339: * @since 2.0
340: */
341: public String toString() {
342: int len = getLength();
343: String s = "FixedBinaryGene[";
344: int value;
345: for (int i = 0; i < len; i++) {
346: if (getBit(i)) {
347: value = 1;
348: } else {
349: value = 0;
350: }
351: if (i == 0) {
352: s += value;
353: } else {
354: s += "," + value;
355: }
356: }
357: return s + "]";
358: }
359:
360: @Override
361: public String getBusinessKey() {
362: return toString();
363: }
364:
365: /**
366: * @return the size of the gene, i.e the number of atomic elements
367: *
368: * @author Klaus Meffert
369: * @since 2.0
370: */
371: public int size() {
372: return m_value.length;
373: }
374:
375: /**
376: * Applies a mutation of a given intensity (percentage) onto the atomic
377: * element at given index
378: * @param a_index index of atomic element, between 0 and size()-1
379: * @param a_percentage percentage of mutation (greater than -1 and smaller
380: * than 1)
381: *
382: * @author Klaus Meffert
383: * @since 2.0
384: */
385: public void applyMutation(final int a_index,
386: final double a_percentage) {
387: if (a_index < 0 || a_index >= getLength()) {
388: throw new IllegalArgumentException(
389: "Index must be between 0 and getLength() - 1");
390: }
391: if (a_percentage > 0) {
392: // change to 1
393: // ---------------
394: if (!getBit(a_index)) {
395: setBit(a_index, true);
396: }
397: } else if (a_percentage < 0) {
398: // change to 0
399: // ---------------
400: if (getBit(a_index)) {
401: setBit(a_index, false);
402: }
403: }
404: }
405:
406: /**
407: * Compares this Gene with the specified object for order. A
408: * 0 value is considered to be less than a 1 value. A null value
409: * is considered to be less than any non-null value.
410: * A Gene is greater than another one of the same length if it has more 1's
411: * than the other one. If there is the same number of 1's the Gene with the
412: * highest value (binary to int) is greater.
413: *
414: * @param a_other the FixedBinaryGene to be compared
415: * @return a negative integer, zero, or a positive integer as this object
416: * is less than, equal to, or greater than the specified object.
417: *
418: * @throws ClassCastException if the specified object's type prevents it
419: * from being compared to this Gene
420: *
421: * @author Klaus Meffert
422: * @since 2.0
423: */
424: public int compareTo(final Object a_other) {
425: FixedBinaryGene otherGene = (FixedBinaryGene) a_other;
426: // First, if the other gene is null, then this is the greater gene.
427: // ----------------------------------------------------------------
428: if (otherGene == null) {
429: return 1;
430: }
431: int this Len = getLength();
432: int otherLen = otherGene.getLength();
433: if (this Len != otherLen) {
434: if (this Len > otherLen) {
435: return 1;
436: } else {
437: return -1;
438: }
439: }
440: boolean b1, b2;
441: for (int i = 0; i < this Len; i++) {
442: b1 = getBit(i);
443: b2 = otherGene.getBit(i);
444: if (b1) {
445: if (!b2) {
446: return 1;
447: }
448: } else {
449: if (b2) {
450: return -1;
451: }
452: }
453: }
454: // Compare application data, if possible.
455: // --------------------------------------
456: if (isCompareApplicationData()) {
457: return compareApplicationData(getApplicationData(),
458: otherGene.getApplicationData());
459: } else {
460: return 0;
461: }
462: }
463:
464: /**
465: * Not called as getAllele() is overridden.
466: *
467: * @return same as getAllele()
468: */
469: protected Object getInternalValue() {
470: return m_value;
471: }
472:
473: /**
474: * Modified hashCode() function to return different hashcodes for differently
475: * ordered genes in a chromosome --> does not work as internal value always
476: * initialized!
477: *
478: * @return this Gene's hash code
479: *
480: * @author Klaus Meffert
481: * @since 2.2
482: */
483: public int hashCode() {
484: int result = 0;
485: for (int i = 0; i < m_value.length; i++) {
486: if (m_value[i] == 0) {
487: result += 31 * result + 47;
488: } else {
489: result += 31 * result + 91;
490: }
491: }
492: return result;
493: }
494:
495: }
|