A multi-policy sequence-based selection hyper-heuristic for multi-objective optimization

Selection hyper-heuristics (SSHH) are search strategies that can be successfully applied to multi-objective optimization (MOO) problems. They showed resilient results to different types of optimization problems, which may come at the cost of a longer resolution time than other metaheuristics. Learning a single selection rule in MOO might be limiting because the information from the multiple objectives might be unexploited. A novel approach named the multi-policy approach is proposed and discussed to further enhance the searching ability of sequence-based selection hyper-heuristics, together with an ad-hoc learning rule. The availability of a set of problem-specific low-level heuristics is assumed and the resolution of a specific class of combinatorial problems, i.e., vehicle routing problems (VRPs), is considered for a numerical example. The multi-policy approach showed the ability to learn different selection rules for each objective and to change them during the execution of the algorithm, i.e., when solutions are getting closer to the Pareto front. The availability of parallel computation can speed up the calculation since the methodology is suitable for parallelization. The proposed methodology was found to produce production-ready solutions and the approach is expected to be successfully extended to problems different from the VRP.