A Modified Multi-Level Hyper Heuristic for Tackling Combinatorial Optimization Problems

Awad, Asmaa Ibrahim; Abdel Raouf, Osama; El-Hefnawy, Nancy; Kafafy, Ahmed

doi:10.21608/ijci.2023.224216.1117

A Modified Multi-Level Hyper Heuristic for Tackling Combinatorial Optimization Problems

Document Type : Original Article

Authors

¹ assistant lecturer at faculty of artificial intelligence Menofia University

² Faculty of Artificial intelligence, Menoufia University, Menoufia, Egypt

³ Faculty of Computers and Information, Tanta University, Tanta, Egypt

⁴ Operations Research & DSS Dept., Faculty of Computers and Information, Menoufia University, Menoufia, Egypt

10.21608/ijci.2023.224216.1117

Abstract

Hyper-heuristics are search techniques that operate on heuristic spaces by selecting low-level heuristics appropriately. Hyper-heuristic aims to generate a generalized and automated approaches to solve various problem domains. However, the effectiveness of hyper-heuristics depends on the cooperation of several low-level heuristics to provide high-quality solutions. Low-level heuristics can be categorized as either constructive or perturbative. they aim to construct or improve existing solutions. This paper presents a proposed Modified Multi-Level Hyper-Heuristic (MMHH) applied on a multilevel framework with three layers. The first layer is highest-level heuristic which selects a suitable hyper-heuristic algorithm. while the second layer called high-level heuristic that chooses suitable low-level heuristic from a set of heuristics. Two reward techniques are provided, one based on the amount of improvement, and the other based on the number of improvements. Two different scenarios for combining two reward selection algorithms are investigated. The first scenario is based on adopting a set of different weights for each technique. The second one is based on adapting the balancing between the two reward techniques by utilizing the idea of simulated annealing. The performance of the proposed MMHH algorithm is assessed by comparing it to a set of state-of-the-art hyper-heuristics, which include multi-level hyper-heuristics amount of improvement(MHHA) and number of improvements(MHHN), Dynamic Multi-Armed Bandit, Fitness-Rate-Rank Multi-Armed Bandit, and Deep QNetwork, across six problem domains from the HyFlex Framework. Based on the experimental results, it is evident that the MMHH demonstrates high competitiveness and outperforms the other compared methods in five out of the six benchmarks

Keywords