New insights into diversification of hyper-heuristics

Area of Science:

• Artificial Intelligence
• Operations Research
• Computational Science

Background:

• Hyper-heuristics balance intensification and diversification using low-level heuristics.
• Traditional diversification often perturbs solutions to escape local optima.

Purpose of the Study:

• To introduce a new diversification mechanism based on instance perturbation.
• To develop a novel hyper-heuristic framework, HIP-HOP, to incorporate instance perturbation.

Main Methods:

• Proposed a diversification mechanism by perturbing the problem instance, not the solutions.
• Designed HIP-HOP, a hyper-heuristic framework using grammar-guided strategies to manipulate low-level heuristics.
• Ensured solution feasibility through grammar-based constraints.

Main Results:

• HIP-HOP achieved promising performance on Ising spin glass and p-median problems.
• Statistical tests confirmed the effectiveness of the proposed approach.
• Runtime analysis showed competitive solutions with sufficient time, despite a slower start.

Conclusions:

• Instance perturbation offers a viable alternative for diversification in hyper-heuristics.
• The HIP-HOP framework successfully integrates instance perturbation for enhanced optimization.
• The approach demonstrates potential for solving complex combinatorial optimization problems.