org.apache.commons.math3.genetics
Class CycleCrossover<T>

java.lang.Object
  extended by org.apache.commons.math3.genetics.CycleCrossover<T>
Type Parameters:
T - generic type of the AbstractListChromosomes for crossover
All Implemented Interfaces:
CrossoverPolicy

public class CycleCrossover<T>
extends Object
implements CrossoverPolicy

Cycle Crossover [CX] builds offspring from ordered chromosomes by identifying cycles between two parent chromosomes. To form the children, the cycles are copied from the respective parents.

To form a cycle the following procedure is applied:

  1. start with the first gene of parent 1
  2. look at the gene at the same position of parent 2
  3. go to the position with the same gene in parent 1
  4. add this gene index to the cycle
  5. repeat the steps 2-5 until we arrive at the starting gene of this cycle
The indices that form a cycle are then used to form the children in alternating order, i.e. in cycle 1, the genes of parent 1 are copied to child 1, while in cycle 2 the genes of parent 1 are copied to child 2, and so forth ...

Example (zero-start cycle):
 p1 = (8 4 7 3 6 2 5 1 9 0)    X   c1 = (8 1 2 3 4 5 6 7 9 0)
 p2 = (0 1 2 3 4 5 6 7 8 9)    X   c2 = (0 4 7 3 6 2 5 1 8 9)

 cycle 1: 8 0 9
 cycle 2: 4 1 7 2 5 6
 cycle 3: 3
 
This policy works only on AbstractListChromosome, and therefore it is parameterized by T. Moreover, the chromosomes must have same lengths.

Since:
3.1
Version:
$Id: CycleCrossover.java 1385297 2012-09-16 16:05:57Z tn $
See Also:
Cycle Crossover Operator

Field Summary
private  boolean randomStart
          If the start index shall be chosen randomly.
 
Constructor Summary
CycleCrossover()
          Creates a new CycleCrossover policy.
CycleCrossover(boolean randomStart)
          Creates a new CycleCrossover policy using the given randomStart behavior.
 
Method Summary
 ChromosomePair crossover(Chromosome first, Chromosome second)
          Perform a crossover operation on the given chromosomes.
 boolean isRandomStart()
          Returns whether the starting index is chosen randomly or set to zero.
protected  ChromosomePair mate(AbstractListChromosome<T> first, AbstractListChromosome<T> second)
          Helper for crossover(Chromosome, Chromosome).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

randomStart

private final boolean randomStart
If the start index shall be chosen randomly.

Constructor Detail

CycleCrossover

public CycleCrossover()
Creates a new CycleCrossover policy.


CycleCrossover

public CycleCrossover(boolean randomStart)
Creates a new CycleCrossover policy using the given randomStart behavior.

Parameters:
randomStart - whether the start index shall be chosen randomly or be set to 0
Method Detail

isRandomStart

public boolean isRandomStart()
Returns whether the starting index is chosen randomly or set to zero.

Returns:
true if the starting index is chosen randomly, false otherwise

crossover

public ChromosomePair crossover(Chromosome first,
                                Chromosome second)
                         throws DimensionMismatchException,
                                MathIllegalArgumentException
Perform a crossover operation on the given chromosomes.

Specified by:
crossover in interface CrossoverPolicy
Parameters:
first - the first chromosome.
second - the second chromosome.
Returns:
the pair of new chromosomes that resulted from the crossover.
Throws:
MathIllegalArgumentException - if the chromosomes are not an instance of AbstractListChromosome
DimensionMismatchException - if the length of the two chromosomes is different

mate

protected ChromosomePair mate(AbstractListChromosome<T> first,
                              AbstractListChromosome<T> second)
                       throws DimensionMismatchException
Helper for crossover(Chromosome, Chromosome). Performs the actual crossover.

Parameters:
first - the first chromosome
second - the second chromosome
Returns:
the pair of new chromosomes that resulted from the crossover
Throws:
DimensionMismatchException - if the length of the two chromosomes is different


Copyright (c) 2003-2013 Apache Software Foundation