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