Fitness Landscapes Analysis For Perturbative Hyper-Heuristics

Fitness landscapes analysis has been applied to analyze the structure of constructive hyper-heuristics space, which reveals these landscapes have a high neutrality and positional bias. They also have the feature of a globally convex or big valley structure. Ochoa conducted a fitness landscapes analysis on a hyper-heuristic search space by using graph coloring heuristics for timetabling. The result confirmed that the optimal solution was not isolated in the space, but surrounded by many local optimal solutions. We can use these futures to design more efficient hyper-heuristics. In the other related paper, Ochoa performed a fitness landscapes analysis of the hyper-heuristic space induced by a dispatching-rule-based hyper-heuristic for hybrid flowshop scheduling problem. This study confirmed that it was suitable for hyper-heuristic space by using fitness landscapes analysis and it was related between them.However, there is no study of applying fitness landscapes analysis for perturbative hyper-heuristics space. One reason is that the process of building a solution of a problem instance is different for constructive hyper-heuristics and perturbative hyper-heuristics: constructive hyper-heuristics start with an empty solution, and build a full solution step by step; perturbative hyper-heuristics start with a full solution, and gradually optimize this solution. Constructive hyper-heuristics will generate a certain solution after execute a heuristic algorithm sequence, but for perturbative hyper-heuristics, the solution is uncertain. Moreover, the initial solution has a big influence on the perturbative hyper-heuristics, meanwhile the initial solution has no influence on constructive hyper-heuristics. Based on these reasons, there is no research on perturbative hyper-heuristics space by using fitness landscapes analysis so far. The purpose of this paper is to make up the gap. Some methods of this paper use to reduce the impact of initial solution on perturbative hyper-heuristics, and we seek to use the average of multiple solutions fitness as the fitness of heuristic algorithm sequence. Furthermore, we use the notion of fitness distance correlation to explore the relationship of fitness and distance between local optimal solutions and global optimal solution, and find positive relationship between them; we use escape analysis to find a perfect mutation ratio for local optimal solutions, which can guide the algorithm design.