This research is concerned with the optimisation of multi-modal numerical problems using genetic algorithms (GAs). GAs use randomised operators operating over a population of candidate solutions to generate new points in the search space. As the scale and complexity of target applications increase, run time becomes a major inhibitor. Parallel genetic algorithms (PGAs) have therefore become an important area of research. Coarse-grained implementations are one of the most popular models and many researchers are concerned primarily with this area. The island model was the only one class of parallel genetic algorithm on the coarse-grained processing platform. There are indiscriminate overlaps between sub-populations in the island model even if there is no communication between sub-populations. In order to determine whether the removal of the overlaps between sub-populations is beneficial, the partition model based on domain decomposition was motivated and showed that it can offer superior performance on a number of two dimensional test problems. However the partition model has a certain scalability problem. The main contribution of this thesis is to propose and develop an alternative approach, which replicates the beneficial behaviour of the partition model using more scalable techniques. It operates in a similar manner to the island model, but periodically performs a clustering analysis on each sub-population. The clustering analysis is used to identify regions of the search space in which more than one sub-population are sampling. The overlapping clusters are then merged and redistributed amongst sub-populations so that only one sub-population has samples in that region of the search space. It is shown that these overlaps between sub-populations are identified and removed by the clustering analysis without a priori domain knowledge. The performance of the new approach employing the clustering analysis is then compared with the island model and the partition model on a number of non-trivial problems. These experiments show that the new approach is robust, efficient and effective, and removes the scalability problem that prevents the wide application of the partition model.
| Date of Award | 2008 |
|---|
| Original language | English |
|---|
| Awarding Institution | - Nottingham Trent University
|
|---|