A choice function based hyper-heuristic for multi-objective optimisation
Maashi, Mashael S. . 2012
Hyper-heuristics have drawn increasing attention from the research community in recent years, although their roots can be traced back to the 1960’s. They perform a search over the space of heuristics rather than searching over the solution space directly. Research attention has focussed on two types of hyper-heuristics: selection and generation. A selection hyper-heuristic manages a set of low level heuristics and aims to choose the best heuristic at any given time using historic performance to make this decision, along with the need to diversify the search at certain times. In this study, we propose a choice function based hyper-heuristic for multi-objective optimization that 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 acts as the high level strategy, which adaptively ranks the performance of three low-level heuristics, deciding which one to call at each decision point. “All Moves” is employed as an acceptance strategy, meaning that we accept the output of each low level heuristic whether it improves the quality of the solution or not. Four performance metrics (Algorithm effort (AE), Ratio of non-dominated individuals (RNI), Size of space covered (SSC) and Uniform distribution of a non-dominated population (UD)) act as an online learning mechanism to provide knowledge of the problem domain to the high level strategy. The experimental results demonstrate the effectiveness of this hyper-heuristic approach when tested on the Walking Fish Group test suite, a common benchmark for multi-objective optimization.
