Page 126 - IJOCTA-15-2

Parallel late acceptance hill-climbing for binary-encoded optimization problems
Table 9. Gap scores of sequential LAHC on MCP instances for different L values

Instance L=10 L=20 L=50 L=100
pw01 100.0 2.1313 1.9034 1.8623 1.1823
pw01 100.1 2.9369 1.6311 1.4044 0.2461
pw01 100.2 2.6476 2.0832 1.0138 0.9365
pw01 100.3 1.9434 1.8515 0.9516 1.1403
pw01 100.4 2.6891 1.8293 1.2423 1.5758
pw01 100.5 3.5878 1.9511 2.6409 1.2225
pw01 100.6 2.1491 2.0177 1.4090 2.1196
pw01 100.7 2.9074 1.3679 1.1427 1.1172
pw01 100.8 3.9975 2.3393 1.6632 2.0213
pw01 100.9 2.1032 1.9766 1.8389 1.1920
pw05 100.0 0.9667 0.8165 0.5186 0.3040
pw05 100.1 1.0470 0.9654 0.7201 0.5395
pw05 100.2 0.9715 0.7211 0.7256 0.5424
pw05 100.3 1.1562 0.9620 0.7240 0.4825
pw05 100.4 0.9567 0.8545 0.4538 0.3065
pw05 100.5 1.7371 1.1033 0.7745 0.4587
pw05 100.6 0.8957 0.7724 0.4357 0.3630
pw05 100.7 1.0672 0.7803 0.4659 0.3512
pw05 100.8 1.7742 1.0627 0.7083 0.3607
pw05 100.9 0.9437 1.0532 0.5930 0.3013
pw09 100.0 0.6976 0.4750 0.3340 0.2088
pw09 100.1 0.6162 0.4852 0.3237 0.2556
pw09 100.2 0.8040 0.5416 0.5269 0.3442
pw09 100.3 0.6915 0.6852 0.3603 0.2920
pw09 100.4 0.7543 0.6208 0.4042 0.3295
pw09 100.5 0.6412 0.4938 0.2112 0.2271
pw09 100.6 0.7847 0.6349 0.5320 0.3375
pw09 100.7 0.5220 0.4822 0.4646 0.2889
pw09 100.8 0.6553 0.5481 0.3607 0.2170
pw09 100.9 0.7119 0.7256 0.3385 0.1491
Avg.Gap 1.5163 1.1245 0.8382 0.6471

Table 10 presents the average gap scores on threads increases. This can be clearly seen clearly
30 trials with an L = 50 of PLAHC using in all instances, where the difference in perfor-
different numbers of threads, which are 4, 8, mance between 4 threads and 32 threads is quite
16, and 32 shown in the columns. The results significant.
show interesting patterns across different prob-
lem sizes. For all instances, the 4-thread im- Comparing all experiments, including sequen-
plementation consistently produces the best re- tial implementations with different history list
sults. The gap scores increases as the number lengths (L = 10, 20, 50, 100) and parallel imple-
of threads increases, suggesting that for these mentations with L = 50 and L = 100 using
simpler problems, a lower degree of paralleliza- different number of threads (4, 8, 16, 32), the
tion is most effective. This may be because best overall configuration emerges as the paral-
the overhead of managing more threads out- lel implementation with L = 100 and 4 threads.
weighs the benefits of increased parallelism for This configuration consistently produces the best
these smaller problem sizes. For the pw09 se- average gaps scores across all problem instance
ries, increasing to 16 or 32 threads generally re- groups (pw01, pw05, pw09). The longer history
sults in a decrease in performance. In summary, list (L = 100) generally outperforms the shorter
these results highlight the importance of care- ones, indicating the benefits of a larger search his-
fully matching the degree of parallelization to tory for the sequential LAHC. Parallelization of
the specific problem complexity. For the ma- the LAHC algorithm using 4 threads shows the
jority of instances, 4-thread implementation pro- highest level of efficiency. This is because the
vides better balance between parallelism and effi- overhead associated with parallel processing re-
ciency. duces the benefits of parallelism as the number
of threads increases. This optimal configuration
Table 11 presents the average gap scores with successfully balances exploration of the solution
an L = 100 of PLAHC. According to the ex- space with computational efficiency, demonstrat-
perimental results, across all three groups (pw01, ing robustness to varying problem characteris-
pw05, and pw09), the 4-thread implementation tics. It effectively combines the benefits of ex-
consistently produces the best results, with per- tensive search history with efficient parallel pro-
formance generally decreasing as the number of cessing, making it the most appropriate choice
321