com.softtechdesign.ga
Class GA

java.lang.Object
  |
  +--com.softtechdesign.ga.GA

All Implemented Interfaces:

java.lang.Runnable

Direct Known Subclasses:

GAFloat, GAString, GAStringsSeq

public abstract class GA

extends java.lang.Object

implements java.lang.Runnable

 Package ga
 --------------------------------------------------------------------------------------------
 The GAFloat, GAString, and GASequenceList classes all extend the GA class and can be used
 to model different populations of candidate solutions. You will generally have to extend
 one of these classes every time you create a new GA. In the simplest cases, you will subclass
 one of these classes and then just override and implement your own GetFitness() function. The
 three main subclasses of GA are:
   GAString (chromosomes are stored as strings)
   GAFloat (chromosomes are stored as floating point numbers)
   GASequenceList (chromosomes are stored as strings, additional methods in this class handle
                   sorting sequences. For example, the GASalesman class extends GASequenceList)

 For example:
   If your chromosomes are floating point numbers, you should subclass TGAFloat and override
   the getFitness() function with your own.

   If your chromosomes are strings, you should subclass TGAString and override the
   getFitness() function with your own.

   If your chromosomes are characters in a sequence (or list) that needs to be rearranged, you
   should use TGASequenceList and override the getFitness() function with your own.
 ---------------------------------------------------------------------------------------------
 
  This main abstract class is extended by the 3 main GA subclasses:
  GAString, GAFloat, GASequenceList
  It (obviously) contains the methods common to all GA subclasses
 

Author:

Jeff Smith jeff@SoftTechDesign.com

Field Summary

(package private) int	bestFitnessChromIndex index of fittest chromosome in current generation
(package private) Chromosome[]	chromNextGen storage for temporary holding pool for next generation chromosomes
protected int	chromosomeDim dimension of chromosome (number of genes)
(package private) Chromosome[]	chromosomes storage for pool of chromosomes for current generation
(package private) boolean	computeStatistics compute statistics for each generation during evolution?
(package private) double	crossoverProb probability that a crossover will occur during genetic mating
protected int	crossoverType type of crossover to be employed during genetic mating
(package private) double[]	genAvgDeviation statistics--average deviation of current generation
(package private) double[]	genAvgFitness statistics--average fitness of current generation
(package private) int	maxGenerations maximum generations to evolve
(package private) int	maxPrelimGenerations prelim generations.
(package private) double	mutationProb probability of a mutation occuring during genetic mating.
(package private) int	numPrelimRuns number of prelim generations to evolve.
protected int	populationDim number of chromosomes to evolve.
(package private) Chromosome[]	prelimChrom storage for pool of prelim generation chromosomes
(package private) int	randomSelectionChance 1-100 (e.g.
(package private) int	worstFitnessChromIndex index of least fit chromosome in current generation

Constructor Summary

GA(int chromosomeDim, int populationDim, double crossoverProb, int randomSelectionChance, int maxGenerations, int numPrelimRuns, int maxPrelimGenerations, double mutationProb, int crossoverType, boolean computeStatistics)
Initializes the GA using given parameters

Method Summary

(package private) void	addChromosomesToLog(int iGeneration, int iNumChromosomesToDisplay) Display chromosome information to System.out
(package private) long	binaryStrToInt(java.lang.String sBinary) Take a binary string and convert it to the long integer.
(package private) void	computeFitnessRankings() Calculate rankings for all chromosomes.
(package private) void	copyNextGenToThisGen() Copy the chromosomes previously created and stored in the "next" generation into the main chromsosome memory pool.
(package private) void	doGeneticMating() Create the next generation of chromosomes by genetically mating fitter individuals of the current generation.
protected abstract void	doOnePtCrossover(Chromosome Chrom1, Chromosome Chrom2) do one point crossover between the two given chromosomes
protected abstract void	doRandomMutation(int iChromIndex) do a random mutation on given chromosome
protected abstract void	doTwoPtCrossover(Chromosome Chrom1, Chromosome Chrom2) do two point crossover between the two given chromosomes
protected abstract void	doUniformCrossover(Chromosome Chrom1, Chromosome Chrom2) do uniform crossover between the two given chromosomes
int	evolve() Main routine that runs the evolution simulation for this population of chromosomes.
double	getAvgDeviation(int iGeneration) Gets the average deviation of the given generation of chromosomes
protected double	getAvgDeviationAmongChroms() Get the average deviation from the current population of chromosomes.
double	getAvgFitness() Go through all chromosomes and calculate the average fitness (of this generation)
double	getAvgFitness(int iGeneration) Gets the average fitness of the given generation of chromosomes
int	getChromosomeDim() Gets the dimension (size or number) of genes per chromosome
boolean	getComputeStatistics() Returns whether statistics will be computed for this evolution run
double	getCrossoverProb() Gets the crossover probability
int	getCrossoverType() Gets the crossover type (e.g.
protected abstract double	getFitness(int iChromIndex) get the fitness value for the given chromosome
(package private) int	getFitnessRank(double fitness) Calculate the ranking of the parameter "fitness" with respect to the current generation.
Chromosome	getFittestChromosome() Returns the fittest chromosome in the population
double	getFittestChromosomesFitness() Gets the fitness value of the fittest chromosome in the population
int	getMaxGenerations() Gets the maximum number of generations this evolution will evolve
int	getMaxPrelimGenerations() Gets the maximum number of preliminary generations to evolve
double	getMutationProb() Returns the mutation probability
int	getNumPrelimRuns() Gets the number of preliminary runs that will be performed before the main evolution begins
int	getPopulationDim() Gets the dimension (size or number) of chromosomes in the population
(package private) double	getRandom(double upperBound) return a double random number between 0 and upperBound
(package private) int	getRandom(int upperBound) return a integer random number between 0 and upperBound
int	getRandomSelectionChance() Gets the random selection probability
protected abstract void	initPopulation() initialize the population (chromosomes) to random values
void	run() Runs the evolution by calling evolve() routine
void	selectTwoParents(int[] indexParents) Select two parents from population, giving highly fit individuals a greater chance of being selected.

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

mutationProb

double mutationProb

probability of a mutation occuring during genetic mating. For example, 0.03 means 3% chance

maxGenerations

int maxGenerations

maximum generations to evolve

numPrelimRuns

int numPrelimRuns

number of prelim generations to evolve. Set to zero to disable

maxPrelimGenerations

int maxPrelimGenerations

prelim generations. Prelim runs are useful for building fitter "starting" chromosome stock before the main evolution run.

randomSelectionChance

int randomSelectionChance

1-100 (e.g. 10 = 10% chance of random selection--not based on fitness). Setting nonzero randomSelectionChance helps maintain genetic diversity during evolution

crossoverProb

double crossoverProb

probability that a crossover will occur during genetic mating

chromosomeDim

protected int chromosomeDim

dimension of chromosome (number of genes)

populationDim

protected int populationDim

number of chromosomes to evolve. A larger population dim will result in a better evolution but will slow the process down

chromosomes

Chromosome[] chromosomes

storage for pool of chromosomes for current generation

chromNextGen

Chromosome[] chromNextGen

storage for temporary holding pool for next generation chromosomes

prelimChrom

Chromosome[] prelimChrom

storage for pool of prelim generation chromosomes

bestFitnessChromIndex

int bestFitnessChromIndex

index of fittest chromosome in current generation

worstFitnessChromIndex

int worstFitnessChromIndex

index of least fit chromosome in current generation

crossoverType

protected int crossoverType

type of crossover to be employed during genetic mating

genAvgDeviation

double[] genAvgDeviation

statistics--average deviation of current generation

genAvgFitness

double[] genAvgFitness

statistics--average fitness of current generation

computeStatistics

boolean computeStatistics

compute statistics for each generation during evolution?

Constructor Detail

GA

public GA(int chromosomeDim,
          int populationDim,
          double crossoverProb,
          int randomSelectionChance,
          int maxGenerations,
          int numPrelimRuns,
          int maxPrelimGenerations,
          double mutationProb,
          int crossoverType,
          boolean computeStatistics)

Initializes the GA using given parameters

Parameters:

chromosomeDim -

populationDim -

crossoverProb -

randomSelectionChance -

maxGenerations -

numPrelimRuns -

maxPrelimGenerations -

mutationProb -

crossoverType -

computeStatistics -

Method Detail

initPopulation

protected abstract void initPopulation()

initialize the population (chromosomes) to random values

doRandomMutation

protected abstract void doRandomMutation(int iChromIndex)

do a random mutation on given chromosome

doOnePtCrossover

protected abstract void doOnePtCrossover(Chromosome Chrom1,
                                         Chromosome Chrom2)

do one point crossover between the two given chromosomes

doTwoPtCrossover

protected abstract void doTwoPtCrossover(Chromosome Chrom1,
                                         Chromosome Chrom2)

do two point crossover between the two given chromosomes

doUniformCrossover

protected abstract void doUniformCrossover(Chromosome Chrom1,
                                           Chromosome Chrom2)

do uniform crossover between the two given chromosomes

getFitness

protected abstract double getFitness(int iChromIndex)

get the fitness value for the given chromosome

run

public void run()

Runs the evolution by calling evolve() routine

Specified by:

run in interface java.lang.Runnable

getAvgDeviation

public double getAvgDeviation(int iGeneration)

Gets the average deviation of the given generation of chromosomes

Parameters:

iGeneration -

Returns:

getAvgFitness

public double getAvgFitness(int iGeneration)

Gets the average fitness of the given generation of chromosomes

Parameters:

iGeneration -

Returns:

getMutationProb

public double getMutationProb()

Returns the mutation probability

Returns:

double

getMaxGenerations

public int getMaxGenerations()

Gets the maximum number of generations this evolution will evolve

Returns:

int

getNumPrelimRuns

public int getNumPrelimRuns()

Gets the number of preliminary runs that will be performed before the main evolution begins

Returns:

int

getMaxPrelimGenerations

public int getMaxPrelimGenerations()

Gets the maximum number of preliminary generations to evolve

Returns:

int

getRandomSelectionChance

public int getRandomSelectionChance()

Gets the random selection probability

Returns:

int

getCrossoverProb

public double getCrossoverProb()

Gets the crossover probability

Returns:

double

getChromosomeDim

public int getChromosomeDim()

Gets the dimension (size or number) of genes per chromosome

Returns:

int

getPopulationDim

public int getPopulationDim()

Gets the dimension (size or number) of chromosomes in the population

Returns:

int

getCrossoverType

public int getCrossoverType()

Gets the crossover type (e.g. one point, two point, uniform, roulette)

Returns:

getComputeStatistics

public boolean getComputeStatistics()

Returns whether statistics will be computed for this evolution run

Returns:

boolean

getFittestChromosome

public Chromosome getFittestChromosome()

Returns the fittest chromosome in the population

Returns:

Chromosome

getFittestChromosomesFitness

public double getFittestChromosomesFitness()

Gets the fitness value of the fittest chromosome in the population

Returns:

double

getRandom

int getRandom(int upperBound)

return a integer random number between 0 and upperBound

Parameters:

upperBound -

Returns:

int

getRandom

double getRandom(double upperBound)

return a double random number between 0 and upperBound

Parameters:

upperBound -

Returns:

double

evolve

public int evolve()

Main routine that runs the evolution simulation for this population of chromosomes.

Returns:

number of generations

getAvgFitness

public double getAvgFitness()

Go through all chromosomes and calculate the average fitness (of this generation)

Returns:

double

selectTwoParents

public void selectTwoParents(int[] indexParents)

Select two parents from population, giving highly fit individuals a greater chance of being selected.

Parameters:

indexParents -

getFitnessRank

int getFitnessRank(double fitness)

Calculate the ranking of the parameter "fitness" with respect to the current generation. If the fitness is high, the corresponding fitness ranking will be high, too. For example, if the fitness passed in is higher than any fitness value for any chromosome in the current generation, the fitnessRank will equal the populationDim. And if the fitness is lower than any fitness value for any chromosome in the current generation, the fitnessRank will equal zero.

Parameters:

fitness -

Returns:

int the fitness ranking

computeFitnessRankings

void computeFitnessRankings()

Calculate rankings for all chromosomes. High ranking numbers denote very fit chromosomes.

doGeneticMating

void doGeneticMating()

Create the next generation of chromosomes by genetically mating fitter individuals of the current generation. Also employ elitism (so the fittest 2 chromosomes always survive to the next generation). This way an extremely fit chromosome is never lost from our chromosome pool.

copyNextGenToThisGen

void copyNextGenToThisGen()

Copy the chromosomes previously created and stored in the "next" generation into the main chromsosome memory pool. Perform random mutations where appropriate.

addChromosomesToLog

void addChromosomesToLog(int iGeneration,
                         int iNumChromosomesToDisplay)

Display chromosome information to System.out

Parameters:

iGeneration -

iNumChromosomesToDisplay -

getAvgDeviationAmongChroms

protected double getAvgDeviationAmongChroms()

Get the average deviation from the current population of chromosomes. The smaller this deviation, the higher the convergence is to a particular (but not necessarily optimal) solution. It calculates this deviation by determining how many genes in the populuation are different than the bestFitGenes. The more genes which are "different", the higher the deviation.

Returns:

binaryStrToInt

long binaryStrToInt(java.lang.String sBinary)

Take a binary string and convert it to the long integer. For example, '1101' --> 13

Parameters:

sBinary -

Returns:

long