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, Positionbased Ordered Mutation Reproduction, Orderbased 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 nonposition value mutated.
 Ordered

 Orderbased
 Two randomly selected elements are swapped.
 Positionbased
 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

 Positionbased
 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.
 Orderbased
 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:
