Abstract

Multi-objective problems, requiring the optimisation of two or more conflicting 
criteria, abound in the real world. Multi-objective optimisers produce solution 
sets that represent the trade-offs between problem criteria. As a result of 
computational and space limitations, a multi-objective optimiser is often unable
to retain all generated trade-off solutions and instead must endeavour to keep the
solutions that best cover the trade-off front. Indicators which map these sets into
unary values that can be easily compared are valuable and are used frequently in
multi-objective performance assessment, or as a part of the selection operator of a
multi-objective optimiser.

One indicator which incorporates many mathematical properties favourable for use
in multi-objective optimisation is the hypervolume indicator. Hypervolume is the
n-dimensional space that is "contained" by a set of points. It encapsulates in a
single unary value a measure of the spread of the solutions along the Pareto front,
as well as the closeness of the solutions to the Pareto-optimal front. However,
hypervolume has one serious drawback: calculating hypervolume exactly is NP-hard 
and exponential in the number of objectives. This thesis describes research into 
improving the performance of hypervolume calculation and techniques for its use.
One major contribution of this thesis is the introduction of two new calculation
algorithms, IIHSO and WFG, which outperform existing hypervolume calculation
algorithms on several forms of test data. The best performing of the two, WFG,
greatly outperforms all existing algorithms on tested data sets and represents a
substantial improvement in the feasibility of hypervolume calculation. The thesis
also introduces a number of objective reordering heuristics which improve the typical
performance of several existing hypervolume algorithms that use a dimension sweep
approach.

The use of hypervolume within multi-objective optimisers is a relatively new and
developing area. It is not yet known how to best apply hypervolume as part of the
selection criteria within a multi-objective optimiser. Furthermore, hypervolume's
high cost can limit its use within optimisers that require many solutions to be
evaluated. However, it has great promise for use in optimisation if the performance
issue can be limited.

In these hypervolume-based selection and archiving schemes, it is typically necessary 
to determine the solution that contributes the least hypervolume to a set. This
thesis introduces the IHSO algorithm which quickly determines the hypervolume
contributed by a solution. It also describes heuristics designed to improve IHSO's
typical performance. Additionally, it describes and analyses techniques that reduce
the calculations necessary to find the solution which contributes the least hypervolume.
When using hypervolume as part of a selection or archiving process, one important
goal is to reduce the size of a solution set while maximising the hypervolume of this
set. Finding the subset with the optimal hypervolume using naive schemes, results
in combinatorial explosion in the number of hypervolume calculations required.
For this reason, this thesis introduces and compares several simple meta-heuristic
schemes that attempt to maximise the hypervolume of selected subsets. A local
search and two greedy schemes are proposed in this thesis as means of overcoming
this problem.