A binary particle swarm optimization based on the surrogate information with proportional acceleration coefficients for the 0-1 multidimensional knapsack problem. (17th February 2016)

• Record Type: Journal Article
• Authors: Lin, Chin-Jung; Chern, Maw-Sheng; Chih, Mingchang
• Is Part Of: Journal of industrial and production engineering. Volume 33:Number 2(2016)
• Page Start: 77
• Page End: 102
• Publication Date: 2016-02-17
• Subjects: 0-1 Multidimensional knapsack problem -- binary particle swarm optimization -- propotional acceleration coefficients -- surrogate ratio -- OR-library; Industrial engineering -- Periodicals; Production engineering -- Periodicals; 620
• DOI: 10.1080/21681015.2015.1111263
• Languages: English
• ISSNs: 2168-1015

Abstract

Abstract : The 0-1 multidimensional knapsack problem (MKP) has been proven it belongs to difficult NP-hard combinatorial optimization problems. There are various search algorithms based on population concept to solve these problems. The particle swarm optimization (PSO) technique is adapted in our study, which proposes a novel PSO algorithm, namely, the binary PSO based on surrogate information with proportional acceleration coefficients (BPSOSIPAC). The proposed algorithm was tested on 135 benchmark problems from the OR-Library to validate and demonstrate the efficiency in solving multidimensional knapsack problems. The results were then compared with those in the other nine existing PSO algorithms. The simulation and evaluation results showed that the proposed algorithm, BPSOSIPAC, is superior to the other methods according to success rate, average number of function evaluations, average number of function evaluations of successful runs, average error (AE), mean absolute deviation, mean absolute percentage error, least error, standard deviation, best profit, mean profit, worst profit, AE of best profit (%), and AE of mean profit deviation (%).