An adaptive parallel evolutionary algorithm for solving the uncapacitated facility location problem

Sonuç, Emrullah; Özcan, Ender

Abstract

Metaheuristics, providing high level guidelines for heuristic optimisation, have successfully been applied to many complex problems over the past decades. However, their performances often vary depending on the choice of the initial settings for their parameters and operators along with the characteristics of the given problem instance handled. Hence, there is a growing interest into designing adaptive search methods that automate the selection of efficient operators and setting of their parameters during the search process. In this study, an adaptive binary parallel evolutionary algorithm, referred to as ABPEA, is introduced for solving the uncapacitated facility location problem which is proven to be an NP-hard optimisation problem. The approach uses a unary and two other binary operators. A reinforcement learning mechanism is used for assigning credits to operators considering their recent impact on generating improved solutions to the problem instance in hand. An operator is selected adaptively with a greedy policy for perturbing a solution. The performance of the proposed approach is evaluated on a set of well-known benchmark instances using ORLib and M*, and its scaling capacity by running it with different starting points on an increasing number of threads. Parameters are adjusted to derive the best configuration of three different rewarding schemes, which are instant, average and extreme. A performance comparison to the other state-of-the-art algorithms illustrates the superiority of ABPEA. Moreover, ABPEA provides up to a factor of 3.9 times acceleration when compared to the sequential algorithm based on a single-operator.

• Journal Article Type: Article
• Acceptance Date: Mar 21, 2023
• Online Publication Date: Mar 23, 2023
• Publication Date: Aug 15, 2023
• Deposit Date: Mar 30, 2023
• Publicly Available Date: Apr 5, 2023
• Journal: Expert Systems with Applications
• Print ISSN: 0957-4174
• Peer Reviewed: Peer Reviewed
• Volume: 224
• Article Number: 119956
• DOI: https://doi.org/10.1016/j.eswa.2023.119956
• Keywords: Adaptive operator selection; Metaheuristics; Combinatorial optimisation; Parallel algorithms
• Public URL: https://nottingham-repository.worktribe.com/output/18993168
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S095741742300458X?via%3Dihub