An empirical investigation on parallelization strategies for Scatter Search

As other metaheuristics, Scatter Search can gain from a parallel implementation. However, it is not clear beforehand which of the possible alternative parallelization strategies is more effective. To address this question, it has been selected as a test bed for empirical testing a classical combinatorial optimization problem, namely 0–1 knapsack problem, for which the sequential application of Scatter Search is well known. Two phases or groups of steps in the Scatter Search template have been identified as natural candidates for parallelization and several ways of carrying out that parallelization are proposed. An extensive experimental analysis involving 18 different parallel algorithms has been carried out testing the combinations of these alternative parallelization strategies on a battery of large random instances generated using a public code from the literature. The interpretation of the ANOVA results gives cues about the significance of the alternatives used in each phase and about the effect of the dynamic (vs. static) updating of the RefSet. A low average efficiency has been observed, although it has to be taken into account that, due to the termination condition used, not all algorithms tested carry out the same number of iterations.