GeneticAlgorithm class

The genetic algorithm (GA) hosts an ArrayList of Chromosomes. The Chromosomes contain an integer array called "dna". Each position in the array has an upper limit called valueLength. Values in the dna array range from 0 to valueLength - 1. The dna values can represent numbers, an index to objects, traits such as eye colour or skin tone or other things such as letters of the alphabet.

If you need to use the propagate() method in the library you will need to extend the GeneticAlgorithm class. The following example gives an idea of how the GeneticAlgorithm class can be extended and is included in the download:

This example can be seen in use here

Chromosomes are generated with the createChromosome() method. This registers a Chromosome with a GA, giving it access to its utilities. A Chromosome cannot be created outside the context of a GeneticAlgorithm.

Property Summary
int dnaLength
The standard dna length for all instances of Chromosome registered with this GA
int binaryLength
The total number of binary digits a Chromosome uses. This value is equal to dnaLength * valueBits.
int valueLength
The number of dna values allowed. Values in any Chromosome's dna will range from 0 to valueLength - 1. This property affects the number of binary digits used to represent each dna value.
int poolSize
The number of Chromosomes in the GA's genePool ArrayList
int generation
The number of times the propagate() method has been called
float mutationRate
The likelyhood of mutation occurring in a Chromosome when its mutation() method is called. Initially set to 0.001.
float spliceRate
The likelyhood of dna splice occurring in a Chromosome when the splice method is called without a splice position parameter. Initially set to 0.7.
float errorThreshold
The acceptable deviation in calculating whether the fitness of a Chromosome reveals it as a solution. Initially set to 0.0 (no deviation).
int valueBits
A number denoting the number of digits in binary each dna position possesses.
boolean subInteger
Set to true if the GA is set to splice and mutate dna at a sub-integer level. Set to false unless specified otherwise.
ArrayList genePool
A reference to an ArrayList containing the GA's Chromosomes.
Vector solutions
A reference to an ArrayList 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.
static int [] singleBitMask
An array of integers representing all the possible integer numbers that possess only one bit set to 1 and the rest set to 0. This array is 32 in length and is used to flip single bits in subInteger mutations. Users wishing to flip a single bit on an integer themselves should refer to the mutate() method.
static int [] spliceMask
An array of integers representing all the possible integer numbers that consist of only 0s on one side of it's binary representation and 1s on the other. This array is 32 in length and is used to splice binary numbers in subInteger splices. Users wishing to splice the binary of integers themselves should refer to the splice() 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 valueLength, int poolSize)
Creates an environment, constants and methods for a collection of Chromosomes. subInteger property is set to false.
GeneticAlgorithm (int chromosomeLength, int valueLength, int poolSize, boolean subInteger)
Creates an environment, constants and methods for a collection of Chromosomes with the subInteger property defined by the user.

Method Summary
void propagate ()
goes through the entire genePool and selects pairs of Chromosomes to splice and mutate. Automatically adds Chromosomes of fitness within an error threshold of 0.0 to the solutions ArrayList, upon doing so the found property will return true.
float scoreFitness (Chromosome o)
Returns 1 by default. It is intended the user extend the class to define how appropriate the Chromosome's dna sequence is to a given task and override this class.
Chromosome createChromosome ()
Returns a reference to a Chromosome which is created and then added to the GA's genePool ArrayList.
Chromosome createChromosome (int [] dna)
Returns a reference to a Chromosome which is created and then added to the GA's genePool ArrayList. The new Chromosome's dna will be a copy of the array passed to it.
void removeChromosome ()
Removes a Chromosome from the genePool and updates the poolSize value.
Chromosome copyChromosome (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)
Modifies the length of the dna of all Chromosomes in the GA's genePool.

void setValueLength (int valueLength)
Modifies the property traitSize, setting an upper limit on the value of new dna and if subInteger is true, modifies traitBits to contain that number of traits.
void setPoolSize (int poolSize)
Modifies the GA's poolSize field, adding or subtracting Chromosomes to the end of the genePool ArrayList.
void setValueBits (int valueBits)
Modifies the number of bits used to deal with sub-integer operations in the GA and modifies the valueLength property if the bits requested would result in numbers larger than valueLength - 1.
void sortGenePool ()
Orders the Chromosomes in genePool based on their fitness.
Chromosome selection (ArrayList genePool)
Used by the propagate method to select a Chromosome via a roulette method.
static final int base2 (int num)
Returns the number of digits a number would possess if it were converted to a base 2 number (binary).

Constructor Detail

GeneticAlgorithm

public GeneticAlgorithm (int dnaLength, int valueLength, 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 createChromosome() method. When constructing a GeneticAlgorithm with this method, subInteger will be set to false and dna will be spliced at the number boundary.

Parameters:

dnaLength - the length of the dna array in all Chromosomes in GeneticAlgorithm.
valueLength - the number of possible values at any position in a Chromosome's dna
poolSize - the initial number of random Chromosomes to be generated and added to the genePool ArrayList.


GeneticAlgorithm

public GeneticAlgorithm (int dnaLength, int valueLength, int poolSize, boolean subInteger)

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 createChromosome() method.

Parameters:

dnaLength - the length of the dna array in all Chromosomes in GeneticAlgorithm.
valueLength - the number of possible values at any position in a Chromosome's dna
poolSize - the initial number of random Chromosomes to be generated and added to the genePool ArrayList.
subInteger - when set to true, dna is spliced and mutated at the binary level.

Method Detail

propagate

public void propagate ()

Goes through the whole of the genePool ArrayList and selects pairs of Chromosomes to splice and mutate. Then checks whether those found have a fitness score within the error threshold defined by the property errorThreshold. Upon finding fit Chromosomes it sets its found property to true and copies said Chromosomes into the solutions ArrayList. Each call of propagate() increases the GA's generation property by one. propagate() will only operate on genePools divisible by 2, calling propagate on an uneven genePool will throw an exception.


scoreFitness

public float scoreFitness (Chromosome o)

Used by a 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 can ignore this method.

Parameters:

o - a Chromosome to be tested for fitness.


createChromosome

public Chromosome createChromosome ()

Returns a reference to a Chromosome that is created and then added to the GA's genePool ArrayList. The Chromosome's dna is generated randomly.


createChromosome

public Chromosome createChromosome (int [] dna)

Returns a reference to a Chromosome that is created and then added to the GA's genePool ArrayList. The Chromosome created will have a dna property that is copied from the parameter given.

Parameters:

dna - a template for dna that will be copied into the new Chromosome


removeChromosome

public Chromosome removeChromosome (Chromosome o)

Remove the Chromosome specified from the genePool and returns it. The poolSize value is updated also - thus it is recommended you remove Chromosomes from the genePool via this method.

Parameters:

o - a Chromosome to be removed from the genePool


copyChromosome

public Chromosome copyChromosome (Chromosome o)

Given "o", this method duplicates said Chromosome and retains both copies in the genePool. The return value is the reference to the duplicate generated by the operation.

Parameters:

o - a reference to a Chromosome to be duplicated.


setDnaLength

public void setDnaLength (int dnaLength)

This method iterates through all of the Chromosomes in the genePool ArrayList and modifies their dna to a length equal to dnaLength. A value smaller than the previous dnaLength will result in the end of the dna being trimmed. A value longer than the previous dnaLength will result in random values being added to the end of each dna whose upper limit will be valueLength - 1.

Parameters:

dnaLength - the new length of dna to be adopted by all Chromosomes.


setPoolSize

public void setPoolSize (int poolSize)

This method modifies the poolSize property and also affects the contents of the genePool ArrayList. 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 ArrayList to be adopted.


setValueLength

public void setValueLength (int valueLength)

This method modifies the valueLength property and sets the valueBits field to a number of bits large enough to contain the bits in the number valueLength - 1. All new changes in dna will take the change in properties into account. No previous values in dna will be altered, so the user must take this into account in decoding the values in a Chromosome's dna.

Parameters:

valueLength - the new range of values possible at any position in the dna.


setValueBits

public void setValueBits (int valueBits)

This modifies the number of binary bits involved in sub-integer operations and in turn modifies valueBits. This is because the splicing and mutations that will occur will drive the values up to a limit that can be calculated with the following equation:

valueLength = 1 << valueBits

The table below gives an overview of what will happen to valueLength at the lower bit ranges

valueLength valueBits
0 - 1 1
0 - 3 2
0 - 7 3
0 - 15 4
0 - 31 5
0 - 63 6

The maximum number that can be submitted to valueBits is 32 - the amount of bits in an int. If users want to find out how many valueBits they are going to be using, they can use the base2() method, entering the maximum value they expect to use into the method.

Parameters:

valueBits - a value determining the number of binary digits any value in the dna array possesses


sortGenePool

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(), which is exactly what this method does - it is provided simply to get around having to import and use Collections.sort() yourself.


selection

public void selection (ArrayList genePool)

This method removes a Chromosome from the genePool and returns it, based on a combination of the Chromosomes fitness and chance. The method is analogous to assigning portions of a roulette wheel, based on the Chromosome's fitness. The fitter the Chromosome, the more of the wheel they get, without guaranteeing they will be selected first.

As of writing, this method is proving to be problematic with some implementations of the GA. So the user has the option of overriding the selection() method. The overriding method must:

Parameters:

genePool - the property genePool of the GeneticAlgorithm is handed to this method traditionally. genePool is an ArrayList of Chromosomes.


base2

public static final int base2 (int num)

This method return the number of digits num would use if it were converted to a base 2 number - binary. For example: 7 would require 3 digits, being represented in binary as 111. 8 would require 4 digits, being represented as 1000. This function is used internally by the GeneticAlgorithm to determine the valueBits property.

Parameters:

num - a value the user wishes to find the minimum number of binary digits to contain.



Note to self: Don't make a library so bloody flexible next time, all this documentation is taking ****ing ages.