A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Hyper-heuristics offer general problem-solving capabilities, unlike domain-specific methods.
• Traditional hyper-heuristics rely on a two-level structure: high-level strategy and low-level heuristics.
• The high-level strategy is crucial for adapting to varied problem landscapes.

Purpose of the Study:

• To propose a new hyper-heuristic framework with an advanced high-level strategy.
• To enhance heuristic selection and automate acceptance criterion generation.
• To demonstrate the framework's generalizability across different problem domains.

Main Methods:

• Implemented a dynamic multi-armed bandit-extreme value-based reward for online heuristic selection.
• Utilized gene expression programming to automatically generate problem-specific acceptance criteria.
• Evaluated the framework on static (exam timetabling) and dynamic (vehicle routing) combinatorial optimization problems.

Main Results:

• The proposed framework demonstrated strong generalization capabilities across static and dynamic problem domains.
• Achieved competitive or superior results compared to state-of-the-art hyper-heuristics and bespoke methods.
• Validated performance against benchmark datasets from the hyper-heuristic competition test suite.

Conclusions:

• The novel hyper-heuristic framework with its adaptive high-level strategy is effective and generalizable.
• Automated acceptance criterion generation via gene expression programming enhances adaptability.
• The approach offers a promising direction for developing robust and versatile optimization methodologies.