All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class gpjpp.GPPopulation

java.lang.Object
   |
   +----gpjpp.GPObject
           |
           +----gpjpp.GPContainer
                   |
                   +----gpjpp.GPPopulation

public class GPPopulation

extends GPContainer

GPPopulation includes references to the GPVariables configuration of the run and the GPAdfNodeSet set of node types. These references are passed as parameters to lower level classes when needed.

GPPopulation has several public data fields that can be used by the calling program to obtain the status of the population. These include bestOfPopulation (the index of the individual with the best fitness), worstOfPopulation, attemptedDupCount (the number of duplicate individuals detected but rejected when creating the initial population), and others.

Although GPPopulation represents a single population of individuals, it is designed to work with either a single population (steady state evolution) or two populations (generational evolution). This behavior is implemented in the generate() method.

The user must always create a subclass of GPPopulation for use in solving a particular problem. This subclass must override the createGP() method, which creates a GP of user type. That GP subclass must in turn override the evaluate() method to compute fitness for the target problem.

Otherwise, the typical details of using GPPopulation are encapsulated in the GPRun class.

Version:

1.0

adfNs

A reference to the functions and terminals for the run.

attemptedComplexCount

The number of individuals that were created for generation 0 but rejected because their complexity exceeded the global configuration variable MaximumComplexity.

attemptedDupCount

The number of duplicate individuals that were created in generation 0 but rejected.

avgDepth

Average tree depth of the entire population.

avgFitness

Average fitness of the entire population.

avgLength

Average complexity of the entire population.

bestFitness

Best standardized fitness found in the entire population.

bestOfPopulation

The index of the individual with the best standardized fitness.

cfg

A reference to the global configuration variables for the run.

cutoffAdjFitness

The cutoff fitness for an individual to get into group I.

dupCount

The number of duplicate individuals in the current generation.

longestLength

The highest complexity found anywhere in the population.

minTreeDepth

Specifies the minimum tree depth for newly created individuals.

sumAdjFitness

The sum of the adjusted fitness over an entire range.

sumFitness

The sum of the standardized fitness over an entire range.

sumG1AdjFitness

The sum of the adjusted fitness for group I individuals.

sumG2AdjFitness

The sum of the adjusted fitness for group II individuals.

uniqueGPs

A table of the unique GPs found in the population.

worstFitness

Worst standardized fitness found in the entire population.

worstOfPopulation

The index of the individual with the worst standardized fitness.

GPPopulation()

Public null constructor used during stream loading only.

GPPopulation(GPPopulation)

A constructor that can be called to clone a population.

GPPopulation(GPVariables, GPAdfNodeSet)

Constructor used when populations are first created.

addBest(GPPopulation)

Adds the best individual from this generation to the next.

buildUniqueGPs()

Clears the diversity table and calls updateUniqueGPs for each individual in the population.

calcCutoffFitness(GPPopulationRange)

Computes the adjusted fitness boundary that separates group I from group II individuals using Koza's form of greedy over-selection.

calcGroupIFraction(int)

Calculates Koza's c constant for greedy over-selection.

calculateStatistics()

Calculates statistics about a complete population, including the best, average, and worst fitness, complexity, and depth.

checkForDiversity(GP)

Returns true if the specified GP is not already in the diversity table or if cfg.TestDiversity is false.

clearUniqueGPs()

Creates or clears the diversity table and the dupCount and attemptedDupCount fields.

clone()

Implements the Cloneable interface.

create()

Creates all of the individuals in an initial population.

createGP(int)

Creates the GP used for a new individual.

demeticMigration()

Based on the configuration variable DemeticMigProbability, fitness-selects a good individual from each deme and exchanges it with a good individual from the next deme.

evolve(GPPopulationRange)

Based on the configuration variables CrossoverProbability and CreationProbability, creates two individuals using crossover or one new individual using creation (a brand-new GP) or reproduction (a fitness-selected copy of an existing individual).

formatDouble(double, int, int)

Converts a double to a string right justified in a field of specified width.

formatInt(int, int)

Converts an integer to a string right-justified in a field of specified width.

formatParentage(int, int, int, int)

Formats a string that shows the heritage of a crossover, reproduction, or mutation operation.

generate(GPPopulation)

Generates the next generation of individuals using genetic processes.

getUniqueGPsSize()

Computes the size of the hash table used for diversity checking.

greedySelection(int[], int, boolean, GPPopulationRange)

Selects one or more individuals from the specified range of the population by using Koza's "greedy over-selection".

isA()

Returns a code identifying the class in a stream file.

load(DataInputStream)

Loads a GPPopulation from the specified stream.

overflow(int)

Returns a string of asterisks with specified width.

printDetails(int, boolean, boolean, boolean, boolean, boolean, PrintStream)

Prints details about some or all of the population.

printIndividual(GP, int, boolean, boolean, PrintStream)

Prints details about a particular individual to the specified PrintStream.

printOn(PrintStream, GPVariables)

Writes every GP in text format to a PrintStream by simply calling GP.printOn() for every individual in the population.

printStatistics(int, char, PrintStream)

Prints one generation's statistics to the specified PrintStream.

printStatisticsLegend(PrintStream)

Prints a legend line for the standard statistics report to the specified PrintStream.

probabilisticSelection(int[], int, boolean, GPPopulationRange)

Selects one or more individuals from the specified range of the population by using a roulette algorithm.

select(int, GPPopulationRange)

Returns one or more individuals from the specified range of this population using a fitness-based selection method.

selectIndices(int[], int, boolean, GPPopulationRange)

Calls one of the available selection methods based on the configuration variable SelectionType.

selectParents(GPPopulationRange)

Calls select() to select exactly two parents for use in crossover.

sumFitnessRange(GPPopulationRange)

Sums the standardized and adjusted fitnesses over a specified range and stores the results in the fields sumFitness and sumAdjFitness.

tournamentSelection(int[], int, boolean, GPPopulationRange)

Selects one or two individuals from the specified range of the population by using a tournament algorithm.

trimFormatDouble(double, int, int)

Calls formatDouble to create a formatted string and then strips any leading blanks.

updateUniqueGPs(GP)

Adds the specified GP to the diversity table, or increments its count if already in the table.

  protected static int minTreeDepth

Specifies the minimum tree depth for newly created individuals. Default value 2.

  protected double sumAdjFitness

The sum of the adjusted fitness over an entire range. Used for probabilistic and greedy selection only.

  protected double cutoffAdjFitness

The cutoff fitness for an individual to get into group I. Used for greedy selection only.

  protected double sumG1AdjFitness

The sum of the adjusted fitness for group I individuals. Used for greedy selection only.

  protected double sumG2AdjFitness

The sum of the adjusted fitness for group II individuals. Used for greedy selection only.

  protected double sumFitness

The sum of the standardized fitness over an entire range.

  protected GPVariables cfg

A reference to the global configuration variables for the run.

  protected GPAdfNodeSet adfNs

A reference to the functions and terminals for the run.

  protected double avgFitness

Average fitness of the entire population. Used in probabilistic selection and reported by printStatistics(). Calculated in calculateStatistics().

  protected double avgLength

Average complexity of the entire population. Reported by printStatistics() and calculated in calculateStatistics().

  protected double avgDepth

Average tree depth of the entire population. Reported by printStatistics() and calculated in calculateStatistics().

  public double bestFitness

Best standardized fitness found in the entire population. Reported by printStatistics() and calculated in calculateStatistics().

  public double worstFitness

Worst standardized fitness found in the entire population. Reported by printStatistics() and calculated in calculateStatistics().

  public int bestOfPopulation

The index of the individual with the best standardized fitness. In case of ties, the lower complexity wins. The GP associated with this index is obtained by (GP)pop.get(bestOfPopulation).

  public int worstOfPopulation

The index of the individual with the worst standardized fitness. In case of ties, the higher complexity wins. The GP associated with this index is obtained by (GP)pop.get(worstOfPopulation).

  public int longestLength

The highest complexity found anywhere in the population. This may differ from the complexity of the individual that has the worst fitness. longestLength is calculated in printStatistics() but is not printed in any standard reports.

  protected Hashtable uniqueGPs

A table of the unique GPs found in the population. This table is created and updated only if the TestDiversity configuration option is enabled. Each unique GP is entered in the table along with a count of the times it appears in the population. When TestDiversity is enabled, the initial population is guaranteed to be 100% diverse by rejecting any individuals that already appear in the table. For successive generations, duplicates are allowed but the diversity is reported by printStatistics(). The Hashtable approach to tracking diversity is fast enough that the option can be left on at all times.

  public int dupCount

The number of duplicate individuals in the current generation. For the initial generation, this number is always 0. dupCount is not printed in any standard reports, but the diversity ratio (1-dupCount/popSize) is reported by printStatistics().

  public int attemptedDupCount

The number of duplicate individuals that were created in generation 0 but rejected. When diversity checking is enabled generation 0 is guaranteed to be 100% diverse. attemptedDupCount is printed among the standard output of the GPRun class.

  public int attemptedComplexCount

The number of individuals that were created for generation 0 but rejected because their complexity exceeded the global configuration variable MaximumComplexity. attemptedComplexCount is printed among the standard output of the GPRun class.

  public GPPopulation()

Public null constructor used during stream loading only.

  public GPPopulation(GPVariables cfg,
                      GPAdfNodeSet adfNs)

Constructor used when populations are first created. This constructor creates a container capable of holding the population individuals, but does not create the individuals. It also performs a number of consistency checks on the configuration variables and node set.

Parameters:

cfg - the global configuration variables

adfNs - the set of node types for all branches

Throws: RuntimeException

if any problems are found in the configuration. The exception message provides more details.

See Also:

create

  public GPPopulation(GPPopulation gpo)

A constructor that can be called to clone a population. Normally not used.

  protected synchronized Object clone()

Implements the Cloneable interface. This clones a GPPopulation but is normally not used.

Returns:

the cloned object.

Overrides:

clone in class GPContainer

  public byte isA()

Returns a code identifying the class in a stream file.

Returns:

the ID code POPULATIONID.

Overrides:

isA in class GPContainer

  public GP createGP(int numOfTrees)

Creates the GP used for a new individual. The user must override this in a subclass to create GPs of user type. See the example programs.

Parameters:

numOfTrees - the number of branches in the genetic program.

Returns:

the newly created GP.

  protected int getUniqueGPsSize()

Computes the size of the hash table used for diversity checking. It equals an odd number just larger than twice the population size, which should generally avoid having to expand the diversity table after it is created.

  protected void clearUniqueGPs()

Creates or clears the diversity table and the dupCount and attemptedDupCount fields. If TestDiversity is false, does nothing.

  protected void updateUniqueGPs(GP gp)

Adds the specified GP to the diversity table, or increments its count if already in the table. If TestDiversity is false, does nothing.

  protected void buildUniqueGPs()

Clears the diversity table and calls updateUniqueGPs for each individual in the population. If TestDiversity is false, does nothing.

  protected boolean checkForDiversity(GP gp)

Returns true if the specified GP is not already in the diversity table or if cfg.TestDiversity is false. If the GP is already in the table, returns false and increments attemptedDupCount. Used when creating an initial population.

  public void create()

Creates all of the individuals in an initial population. If cfg.TestForDiversity is true, tries up to 50 times per individual to create a unique GP. Also tries up to 50 times per individual to create GPs whose complexity is less than cfg.MaximumComplexity and increments attemptedComplexCount for each individual that fails.

The depth of each GP is guaranteed to fall in the range GPPopulation.minTreeDepth (2) to cfg.MaximumDepthForCreation (6 by default).

create() calls GP.create() to create each individual in the population.

create() uses one of several tree-building strategies depending on the value of the configuration variable CreationType. If this variable equals GPRAMPEDHALF (the default), alternating individuals are created using GPGROW (function nodes to maximum depth) and GPVARIABLE (nodes chosen with a 50:50 probability of being a function or a terminal). With GPRAMPEDHALF, the depth of successive individuals is ramped from minTreeDepth to MaximumDepthForCreation and back again.

If CreationType equals GPRAMPEDVARIABLE, all individuals are created using the GPVARIABLE strategy and the depth of successive individuals is ramped from minTreeDepth to MaximumDepthForCreation.

If CreationType equals GPRAMPEDGROW, all individuals are created using the GPGROW strategy and the depth of successive individuals is ramped.

If CreationType equals GPGROW, all individuals are created using the GPGROW strategy with depth MaximumDepthForCreation.

If CreationType equals GPVARIABLE, all individuals are created using the GPVARIABLE strategy with depth MaximumDepthForCreation.

If a unique individual is not found in 50/4 tries, the tree depth is incremented for each try thereafter, up to a maximum of MaximumDepthForCreation.

If an individual of acceptable complexity is not found in 50/4 tries, the tree depth is decremented for each try thereafter, down to a minimum of minTreeDepth.

If no acceptable individual is found after 50 tries, a RuntimeException is thrown.

After each individual is created, its fitness is calculated by calling GP.evaluate(). After all individuals are created, calculateStatistics() is called.

  protected void tournamentSelection(int selected[],
                                     int numToSelect,
                                     boolean selectWorst,
                                     GPPopulationRange range)

Selects one or two individuals from the specified range of the population by using a tournament algorithm. numToSelect individuals are randomly selected from the specified range and their indexes stored in the selected array. Standardized fitness is used to define "best" and complexity is used to break ties. The tournament size is given by the configuration variable TournamentSize.

Parameters:

selected - an array that, upon return, must contain the indices of the selected individuals.

numToSelect - the number of individuals to select. The value must be 1 or 2.

selectWorst - true if the routine is to select the worst individuals from the range, false to select the best.

range - the range of indices from which to select. Unless demetic migration is enabled, this is the entire population.

Throws: RuntimeException

if numToSelect is greater than 2.

  protected void sumFitnessRange(GPPopulationRange range)

Sums the standardized and adjusted fitnesses over a specified range and stores the results in the fields sumFitness and sumAdjFitness. Used internally.

  protected void probabilisticSelection(int selected[],
                                        int numToSelect,
                                        boolean selectWorst,
                                        GPPopulationRange range)

Selects one or more individuals from the specified range of the population by using a roulette algorithm. Each individual in the specified range has a probability of selection equal to its fitness divided by the sum total fitness of all individuals in the range. Complexity does not play a role in the selection unless it has already been factored into the fitness. All fitness values must be non-negative or this method may hang or produce unexpected results. When selectWorst is false, adjusted fitness is used; otherwise standardized fitness is used.

Parameters:

selected - an array that, upon return, must contain the indices of the selected individuals.

numToSelect - the number of individuals to select. The value must be 1 or more.

selectWorst - true if the routine is to select the worst individuals from the range, false to select the best.

range - the range of indices from which to select. Unless demetic migration is enabled, this is the entire population.

  protected double calcGroupIFraction(int size)

Calculates Koza's c constant for greedy over-selection. Returns 0.32 for range size 1000 or less, and 320/size for any larger range size.

  protected void calcCutoffFitness(GPPopulationRange range)

Computes the adjusted fitness boundary that separates group I from group II individuals using Koza's form of greedy over-selection. First calculates the fitness proportion c, which Koza defines to be 0.32 at population size 1000, 0.16 at 2000, 0.08 at 4000, and so on. For populations less than 1000, a constant value of 0.32 is used. Then uses binary search to find a boundary such that the sum of adjusted fitness for individuals whose fitness is greater than the boundary equals c times the total adjusted fitness. The search doesn't need to be too accurate since c is largely arbitrary anyway, so the search stops when the normalized sum is within 0.005 of c.

The routine stores values in the fields cutoffAdjFitness, sumG1AdjFitness, and sumG2AdjFitness. It assumes that sumAdjFitness has already been calculated by calling sumFitnessRange().

Parameters:

range - the range of indices from which to select. Demetic migration is always disabled when greedy selection is enabled, so this is the entire population. The routine would work for restricted ranges, but this would run counter to Koza's assumptions.

See Also:

calcGroupIFraction

  protected void greedySelection(int selected[],
                                 int numToSelect,
                                 boolean selectWorst,
                                 GPPopulationRange range)

Selects one or more individuals from the specified range of the population by using Koza's "greedy over-selection". This divides the population into two groups based on an adjusted fitness boundary, such that the sum of the adjusted fitness for the first, higher-fitness group has a specified proportion c of the total adjusted fitness. By Koza's definition c equals 0.32 for population size 1000, 0.16 for 2000, 0.08 for 4000, and so on. Then, 80% of the time the method returns an individual from group I using probabilistic selection and the other 20% it returns an individual from group II using probabilistic selection.

Parameters:

selected - an array that, upon return, must contain the indices of the selected individuals.

numToSelect - the number of individuals to select. The value must be 1 or more.

selectWorst - true if the routine is to select the worst individuals from the range, false to select the best.

range - the range of indices from which to select. Demetic migration is always disabled when greedy selection is enabled, so this is the entire population.

See Also:

sumFitnessRange, calcCutoffFitness

  protected void selectIndices(int selected[],
                               int numToSelect,
                               boolean selectWorst,
                               GPPopulationRange range)

Calls one of the available selection methods based on the configuration variable SelectionType. Override this method if you want to implement a new selection technique.

Throws: RuntimeException

if numToSelect is less than 1, or if the specified range is empty, or if an unknown selection method is specified.

See Also:

tournamentSelection, probabilisticSelection, greedySelection

  protected synchronized GPContainer select(int numToSelect,
                                            GPPopulationRange range)

Returns one or more individuals from the specified range of this population using a fitness-based selection method. The returned individuals are cloned copies from this population so that they can be modified (via crossover or mutation) without disturbing the existing population. select() also updates the heritage fields of the cloned individuals to indicate their parent(s). This method uses two preallocated (private) containers of length 1 and 2 to return the individuals in order to avoid allocating new arrays every time the routine is called.

Parameters:

numToSelect - the number of individuals to select. The value must be 1 or 2. One is used to select an individual to reproduce; two is used to select two parents for crossover.

range - the range of indices from which to select. Unless demetic migration is enabled, this is the entire population.

Returns:

an array of GP references holding the selected individuals. The length of the array exactly matches the number of individuals in it.

Throws: RuntimeException

if numToSelect is not 1 or 2.

  protected GPContainer selectParents(GPPopulationRange range)

Calls select() to select exactly two parents for use in crossover.

  protected synchronized GPContainer evolve(GPPopulationRange range)

Based on the configuration variables CrossoverProbability and CreationProbability, creates two individuals using crossover or one new individual using creation (a brand-new GP) or reproduction (a fitness-selected copy of an existing individual). The new individuals are guaranteed to have depth no more than MaximumDepthForCrossover or MaximumDepthForCreation and complexity no more than MaximumComplexity.

Brand-new individuals are created using the GPVARIABLE strategy with depth ramped between calls to this method.

Crossover is considered first, then (if crossover did not occur) creation of a new individual, then (if creation did not occur) reproduction of an existing individual.

Mutation does not occur in this method but rather as an independent step in generate(). Thus an individual passed on via reproduction could still undergo mutation.

Parameters:

range - the range of indices from which to select. Unless demetic migration is enabled, this is the entire population.

Returns:

an array of GP references holding the selected individuals. The length of the array is 2 for individuals created via crossover and 1 for individuals generated by creation or reproduction.

Throws: RuntimeException

if an individual of acceptable complexity cannot be created in 50 attempts.

  protected synchronized void addBest(GPPopulation newPop)

Adds the best individual from this generation to the next. This method does nothing unless the configuration variable AddBestToNewPopulation is true. It can be called only when a steady state population is not in use and therefore newPop exists.

Parameters:

newPop - the population for the next generation.

  public void generate(GPPopulation newPop)

Generates the next generation of individuals using genetic processes. If the configuration variable SteadyState is true, the newPop parameter is ignored and the next generation is created by replacing the worst (fitness-based) individuals in the current generation with new individuals. Otherwise, newPop is filled in from scratch with new individuals. In either case, PopulationSize individuals are created and added to the new generation.

If DemeticGrouping is true, the overall population is divided into "demes" of size DemeSize and each of these is treated individually as a subpopulation.

If AddBestToNewPopulation is true and SteadyState is false, the best individual in this population is automatically added to the new population at its same index location.

After each new individual or pair of individuals is generated by evolve(), generate() calls mutate() to possibly modify the new individuals further.

If TestDiversity is true, the diversity table is updated while the new population is built to keep track of duplicates. No duplicates are rejected within generate(), however.

After the new population is generated, demeticMigration() is called if this feature is activated. Population statistics are always calculated for the new generation.

Parameters:

newPop - an instantiated new population to fill.

  protected synchronized void demeticMigration()

Based on the configuration variable DemeticMigProbability, fitness-selects a good individual from each deme and exchanges it with a good individual from the next deme. This process occurs for each adjacent pair of demes, and the last deme is considered to be adjacent to the first deme.

  protected void calculateStatistics()

Calculates statistics about a complete population, including the best, average, and worst fitness, complexity, and depth. Also stores the indices of the best and worst individuals.

Throws: RuntimeException

if a null GP is unexpectedly found in the population.

  protected static String formatInt(int i,
                                    int width)

Converts an integer to a string right-justified in a field of specified width.

  protected static String overflow(int width)

Returns a string of asterisks with specified width.

  public static String formatDouble(double d,
                                    int width,
                                    int places)

Converts a double to a string right justified in a field of specified width. Returns an overflow string if the number cannot be formatted as specified. Uses scientific notation whenever java.lang.String.valueOf(double) returns a number in scientific format. Rounds the number to the specified number of decimal places. Not industrial strength but works as needed for GPPopulation and GPRun reports.

  public static String trimFormatDouble(double d,
                                        int width,
                                        int places)

Calls formatDouble to create a formatted string and then strips any leading blanks.

  public void printStatisticsLegend(PrintStream sout)

Prints a legend line for the standard statistics report to the specified PrintStream.

  public void printStatistics(int generation,
                              char chk,
                              PrintStream sout)

Prints one generation's statistics to the specified PrintStream. The output is on one line and includes the generation number; the best, average, and worst standardized fitness; the complexity of the best, average, and worst individuals; the depth of the best, average, and worst individuals; and the diversity of the population if cfg.TestDiversity is true. If this generation has been saved to a stream by GPRun's checkpointing facility, the letter 'c' is printed at the end of the line.

Parameters:

generation - the generation number.

chk - the checkpoint character ('c' or ' ').

sout - the statistics PrintStream

  protected String formatParentage(int len,
                                   int index,
                                   int tree,
                                   int cut)

Formats a string that shows the heritage of a crossover, reproduction, or mutation operation.

Parameters:

len - the length of the string to return.

index - the population index of the parent.

tree - the branch number in which crossover or mutation occurred. Branch 0 is converted to "RPB", branch 1 is converted to "ADF0", and so on.

cut - the s-expression index at which crossover or mutation occurred.

  public void printIndividual(GP current,
                              int num,
                              boolean showExpression,
                              boolean showTree,
                              PrintStream dout)

Prints details about a particular individual to the specified PrintStream. The first line shows 'B' if the individual is the best in its population, or 'W' if it is the worst. The line goes on to show the population index (num) of the individual, its reproduction or crossover heritage, its mutation heritage, and its standardized fitness, complexity, and depth.

If showExpression is true, the GP's printOn() method is called to print the s-expression. If showTree is true, the GP's printTree() method is called to print the expression in pseudo-graphic text format.

  public void printDetails(int generation,
                           boolean showAll,
                           boolean showBest,
                           boolean showWorst,
                           boolean showExpression,
                           boolean showTree,
                           PrintStream dout)

Prints details about some or all of the population. It starts by printing a columnar header, then calls printIndividual() for all individuals, the best, and/or the worst depending on the parameters passed to the method.

  protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException

Loads a GPPopulation from the specified stream. Reads all of the GPs from the stream, then rebuilds the diversity table and recalculates the population statistics. Note that GPPopulation doesn't have a save() method because its superclass GPContainer does everything that's necessary in its save() method.

Throws: ClassNotFoundException

if the class indicated by the stream's ID code is not registered with GPObject.

Throws: InstantiationException

if an error occurs while calling new or the null constructor of the specified class.

Throws: IllegalAccessException

if the specified class or its null constructor is not public.

Throws: IOException

if an error occurs while reading the stream.

Overrides:

load in class GPContainer

  public void printOn(PrintStream os,
                      GPVariables cfg)

Writes every GP in text format to a PrintStream by simply calling GP.printOn() for every individual in the population.

Overrides:

printOn in class GPContainer

All Packages  Class Hierarchy  This Package  Previous  Next  Index