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.