A Study of Simulated Annealing Techniques for Multi-Objective Optimisation

Abstract

Many areas in which computational optimisation may be applied are multi-objective optimisation problems; those where multiple objectives must be minimised (for minimisation problems) or maximised (for maximisation problems). Where (as is usually the case) these are competing objectives, the optimisation involves the discovery of a set of solutions the quality of which cannot be distinguished without further preference information regarding the objectives. A large body of literature exists documenting the study and application of evolutionary algorithms to multi-objective optimisation, with particular focus being given to evolutionary strategy techniques which demonstrate the ability to converge to desired solutions rapidly on many problems. Simulated annealing is a single-objective optimisation technique which is provably convergent, making it a tempting technique for extension to multi-objective optimisation. Previous proposals for extending simulated annealing to the multi-objective case have mostly taken the form of a traditional single-objective simulated annealer optimising a composite (often summed) function of the objectives. The first part of this thesis deals with introducing an alternate method for multiobjective simulated annealing, dealing with the dominance relation which operates without assigning preference information to the objectives. Non-generic improvements to this algorithm are presented, providing methods for generating more desirable suggestions for new solutions. This new method is shown to exhibit rapid convergence to the desired set, dependent upon the properties of the problem, with empirical results on a range of popular test problems with comparison to the popular NSGA-II genetic algorithm and a leading multi-objective simulated annealer from the literature. The new algorithm is applied to the commercial optimisation of CDMA mobile telecommunication networks and is shown to perform well upon this problem. The second section of this thesis contains an investigation into the effects upon convergence of a range of optimiser properties. New algorithms are proposed with the properties desired to investigate. The relationship between evolutionary strategies and the simulated annealing techniques is illustrated, and explanation of the differing performance of the previously proposed algorithms across a standard test suite is given. The properties of problems on which simulated annealer approaches are desirable are investigated and new problems proposed to best provide comparisons between different simulated annealing techniques.