Page 117 - IJOCTA-15-2

¨
E. Sonu¸c, E. Ozcan / IJOCTA, Vol.15, No.2, pp.311-329 (2025)
to the global optimum. Experiments on examples new solutions that are better than the solution
of the traveling salesman problem verify the effec- kept in the queue. This is done by maintain-
tiveness of the proposed method and demonstrate ing a history list, which is how the algorithm re-
its ability to obtain competitive results without members past solutions. By keeping a record of
8
the need for any additional parameters. In addi- past solutions, the algorithm compares new can-
tion, LAHC has outperformed some heuristic al- didates with known good solutions and explores
gorithms in an international competition for solv- other possibilities. Figure 1 presents the pseu-
ing the magic square problem. The simplicity docode of LAHC. 11
of the algorithm and its ease of implementation
Over the years, several versions of the LAHC
make it a powerful tool for optimization problems. algorithm have been proposed to improve its per-
Although the LAHC algorithm is a useful
formance and applicability. These include adap-
method for optimization problems, it has some
tive mechanisms for dynamically adjusting pa-
disadvantages. Since a new solution is obtained
rameters, hybrid approaches combining LAHC
from a single solution at each step, the method
with other metaheuristics, and parallel implemen-
can get stuck at a local optimum if the history
tations for efficient exploration of large solution
list is not long enough. One of the simplest 12
spaces. In addition, research efforts have fo-
ways to prevent this is to increase the history
cused on optimizing the algorithm’s parameters
list length. However, this also requires fine tun-
and fine-tuning its behavior for specific problem
ing. This study aims to overcome these disad-
domains. Its adaptability to problems such as
vantages by developing a parallelized version of
exam scheduling and the traveling salesman prob-
the LAHC algorithm focusing to solve BEOPs,
lem was demonstrated, with both its versatility
which is designed specifically for multi-core CPU 13
environments. This is to significantly speed up and areas for improvement being highlighted. A
the search process thanks to parallel computation LAHC-based memetic algorithm for selecting fea-
while preserving the quality of the search results. tures for recognizing facial emotions is presented
14
The main contributions of this paper are summa- and tested on multiple datasets.
rized as follows. To enhance efficiency in complex scenarios,
• We propose a Parallel LAHC (PLAHC) the parallel version of LAHC was proposed, with
algorithm for solving BEOPs, with a fo- the google machine reassignment problem being
cus on the Uncapacitated Facility Loca- specifically addressed. 15 Superior performance to
tion Problem (UFLP) and Maximum Cut single-threaded LAHC was demonstrated by this
Problem (MCP). adaptation, and comparable results to advanced
• PLAHC obtain higher quality results in search algorithms were achieved, emphasizing its
a shorter time compared to the sequen- potential for resource allocation in large-scale
tial LAHC algorithm. The experiments computing environments. A specialized modifi-
demonstrate a significant performance im- cation, custom LAHC was introduced to improve
provements through parallelization, with solution quality for traveling salesman problem
speedups ranging from 3.33x to 10.00x for instances. 16 For anomaly detection, LAHC was
UFLP instances and 2.72x to 9.20x for combined with genetic programming, resulting in
MCP instances as the number of threads competitive models with fewer parameters being
increases. produced. 17
• Comprehensive comparison with state-of-
A recent literature indicates that the LAHC
the-art algorithms, showing that PLAHC
is highly competitive and often outper- algorithm has been demonstrated to be an effec-
forms existing methods for both UFLP tive tool for solving a wide range of optimization
18–20
and MCP. problems in various application areas. The
• Analysis of the trade-offs between paral- balance between exploration and exploitation,
lelism and history list length, providing and the avoidance of local optima, make LACH a
insights into the balance between explo- valuable tool for researchers seeking efficient so-
ration and exploitation in the search pro- lutions to complex optimization problems. How-
ever, the efficacy of the parallel LAHC algorithm
cess.
in accelerating optimization processes and over-
2. Background coming large-scale optimization problems remains
a topic of ongoing investigation. While parallel
2.1. Late acceptance hill-climbing
implementations of LAHC have been previously
LAHC is a stochastic local search to explore the proposed, our PLAHC algorithm differs in several
solution space. The algorithm selectively accepts key aspects from existing approaches. 15 Other
312