All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class gpjpp.GP

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

public class GP

extends GPContainer

Besides the program itself, GP also stores the complexity and maximum depth of the tree, its standard fitness (as computed by a user subclass), its adjusted fitness, and its heritage. The heritage consists of the population indices of the two parents if the GP was created by crossover or the population index of one parent if the GP was created by straight reproduction. It also includes the crossover points and the last mutation locus when applicable.

The user must always create a subclass of GP for use in solving a particular problem. This subclass must override the evaluate() method, which returns a double that indicates the standard fitness of the GP. (The standard fitness must always be non-negative, and the genetic algorithm attempts to find individuals with minimal standard fitness.) The other fields of the GP are calculated by gpjpp.

Usually the user must also override the createGene() method to dynamically create genes of a problem-specific type. See the supplied example programs for more details.

Version:

1.0

adjFitness

The adjusted fitness of the GP.

crossTree

The branch number of this GP's mum and dad when it was generated as a result of crossover.

dadCross

The s-expression index of this GP's "dad" when it was generated as a result of crossover.

dadIndex

The population index of this GP's "dad" when it was generated as a result of crossover or reproduction.

gpDepth

The maximum depth of any branch of the GP.

gpLength

The complexity, or length, of the GP.

mumCross

The s-expression index of this GP's "mum" when it was generated as a result of crossover.

mumIndex

The population index of this GP's "mum" when it was generated as a result of crossover.

shrinkPos

The s-expression index used to apply shrink mutation.

shrinkTree

The branch number used in shrink mutation when this GP was generated.

stdFitness

The standardized fitness of the GP.

swapPos

The s-expression index used to apply swap mutation.

swapTree

The branch number used in swap mutation when this GP was generated.

GP()

Public null constructor used during stream loading only.

GP(GP)

A constructor that is called to clone a GP.

GP(int)

Constructor used when GPs are first created.

betterThan(GP)

Returns true if this GP is better than another specified non-null GP.

calcAdjustedFitness()

Calculates the adjusted fitness after evaluate() has computed the standardized fitness.

calcDepth()

Calculates the depth of the GP by calling GPGene.depth() method for each of its branches.

calcLength()

Calculates the complexity of the GP by calling GPGene.length() method for each of its branches.

clearHeritage()

Sets all of the heritage fields (dadIndex, dadCross, mumIndex, MumCross, crossTree, swapTree, swapPos, shrinkTree, shrinkPos) to -1 when a new GP is created or cloned.

clone()

Implements the Cloneable interface.

create(int, int, int, GPAdfNodeSet)

Creates the branches of this GP and then creates the genes of each branch according to the limits and methods specified.

createGene(GPNode)

Creates a root gene while a new branch is being built.

cross(GPContainer, int, int)

Performs crossover on two GPs.

depth()

Returns the maximum depth of the GP.

drawOn(GPDrawing, String, GPVariables)

Writes a GP in graphic gif file format.

equals(Object)

Determines whether this GP equals another object.

evaluate(GPVariables)

The user must override this method to evaluate and return the standardized fitness of the GP.

getAdjFitness()

Returns the already-calculated adjusted fitness.

getFitness()

Returns the already-calculated standard fitness.

hashCode()

Returns an integer hashcode for this GP.

isA()

Returns a code identifying the class in a stream file.

length()

Returns the complexity (length, or number of nodes) of the GP.

load(DataInputStream)

Loads a GP from the specified stream.

mutate(GPVariables, GPAdfNodeSet)

Uses the configuration probabilities SwapMutationProbability and ShrinkMutationProbability to determine whether to apply either or both forms of mutation to this GP.

printOn(PrintStream, GPVariables)

Writes a GP in text format to a PrintStream.

printTree(PrintStream, GPVariables)

Writes a GP in text tree format to a PrintStream.

save(DataOutputStream)

Saves a GP to the specified stream.

shrinkMutation()

Mutates this GP by finding a random function gene in a random branch and then replacing that gene by one of its immediate children.

swapMutation(GPAdfNodeSet)

Mutates this GP by finding a random function gene in a random branch and changing the node type of that gene.

testNull()

A debugging/testing method used to ensure that no null node or gene references are found in this GP.

  protected double stdFitness

The standardized fitness of the GP. Must be non-negative and 0.0 is considered optimal. This field is initialized with the value returned by the evaluate() method, which must be overridden by the user.

  protected double adjFitness

The adjusted fitness of the GP. This value is initialized by the calcAdjustedFitness() method. Adjusted fitness is always in the range 0.0 to 1.0, with 1.0 being optimal.

  protected int gpLength

The complexity, or length, of the GP. This is a count of the total number of nodes in all branches of the genetic program.

  protected int gpDepth

The maximum depth of any branch of the GP.

  public int dadIndex

The population index of this GP's "dad" when it was generated as a result of crossover or reproduction. This value is shown in the detail report file when enabled. Has the value -1 if the GP was generated by creation.

See Also:

cross

  public int dadCross

The s-expression index of this GP's "dad" when it was generated as a result of crossover. Otherwise has a value of -1. The index is a depth-first count of nodes to reach the crossover locus.

  public int mumIndex

The population index of this GP's "mum" when it was generated as a result of crossover. This value is shown in the detail report file when enabled. Has the value -1 if the GP was generated by creation or reproduction.

  public int mumCross

The s-expression index of this GP's "mum" when it was generated as a result of crossover. Otherwise has a value of -1. The index is a depth-first count of nodes to reach the crossover locus.

  public int crossTree

The branch number of this GP's mum and dad when it was generated as a result of crossover. Otherwise has the value -1. Branch number 0 is the result-producing branch, number 1 is the first ADF, and so on.

  public int swapTree

The branch number used in swap mutation when this GP was generated. Has the value -1 if swap mutation was not involved.

  public int swapPos

The s-expression index used to apply swap mutation. Has the value -1 if swap mutation was not involved. The index is a depth-first count of nodes to reach the mutation locus.

  public int shrinkTree

The branch number used in shrink mutation when this GP was generated. Has the value -1 if shrink mutation was not involved.

  public int shrinkPos

The s-expression index used to apply shrink mutation. Has the value -1 if shrink mutation was not involved. The index is a depth-first count of nodes to reach the mutation locus.

  public GP()

Public null constructor used during stream loading only. Note that heritage fields are not stored on streams, so this information is lost after a checkpoint.

  public GP(int trees)

Constructor used when GPs are first created. This constructor creates a container capable of holding the predefined branches of the GP, but does not fill in any nodes.

Parameters:

trees - the number of branches in the GP.

  public GP(GP gpo)

A constructor that is called to clone a GP. Used whenever a GP is selected for reproduction or crossover. The heritage of the GP is reset by this constructor because it will always be updated by the population manager.

  protected void clearHeritage()

Sets all of the heritage fields (dadIndex, dadCross, mumIndex, MumCross, crossTree, swapTree, swapPos, shrinkTree, shrinkPos) to -1 when a new GP is created or cloned. Used internally.

  protected synchronized Object clone()

Implements the Cloneable interface. This (or its user subclass) is called during reproduction.

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 GPID.

Overrides:

isA in class GPContainer

  public GPGene createGene(GPNode gpo)

Creates a root gene while a new branch is being built. The user must generally override this in a subclass to create genes of user type. See the example programs.

Parameters:

gpo - a node type that is an element of the current branch's node set. Always a function node type.

Returns:

the newly created gene.

  public void testNull()

A debugging/testing method used to ensure that no null node or gene references are found in this GP.

Throws: RuntimeException

if a null branch, gene, or node reference is found.

  public double evaluate(GPVariables cfg)

The user must override this method to evaluate and return the standardized fitness of the GP. The subclass method should not call super.evaluate().

Throws: RuntimeException

if it has not been overridden.

  protected void calcAdjustedFitness()

Calculates the adjusted fitness after evaluate() has computed the standardized fitness. Adjusted fitness is 1/(1+stdFitness). Adjusted fitness is always in the range 0.0 to 1.0 and is optimal at 1.0. Adjusted fitness is used to select the best individuals in probabilistic and greedy selection. Standardized fitness is used to select the worst individuals.

  public double getFitness()

Returns the already-calculated standard fitness.

See Also:

stdFitness, evaluate

  public double getAdjFitness()

Returns the already-calculated adjusted fitness.

See Also:

adjFitness, calcAdjustedFitness

  protected boolean betterThan(GP gp)

Returns true if this GP is better than another specified non-null GP. Compares standardized fitness and then uses complexity as a tiebreaker. Used internally by the tournament selection method.

  public int length()

Returns the complexity (length, or number of nodes) of the GP.

  public int depth()

Returns the maximum depth of the GP.

  protected void calcLength()

Calculates the complexity of the GP by calling GPGene.length() method for each of its branches. Used internally.

See Also:

length

  protected void calcDepth()

Calculates the depth of the GP by calling GPGene.depth() method for each of its branches. Used internally.

See Also:

depth

  public int hashCode()

Returns an integer hashcode for this GP. This is used internally when calculating the diversity of a population. The hash code is composed from the GP's complexity, depth, and the root node type of up to 10 of its branches.

Overrides:

hashCode in class Object

  public boolean equals(Object obj)

Determines whether this GP equals another object. It returns true if obj is not null, is an instance of a GP (or a descendant), and has the same structure and node values as this GP. This function is called when testing the diversity of the population. equals() is called only after the hashCode() function determines that two GPs are at least similar.

Parameters:

obj - any Java object reference, including null.

Returns:

true if this and obj are equivalent.

Overrides:

equals in class Object

  public synchronized void create(int creationType,
                                  int allowableDepth,
                                  int allowableLength,
                                  GPAdfNodeSet adfNs)

Creates the branches of this GP and then creates the genes of each branch according to the limits and methods specified. The GP for which this method is called should have been created by calling the createGP() method of a subclass of GPPopulation. createGP() allocates a branch container of appropriate size but doesn't fill in the children.

Parameters:

creationType - the method used to create the tree, either GPGROW (use function nodes to fill the tree to allowable depth) or GPVARIABLE (choose function and terminal nodes with 50:50 probability).

allowableDepth - the maximum allowable depth of each tree. The allowable depth must always be at least 2.

allowableLength - the maximum allowable number of nodes in the GP. Since create() cannot predict how many nodes will be added recursively it simply stops adding nodes if it exceeds allowableLength. The create() routine in GPPopulation rejects the returned GP if the total complexity exceeds allowableLength.

adfNs - the node set used to select functions and terminals for the GP.

Throws: RuntimeException

if creationType is neither GPGROW nor GPVARIABLE, or if allowableDepth is less than 2.

  public synchronized void shrinkMutation()

Mutates this GP by finding a random function gene in a random branch and then replacing that gene by one of its immediate children. This has the effect of shrinking the tree one level.

  public synchronized void swapMutation(GPAdfNodeSet adfNs)

Mutates this GP by finding a random function gene in a random branch and changing the node type of that gene. The node type is changed randomly to another type that has the same number of arguments. If such a node cannot be found in 5 tries, nothing is done.

  public void mutate(GPVariables cfg,
                     GPAdfNodeSet adfNs)

Uses the configuration probabilities SwapMutationProbability and ShrinkMutationProbability to determine whether to apply either or both forms of mutation to this GP. Swap mutation is considered first, then shrink mutation.

See Also:

swapMutation, shrinkMutation

  public synchronized GPContainer cross(GPContainer parents,
                                        int maxDepthForCrossover,
                                        int maxComplexity)

Performs crossover on two GPs. Then a random gene, preferably a function gene, is chosen from the same random branch of each GP and the two subtrees are swapped between the two GPs.

Parameters:

parents - a container holding the two parent GPs. Upon exit, the same container holds the two GPs after crossover.

maxDepthForCrossover - the maximum depth allowed for either GP after crossover. If the result of a crossover exceeds this depth, the subtrees are swapped back to their original state and another random crossover on the same branch is attempted, continuing until an acceptable result is achieved.

maxComplexity - the maximum complexity (number of nodes) allowed for either GP after crossover. If the result of a crossover exceeds this limit, the subtrees are swapped back and another crossover is attempted.

Returns:

the parents container, now containing the crossed GPs.

Throws: RuntimeException

if parents does not contain exactly 2 GPs, or if both parents don't have the same number of branches, or if the number of branches is zero.

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

Loads a GP from the specified stream. Reads the standardized and adjusted fitness from the stream, then loads the container of gene branches. Afterwards, the length and depth of the GP is recalculated. The heritage of the GP is not stored and therefore is lost after a save/load cycle.

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

  protected void save(DataOutputStream os) throws IOException

Saves a GP to the specified stream. Writes the standardized and adjusted fitness to the stream, then saves the container of gene branches.

Overrides:

save in class GPContainer

  public void printOn(PrintStream os,
                      GPVariables cfg)

Writes a GP in text format to a PrintStream. Each branch is preceded by "RPB" (for the result-producing branch) or "ADFn" (for the ADFs) and continues with the branch's s-expression on one line.

Overrides:

printOn in class GPContainer

See Also:

printOn

  public void printTree(PrintStream os,
                        GPVariables cfg)

Writes a GP in text tree format to a PrintStream. If there are no ADFs, the main branch's tree is printed without any title. Otherwise, each branch is preceded by "RPB" (for the result-producing branch) or "ADFn" (for the ADFs), which is followed by the tree in pseudo-graphic format.

See Also:

printTree

  public void drawOn(GPDrawing ods,
                     String fnameBase,
                     GPVariables cfg) throws IOException

Writes a GP in graphic gif file format. This method simply computes a title for the gif file and then calls GPGene.drawOn. If there are no ADFs, the title is blank; otherwise it is "RPB" for the result-producing branch and "ADFn" for the ADF branches.

All Packages  Class Hierarchy  This Package  Previous  Next  Index