Different Transfer Functions for Binary Particle Swarm Optimization with a New Encoding Scheme for Discounted {0-1} Knapsack Problem. (24th April 2021) - Truong, Tung Khac
Abstract : The discounted {0-1} knapsack problem (DKP01) is a kind of knapsack problem with group structure and discount relationships among items. It is more challenging than the classical 0-1 knapsack problem. In this paper, we study binary particle swarm optimization (PSO) algorithms with different transfer functions and a new encoding scheme for DKP01. An effective binary vector with shorter length is used to represent a solution for new binary PSO algorithms. Eight transfer functions are used to design binary PSO algorithms for DKP01. A new repair operator is developed to handle isolation solution while improving its quality. Finally, we conducted extensive experiments on four groups of 40 instances using our proposed approaches. The experience results show that the proposed algorithms outperform the previous algorithms named FirEGA and SecEGA . Overall, the proposed algorithms with a new encoding scheme represent a potential approach for solving the DKP01.