Specification
3.1 System
specification
The requirements of the
system were captured after a study in genetic algorithms and a
specification was produced. The specification was revised several times
as the project progressed. A list of the functional specifications
(Table 3.1) provides a quick reference as to which aspects of the system
were part of the original specification and
which of them were implemented in the final system, including the
functionality added during the project.
Table 3.1 – List of the system’s general functional
specifications
Function Description
|
Original system specification |
Final system specification |
|
Genetic algorithm engine |
Yes |
Yes |
|
GUI form filling front end for the genetic
algorithm engine parameters setting |
Yes |
Yes |
|
Interface the program so that third party fitness
functions written in the same programming language can be used with
it. |
Yes |
Yes |
|
Interface the program so that third party fitness
functions written in a different to the tool programming language
can be used with it. |
Yes |
Dropped at specification |
|
Number of fitness functions to demonstrate the
genetic algorithm engine’s capability |
Yes |
Yes |
|
Genetic algorithm developers package base
|
No |
Yes |
|
Plot a graph to show the progress of the best and
average/median fitness of a population as the genetic algorithm is
executing |
Yes |
Dropped at design |
|
Show the progress of the best and average/median
fitness of a population as the genetic algorithm is executing in
numerical format |
Yes |
Yes |
|
Provide for multiple execution of a genetic
algorithm with the same parameters (but different initial randomly
generated population) and list comparable summaries of the
executions |
No |
Yes |
|
Log the execution of the algorithm to a text file |
Yes |
Yes |
The system consists of two
parts – the genetic algorithm engine and the front end GUI. The table
above lists only the main functions of the system, abstracting the
actual genetic algorithm engine functionalities for neatness. The list
of the functional specifications of the genetic algorithm engine is
shown separately (Table 3.2).
Table 3.2 - List of the genetic algorithm functional
specifications
Function Description
|
Original system specification |
Final system specification |
|
Chromosome binary alphabet |
Yes |
Yes |
|
Gray coded genotype |
Yes |
Yes |
|
Single chromosome genotype |
Yes |
Yes |
|
Multiple chromosome genotype, where all the
chromosomes have the same parameters |
No |
Yes |
|
Whole number (integer) chromosome decoding |
Yes |
Yes |
|
Uniform real number (uniformly distributed float)
chromosome decoding |
Yes |
Yes |
|
String chromosome decoding |
Yes |
Dropped at implementation |
|
Invalid chromosome rejection |
No |
Dropped at implementation |
|
User specified fitness range |
Yes |
Yes |
|
User specified fitness optimisation (minimising
or maximising) |
No |
Yes |
|
Infinity considered as part of the fitness range |
Yes |
Dropped at specification |
|
User specified population size with a value limit |
Yes |
Yes |
|
Roulette wheel parent selection according to rank
not fitness (linear normalisation) |
Yes |
Yes |
|
Tournament with user specified number of
participating candidates |
Yes |
Yes |
|
2 parents genetic operations |
Yes |
Yes |
|
1,3 and 4 parents genetic algorithm |
Yes |
Dropped at design |
|
Single point crossover with a moving randomly
generated crossover position (regenerated for every crossover) |
Yes |
Yes |
|
Single point crossover with a fixed randomly
generated crossover position |
No |
Yes |
|
Single point crossover with a fixed user
specified crossover position |
No |
Yes |
|
Multiple points crossover with randomly generated
number of crossover points distributed uniformly over the bit
pattern |
Yes |
Yes |
|
Multiple points crossover with a user specified
number of crossover points distributed uniformly over the bit
pattern |
Yes |
Yes |
|
Uniform crossover using randomly generated
masking bit pattern |
Yes |
Dropped at design |
|
Uniform crossover using user specified masking
bit pattern |
Yes |
Dropped at design |
|
Heuristic crossover using user a specified
formula |
Yes |
Dropped at design |
|
Last bit flip mutation |
Yes |
Yes |
|
Flip random number of bits not exceeding the user
specified maximum number of points |
Yes |
Yes |
|
Single random bit mutation – uniform mutation
(regenerated for every mutation) |
No |
Yes |
|
Termination of algorithm after a user specified
number of crossovers (1 crossover = 2 function calls) |
Yes |
Yes |
|
Termination of algorithm after a user specified
target fitness or better is reached (for maximising or minimising
functions) |
Yes |
Yes |
|
Termination of algorithm after a user specified
target fitness or better becomes the average fitness of the
population |
Yes |
Dropped at design |
|
Termination of algorithm after the difference
between the best and worst fitness converges to a certain percentage
of that original difference |
No |
Yes |
The primary aim of the
project is to have a working genetic algorithm engine with a GUI front
end and a number of fitness functions to demonstrate its performance.
Most of the functions form the original
specification have been successfully implemented and a complete
software tool has been produced.
Those functions on the
tables that were removed from the original specification at the
feasibility study stage will be discussed in the following section. The
functions that were not completed because of time restrictions will be
considered in the implementation chapter. The remaining functions that
were not implemented and all those successfully done will be discussed
in the design chapter of this project.
3.2 Design
issues
A design issue was the
integration of the genetic algorithm tool in such a way that fitness
functions written in a different language to the software tool’s
operation environment, interpreter or compiler. Strictly speaking this
is feasible to implement; in the simplest way by sharing memory
locations or a text file between the two environments. There are many
issues involved when variable have to be passed from one environment to
another. One of them is the floating-point precession and number
interpretation as a whole. Many development environments (Java), do not
allow direct memory access, and even for those which do (C, C++) it is
considered risky because of possible interference with memory space of
other threads in multithreaded operating systems. Another issue is speed
of execution; when data is to be passed from the fitness function to the
genetic algorithm and vice versa trough a text file, the performance of
the genetic algorithm will be bottlenecked by the speed of the secondary
storage. The design, implementation and execution overheads of this
function for the genetic algorithm tool were considered to be
disproportionate to the function’s necessity for the completeness of the
project. Even more, Microsoft has integrated 30 different programming
languages into their new “dot NET” framework that is supposed to enable
software developers to integrate software written in different
programming languages.
The other functionality
that was removed from the specification during the feasibility study was
part of the genetic algorithm – the choice for the target fitness of a
genotype in the genetic algorithm to be negative or positive infinity.
Strictly speaking this is possible to implement in some programming
languages (Java), as they provide a special flag to represent negative
and positive infinity of a floating point variable. There
were no fitness functions found that would
necessitate this option, probably because a specific solution is the
target that must have a specific fitness.
The only concern for
building the rest of the system is whether there will be enough time for
the specified functionality to be included.
3.3 Tools
required
The use of a number of
tools and development resources would be also necessary to develop the
“General Genetic Algorithm Tool” (GGAT) and produce this report. Here is
a list of all the design, implementation, testing and report producing
software that would be necessary for the completion of this project.
|
UML Tools: |
Together 4.0 |
|
Programming
Environment: |
Java Development Kit
1.3 (Sun Microsystems) |
|
Application Programming
Interfaces (APIs): |
Java 2 Platform API
Specification |
|
Integrated Development
Environments (IDEs): |
Forte for Java 2.0 (Sun
Microsystems) |
|
Image editing software |
Ulead Photoimpact 6 |
|
Graph software: |
Advanced Grapher 1.0 |
|
Word processing
software: |
MS Word 2000, Emacs, MS
Notepad 5.0 |
|
Web design software: |
MS FrontPage 2000 |
