org.jgap.impl
Class GreedyCrossover

java.lang.Object
  org.jgap.impl.GreedyCrossover

All Implemented Interfaces:

GeneticOperator, java.io.Serializable

public class GreedyCrossover

extends java.lang.Object

implements GeneticOperator

Greedy crossover can be best explained in the terms of the Traveling Salesman Problem: The algorithm selects the first city of one parent, compares the cities leaving that city in both parents, and chooses the closer one to extend the tour. If one city has already appeared in the tour, we choose the other city. If both cities have already appeared, we randomly select a non-selected city.

Since:

2.0

Author:

Audrius Meskauskas, Neil Rotstan, Klaus Meffert (reused code from CrossoverOperator)

See Also:

Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the Second International Conference on Genetic Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985. and also {@link http://ecsl.cs.unr.edu/docs/techreports/gong/node3.html Sushil J. Louis & Gong Li }, Serialized Form

Field Summary

static boolean

ASSERTIONS Switches assertions on.

Constructor Summary

GreedyCrossover()

Method Summary

double	distance(java.lang.Object a_from, java.lang.Object a_to) Compute the distance between "cities", indicated by these two given genes.
int	getStartOffset() Gets a number of genes at the start of chromosome, that are excluded from the swapping.
void	operate(Population a_population, java.util.List a_candidateChromosomes) The operate method will be invoked on each of the genetic operators referenced by the current Configuration object during the evolution phase.
void	setStartOffset(int a_offset) Sets a number of genes at the start of chromosome, that are excluded from the swapping.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ASSERTIONS

public static boolean ASSERTIONS

Switches assertions on. Must be true during tests and debugging.

Constructor Detail

GreedyCrossover

public GreedyCrossover()

Method Detail

distance

public double distance(java.lang.Object a_from,
                       java.lang.Object a_to)

Compute the distance between "cities", indicated by these two given genes. The default method expects the genes to be a IntegerGenes's and returns they absolute difference, that makes sense only for tests.

Parameters:

a_from - Object

a_to - Object

Returns:

double

operate

public void operate(Population a_population,
                    java.util.List a_candidateChromosomes)

Description copied from interface: GeneticOperator

The operate method will be invoked on each of the genetic operators referenced by the current Configuration object during the evolution phase. Operators are given an opportunity to run in the order that they are added to the Configuration. Implementations of this method may reference the population of Chromosomes as it was at the beginning of the evolutionary phase and/or they may instead reference the candidate Chromosomes, which are the results of prior genetic operators. In either case, only Chromosomes added to the list of candidate chromosomes will be considered for natural selection. Implementations should never modify the original population, but should first make copies of the Chromosomes selected for modification and operate upon the copies.

Specified by:

operate in interface GeneticOperator

Parameters:

a_population - The population of chromosomes from the current evolution prior to exposure to any genetic operators. Chromosomes in this array should never be modified.

a_candidateChromosomes - The pool of chromosomes that have been selected for the next evolved population.

setStartOffset

public void setStartOffset(int a_offset)

Sets a number of genes at the start of chromosome, that are excluded from the swapping. In the Salesman task, the first city in the list should (where the salesman leaves from) probably should not change as it is part of the list. The default value is 1.

Parameters:

a_offset - int

getStartOffset

public int getStartOffset()

Gets a number of genes at the start of chromosome, that are excluded from the swapping. In the Salesman task, the first city in the list should (where the salesman leaves from) probably should not change as it is part of the list. The default value is 1.

Returns:

the offset