Multitask Genetic Programming-Based Generative Hyperheuristics: A Case Study in Dynamic Scheduling.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Evolutionary multitask learning excels at handling multiple tasks simultaneously.
• Hyperheuristics aim to generate general problem-solving heuristics, unlike specific task solvers.
• Existing multitask hyperheuristics are limited to heuristic selection, not generation.

Purpose of the Study:

• To propose a novel multitask generative hyperheuristic approach using genetic programming (GP).
• To adapt evolutionary multitask learning principles to GP-based hyperheuristics for heuristic generation.
• To address the gap in applying multitask learning to hyperheuristic generation.

Main Methods:

• Developed a novel multitask generative hyperheuristic framework based on genetic programming (GP).
• Introduced an evolutionary framework and selection pressure suitable for multitask GP hyperheuristics.
• Implemented an origin-based offspring reservation strategy to preserve individual quality across tasks.

Main Results:

• The proposed approach significantly improved the quality of scheduling heuristics across various multitask dynamic flexible job shop scheduling scenarios.
• Empirical studies confirmed the effectiveness on both homogeneous and heterogeneous problem instances.
• Evolved heuristics demonstrated positive transfer and mutual assistance among tasks within the multitask setting.

Conclusions:

• The novel multitask generative hyperheuristic approach effectively enhances heuristic generation for complex scheduling problems.
• The method facilitates mutual learning and improvement across multiple related tasks.
• This work opens new avenues for applying evolutionary multitask learning in the hyperheuristic domain.