Page 120 - IJOCTA-15-2

Parallel late acceptance hill-climbing for binary-encoded optimization problems
random initial solution. It then creates a history number of facilities, customers, and optimal so-
list of length L filled with this initial fitness value. lutions. The problem size is denoted as n × m,
This list acts as a memory of recent solution qual- where n represents the number of facilities and m
ities. represents the number of customers.
The core of LAHC is its main loop, which
runs for a given number of iterations. At each Table 1. ORLib problem instances for UFLP
iteration, each threads generates a new candidate
Instance Size Optimal cost
solution using random bit flipping. This process
Cap71 16 x 50 932,615.75
takes the current solution, represented as a bit
Cap72 16 x 50 977,799.40
string, and randomly selects one or more bits
Cap73 16 x 50 1,010,641.45
to flip - changing 0s to 1s or vice versa. This Cap74 16 x 50 1,034,976.98
method of solution generation is crucial because
it creates small, random changes to the current so- Cap101 25 x 50 796,648.44
lution, allowing the algorithm to explore nearby Cap102 25 x 50 854,704.20
points in the search space while maintaining the Cap103 25 x 50 893,782.11
Cap104 25 x 50 928,941.75
overall structure of the solution. The threads
continue to generate candidate solutions and at-
Cap131 50 x 50 793,439.56
tempt to improve the quality of the results until a Cap132 50 x 50 851,495.33
predetermined stopping criterion (e.g., a specific Cap133 50 x 50 893,076.71
number of iterations) is met. Upon satisfaction Cap134 50 x 50 928,941.75
of the stopping criterion, the parallel section is
completed. The best solution of each thread is CapA 100 x 1000 17,156,454.48
stored in an shared array accessible to all threads, CapB 100 x 1000 12,979,071.58
CapC 100 x 1000 11,505,594.33
and the master thread identifies the best solution
among them and displays it as the global best
solution.
First, we test different history list lengths
We use multi-threaded programming with (L) to demonstrate the performance of sequential
OpenMP to speed up the LAHC. Furthermore, LAHC on UFLP instances in ORLib. Note that
different numbers of threads (4, 8, 16 and 32) are the termination criterion is a predetermined num-
tested and the effect on the overall performance ber of function evaluations = 80,000. Each experi-
of the proposed approach is analyzed.
ment is run for 30 trials for each problem instance.
4. Computational experiments and Table 2 shows the sequential LAHC results using
results the gap score, which is the ratio of the mean to
the distance between the mean and the optimum
We perform all experiments on a PC with an in percent. The results show a clear trend of im-
eight-core processor (Intel(R) Xeon(R) E5-2630 proved performance as L increases from 10 to 100.
CPU @ 2.40 GHz), with 64 GB of RAM, running The average gap score consistently decreases, with
the Windows 10 64-bit operating system. PLAHC L = 100 yielding the best overall results at 0.84.
is implemented in standard C using the gcc com- Smaller problem instances (cap71-cap74) perform
piler with OpenMP version 4.5. well across all L values, often reaching optimal so-
To systematically tune effective parameter lutions, while larger instances benefit more signif-
settings for PLAHC, we performed different pa- icantly from increasing L values. This is particu-
rameter configurations on a subset of represen- larly evident for the extra large instances (capa,
tative problem instances. We explore the length capb, capc), where significant decreases in gap
of the history list (L) ∈ {10, 20, 50, 100} and the scores are observed.
number of threads (nt) ∈ {4, 8, 16, 32}. A fixed
computational budget of 80,000 objective func- Table 3 shows the gap scores of PLAHC us-
tion evaluations was allocated for each parameter ing 4 threads. The best overall performance
combination, with 30 independent runs performed is achieved with L = 50, with an average gap
to ensure statistical significance. score of 0.35, closely followed by L = 100 with
0.44. Small and medium instances consistently
4.1. Computational results for UFLP
achieve optimal or near-optimal solutions, even
We tested PLAHC on UFLP using the ORLib with shorter history lists. Larger instances still
benchmark set. 41 This problem set has 15 UFLP benefit from larger L values, with L = 100 gen-
problems in 4 groups. Table 1 shows the main erally performing best for complex problems. For
characteristics of these problems, including the the largest instances (capa, capb, capc), L = 50
315