×

Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. (English) Zbl 1427.90239

Summary: The multidimensional knapsack problem (MKP) is a difficult combinatorial optimization problem, which has been proven as NP-hard problems. Various population-based search algorithms are applied to solve these problems. The particle swarm optimization (PSO) technique is adapted in our study, which proposes two novel PSO algorithms, namely, the binary PSO with time-varying acceleration coefficients (BPSOTVAC) and the chaotic binary PSO with time-varying acceleration coefficients (CBPSOTVAC). The two proposed methods were tested using 116 benchmark problems from the OR-Library to validate and demonstrate the efficiency of these algorithms in solving multidimensional knapsack problems. The results were then compared with those in the other two existing PSO algorithms. The simulation and evaluation results showed that the proposed algorithms, BPSOTVAC and CBPSOTVAC, are superior over the other methods according to its success rate, mean absolute deviation, mean absolute percentage error, least error, and standard deviation.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fréville, A., The multidimensional 0-1 knapsack problem: an overview, Eur. J. Oper. Res., 155, 1-21 (2004) · Zbl 1045.90050
[2] Meier, H.; Christofides, N.; Salkin, G., Capital budgeting under uncertainty - an integrated approach using contingent claims analysis and integer programming, Operations Research, 49, 196-206 (2001) · Zbl 1163.90665
[3] Beaujon, G. J.; Martin, S. P.; McDonald, C. C., Balancing and optimizing a portfolio of R&D projects, Naval Research Logistics, 48, 18-40 (2001) · Zbl 0976.91030
[4] Shih, W., A branch and bound method for the multiconstraint zero-one knapsack problems, Journal of the Operations Research Society, 30, 369-378 (1979) · Zbl 0411.90050
[5] Bertsimas, D.; Demir, R., An approximate dynamic programming approach to multidimensional knapsack problems, Manage. Sci., 48, 550-565 (2002) · Zbl 1232.90322
[6] Vasquez, M.; Hao, J. K., A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite, Computational Optimization and Applications, 20, 137-157 (2001) · Zbl 0983.90082
[7] Garey, M. D.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[8] Drexel, A., A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing, 40, 1-8 (1988) · Zbl 0638.65053
[9] Vasquez, M.; Vimont, Y., Improved results on the 0-1 multidimensional knapsack problem, Eur. J. Oper. Res., 165, 70-81 (2005) · Zbl 1112.90366
[10] Raidl, G. R.; Gottlieb, J., Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithm: a case study for the multidimensional knapsack problem, Evolutionary Computation, 13, 441-475 (2005)
[11] Ke, L.; Feng, Z.; Ren, Z.; Wei, X., An ant colony optimization approach for the multidimensional knapsack problem, Journal of Heuristics, 16, 65-83 (2010) · Zbl 1184.90141
[12] Bansal, J. C.; Deep, K., A modified binary particle swarm optimization for knapsack problems, Appl. Math. Comput., 218, 11042-11061 (2012) · Zbl 1284.90062
[13] Kennedy, J.; Eberhart, R. C., Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, 4, 1942-1948 (1995)
[14] Kennedy, J.; Eberhart, R. C., A discrete binary version of the particle swarm algorithm, Proceedings of IEEE international conference on systems, man, and cybernetics, 5, 4104-4109 (1997)
[15] Liao, Y.-F.; Yau, D.-H.; Chen, C.-L., Evolutionary algorithm to traveling salesman problems, Comput. Math. Appl., 64, 788-797 (2012) · Zbl 1322.90119
[16] Azadeh, A.; Sangari, M. S.; Amiri, A. S., A particle swarm algorithm for inspection optimization in serial multi-stage processes, Applied Mathematical Modeling, 36, 1455-1464 (2012) · Zbl 1243.90252
[17] Montalvo, I.; Izquierdo, J.; Pérez, R.; Tung, M., Particle swarm optimization applied to the design of water supply systems, Comput. Math. Appl., 56, 769-776 (2008) · Zbl 1155.90486
[18] Chih, M.; Yeh, L.-L.; Li, F.-C., Particle swarm optimization for the economic and economic statistical designs of the \(\overline{X}\) control chart, Applied Soft Computing, 11, 5053-5067 (2011)
[19] Yeh, W. C.; Lin, Y. C.; Chung, Y. Y.; Chih, M., A particle swarm optimization approach based on Monte Carlo simulation for solving the complex network reliability problem, IEEE Trans. Reliab., 59, 212-221 (2010)
[20] Cho, H.; Kim, D.; Olivera, F.; Guikema, S. D., Enhanced speciation in particle swarm optimization for multi-modal problems, Eur. J. Oper. Res., 213, 15-23 (2011)
[21] Chuang, L.-Y.; Yang, C.-H.; Li, J.-C., Chaotic maps based on binary particle swarm optimization for feature selection, Applied Soft Computing, 11, 239-248 (2011)
[22] Wang, Y.; Yang, Y., Particle swarm with equilibrium strategy of selection for multi-objective optimization, Eur. J. Oper. Res., 200, 187-197 (2010) · Zbl 1187.90263
[23] Kuo, R. J.; Hong, S. Y.; Huang, Y. C., Integration of particle swarm optimization-based fuzzy neural network and artificial neural network for supplier selection, Applied Mathematical Modeling, 34, 3976-3990 (2010) · Zbl 1201.90205
[25] Kennedy, J.; Eberhart, R. C.; Shi, Y., Swarm Intelligence (2001), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco
[26] Ratnweera, A.; Halgamuge, S. K.; Watson, H. C., Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients, IEEE Trans. Evol. Comput., 8, 240-255 (2004)
[27] Yang, J. M.; Cheng, Y. P.; Horng, J. T.; Kao, C. Y., Applying family competition to evolution strategies for constrained optimization, Lect. Notes Comput. Sci., 1213, 201-211 (1997)
[29] Unler, A.; Murat, A., A discrete particle swarm optimization method for feature selection in binary classification problems, Eur. J. Oper. Res., 206, 528-539 (2010) · Zbl 1188.90280
[30] Shi, Y.; Eberhart, R. C., Empirical study of particle swarm optimization, Proceedings of the congress on evolutionary computation, 3, 101-106 (1999)
[31] Chuanwen, J.; Bompard, E., A hybrid method of chaotic particle swarm optimization and linear interior for reactive power optimization, Mathematics and Computers in Simulation, 68, 57-65 (2005) · Zbl 1108.90048
[32] Xiang, T.; Liao, X., K.-w. Wong, An improved particle swarm optimization algorithm combined with piecewise linear chaotic map, Appl. Math. Comput., 190, 1637-1645 (2007) · Zbl 1122.65363
[33] Jiang, C.; Etorre, B., A self-adaptive chaotic particle swarm algorithm for short term hydroelectric system scheduling in deregulated environment, Energy Convers. Manage., 46, 2689-2696 (2005)
[34] Senyu, S.; Toyada, Y., An approach to linear programming with 0-1 variables, Manage. Sci., 15, B196-B207 (1967)
[35] Weingartner, H. M.; Ness, D. N., Methods for the solution of the multi-dimensional 0/1 knapsack problem, Operations Research, 15, 83-103 (1967)
[36] Freville, A.; Plateau, G., Hard 0-1 multiknapsack test problems for size reduction methods, Investigation Operativa, 1, 251-270 (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.