Practical issues concerning the implementation and application of genetic algorithms to a number of optimisation problems are the main subjects dealt with in this thesis. Genetic algorithms (GAs) are an attractive class of computational models that attempt to mimic the mechanisms of natural evolution to solve problems in a wide variety of domains. A general purpose genetic algorithm toolkit is developed and applied to the Steiner Problem in Graphs and the Radio Link Frequency Assignment Problem. The toolkit is then extended to cover a large number of parallel genetic algorithm models which are then compared. Solutions for the two case studies are presented with each of the parallel GAs. The thesis begins with a general introduction to genetic algorithms. Holland's original genetic algorithm is described and it's workings illustrated on a simple function minimisation problem. The notion of a schema or similarity template as a basic building block in genetic algorithms is introduced and the schema theory presented. A description of important theoretical results is given and the introduction to genetic algorithms continues with practical issues that are dealt with in the second chapter. The basic components of a modern genetic algorithm are outlined and examples for important components, as found in the Jiterature, are given. The second chapter concludes with the description of a number of applications of genetic algorithms to areas such as function optimisation, combinatorial optimisation, genetic programming, process control and classifier systems. In Chapter 3, the sequential GA toolkit, GAmeter, is described. The General Search paradigm around which the toolkit is implemented is introduced. Notable characteristics of the genetic algorithms kernel and the user interface are mentioned. A popular function optimisation problem is used to illustrate important aspects of genetic algorithms and aspects specific to the toolkit. The Steiner Tree problem in graphs is the first of two case studies examined in detail in this thesis. This is a popular NP-complete problem with a range of applications in areas such as communications, scheduling and printed circuit design. A survey of standard techniques, such as simplification methods, exact algorithms and heuristics is given. Two possible representations for solving it using genetic algorithms are described and applied to a well-known set of problems. Chapter 4 concludes with a comparison of the best GA technique with other heuristics for this problem. The Radio Link Frequency Assignment Problem, described in Chapter 5, is the second case study investigated in this thesis. Genetic algorithms were applied to this problem as part of a EUCLID (European Cooperation for the Long Term in Defence) funded multi-national study to compare exact and heuristic techniques for hard combinatorial problems associated with military applications. A number of approaches used to solve this highly constrained, hard problem for genetic algorithms are described. These include a range of new genetic operators and catalytic terms that are added to the fitness function. Apart from the direct approach to solving this problem using genetic algorithms, for which the majority of operators and catalytic terms apply, an indirect approach which combines genetic algorithms with backtracking is described. The possibility of using a meta genetic algorithm to chose the best of a multitude of options, e.g. genetic operators and parameter settings for a GA applied to the Radio Link Frequency Assignment Problem is investigated. Results are reported for two sets of problems that were used by all participants in this project. An overview of the techniques investigated for this project is given and the chapter concludes with comparisons between all these techniques. In Chapter 6, an overview of general aspects in parallel processing is given. Parallel computer architectures, parallel programming paradigms and performance measurement are the main subjects dealt with in this chapter. Special emphasis is given to material relevant to the investigation on parallel genetic algorithms, presented in the following chapter. In Chapter 7, parallel genetic algorithms are examined in some detail. A number of parallel GA models are described and classified according to whether they are designed around the sequential GA or around a more natural model. A ParallelSequential General Search paradigm is presented that unifies the various parallel models and is used to extend the GA toolkit into a parallel GA toolkit for a parallel system based on Transputers. The parallel GA models are applied to problems from both of the case studies considered in this thesis. A comparison between the various parallel GA models concludes this chapter. The thesis finishes with a summary of a number of conclusions drawn from this research together with some suggestions for how this work may be continued in the future.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:318080 |
| Date | January 1996 |
| Creators | Kapsalis, A. |
| Publisher | University of East Anglia |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0019 seconds