Meta-Heuristic Combining Prior Online and Offline Information for the Quadratic Assignment Problem

Area of Science:

• Computer Science
• Operations Research

Background:

• Meta-heuristics for NP-hard combinatorial optimization problems (COPs) utilize various information types.
• These include a priori (domain knowledge), a posteriori (learned from solutions), and online (construction process) information.

Purpose of the Study:

• To investigate the impact of different information types on meta-heuristic performance for COPs.
• To propose methods for extracting and combining these information types effectively.

Main Methods:

• Developed an improved scheme for extracting online local information.
• Created a unified framework for integrating a priori, a posteriori, and online information.
• Evaluated performance using heuristic algorithms for the quadratic assignment problem (QAP).

Main Results:

• Demonstrated that combining information types enhances meta-heuristic performance.
• Showcased the benefits of online information for local exploitation and a posteriori information for global exploration.
• Validated the effectiveness of the unified framework.

Conclusions:

• The study provides principles for designing effective meta-heuristics by leveraging different information sources.
• Integrating diverse information types is crucial for optimizing performance in solving complex combinatorial optimization problems.