Date of Award

2007

Document Type

Thesis

Publisher

Edith Cowan University

Degree Name

Bachelor of Science Honours

School

School of Computer and Security Science

Faculty

Faculty of Computing, Health and Science

First Supervisor

Phillip Hingston

Second Supervisor

Dr Martin Masek

Abstract

The two main issues relating to the use of Multiobjective Evolutionary Algorithms (MOEAs) are the efficiency and effectiveness of the algorithms. As a result of the multiobjective and multi dimensional nature of MOEAs, the overall execution time that is taken to solve real world problems with MOEAs can be significant. Therefore, a few studies have recently been completed to address these performance issues by the use of parallelisation methods. The most widely known parallel Multiobjective Evolutionary Algorithm (pMOEA) models are the Master-slave, the Island, and the Diffusion models. The Master-slave and the Island models are generally implemented using message passing parallelisation mechanisms in a cluster environment while the Diffusion model is implemented using a shared memory parallelisation mechanism. Although any MOEA can be made to execute in parallel based on the above models, there is no known study that identifies which parallelisation model is suitable for problems based on their characteristics. In this study, we compared a serial MOEA and the above-mentioned Master-slave and Island pMOEAs to identify which parallelisation models perform best in a cluster environment in solving problems with certain characteristics. Modality, separability, and bias were the problem characteristics that were studied. The study was conducted using implementations of one serial and the Master-slave and the Island pMOEA versions of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) in a clustered environment. The parallelisation of NSGA-II was achieved by the use of Message Passing Interface (MPI) routines that were executed on multiple processors of a cluster. At the end of the study, the speedup and the quality improvement of the results achieved by the Master-slave and the Island pMOEA models over the serial MOEA was examined. Most problem characteristics had a significant effect on the effectiveness of the Masterslave and the Island pMOEA models. The Master-slave model was marginally more effective than the Island model in solving problems with the multi-modal problem characteristic. However, the Island model with a suitable amount of migration was more effective than the Master-slave model in solving problems with uni-modal, separable, non-separable, and biased problem characteristics. The Master-slave and the Island models were equally effective in solving problems with the non-biased problem characteristic. The results of this research can be used by others to determine which parallelisation models should be used when parallelising MOEAs in a cluster environment to solve problems with known characteristics.

Download

Share

 
COinS