Nhảy đến nội dung

A novel binary social spider algorithm for 0-1 knapsack problem


Phuong Hoai Nguyen, Dong Wang and Tung Khac Truong*

Source title: 
International Journal of Innovative Computing, Information and Control, 13(6): 2039-2049, 2017 (Scopus)
Academic year of acceptance: 

The 0-1 knapsack problem (KP01) is a well-known NP-hard optimization problem. Recently a new metaheuristic algorithm, called social spider algorithm, was proposed, which has been successfully applied to solving various continuous optimization problems. This paper proposes a binary social spider algorithm to solve KP01 efficiently. This algorithm is composed of discrete process and constraint handling process. In discrete process, a popular sigmoid function is used to achieve good discrete process result. Two constraint handling techniques are utilized. The repair operator with ADD phase and DROP phase is executed to treat infeasibility and improve the efficiency. The experimental results have proven the superior performance of BSSA compared to genetic algorithm and particle swarm optimization.