Page 118 - IJOCTA-15-2

Parallel late acceptance hill-climbing for binary-encoded optimization problems
Algorithm 1 The pseudocode of LAHC.
Input: initial solution ▷ the starting solution
fitness function ▷ function to evaluate solution quality
L ▷ length of the late acceptance list
max iterations ▷ maximum number of iterations
Output: best solution ▷ the best solution found
Begin
1: current solution ← initial solution
2: best solution ← initial solution
3: current fitness ← fitness function(current solution)
4: fitness list ← [current fitness] * L ▷ create a list of length L filled with current fitness
5: for iteration ≤ max iterations do
6: candidate solution ← generate neighbor(current solution)
7: candidate fitness ← fitness function(candidate solution)
8: v ← iteration mod L
9: if candidate fitness ≤ current fitness or candidate fitness ≤ fitness list[v] then
10: current solution ← candidate solution
11: current fitness ← candidate fitness
12: end if
13: if current fitness ≤fitness function(best solution)) then
14: best solution ← current solution
15: end if
16: fitness list[v] ← current fitness
17: end for
18: return best solution
End

Figure 1. The pseudocode of LAHC algorithm

parallel LAHC implementations use problem- discrete solution space in which the total num-
h
specific neighborhood operators, a shared mem- ber of possible solutions is finite, specifically 2 ,
ory architecture with synchronized global solution where h is the number of bits in the encoding.
access, and a fixed thread count based on available BEOPs are characterized by a non-continuous
cores to optimize performance for a given prob- solution space of distinct points and often exhibit
lem. We propose a generalized parallel frame- combinatorial complexity, falling into the NP-
work for binary optimization uses independent hard category, which makes them challenging to
history lists per thread to maintain solution diver- solve for large instances due to the exponential
sity, adapts the number of threads based on prob- growth of the search space with the number of
lem characteristics, and provides efficient coordi- bits.
nation between threads. This approach balances
2.2.1. Uncapacitated facility location problem
exploration and exploitation, improving scalabil-
ity and solution quality for diverse optimization The Uncapacitated Facility Location Problem
problems. Furthermore, to the best of our knowl- (UFLP) is a minimization BEOP and the objec-
edge, this is one of the first studies on the use of tive is to minimize costs by assigning facilities to
parallel LAHC to solve UFLP and MCP. locations. Let n denote the set of potential facility
locations and m represent the number of demand
points (customers). The mathematical formula-
2.2. Binary-encoded optimization problem 1 21
tion of UFLP is as follows:
(BEOP)
n m n
BEOPs represent a fundamental class of chal- X X X
minimize c ij x ij + (1)
lenges in the field of optimization and decision f i y i
making. A potential solution for a BEOP is rep- i=1 j=1 i=1
resented as a binary variable. In this encoding s.t.
scheme, each bit typically represents a yes/no de- n
X
cision or the presence/absence of a particular fea- x ij = 1, j = 1, 2, ..., m (2)
ture or element. This binary structure leads to a
i=1
313