Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization

Joshua D. Knowles

Ph.D. Thesis, 2002, Department of Computer Science, University of Reading, UK.
Examiners: Professor Kalyanmoy Deb and Professor Kevin Warwick.
Thesis supervisor: Mr. David Corne.


In recent years, a gradual increase in the sophistication of multiobjective evolutionary algorithms (MOEAs) for Pareto optimization has been seen, accompanied by an ever-growing list of applications. Despite this trend, however, the proposition that methods based on local search may be a good alternative approach --- with the advantages of ease-of-use and lower computational overhead --- has not been thoroughly tested. In this thesis we develop a novel, local-search algorithm for Pareto optimization, called PAES, enabling us to test and compare MOEAs against this philosophically different search method.

To help perform this testing, we develop new statistical performance metrics for evaluating collections of approximations to the Pareto set, based on a critical review of currently available methods. Using these metrics, we find that PAES performs well in comparison with popular, modern MOEAs, on a variety of test function and real-world telecommunications problems. These results suggest that local-search-based methods for Pareto optimization do merit further investigation.

Some of the elements of PAES are also more generally applicable for use in the design of other algorithms. In particular, the archiving strategy used by PAES, which incorporates rules to bound the number of solutions stored, and to ensure that they are distributed widely and evenly in objective space, may be used in any multiobjective search algorithm for storing solutions. We demonstrate the generality of the basic PAES procedures by outlining several more sophisticated variants, including multi-start and tabu search algorithms.

We also combine local-search and population-based evolutionary methods together, forming a new memetic algorithm, M-PAES, for Pareto optimization. M-PAES is tested using a number of problems from the literature, and is found to exhibit promising performance compared to other methods. Finally, we use M-PAES to provide a set of benchmark results for some difficult new instances of the multi-criteria minimum spanning tree (mc-MST) problem.

Other publications by Joshua Knowles

Last modified: Tue Feb 4 11:48:35 CET 2003