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: * The crossover operator randomly selects two Chromosomes from the
017: * population and "mates" them by randomly picking a gene and then
018: * swapping that gene and all subsequent genes between the two
019: * Chromosomes. The two modified Chromosomes are then added to the
020: * list of candidate Chromosomes.
021: *
022: * If you work with CompositeGene's, this operator expects them to contain
023: * genes of the same type (e.g. IntegerGene). If you have mixed types, please
024: * provide your own crossover operator.
025: *
026: * This CrossoverOperator supports both fixed and dynamic crossover rates.
027: * A fixed rate is one specified at construction time by the user. This
028: * operation is performed 1/m_crossoverRate as many times as there are
029: * Chromosomes in the population. Another possibility is giving the crossover
030: * rate as a percentage. A dynamic rate is one determined by this class on the
031: * fly if no fixed rate is provided.
032: *
033: * @author Neil Rotstan
034: * @author Klaus Meffert
035: * @author Chris Knowles
036: * @since 1.0
037: */
038: public class CrossoverOperator extends BaseGeneticOperator implements
039: Comparable {
040: /** String containing the CVS revision. Read out via reflection!*/
041: private final static String CVS_REVISION = "$Revision: 1.42 $";
042:
043: /**
044: * The current crossover rate used by this crossover operator (mutual
045: * exclusive to m_crossoverRatePercent and m_crossoverRateCalc).
046: */
047: private int m_crossoverRate;
048:
049: /**
050: * Crossover rate in percentage of population size (mutual exclusive to
051: * m_crossoverRate and m_crossoverRateCalc).
052: */
053: private double m_crossoverRatePercent;
054:
055: /**
056: * Calculator for dynamically determining the crossover rate (mutual exclusive
057: * to m_crossoverRate and m_crossoverRatePercent)
058: */
059: private IUniversalRateCalculator m_crossoverRateCalc;
060:
061: /**
062: * true: x-over before and after a randomly chosen x-over point
063: * false: only x-over after the chosen point.
064: */
065: private boolean m_allowFullCrossOver;
066:
067: /**
068: * true: also x-over chromosomes with age of zero (newly created chromosomes)
069: */
070: private boolean m_xoverNewAge;
071:
072: /**
073: * Constructs a new instance of this CrossoverOperator without a specified
074: * crossover rate, this results in dynamic crossover rate being turned off.
075: * This means that the crossover rate will be fixed at populationsize/2.<p>
076: * Attention: The configuration used is the one set with the static method
077: * Genotype.setConfiguration.
078: *
079: * @throws InvalidConfigurationException
080: *
081: * @author Chris Knowles
082: * @since 2.0
083: */
084: public CrossoverOperator() throws InvalidConfigurationException {
085: super (Genotype.getStaticConfiguration());
086: init();
087: }
088:
089: /**
090: * Constructs a new instance of this CrossoverOperator without a specified
091: * crossover rate, this results in dynamic crossover rate being turned off.
092: * This means that the crossover rate will be fixed at populationsize/2.
093: *
094: * @param a_configuration the configuration to use
095: * @throws InvalidConfigurationException
096: *
097: * @author Klaus Meffert
098: * @since 3.0
099: */
100: public CrossoverOperator(final Configuration a_configuration)
101: throws InvalidConfigurationException {
102: super (a_configuration);
103: init();
104: }
105:
106: /**
107: * Initializes certain parameters.
108: *
109: * @author Klaus Meffert
110: * @since 3.3.2
111: */
112: protected void init() {
113: // Set the default crossoverRate to be populationsize/2.
114: // -----------------------------------------------------
115: m_crossoverRate = 2;
116: m_crossoverRatePercent = -1;
117: setCrossoverRateCalc(null);
118: setAllowFullCrossOver(true);
119: }
120:
121: /**
122: * Constructs a new instance of this CrossoverOperator with a specified
123: * crossover rate calculator, which results in dynamic crossover being turned
124: * on.
125: *
126: * @param a_configuration the configuration to use
127: * @param a_crossoverRateCalculator calculator for dynamic crossover rate
128: * computation
129: * @throws InvalidConfigurationException
130: *
131: * @author Chris Knowles
132: * @author Klaus Meffert
133: * @since 3.0 (since 2.0 without a_configuration)
134: */
135: public CrossoverOperator(final Configuration a_configuration,
136: final IUniversalRateCalculator a_crossoverRateCalculator)
137: throws InvalidConfigurationException {
138: this (a_configuration, a_crossoverRateCalculator, true);
139: }
140:
141: /**
142: * Constructs a new instance of this CrossoverOperator with a specified
143: * crossover rate calculator, which results in dynamic crossover being turned
144: * on.
145: *
146: * @param a_configuration the configuration to use
147: * @param a_crossoverRateCalculator calculator for dynamic crossover rate
148: * computation
149: * @param a_allowFullCrossOver true: x-over before AND after x-over point,
150: * false: only x-over after x-over point
151: * @throws InvalidConfigurationException
152: *
153: * @author Klaus Meffert
154: * @since 3.3.2
155: */
156: public CrossoverOperator(final Configuration a_configuration,
157: final IUniversalRateCalculator a_crossoverRateCalculator,
158: boolean a_allowFullCrossOver)
159: throws InvalidConfigurationException {
160: super (a_configuration);
161: setCrossoverRateCalc(a_crossoverRateCalculator);
162: setAllowFullCrossOver(a_allowFullCrossOver);
163: }
164:
165: /**
166: * Constructs a new instance of this CrossoverOperator with the given
167: * crossover rate.
168: *
169: * @param a_configuration the configuration to use
170: * @param a_desiredCrossoverRate the desired rate of crossover
171: * @throws InvalidConfigurationException
172: *
173: * @author Chris Knowles
174: * @author Klaus Meffert
175: * @since 3.0 (since 2.0 without a_configuration)
176: */
177: public CrossoverOperator(final Configuration a_configuration,
178: final int a_desiredCrossoverRate)
179: throws InvalidConfigurationException {
180: this (a_configuration, a_desiredCrossoverRate, true);
181: }
182:
183: /**
184: * Constructs a new instance of this CrossoverOperator with the given
185: * crossover rate. No new chromosomes are x-overed.
186: *
187: * @param a_configuration the configuration to use
188: * @param a_desiredCrossoverRate the desired rate of crossover
189: * @param a_allowFullCrossOver true: x-over before AND after x-over point,
190: * false: only x-over after x-over point
191: * @throws InvalidConfigurationException
192: *
193: * @author Klaus Meffert
194: * @since 3.3.2
195: */
196: public CrossoverOperator(final Configuration a_configuration,
197: final int a_desiredCrossoverRate,
198: boolean a_allowFullCrossOver)
199: throws InvalidConfigurationException {
200: this (a_configuration, a_desiredCrossoverRate,
201: a_allowFullCrossOver, false);
202: }
203:
204: /**
205: * Constructs a new instance of this CrossoverOperator with the given
206: * crossover rate.
207: *
208: * @param a_configuration the configuration to use
209: * @param a_desiredCrossoverRate the desired rate of crossover
210: * @param a_allowFullCrossOver true: x-over before AND after x-over point,
211: * false: only x-over after x-over point
212: * @throws InvalidConfigurationException
213: * @param a_xoverNewAge true: also x-over chromosomes with age of zero (newly
214: * created chromosomes)
215: *
216: * @author Klaus Meffert
217: * @since 3.3.2
218: */
219: public CrossoverOperator(final Configuration a_configuration,
220: final int a_desiredCrossoverRate,
221: final boolean a_allowFullCrossOver,
222: final boolean a_xoverNewAge)
223: throws InvalidConfigurationException {
224: super (a_configuration);
225: if (a_desiredCrossoverRate < 1) {
226: throw new IllegalArgumentException(
227: "Crossover rate must be greater zero");
228: }
229: m_crossoverRate = a_desiredCrossoverRate;
230: m_crossoverRatePercent = -1;
231: setCrossoverRateCalc(null);
232: setAllowFullCrossOver(a_allowFullCrossOver);
233: setXoverNewAge(a_xoverNewAge);
234: }
235:
236: /**
237: * Constructs a new instance of this CrossoverOperator with the given
238: * crossover rate. No new chromosomes are x-overed.
239: *
240: * @param a_configuration the configuration to use
241: * @param a_crossoverRatePercentage the desired rate of crossover in
242: * percentage of the population
243: * @throws InvalidConfigurationException
244: *
245: * @author Chris Knowles
246: * @author Klaus Meffert
247: * @since 3.0 (since 2.0 without a_configuration)
248: */
249: public CrossoverOperator(final Configuration a_configuration,
250: final double a_crossoverRatePercentage)
251: throws InvalidConfigurationException {
252: this (a_configuration, a_crossoverRatePercentage, true);
253: }
254:
255: /**
256: * Constructs a new instance of this CrossoverOperator with the given
257: * crossover rate. No new chromosomes are x-overed.
258: *
259: * @param a_configuration the configuration to use
260: * @param a_crossoverRatePercentage the desired rate of crossover in
261: * percentage of the population
262: * @param a_allowFullCrossOver true: x-over before AND after x-over point,
263: * false: only x-over after x-over point
264: * @throws InvalidConfigurationException
265: *
266: * @author Klaus Meffert
267: * @since 3.3.2.
268: */
269: public CrossoverOperator(final Configuration a_configuration,
270: final double a_crossoverRatePercentage,
271: boolean a_allowFullCrossOver)
272: throws InvalidConfigurationException {
273: this (a_configuration, a_crossoverRatePercentage,
274: a_allowFullCrossOver, false);
275: }
276:
277: /**
278: * Constructs a new instance of this CrossoverOperator with the given
279: * crossover rate.
280: *
281: * @param a_configuration the configuration to use
282: * @param a_crossoverRatePercentage the desired rate of crossover in
283: * percentage of the population
284: * @param a_allowFullCrossOver true: x-over before AND after x-over point,
285: * false: only x-over after x-over point
286: * @param a_xoverNewAge true: also x-over chromosomes with age of zero (newly
287: * created chromosomes)
288: * @throws InvalidConfigurationException
289: *
290: * @author Klaus Meffert
291: * @since 3.3.2.
292: */
293: public CrossoverOperator(final Configuration a_configuration,
294: final double a_crossoverRatePercentage,
295: final boolean a_allowFullCrossOver,
296: final boolean a_xoverNewAge)
297: throws InvalidConfigurationException {
298: super (a_configuration);
299: if (a_crossoverRatePercentage <= 0.0d) {
300: throw new IllegalArgumentException(
301: "Crossover rate must be greater zero");
302: }
303: m_crossoverRatePercent = a_crossoverRatePercentage;
304: m_crossoverRate = -1;
305: setCrossoverRateCalc(null);
306: setAllowFullCrossOver(a_allowFullCrossOver);
307: setXoverNewAge(a_xoverNewAge);
308: }
309:
310: /**
311: * Does the crossing over.
312: *
313: * @param a_population the population of chromosomes from the current
314: * evolution prior to exposure to crossing over
315: * @param a_candidateChromosomes the pool of chromosomes that have been
316: * selected for the next evolved population
317: *
318: * @author Neil Rotstan
319: * @author Klaus Meffert
320: * @since 2.0
321: */
322: public void operate(final Population a_population,
323: final List a_candidateChromosomes) {
324: // Work out the number of crossovers that should be performed.
325: // -----------------------------------------------------------
326: int size = Math.min(getConfiguration().getPopulationSize(),
327: a_population.size());
328: int numCrossovers = 0;
329: if (m_crossoverRate >= 0) {
330: numCrossovers = size / m_crossoverRate;
331: } else if (m_crossoverRateCalc != null) {
332: numCrossovers = size
333: / m_crossoverRateCalc.calculateCurrentRate();
334: } else {
335: numCrossovers = (int) (size * m_crossoverRatePercent);
336: }
337: RandomGenerator generator = getConfiguration()
338: .getRandomGenerator();
339: IGeneticOperatorConstraint constraint = getConfiguration()
340: .getJGAPFactory().getGeneticOperatorConstraint();
341: // For each crossover, grab two random chromosomes, pick a random
342: // locus (gene location), and then swap that gene and all genes
343: // to the "right" (those with greater loci) of that gene between
344: // the two chromosomes.
345: // --------------------------------------------------------------
346: int index1, index2;
347: for (int i = 0; i < numCrossovers; i++) {
348: index1 = generator.nextInt(size);
349: index2 = generator.nextInt(size);
350: IChromosome chrom1 = a_population.getChromosome(index1);
351: IChromosome chrom2 = a_population.getChromosome(index2);
352: // Verify that crossover is allowed.
353: // ---------------------------------
354: if (!isXoverNewAge() && chrom1.getAge() < 1
355: && chrom2.getAge() < 1) {
356: // Crossing over two newly created chromosomes is not seen as helpful
357: // here.
358: // ------------------------------------------------------------------
359: continue;
360: }
361: if (constraint != null) {
362: List v = new Vector();
363: v.add(chrom1);
364: v.add(chrom2);
365: if (!constraint.isValid(a_population, v, this )) {
366: // Constraint forbids crossing over.
367: // ---------------------------------
368: continue;
369: }
370: }
371: // Clone the chromosomes.
372: // ----------------------
373: IChromosome firstMate = (IChromosome) chrom1.clone();
374: IChromosome secondMate = (IChromosome) chrom2.clone();
375: // Cross over the chromosomes.
376: // ---------------------------
377: doCrossover(firstMate, secondMate, a_candidateChromosomes,
378: generator);
379: }
380: }
381:
382: private void doCrossover(IChromosome firstMate,
383: IChromosome secondMate, List a_candidateChromosomes,
384: RandomGenerator generator) {
385: Gene[] firstGenes = firstMate.getGenes();
386: Gene[] secondGenes = secondMate.getGenes();
387: int locus = generator.nextInt(firstGenes.length);
388: // Swap the genes.
389: // ---------------
390: Gene gene1;
391: Gene gene2;
392: Object firstAllele;
393: for (int j = locus; j < firstGenes.length; j++) {
394: // Make a distinction for ICompositeGene for the first gene.
395: // ---------------------------------------------------------
396: if (firstGenes[j] instanceof ICompositeGene) {
397: // Randomly determine gene to be considered.
398: // -----------------------------------------
399: int index1 = generator.nextInt(firstGenes[j].size());
400: gene1 = ((ICompositeGene) firstGenes[j]).geneAt(index1);
401: } else {
402: gene1 = firstGenes[j];
403: }
404: // Make a distinction for the second gene if CompositeGene.
405: // --------------------------------------------------------
406: if (secondGenes[j] instanceof ICompositeGene) {
407: // Randomly determine gene to be considered.
408: // -----------------------------------------
409: int index2 = generator.nextInt(secondGenes[j].size());
410: gene2 = ((ICompositeGene) secondGenes[j])
411: .geneAt(index2);
412: } else {
413: gene2 = secondGenes[j];
414: }
415: firstAllele = gene1.getAllele();
416: gene1.setAllele(gene2.getAllele());
417: gene2.setAllele(firstAllele);
418: }
419: // Add the modified chromosomes to the candidate pool so that
420: // they'll be considered for natural selection during the next
421: // phase of evolution.
422: // -----------------------------------------------------------
423: a_candidateChromosomes.add(firstMate);
424: a_candidateChromosomes.add(secondMate);
425: }
426:
427: /**
428: * Sets the crossover rate calculator.
429: *
430: * @param a_crossoverRateCalculator the new calculator
431: *
432: * @author Chris Knowles
433: * @since 2.0
434: */
435: private void setCrossoverRateCalc(
436: final IUniversalRateCalculator a_crossoverRateCalculator) {
437: m_crossoverRateCalc = a_crossoverRateCalculator;
438: if (a_crossoverRateCalculator != null) {
439: m_crossoverRate = -1;
440: m_crossoverRatePercent = -1d;
441: }
442: }
443:
444: /**
445: * Compares the given object to this one.
446: *
447: * @param a_other the instance against which to compare this instance
448: * @return a negative number if this instance is "less than" the given
449: * instance, zero if they are equal to each other, and a positive number if
450: * this is "greater than" the given instance
451: *
452: * @author Klaus Meffert
453: * @since 2.6
454: */
455: public int compareTo(final Object a_other) {
456: /**@todo consider Configuration*/
457: if (a_other == null) {
458: return 1;
459: }
460: CrossoverOperator op = (CrossoverOperator) a_other;
461: if (m_crossoverRateCalc == null) {
462: if (op.m_crossoverRateCalc != null) {
463: return -1;
464: }
465: } else {
466: if (op.m_crossoverRateCalc == null) {
467: return 1;
468: }
469: }
470: if (m_crossoverRate != op.m_crossoverRate) {
471: if (m_crossoverRate > op.m_crossoverRate) {
472: return 1;
473: } else {
474: return -1;
475: }
476: }
477: if (m_allowFullCrossOver != op.m_allowFullCrossOver) {
478: if (m_allowFullCrossOver) {
479: return 1;
480: } else {
481: return -1;
482: }
483: }
484: if (m_xoverNewAge != op.m_xoverNewAge) {
485: if (m_xoverNewAge) {
486: return 1;
487: } else {
488: return -1;
489: }
490: }
491: // Everything is equal. Return zero.
492: // ---------------------------------
493: return 0;
494: }
495:
496: /**
497: * @param a_allowFullXOver x-over before and after a randomly chosen point
498: *
499: * @author Klaus Meffert
500: * @since 3.3.2
501: */
502: public void setAllowFullCrossOver(boolean a_allowFullXOver) {
503: m_allowFullCrossOver = a_allowFullXOver;
504: }
505:
506: /**
507: * @return x-over before and after a randomly chosen x-over point
508: *
509: * @author Klaus Meffert
510: * @since 3.3.2
511: */
512: public boolean isAllowFullCrossOver() {
513: return m_allowFullCrossOver;
514: }
515:
516: /**
517: * @return the crossover rate set
518: *
519: * @author Klaus Meffert
520: * @since 3.3.2
521: */
522: public int getCrossOverRate() {
523: return m_crossoverRate;
524: }
525:
526: /**
527: * @return the crossover rate set
528: *
529: * @author Klaus Meffert
530: * @since 3.3.2
531: */
532: public double getCrossOverRatePercent() {
533: return m_crossoverRatePercent;
534: }
535:
536: /**
537: * @param a_xoverNewAge true: also x-over chromosomes with age of zero (newly
538: * created chromosomes)
539: *
540: * @author Klaus Meffert
541: * @since 3.3.2
542: */
543: public void setXoverNewAge(boolean a_xoverNewAge) {
544: m_xoverNewAge = a_xoverNewAge;
545: }
546:
547: /**
548: * @return a_xoverNewAge true: also x-over chromosomes with age of zero (newly
549: * created chromosomes)
550: *
551: * @author Klaus Meffert
552: * @since 3.3.2
553: */
554: public boolean isXoverNewAge() {
555: return m_xoverNewAge;
556: }
557: }
|