This thesis is concerned with the optimisation of multi-modal numerical problems using genetic algorithms. Genetic algorithms are an established technique, inspired by principles of genetics and evolution, and have been successfully utilised in a wide range of applications. However, they are computationally intensive and consequently, addressing problems of increasing size and complexity has led to research into parallelisation. this thesis is concerned with coarse-grained parallelism because of the growing importance of cluster computing. Current parallel genetic algorithm technology offers one coarse-grained approach, usually referred to as the island model. Parallelisation is concerned with the division of a computational system into components which can be executed concurrently on multiple processing nodes. It can be based on a decomposition of either the process or the domain on which it operates. The island model is a process based approach, which divides the genetic algorithm population into a number of co-operating sub-populations. This research examines an alternative approach based on domain decomposition - the search space is divided into a number of regions which are separately optimised. The aims of this research are to determine whether domain decomposition is useful in terms of search performance, and whether it is feasible when there is no a priori knowledge of the search space. It is established, empirically that domain decomposition offers a more robust sampling of the search space. It is further shown that the approach is beneficial when there is an element of deception in the problem. However, domain decomposition is non-trivial when the domain is irregular. the irregularities of the search space result in a computational load imbalance which would reduce the efficiency of a parallel implementation. To address this, a dynamic load-balancing algorithm is developed which adjusts the decomposition of the search space, at run time according to the fitness distribution. Using this algorithm, it is shown that domain decomposition is feasible, and offers significant search advantages in the field of multi-modal numerical optimisation. The performance is compared with a serial implementation and an island model parallel implementation on a number of non-trivial problems. It is concluded that the domain decomposition approach offers superior performance on these problems in terms of rapid convergence and final solution quality. Approaches to the extension and generalisation of the approach are suggested for further work.
| Date of Award | 2001 |
|---|
| Original language | English |
|---|
| Awarding Institution | - Nottingham Trent University
|
|---|