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
   111   112   113   114   115   116   117   118   119   120   121