External Specification

The toolkit will be composed of a collection of components organised in a number of component hierarchies which describe their relationships. The taxonomic hierarchy groups components with similar tasks together, for example apples are under fruit. The functional hierarchy shows a components use of other components, for example apples are under teeth. The containment hierarchy shows a components storage of other components, for example pips are under apples. All components are also grouped as part of the core, auxiliary, or extended toolkit. Components are presented here according to the taxonomic hierarchy with other hierarchies described in the text.

To create a genetic algorithm with this toolkit the programmer has to combine a number of predefined components with a few that have been hand coded. A simple example of constructing a genetic algorithm using the toolkit follows with component names emphasised. A description of each component can be found later in the specification.

Classic Genetic Algorithm

A genetic algorithm is required to optimise a simple function.

f(x) = x.sin(10¹.x) + 1.0

The problem is to find x from the range [-1, 2] which maximises the function f, ie to find x0, such that

f(x0) ³ f(x) for all x Î [-1, 2]

Two important decisions have to made about the genetic algorithm: how to represent potential solutions, and which model will drive the genetic algorithm. The use of classic genetic algorithm techniques dictates our choices here. The Generational Model will define the order of actions within our algorithm and solutions will be represented using a Bit Vector. To store a solution to an accuracy of 6 decimal places will require 22 bits for each vector.

To decide which solutions are better an Evaluation function must take the bit vector representation and return a number

E = -1.0 + v.3/(222 - 1)

where v is the bit vector interpreted as a positional code integer, this can be done using Function Binary Bit Vector Evaluation.

The initial Population of solutions will be created using Bit Vector Random Initialisation and subsequent solutions will be bred using two Reproduction operators, Bit Random Single Vector Mutation and One Point Vector Crossover. Operator distribution is 22% and 25% respectively with the remainder made up using Clone.

The Toolkits

The core toolkit consists of those components required to implement the classic genetic algorithm "The Blues" as shown in the report.

Generational Model, Count Ending, Bit Representation, Vector Representation, Individual, Population, Bit Random Initialise, Vector Random Initialise, Evaluation, Unity Fitness, Roulette Wheel Selector, Clone Reproduction, Xor Reproduction, Position-based Ordered Mutation Reproduction, Order-based Ordered Crossover Reproduction, Random

The auxiliary toolkit consists of those components which extend functionality for genetic algorithms such as decision support.

History

The extended toolkit consists of all components suitable for other genetic algorithms.

Component Overview

The Model, or breeding technique, component controls the general activity of the genetic algorithm. A genetic algorithm consists of a single Model and subsidiary components controlled by it.

The Ending component controls the length of time spent on the genetic algorithm.

The Representation component encodes a possible solutions. Choosing which Representation is important to the design of the entire genetic algorithm.

The Individual component is a particular instance of a possible solution. Each Individual is associated with a Representation and a unique identification which separates it from all other Individuals, even those with identical Representations.

The Population component is a bag of Individuals or a bag of Populations. Operations include all standard bag operations.

The Evaluation component converts a Representation to a numerical representation of how good a solution it encodes.

The Fitness component converts and Individuals Evaluation into its fitness compared to the rest of the Population.

The Selector component chooses an Individual from a Population, perhaps using information about that Individual and the rest of the Population.

The Reproduction component creates N new Individuals for the destination Population from the source Population.

The History component can store an association of Individuals, their parents and Reproduction components or Initialisers, and the Random settings.

The Random component generates pseudo random numbers starting from either a given seed or the seed is taken from the time.

Model Component

The Model, or breeding technique, component controls the general activity of the genetic algorithm. A genetic algorithm consists of a single Model and subsidiary components controlled by it. Although the toolkit provides a range of Model components it is impossible to provide the variety which may be required. Instead unusual Models can be hand coded making use of subsidiary components from the toolkit.

Functional: Ending, Individual, Population, Initialise, Evaluation, Fitness, Selector, Reproduction, History, Random

Containment: Ending, Population, Initialise, Evaluation, Fitness, Selector, Reproduction, History, Random

Generational: The first Population is Initialised then a new Population of the same size is created using the Reproduction operator. The current Population is then replaced and the new Population used for further breeding.
Generational Elitism: Generational but the first Individual of the new Population is a clone of the best Individual of the previous Population.
Tournament: Generational but new Individuals are together with current Individuals. N Individuals are selected and the best is placed in the next generation. This is repeated until the next generation is full.
Steady State: The first Population is Initialised then N new Individuals are created using the Reproduction operator. These replace N individuals selected from the old population.
Steady State Without Duplicates: Steady State but new Individuals must not have identical Representations to current Individuals.
Preselection: Steady State but Individuals only replace inferior parents.

Ending Component

The Ending component controls the length of time spent on the genetic algorithm.

Functional:

Containment: Ending

And: The Model continues until both given ending conditions are true.
Or: The Model continues until either of two ending conditions are true.
Count: The Model is allowed N cycles before halting.
Time: The Model is allowed N seconds before halting.
Evaluation: The Model continues until a given Evaluation is reached.
Convergence: The Model continues until the population converges and no further change in Evaluation is seen.

Representation Component

The Representation component encodes a possible solutions. Choosing which Representation is important to the design of the entire genetic algorithm. Functional: Containment: Representation

Bit: A single bit, 0 or 1.
Number: A single number with value between upper and lower bounds.
Vector: A sequence of elements with identical Representations.
Matrix: A matrix of elements with identical Representations.
Ordered: A particular permutation of elements draw from a particular Representation.
Tag: A integer position paired with another Representation, can be used to make a tagged vector for use with the Inversion operator.

Individual Component

The Individual component is a particular instance of a possible solution. Each Individual is associated with a Representation and a unique identification which separates it from all other Individuals, even those with identical Representations.

Functional: Representation

Containment: Representation

Population Component

The Population component is a bag of Individuals or a bag of Populations. Operations include all standard bag operations.

Functional: Representation, Individual, Evaluation

Containment: Individual, Population

Initialise Component

The Initialise component is used to create a number of new Individuals for a given Population. The Initialiser must be tailored to particular Representations.

Functional: Representation, Population, Evaluation, Selector, Reproduction, Random

Containment: Initialise, Reproduction

Random

Bit: Assigned 0 or 1 with equal probability.
Number: Assigned a number between upper and lower boundary with equal probability.
Vector: Initialise each element separately.
Matrix: Initialise each element separately.
Ordered: Assign one of the possible permutation of elements with equal probability.
Tag Vector: Initialise each Tag separately and assign the correct integer position.

Search

Initialise N Individuals at a time and pick the one with the highest Evaluation. Selection between Individuals with equal fitness will be made randomly.

Distributed

Generated Individuals are as different as possible from each other. This technique must be tailored for each Representation.

Heuristic

Individuals with particular characteristics are generated using heuristics particular the problem. This technique must be tailored to each Representation and each problem.

Evaluation Component

The Evaluation component converts a Representation to a numerical representation of how good a solution it encodes. The evaluation is dependent on both the Representation and the problem. In most situations the Evaluation component will be hand coded by the programmer.

Functional: Representation, Individual

Containment: Evaluation

Vector

Bit

Binary: Evaluation is equal to the positional code interpretation of the bit vector.
Gray: Evaluation is equal to the gray code interpretation of the bit vector.

Function

Apply a known function to the result of another Evaluation.

Fitness Component

The Fitness component converts and Individuals Evaluation into its fitness compared to the rest of the Population.

Functional: Individual, Population Containment:

Unity: Fitness is equal to evaluation.
Windowing: Fitness is equal to the amount an Individual's Evaluation exceeds the minimum evaluation within the Population minus some known guard value.
Linear Normalisation: Order Individuals by decreasing Evaluation. The best Individual is given a known fitness and thereafter the fitness is decreased by a constant amount.
Linear Scaling: Fitness is equal to (a * evaluation + b) where a and b are normally selected so that the average fitness is mapped to itself and the best fitness is increased by some desired multiple.
Sigma Truncation: Fitness is equal to (evaluation + average evaluation - c * s) where c is chosen from around 1 to 5 and s is the Population's standard deviation. Negative fitness values are set to zero.
Power Law Scaling: Fitness is equal to (evaluation k) where k is a problem dependent value close to 1.

Selector Component

The Selector component chooses an Individual from a Population, perhaps using information about that Individual and the rest of the Population.

Functional: Individual, Population, Fitness, Random

Containment:

Best: Individual with the highest fitness within the Population is selected. Selection between Individuals with equal fitness will be made randomly.
Worst: Individual with the lowest fitness within the Population is selected. Selection between Individuals with equal fitness will be made randomly.
Random: Each Individual has an equal probability of being selected.
Roulette Wheel: Each Individual has a probability of being selected proportional to its fitness divided by the average fitness of the Population.
Anti Roulette Wheel: Each Individual has a probability of being selected inversely proportional to its fitness divided by the average fitness of the Population.
Stochastic: The first Individual is chosen using a roulette wheel and the subsequent (N - 1) Individuals taken evenly from the entire population, then the cycle repeats.
Expected Value: Associated with each Individual is a count equal to that Individual's fitness divided by the average fitness of the Population. Whenever an Individual is selected to reproduce, using another Selector component, its count is decremented by one. When a count falls below zero the Individual is no long available for further selection.
Similarity: The Individual selected is that closest to the given Individual. Selection between equally similar Individuals will be made randomly. This technique must be tailored to each Representation and each problem.

Reproduction Component

The Reproduction component creates N new Individuals for the destination Population from the source Population. Reproduction components must be tailored to a each Representation and each Problem.

Functional: Representation, Individual, Population, Selector, Random

Containment: Selector, Reproduction

Clone

Individual's Representation is an exact copy of the parent's Representation.

Xor

Individuals are created with either one Reproduction component or another but not both using the given probability distribution.

And

Individuals are created with one Reproduction followed by another. The second Reproduction component may require several Individuals to be generated by the first component.

Or

Individuals are created with either of two Reproduction components or both using the given probabilities. The second Reproduction component may require several Individuals to be generated by the first component.

Inversion

Tag Vector

Biased: Individual's Representation is the same as the parent's Representation except that the order of a sequence of elements between two random points has been reversed.
Unbiased: Individual's Representation is the same as the parent's Representation except that the order of a sequence of element between a random point and a randomly selected end has been reversed.

Mutation

Bit

Inverts value.

Number

Random: Assign a number between upper and lower boundary with equal probability.
Creep: Modify the number by either adding or subtracting a know value.

Vector

Single

Each element has an equal probability of being chosen and mutated.

Deletion

A randomly chosen element is deleted. Only suitable for variable length vectors.

Addition

Duplication: A randomly chosen element is duplicated with the duplicate placed next to the original. Only suitable for variable length vectors.
Initialised: A newly initialised element is inserted into the list. Only suitable for variable length vectors.
Related: A pair of adjacent elements is randomly chosen and a new element related to each is inserted between them. This must be tailored to each Representation and each problem. Only suitable for variable length vectors.

Tag Vector

Cut: Parent vector is cut at a random point. Only suitable for messy genetic algorithms.
Single: Each element has an equal probability of being chosen and the non-position value mutated.

Ordered

Order-based: Two randomly selected elements are swapped.
Position-based: One randomly selected element is placed before another.
Scramble Sublist: Select a sublist of size N and randomly permute it.

Random Hill Climb

N new Representations are created using a Mutation component and the one with the best Evaluation is chosen. Selection between Individuals with equal evaluation will be made randomly.

Crossover

Number

Average: Assign the average of two parent numbers.

Vector

One Point: A crosspoint is selected at random and the tail of each parent is swapped with the other parent.
Two Point: Two crosspoints are selected at random and the elements between are swapped with the other parent. Initial and final elements of the vector are considered adjacent.
Multi Point: N pairs of crosspoints are selected at random and the elements between are swapped with the other parent. Initial and final elements of the vector are considered adjacent.
Segmented: Multi Point Crossover in which the number of segments can vary. For each element there is a probability that the current segment will end and a new one begin.
Uniform: Each element is taken from either parent with equal probability.
Shuffle: Randomly permute both parent vectors, perform a Crossover, and reverse permute them.
Traverse: Apply given Crossover to each pair of elements in parent vectors.

Tag Vector

Splice: Parent's representations are joined end to end. Only suitable for messy genetic algorithms.

Ordered

Position-based: A set of positions is randomly selected and the positions of elements selected in one parent is imposed on the corresponding elements in the other parent.
Order-based: A set of positions is randomly selected and the order of elements in the selected positions in one parent is imposed on the corresponding elements in the other parent.

Repair

The parents representation is corrected so it no longer violates constraints made on the solution.

History Component

The History component can store an association of Individuals, their parents and Reproduction components or Initialisers, and the Random settings.

Functional: Individual, Reproduction, Initialise, Random

Containment: Individual

Random Component

The Random component generates pseudo random numbers starting from either a given seed or the seed is taken from the time.

Functional:

Containment: