A Versatile Genetic Algorithm System in Ada: Implementation and Applications
Max Edwards
During development, the design of the system as a whole went through several revision phases, each inevitably adding a new layer of complexity to the software, but also a new level of versatility. The "final" design as presented in this report is by no means without room for further development and improvement, but nevertheless possesses a structure which has proved to be very suitable for the diverse applications originally intended, and in most aspects arguably meets the requirements stated in section 3.2.
The overall design specification can be summarised as consisting of packages in four main categories:
1. The core Genetic Algorithm "engine"
2. Building-block packages
3. Problem packages
4. Auxiliary packages, of generally useful non-genetic routines
The following sub-sections describe how this categorisation was arrived at, and list the packages within each category along with their purposes. Subsequent sections present the structure of the system as whole, in terms of the packages that it consists of.
The purpose of this category is to provide an abstract representation of the main genetic algorithm concepts. It implements all the higher level problem-independent types and procedures that are need to create a genetic algorithm, most notably a Population type structure and a procedure which manipulates it in order to breed a new generation. Category 1 packages form a high-level interface between the main program and packages in the other categories.
The category consists of two packages which form the backbone of all genetic algorithms created using VAGAS; many application-specific modules, from the other categories, must be added before a working program can be created. The core GA packages are:
• Genetic, a package of declarations and general GA procedures. This package is used by all other packages except those in the fourth "Auxiliary routines" category;
• Genetic_Algorithm, a generic package which when instantiated2 for a particular problem provides all the data structures and procedures necessary to run GAs to solve that problem;
The second package category comes from the requirement that useful but non-essential genetic algorithm components, namely common chromosome types and operators, must be made available to the GA experimenter.
This category therefore consists of packages which provide many of the types and sub-programs needed for constructing common genetic algorithms; in this category are "Chromosome packages", selection and fitness-scaling routines, and user-interface facilities. These packages were designed to integrate very easily into the main Genetic_Algorithm package, by conforming to the specifications of the various objects that it requires upon instantiation.
Into this category fall the following packages:
• Standard_Chromosome and Permutation_Chromosome: "chromosome packages", which define and manipulate common chromosome structures, allowing various crossover and mutation operators to be selected.
• Selection and Scaling: useful selection and fitness-scaling routines.
• Fixed_Point_Coding: a facility for easy implementation of common binary codings.
• Report: a user-interface package, providing facilities for the input and output of some of the types defined in the Genetic package, and displaying graphically the statistics from a genetic algorithm run.
The third package category comes from the requirement that common or interesting GA problems should be made easily accessible in a GA-compatible form. This requirement, like many others, was not identified until the implementation process was well under way. After the system had been in use for a while, and several working GAs had been implemented, it was realised that a method of encapsulating an application problem, into a package which could be readily used with the main VAGAS packages, would be very useful. This lead directly to the creation of the third design category, which was to consist of "problem packages" implemented to provide a chromosome package and a fitness function which acts on the chromosome type, both in a form suitable for use with the main Genetic_Algorithm package. In addition, they were to provide various useful problem-specific routines, e.g. for displaying potential solutions.
2The designers of Ada recognised the fact that many algorithms are not concerned with the exact nature of some of the types and procedures that they use. They therefore provided a mechanism which allows such algorithms to be implemented in a "generic manner", independent of these objects. In order to use a generic procedure or package, it must first be "instantiated" by providing details of these types and procedures. This feature of Ada makes it far more suitable for modular programming than older languages such as C.
Common problems packaged in this way are very useful when a problem is to be implemented in several different programs, e.g. implementing a "meta-level" genetic algorithm to optimise the parameters for another GA program that has already been written. In addition to greatly reducing the amount of code that has to be re-written, the availability of a problem package also makes changes to the main problem much easier.
The packages in this category contain everything necessary to create genetic algorithms for common NP-hard or optimisation problems. Four such problem packages were developed:
• TSP_Pack: a Travelling Salesperson Problem (see 4.1);
• Meta_Pack: a Meta-Level problem, that of optimising the run-time parameters for a given genetic algorithm (see 4.2);
• TTBL_Pack: a basic Time tabling Problem (see 4.3);
• DeJong_Pack: DeJong's Optimisation Test Functions (see 4.4);
Further thought lead to the realisation that certain auxiliary packages would almost certainly be required, which would not only be problem-independent but GA-independent as well, and thus category 4 was created.
These packages contain procedures not related to genetic algorithms, possibly incorporating system-dependent aspects. There are three packages of such routines, all of which are system dependent in some way, and may well need to be rewritten (with the same specification) or augmented for use on systems other than the University of York Department of Computer Science computing facilities. Into this category fall:
• Random_Numbers, providing basic random-number generators. The package listing presented in the Appendix makes use of random number facilities within the York Ada mathematical libraries - ideally, a standalone random numbers package would have been written.
• Basic_Maths, providing essential mathematical functions such as sine and square-root. This again relies on the York Ada maths libraries.
• Graphics, defining types and procedures for basic graphical facilities. The system-dependent aspect of this package is simply that the only instance of a Display procedure provided uses the York bitmap format, not likely to be widely available, and so a more common format such as "GIF" or "Windows BMP" would have been more appropriate had the relevant information been available.
The diagram in figure 3.1. shows how the main genetic components of VAGAS are designed to be used together. It demonstrates how various "objects" (types, procedures and functions), which are required by the main Genetic_Algorithm package, are provided by the other packages which make up the VAGAS system. The purposes of these objects is summarised in 3.5.1, whilst complete descriptions of each package can be found in 3.6. and Appendix A. The diagram does not show how the non-genetic auxiliary packages (Graphics, Basic_Maths, Random_Numbers) are used.
The diagram shows how the Genetic_Algorithm package, once instantiated for the problem in hand, is used by the main program to carry out GA runs for that problem.