Page 116 - IJOCTA-15-2
P. 116
An International Journal of Optimization and Control: Theories & Applications
ISSN: 2146-0957 eISSN: 2146-5703
Vol.15, No.2, pp.311-329 (2025)
https://doi.org/10.36922/ijocta.1696
RESEARCH ARTICLE
Parallel late acceptance hill-climbing for binary-encoded
optimization problems
¨
Emrullah Sonu¸c 1,2* and Ender Ozcan 2
1
Department of Computer Engineering, Karabuk University, T¨urkiye
2
Computational Optimisation and Learning (COL) Lab, School of Computer Science, University of
Nottingham, United Kingdom
esonuc@karabuk.edu.tr, ender.ozcan@nottingham.ac.uk
ARTICLE INFO ABSTRACT
Article History: This paper presents a Parallel Late Acceptance Hill-Climbing (PLAHC) al-
Received: September 30, 2024 gorithm for solving binary-encoded optimization problems, with a focus on
Accepted: February 7, 2025 the Uncapacitated Facility Location Problem (UFLP) and the Maximum Cut
Published Online: April 7, 2025 Problem (MCP). The experimental results on various benchmark problem
Keywords: instances demonstrate that PLAHC significantly improves upon the sequen-
Late acceptance hill-climbing tial implementation of the standard Late Acceptance Hill-Climbing method in
Max-cut problem terms of solution quality and computational efficiency. For UFLP instances,
Metaheuristics an 8-thread implementation with a history list length of 50 achieves the best
Uncapacitated facility location problem results, while for MCP instances, a 4-thread implementation with a history
Parallel algorithms list length of 100 is the most effective configuration. The speedup analysis
shows performance improvements ranging from 3.33x to 10.00x for UFLP and
AMS Classification:
2.72x to 9.20x for MCP as the number of threads increases. The performance
68T20; 90C27
comparisons to the state-of-the-art algorithms illustrate that PLAHC is highly
competitive, often outperforming existing sequential methods, indicating the
potential of exploiting parallelism to improve heuristic search algorithms for
complex optimization problems.
1. Introduction problems. While HC accepts a non-worse solu-
tions during the search process, it stucks a local
A Binary-Encoded Optimization Problem optimum which prevents the diversification. To
(BEOP) is a type of optimization problem in tackle this, several variants of HC algorithm have
which the solution is represented as a sequence been proposed such as β-HC, Late Acceptance
7
of binary values (0s and 1s). BEOPs are used in HC, and Expansion-based HC. 9
8
many different areas of operations research, in- The Late Acceptance HC (LAHC) algorithm,
cluding knapsack problems, 1,2 feature, selection 3 first proposed in 2012, is a version of the classi-
maximum cut problem 4 and facility location. cal HC method designed to address the limita-
5
problem Due to the nature of BEOPs, the ex- tions of early convergence and getting stuck in
ponential growth of the number of variables in local optimum. 10 Unlike traditional HC, LAHC
the search space makes the process of performing does not immediately reject moves that lead to
a comprehensive search inapplicable for complex worse solutions. It compares the current solution
problems. For this purpose, the design of heuris-
with several previous solutions instead of the pre-
tic/metaheuristic algorithm for these problems is vious one, and then accepts or rejects it. Accept-
the main motivation of researchers. 6
ing worse solutions early in the search process al-
Hill-Climbing (HC) is one of the simplest lows for a more robust exploration of the solution
heuristic method to handle BEOPs and similar space and generally provides better convergence
*Corresponding Author
311

