New scatter search algorithm for multidimensional knapsack problem
一种新的求解多维背包问题的分散算法

To avoid falling into local optimal solution and the premature convergence in the process of searching optimization solutions, this paper presented a new scatter search algorithm. The designed algorithm combined the solution construction mechanism of ant colony optimization(ACO) into scatter search(SS). It considered both solution quality and diversification. Simultaneously, the algorithm adopted the dynamic updating strategy and the parameter criterion of threshold accepting to accelerate the convergence towards high-quality regions of the search space. The performance of the proposed algorithm was tes-ted on MDKP benchmark problems from the OR Library. The experimental results show that the proposed algorithm can avoid trapping in local optimal solution and enhance the ability of global optimization, and it is competitive to solve the multidimensional knapsack problem compared with the other heuristic methods in terms of solution quality.