The genetic algorithm (GA) hosts a Vector of Chromosomes. The Chromosomes contain an integer array called "dna()". The value of each item in the array has a maximum value called traitSize(). The dna() values are used to represent numbers or an index to objects or chars by the user of the library. The following example gives an idea of how the GeneticAlgorithm class can be extended:
This example can be seen in use here
Chromosomes are generated with the GeneticAlgorithm.makeChromosome() method. This registers a Chromosome with a GA, giving it access to its utilities. Fields are accessed by method to protect modifications that may be made to the library. Field methods accessing objects will return references and changes made to those references will occur within the GA also.
| Field Method Summary | |
| int | dnaLength () Returns the standard dna() length for all instances Chromosome registered with this GA |
| int | traitSize () Returns the maximum value currently allowed in a Chromosome's dna() array |
| int | poolSize () Returns the number of Chromosomes in the GA's genePool Vector |
| int | generation () Returns the number of times the propagate() method has been called |
| float | mutationRate () Returns the likelyhood of mutation occurring in a Chromosome when its mutation() method is called Initially set to 0.001. |
| float | crossOverRate () Returns the likelyhood of dna() cross over occurring in a Chromosome when its crossOver() method is called. Initially set to 0.7. |
| float | errorThreshold () Returns the acceptable deviation from the figure 0.0 in calculating whether the fitness of a Chromosome reveals it as a solution. Initially set to 0.0 (no deviation). |
| int | traitBits () Returns a value denoting the number of bits required to deal with a GA that has been set to cross over and mutate dna() at a sub-integer level |
| boolean | subInteger () Returns true if the GA is set to cross over and mutate dna() at a sub-integer level. Initially set to false. |
| Vector | genePool () Returns a reference to a Vector containing the GA's Chromosomes. |
| Vector | solutions () Returns a reference to a Vector containing Chromosomes that have been cloned from the genePool() and have a fitness within the error threshold of 0.0. solutions() is populated during the propagate() method. |
| boolean | found () Returns true if a Chromosome has been found with a fitness within the error threshold of 0.0. |
| Constructor Summary |
| GeneticAlgorithm (int
chromosomeLength, int traitSize, int poolSize) Creates an environment, constants and methods for a collection of Chromosomes. |
| Method Summary | |
| void | propagate () goes through the entire genePool and selects pairs of Chromosomes to cross over and mutate. Automatically adds Chromosomes of fitness within an error threshold of 0.0 to the solutions() Vector, upon doing so the found() field will return true. |
| abstract float | scoreFitness (Chromosome o) Defined by the user of the library to return a value approaching 0.0 depending on how appropriate the Chromosome's dna() sequence is to a given task. |
| Chromosome | makeChromosome () Returns a reference to a Chromosome which is created and then added to the GA's genePool Vector. |
| Chromosome | makeChromosome (int [] dna) Returns a reference to a Chromosome which is created and then added to the GA's genePool Vector. The new Chromosome's dna() will be a copy of the array passed to it. |
| Chromosome | copy (Chromosome o) Returns a reference to a copy of the Chromosome given in the parameters which is automatically added to the genePool(). |
| void | setDnaLength (int
dnaLength) |
| void | setTraitSize (int traitSize) Modifies the field traitSize() and sets an upper limit on the value of new dna. |
| void | setPoolSize (int poolSize) Modifies the GA's poolSize() field, adding or subtracting Chromosomes to the end of the genePool() Vector. |
| void | setMutationRate (float mutationRate) Modifies the likelyhood of dna() being mutated when a Chromosome's mutate() method is called. |
| void | setCrossOverRate (float crossOverRate) Modifies the likelyhood of dna() being crossed over when a Chromosome's crossOver() method is called. |
| void | setErrorThreshold (float errorThreshold) Modifies the degree of acceptable deviation from the value 0.0 in determining whether a solution is found and added to the solutions() Vector and the setting of the GA's found() field to true. |
| void | setFound (boolean found) Modifies the found() field in the GA. |
| void | setTraitBits (int traitBits) Modifies the number of bits used to deal with sub-integer operations in the GA and modifies the traitSize() field if the bits needed for new dna() would be too large. |
| void | setSubInteger (boolean subInteger) Set to true makes the GA cross over and mutate Chromosomes at the sub-integer level. |
| void | setGenePool (Vector genePool) Replaces the current genePool Vector with the one passed in the parameter. |
| void | setSolutions (Vector Solutions) Replaces the current solutions Vector with the one passed in the parameter. |
| void | sortGenePool () Orders the Chromosomes in genePool based on their fitness. |
| static final int | getTraitBits (int num) Returns the number of bits that will be required by an arbitrary traitSize(). |
| Constructor Detail |
public abstract GeneticAlgorithm (int dnaLength, int traitSize, int poolSize)
Creates a collection of Chromosomes according to the parameters given. Chromosomes require registration with a GeneticAlgorithm to access common behaviours. A Chromosome requires too much enviromental information to operate alone. A GA initialised with a poolSize of zero can be populated by the makeChromosome() method.
Parameters:
dnaLength - the length of the dna() array
in all Chromosomes in GeneticAlgorithm.
traitSize - the current maximum value of values
in all Chromosome's dna()
poolSize - the initial number of random Chromosomes
to be generated and added to the genePool() Vector.
| Method Detail |
public void propagate ()
Goes through the whole of the genePool() Vector and pairs of selected candidates for cross over and mutation. Then checks whether those found have a fitness score within an error threshold of 0.0. Upon finding fit Chromosomes it sets its found() field to true and copies said Chromosomes into a solutions() Vector. Each call of propagate() increases the GA's generation() field by one.
public abstract float scoreFitness (Chromosome o)
Used by Chromosome in its constructor to determine its fitness. A fit Chromosome should have a fitness score approaching 0.0. The overridden method must return a float value to be used as a fitness score. The user should define a method of decoding the dna() in Chromosome "o" so that they can write instructions to determine the validity and the fitness of the Chromosome. It is possible to run a GA without the use of the scoreFitness method, the user may have created an environment where the breeding of Chromosomes occurs based on the proximity of particles rather than use of propagate() or another method. In such a case the user is advised to simply state "return 1.0" in scoreFitness's block parenthesis {}.
Parameters:
o - a Chromosome to be tested for fitness.
public Chromosome makeChromosome ()
Returns a reference to a Chromosome that is created and then added to the GA's genePool() Vector. Chromosomes can be created outside of a GA, but always require registration with one on construction owing to the utilities and parameters that have been placed in GeneticAlgorithm to conserve memory. Such a Chromosome will not exist inside the genePool() Vector and will not be updated if changes are made to the GA that will affect the operation of the Chromosome. The user is advised to use GeneticAlgorithm.makeChromsome() to generate any Chromosomes they wish to use.
public Chromosome makeChromosome (int [] dna)
Returns a reference to a Chromosome that is created and then added to the GA's genePool() Vector. The Chromosome created will have a dna() field that is copied from the parameter given. Chromosomes can be created outside of a GA, but always require registration with one on construction owing to the utilities and parameters that have been placed in GeneticAlgorithm to conserve memory. Such a Chromosome will not exist inside the genePool() Vector and will not be updated if changes are made to the GA that will affect the operation of the Chromosome. The user is advised to use GeneticAlgorithm.makeChromsome() to generate any Chromosomes they wish to use.
Parameters:
dna - a template for dna that will be copied into the new Chromosome
public Chromosome copy (Chromosome o)
Given "o", this method will return a reference to a copy of "o" and add it to the genePool() Vector.
Parameters:
o - a reference to a Chromosome to be copied.
public void setChromosomeLength (int chromosomeLength)
This method iterates through all of the Chromosomes in the genePool() Vector and modifies their dna() to a length equal to chromosomeLength. A value smaller than the previous chromosomeLength() will result in the end of the dna being trimmed. A value longer than the previous chromosomeLength will result in random values being added to the end of dna() whose upper limit will be trait().size() - 1.
Parameters:
chromosomeLength - the new length of dna() to be adopted by all Chromosomes.
public void setPoolSize (int poolSize)
This method modifies the poolSize() field and also affects the contents of the genePool() Vector. If the parameter given is smaller than the previous poolSize() the genePool() is trimmed accordingly. If the parameter given is larger than the previous poolSize(), the genePool() is filled with new random Chromosomes.
Parameters:
poolSize - the new size of the genePool() Vector to be adopted.
public void setMutationRate (float mutationRate)
This method modifies the likelyhood that mutation will occur when a Chromosome's mutation() method is called. mutationRate() has an initial value of 0.001 and has a range of 0.0 to 1.0. Setting a value of 1.0 or greater will randomize the whole chromosome. During mutation each trait is tested for possible mutation, with subInteger() set to true, each binary bit of every trait is tested for possible mutation as well. Thus mutation is more likely to occur with sub-integer operations activated. However if the mutation rate is set to 1.0 or higher with sub-integer operations activated, all this will do is flip the dna between one value and another, because sub-integer mutation is simply the transformation of a binary bit from 1 to 0 or vice versa. Sub-integer mutations may result in number out of the range of the trait() Vector to a value determined by 2 to the power of traitBits(). See the setTraitBits() method for a table of number ranges.
Parameters:
mutationRate - a value between 0.0 and 1.0 that defines the probability that mutation will occur.
public void setCrossOveRate (float crossOverRate)
This method modifies the likelyhood that cross over of dna() will occur when a Chromosome's crossOver() method is called. crossOver() is initially set to 0.7 and ranges from 0.0 to 1.0. Setting a value of 1.0 or more guarantees cross over every time. Without sub-integer operations enabled the GA will pick an arbitrary point in the dna() to effect an exchange. With sub-integer operations the cross over will occur at the binary level, the splice point being a random point along the bit range of the numbers. This results in numbers that may be out of the range of the trait() Vector up to a value determined by 2 to the power of traitBits(). See the setTraitBits() method for a table of number ranges.
Parameters:
crossOverRate - a value between 0.0 and 1.0 that determines whether cross over of dna() will occur.
public void setErrorThreshold (float errorThreshold)
This method modifies the acceptable range around 0.0 for the fitness score of a Chromosome in determining if the Chromosome can be added to the solutions() Vector and the GA's found() field be set to true. errorThreshold has and initial value of 0.0, meaning that nothing other than a fitness score of 0.0 is acceptable.
Parameters:
errorThreshold - a value indicating the level of deviation to be accepted for fitness.
public void setFound (boolean found)
This modifies the found() field of the GA. It has no impact on the contents of the solutions() Vector or any other part of the GA. If a new solution is discovered and found() has been set to false it will be set to true. found() has an initial value of false.
Parameters:
found - a value to override the current value of the field found().
public void setTraitSize (int traitSize)
This method modifies the traitSize() field and sets the traitBits() field to a value of bits high enough to contain the bits in the number traitSize(). All new changes in dna will take the change in fields into account. No previous values in dna() will be altered, so the user must take this into account in decoding the values in Chromosome.dna().
Parameters:
traitSize - the new maximum value for dna(), excluding when using sub-integer operations.
public void setTraitBits (int traitBits)
This modifies the number of binary bits involved in sub-integer operations. When sub-integer operations are activated the possible values in a Chromosomes's dna() may reach up to 2 to the power of traitBits(). This is because the exchange and mutation of bits requires a range of numbers that is 2 to the power of a given number (the maximum number of zeros and ones involved in the operation). If one uses sub-integer operations they should consider the table below when determining the amount of traits that are going to be available to the Chromosomes.
| Number range | traitBits() |
| 0 - 1 | 1 |
| 0 - 4 | 2 |
| 0 - 8 | 3 |
| 0 - 16 | 4 |
| 0 - 32 | 5 |
| 0 - 64 | 6 |
If users want to find out how many traitBits they are going to be using, they can use the getTraitBits() method.
Parameters:
traitBits - a value determining the number of bits used in sub-integer operations
public void setSubInteger (boolean subInteger)
This modifies the subInteger() field that is used for determining whether the GA will process sub-integer operations. This field is initially set to false. It is up to the user whether they activate sub-integer operations, but in doing so they must safeguard their code against dna() values falling outside trait().size(). These extraneous values come from altering the values in dna() at the binary level. This leads to values which can be up to a value determined by 2 to the power of traitBits(). See the setTraitBits() method for a table of number ranges.
Parameters:
subInteger - a boolean value activating or deactivating sub-integer operations.
public void setGenePool (Vector genePool)
This replaces the current genePool() Vector with the one defined in the parameter. The poolSize() field is modified accordingly.
Parameters:
genePool - a Vector containing Chromosomes.
public void setSolutions (Vector solutions)
This replaces the current solutions() Vector with the one defined in the parameter.
Parameters:
solutions - a Vector containing Chromosomes.
public void sortGenePool ()
This method sorts all of the Chromosomes in genePool() according to their fitness. Chromosomes implement the interface Comparable, and can be sorted using Collections.sort(givenVector), where givenVector is a collection of Chromosomes. This method is simply a shorthand call for the user.
public static final int getTraitBits (int num)
This method returns a value that is used internally in the GA to calculate the number of bits involved in a sub-integer operation for a givenTraitSize(), as well as the tables involved for the binary masks. The user can use this method to determine how many bits a given traitSize is going to use, namely 2 to the power of traitBits().
Parameters:
num - a value that is used to determined the minimum number of bits required to contain it.
Note to self: Don't make a library so bloody flexible next time, all this documentation is taking ****ing ages.