AN INVESTIGATION OF MULTI-OBJECTIVE HYPER-HEURISTICS FOR MULTI-OBJECTIVE OPTIMISATION
Maashi, Mashael S. . 2014
In this thesis, we investigate and develop a number of online learning
selection choice function based hyper-heuristic methodologies that attempt to
solve multi-objective unconstrained optimisation problems. For the first time,
we introduce an online learning selection choice function based hyperheuristic
framework for multi-objective optimisation. Our multi-objective
hyper-heuristic controls and combines the strengths of three well-known
multi-objective evolutionary algorithms (NSGAII, SPEA2, and MOGA), which
are utilised as the low level heuristics. A choice function selection heuristic
acts as a high level strategy which adaptively ranks the performance of those
low-level heuristics according to feedback received during the search process,
deciding which one to call at each decision point. Four performance
measurements are integrated into a ranking scheme which acts as a feedback
learning mechanism to provide knowledge of the problem domain to the high
level strategy. To the best of our knowledge, for the first time, this thesis
investigates the influence of the move acceptance component of selection
hyper-heuristics for multi-objective optimisation. Three multi-objective choice
function based hyper-heuristics, combined with different move acceptance
strategies including All-Moves as a deterministic move acceptance and the
Great Deluge Algorithm (GDA) and Late Acceptance (LA) as a nondeterministic
move acceptance function.
GDA and LA require a change in the value of a single objective at each
step and so a well-known hypervolume metric, referred to as D metric, is
proposed for their applicability to the multi-objective optimisation problems. D
metric is used as a way of comparing two non-dominated sets with respect to
the objective space. The performance of the proposed multi-objective
selection choice function based hyper-heuristics is evaluated on the Walking
Fish Group (WFG) test suite which is a common benchmark for multi-objective
optimisation. Additionally, the proposed approaches are applied to the vehicle
crashworthiness design problem, in order to test its effectiveness on a realworld
multi-objective problem. The results of both benchmark test problems
demonstrate the capability and potential of the multi-objective hyper-heuristic
approaches in solving continuous multi-objective optimisation problems. The
multi-objective choice function Great Deluge Hyper-Heuristic
(HHMO_CF_GDA) turns out to be the best choice for solving these types of
problems.
