search
Class GeneticSearch

java.lang.Object
  |
  +--search.GeneticSearch

public class GeneticSearch
extends java.lang.Object

The GeneticSearch class implements the genetic search algorithm as follows:

  1. initialize the population
  2. evaluate each chromosome and insert into the population
  3. create new chromosomes using crossover/mutation operators
  4. replace population with next generation
  5. loop until time is up or other stopping condition is reached


Field Summary
protected  double avgFitness
           
protected  int chromosomeLength
           
protected  double crossoverRate
           
protected  boolean debugOn
           
protected  double fitnessThreshold
           
protected  java.lang.Class geneticObjectClass
           
protected  java.lang.String geneticObjectClassName
           
protected  double maxFitness
           
protected  int maxNumPasses
           
protected  double minFitness
           
protected  double mutationRate
           
protected  int numPasses
           
protected  java.util.Hashtable operatorFitness
           
protected  java.util.Vector population
           
protected  int populationSize
           
protected  int replacementSize
           
protected  double[] summedFitness
           
protected  double totalFitness
           
protected  javax.swing.JTextArea traceTextArea
           
protected  java.lang.String vocabulary
           
 
Constructor Summary
GeneticSearch()
          Create a genetic search agent.
 
Method Summary
 GeneticSearchObject createChild(java.lang.String chromosome)
          Creates and initializes a child genetic object from a chromosome if it is unique or, if duplicates are allowed, even if it is not unique.
 GeneticSearchObject[] createChildren(java.lang.String[] chromosome)
          Creates and initializes new population members based on newly-derived chromosomes.
protected  java.util.Vector createNewMembers()
          Generates a number of population members through the application of genetic operators.
protected  void displayPopulation()
          Displays the entire population in the text window.
protected  void evaluatePopulation()
          Evaluates each population member based on fitness.
 double getAvgFitness()
          Gets the average raw fitness value for the current population.
 int getChromosomeLength()
          Gets the length of the chromosome for the current population.
 double getCrossoverRate()
          Gets the crossover rate.
 double getFitnessThreshold()
          Gets the raw fitness threshold value.
 java.lang.String getGeneticObjectClassName()
          Returns the name of the genetic object class.
 double getMaxFitness()
          Gets the maximum raw fitness value for the current population.
 int getMaxNumPasses()
          Gets the maximum number of generations to search.
 double getMinFitness()
          Gets the minimum raw fitness value for the current population.
 double getMutationRate()
          Get the current mutation rate.
 int getNumPasses()
          Gets the number of generations that have been searched.
 java.util.Hashtable getOperatorFitness()
          Gets the supported fitness operators and their fitness values.
 java.util.Vector getPopulation()
          Gets the entire population.
 int getPopulationSize()
          Gets the population size.
 int getReplacementSize()
          Gets the replacement size.
 java.lang.String getVocabulary()
          Get the chromosome vocabulary.
 void init()
          Initalizes the popualation.
protected  void insertIntoPopulation(GeneticSearchObject newMember, java.util.Vector list)
          Inserts a member into the population according to its raw fitness value.
protected  void integratePopulation(java.util.Vector newPopulation)
          Adds new members to the population.
 java.lang.String[] invokeOperator(java.lang.String operatorName, java.lang.String[] parents)
          Appies an operator to the parent chromosomes to create the child chromosomes.
 java.lang.String[] mutate(java.lang.String[] parents)
          Mutates two parent chromosomes, subject to the mutation rate, to create two children chromosomes.
 java.lang.String mutateChromosome(java.lang.String chromosome)
          Mutates a single chromosome by doing a bitwise test against the mutation rate and then rolling the dice to select a new bit value from the vocabulary.
 java.lang.String[] onePointCrossover(java.lang.String[] parents)
          Given two parent chromosomes, does a single-point crossover, creating two children chromosomes.
 java.lang.String[] onePointCrossoverAndMutate(java.lang.String[] parents)
          Given two parent chromosomes, does a single-point crossover, creating two children chromosomes and mutating bits at the specified rate
 void processOneGeneration()
          Processes one generation by evaluating each chromosome and insert it into the population, creating new chromosomes and members using crossover/mutation operators, and deleting members of the old population to make room for new members.
 void reset()
          Resets the population for another search.
 GeneticSearchObject rouletteWheelSelection()
          Selects a member of the population using the roulette wheel algorithm.
 void search()
          Does a complete genetic search by initializing the population then processing the population, one generation at a time until the maximum number of passes are made or the maximum fitness threshold is reached.
 java.lang.String selectOperator()
          Randomly selects an operator to be applied to the parents.
 GeneticSearchObject[] selectParents()
          Choose two population members to reproduce using the roulette wheel selection technique.
 void setCrossoverRate(double rate)
          Sets the crossoverRate which is used when a crossover operator is selected to determine whether a crossover will actually be performed.
 void setDebugOn(boolean debugOn)
          Sets the debug flag.
 void setFitnessThreshold(double thresh)
          Sets the raw fitness threshold which is used to halt the search if the raw fitness value exceeds this threshold.
 void setGeneticObjectClassName(java.lang.String aClassName)
          Sets the name of the class of genetic objects to be searched.
 void setMaxNumPasses(int num)
          Sets the maximum number of generations to search.
 void setMutationRate(double rate)
          Sets the mutation rate which is used when a mutate operator is selected to determine whether each bit is mutated or not.
 void setOperatorFitness(java.util.Hashtable opFitness)
          Sets table of fitness operators and fitness values that are used during reproduction.
 void setPopulationSize(int size)
          Sets the population size.
 void setReplacementSize(int size)
          Sets the number of population members to replace in each generation.
 void setTextArea(javax.swing.JTextArea j)
          Method setTextArea
protected  void trace(java.lang.String text)
          Writes trace data out to the text window.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

geneticObjectClass

protected java.lang.Class geneticObjectClass

population

protected java.util.Vector population

operatorFitness

protected java.util.Hashtable operatorFitness

chromosomeLength

protected int chromosomeLength

vocabulary

protected java.lang.String vocabulary

geneticObjectClassName

protected java.lang.String geneticObjectClassName

maxNumPasses

protected int maxNumPasses

fitnessThreshold

protected double fitnessThreshold

populationSize

protected int populationSize

replacementSize

protected int replacementSize

crossoverRate

protected double crossoverRate

mutationRate

protected double mutationRate

maxFitness

protected double maxFitness

minFitness

protected double minFitness

avgFitness

protected double avgFitness

totalFitness

protected double totalFitness

summedFitness

protected double[] summedFitness

numPasses

protected int numPasses

traceTextArea

protected javax.swing.JTextArea traceTextArea

debugOn

protected boolean debugOn
Constructor Detail

GeneticSearch

public GeneticSearch()
Create a genetic search agent.
Method Detail

setTextArea

public void setTextArea(javax.swing.JTextArea j)
Method setTextArea
Parameters:
j - the JTextArea object

setDebugOn

public void setDebugOn(boolean debugOn)
Sets the debug flag.
Parameters:
debugOn - the boolean value for the debug flag

init

public void init()
Initalizes the popualation.

processOneGeneration

public void processOneGeneration()
Processes one generation by evaluating each chromosome and insert it into the population, creating new chromosomes and members using crossover/mutation operators, and deleting members of the old population to make room for new members.

search

public void search()
Does a complete genetic search by initializing the population then processing the population, one generation at a time until the maximum number of passes are made or the maximum fitness threshold is reached.

setGeneticObjectClassName

public void setGeneticObjectClassName(java.lang.String aClassName)
Sets the name of the class of genetic objects to be searched.
Parameters:
aClassName - the String that represents the fully-specified (package prefixed) class name of the genetic objects to be searched

getGeneticObjectClassName

public java.lang.String getGeneticObjectClassName()
Returns the name of the genetic object class.
Returns:
the class name of the genetic object class

setPopulationSize

public void setPopulationSize(int size)
Sets the population size.
Parameters:
size - the integer value that represents the size of the population

getPopulationSize

public int getPopulationSize()
Gets the population size.
Returns:
the population size

getPopulation

public java.util.Vector getPopulation()
Gets the entire population.
Returns:
null if the population does not exist. Otherwise, returns the entire population vector.

setReplacementSize

public void setReplacementSize(int size)
Sets the number of population members to replace in each generation.
Parameters:
size - the number of members to be replaced

getReplacementSize

public int getReplacementSize()
Gets the replacement size.
Returns:
the number of members created or replaced each cycle

getVocabulary

public java.lang.String getVocabulary()
Get the chromosome vocabulary.
Returns:
the bit string that represents chromosome vocabulary

getNumPasses

public int getNumPasses()
Gets the number of generations that have been searched.
Returns:
the current generation number

setMaxNumPasses

public void setMaxNumPasses(int num)
Sets the maximum number of generations to search.
Parameters:
num - the maximum number of generations to search

getMaxNumPasses

public int getMaxNumPasses()
Gets the maximum number of generations to search.
Returns:
the maximum number of generations to search

setFitnessThreshold

public void setFitnessThreshold(double thresh)
Sets the raw fitness threshold which is used to halt the search if the raw fitness value exceeds this threshold.
Parameters:
thresh - the fitness threshold

getFitnessThreshold

public double getFitnessThreshold()
Gets the raw fitness threshold value.
Returns:
the fitness threshold

setCrossoverRate

public void setCrossoverRate(double rate)
Sets the crossoverRate which is used when a crossover operator is selected to determine whether a crossover will actually be performed.
Parameters:
rate - the double value for the crossover rate

getCrossoverRate

public double getCrossoverRate()
Gets the crossover rate.
Returns:
the crossover rate

setMutationRate

public void setMutationRate(double rate)
Sets the mutation rate which is used when a mutate operator is selected to determine whether each bit is mutated or not.
Parameters:
rate - the double value for the mutation rate

getMutationRate

public double getMutationRate()
Get the current mutation rate.
Returns:
the mutation rate

getAvgFitness

public double getAvgFitness()
Gets the average raw fitness value for the current population.
Returns:
the average raw fitness value

getMinFitness

public double getMinFitness()
Gets the minimum raw fitness value for the current population.
Returns:
the minimum raw fitness value

getMaxFitness

public double getMaxFitness()
Gets the maximum raw fitness value for the current population.
Returns:
the maximum raw fitness value

getChromosomeLength

public int getChromosomeLength()
Gets the length of the chromosome for the current population.
Returns:
the chromosome length

setOperatorFitness

public void setOperatorFitness(java.util.Hashtable opFitness)
Sets table of fitness operators and fitness values that are used during reproduction.
Parameters:
opFitness - a Hashtable of fitness operators and fitness values (selection probabilities). The sum of the fitness values should equal 100.

getOperatorFitness

public java.util.Hashtable getOperatorFitness()
Gets the supported fitness operators and their fitness values.
Returns:
the fitness operator table

createChildren

public GeneticSearchObject[] createChildren(java.lang.String[] chromosome)
Creates and initializes new population members based on newly-derived chromosomes.
Parameters:
chromosome - a String array of chromosomes
Returns:
an array of GeneticSearchObjects

createChild

public GeneticSearchObject createChild(java.lang.String chromosome)
Creates and initializes a child genetic object from a chromosome if it is unique or, if duplicates are allowed, even if it is not unique.
Parameters:
chromosome - the String representation of the child chromosome
Returns:
the fully-initialized child population member or null, if the child could not be created

evaluatePopulation

protected void evaluatePopulation()
Evaluates each population member based on fitness.

createNewMembers

protected java.util.Vector createNewMembers()
Generates a number of population members through the application of genetic operators. If the replacement size equals the population size, elitism is used to carry over the member with the highest fitness.
Returns:
a new population of members

integratePopulation

protected void integratePopulation(java.util.Vector newPopulation)
Adds new members to the population. This implementation simply replaces the previous population with the new population.
Parameters:
newPopulation - a Vector of new genetic objects to be added to the population

insertIntoPopulation

protected void insertIntoPopulation(GeneticSearchObject newMember,
                                    java.util.Vector list)
Inserts a member into the population according to its raw fitness value.
Parameters:
newMember - the GeneticSearchObject to insert into the population
list - the Vector that contains the population

selectParents

public GeneticSearchObject[] selectParents()
Choose two population members to reproduce using the roulette wheel selection technique.
Returns:
the two population members

selectOperator

public java.lang.String selectOperator()
Randomly selects an operator to be applied to the parents. The total operator fitness must be equal to 100.
Returns:
the name of the selected operator

rouletteWheelSelection

public GeneticSearchObject rouletteWheelSelection()
Selects a member of the population using the roulette wheel algorithm.
Returns:
a single member of the population chosen at random

reset

public void reset()
Resets the population for another search.

invokeOperator

public java.lang.String[] invokeOperator(java.lang.String operatorName,
                                         java.lang.String[] parents)
Appies an operator to the parent chromosomes to create the child chromosomes.
Parameters:
operatorName - the String name of operator to be invoked
parents - the String array that contains parent chromosomes
Returns:
the set of children chromosomes that were created

onePointCrossoverAndMutate

public java.lang.String[] onePointCrossoverAndMutate(java.lang.String[] parents)
Given two parent chromosomes, does a single-point crossover, creating two children chromosomes and mutating bits at the specified rate
Parameters:
parents - the String array that contains the parent chromosomes from which two children chromosomes are created
Returns:
the set of children chromosomes created from parent chromosomes

mutateChromosome

public java.lang.String mutateChromosome(java.lang.String chromosome)
Mutates a single chromosome by doing a bitwise test against the mutation rate and then rolling the dice to select a new bit value from the vocabulary.
Parameters:
chromosome - the String that represents the original chromosome
Returns:
the (potentially) mutated chromosome string

onePointCrossover

public java.lang.String[] onePointCrossover(java.lang.String[] parents)
Given two parent chromosomes, does a single-point crossover, creating two children chromosomes.
Parameters:
parents - the String array that contains the parent chromosomes from which the children are created
Returns:
the set of children chromosomes created from parent chromosomes

mutate

public java.lang.String[] mutate(java.lang.String[] parents)
Mutates two parent chromosomes, subject to the mutation rate, to create two children chromosomes.
Parameters:
parents - the String array that represent the parent chromosomes
Returns:
the set of potentially mutated children chromosomes

trace

protected void trace(java.lang.String text)
Writes trace data out to the text window.
Parameters:
text - the String object that contains

displayPopulation

protected void displayPopulation()
Displays the entire population in the text window.