Hyper-Heuristics based on Reinforcement Learning, Balanced Heuristic Selection and Group Decision Acceptance

Santiago J�nior, Valdivino Alexandre de; �zcan, Ender; Carvalho, Vinicius Renan de

Abstract

In this paper, we introduce a multi-objective selection hyper-heuristic approach combining Reinforcement Learning, (meta)heuristic selection, and group decision-making as acceptance methods, referred to as Hyper-Heuristic based on Reinforcement LearnIng, Balanced Heuristic Selection and Group Decision AccEptance (HRISE), controlling a set of Multi-Objective Evolutionary Algorithms (MOEAs) as Low-Level (meta)Heuristics (LLHs). Along with the use of multiple MOEAs, we believe that having a robust LLH selection method as well as several move acceptance methods at our disposal would lead to an improved general-purpose method producing most adequate solutions to the problem instances across multiple domains. We present two learning hyper-heuristics based on the HRISE framework for multi-objective optimisation, each embedding a group decision-making acceptance method under a different rule: majority rule (HRISE_M) and responsibility rule (HRISE_R). A third hyper-heuristic is also defined where both a random LLH selection and a random move acceptance strategy are used. We also propose two variants of the late acceptance method and a new quality indicator supporting the initialisation of selection hyper-heuristics using low computational budget. An extensive set of experiments were performed using 39 multi-objective problem instances from various domains where 24 are from four different benchmark function classes, and the remaining 15 instances are from four different real-world problems. The cross-domain search performance of the proposed learning hyper-heuristics indeed turned out to be the best, particularly HRISE_R, when compared to three other selection hyper-heuristics, including a recently proposed one, and all low-level MOEAs each run in isolation.

Citation

Santiago Júnior, V. A. D., Özcan, E., & Carvalho, V. R. D. (2020). Hyper-Heuristics based on Reinforcement Learning, Balanced Heuristic Selection and Group Decision Acceptance. Applied Soft Computing, 97(Part A), Article 106760. https://doi.org/10.1016/j.asoc.2020.106760

• Journal Article Type: Article
• Acceptance Date: Sep 25, 2020
• Online Publication Date: Oct 1, 2021
• Publication Date: Dec 1, 2020
• Deposit Date: Dec 2, 2021
• Publicly Available Date: Dec 7, 2021
• Journal: Applied Soft Computing
• Print ISSN: 1568-4946
• Electronic ISSN: 1872-9681
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 97
• Issue: Part A
• Article Number: 106760
• DOI: https://doi.org/10.1016/j.asoc.2020.106760
• Keywords: Software, Artificial Intelligence
• Public URL: https://nottingham-repository.worktribe.com/output/4948353
• Publisher URL: https://www.sciencedirect.com/science/article/abs/pii/S1568494620306980?via%3Dihub
• Additional Information: This article is maintained by: Elsevier; Article Title: Hyper-Heuristics based on Reinforcement Learning, Balanced Heuristic Selection and Group Decision Acceptance; Journal Title: Applied Soft Computing; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.asoc.2020.106760; Content Type: article; Copyright: © 2020 Elsevier B.V. All rights reserved.