A perturbation adaptive pursuit strategy based hyper-heuristic for multi-objective optimization problems

Abstract For multi-objective optimization problems, obtaining a uniformly distributed approximation set is among the most important issues. During the past decades, various diversity mechanisms have been proposed to address this challenge. However, the existing diversity mechanisms tend to be problem-specific, and may not generalize well over different problem domains. Inspired by the idea of utilizing multiple low-level heuristics to achieve better diversity performance in multi-discipline problem solving, we focus on efficient algorithm design based on the methodology of selection hyper-heuristics. This study proposes a novel selection hyper-heuristic operating over multiple diversity mechanisms. The unique feature of the proposed approach lies in its ability to intelligently learn, select, and combine different diversity mechanisms with the purpose of taking advantages of them to obtain well-distributed approximation sets. Moreover, this work develops a new learning mechanism, the perturbation adaptive pursuit strategy, which is incorporated into the proposed hyper-heuristic to improve the decision-making process of selecting suitable diversity mechanisms for the problem at hand. The performance of the proposed hyper-heuristic is tested on 2-objective ZDT, 3-objective DTLZ, and 5-objective WFG test suites. Additionally, experiments are also conducted to investigate the ability of the novel hyper-heuristic to integrate existing multi-objective meta-heuristics on MaOP test suite from 3- to 10-objectives. Experimental results demonstrate the effectiveness of the proposed selection hyper-heuristic for cross-domain capacity, particularly in producing well distributed approximation set with respect to Spacing metric and Hypervolume metric.