Fast Sequential and Parallel Implementation of Genetic Algorithms using the GAmeter Toolkit

A General Search Paradigm is formulated using a higher order function and, in this context, we discuss the properties which characterize genetic algorithms, tabu search, simulated annealing, etc.From the specification of this general search algorithm, we develop a formal specification of a class of genetic algorithms. By suitable settings of input parameters, we show that a wide variety of (genetic) algorithms can then be instantiated. We have developed kernel software to implement this specification on different architectures. In particular, we have versions running sequentially on Macintosh computers and under Unix and another, parallel version on a Meiko transputer rack. The user interface is identical and the user of the system need have no architecturedependent knowledge to use this software. We briefly describe these implementations and show how simple it is to port genetic algorithms from one achitecture to the other.The toolkit implementing the kernel together with its associated interface is called GAmtier and we report on the use of this software on a number of case studies in combinatorial optimisation. We have encouraging results on a range of examples including the undirected and directed Steiner tree problems.The main strengths of our software is its excellent graphics interface and its wide applicability. However, it also has a number of novel features including dynamic control of parameters such as population size and crossover/mutation probabilities, thus giving additional control to the user.