Fusing Binary Particle Swarm Optimzation with Simulated Annealing for Knapsack Problems
作者： Mana Anantathanavit , Mud-Armeen Munlin
DOI: 10.1109/ICIEA.2014.6931496
关键词:
摘要: The Knapsack Problems (KPs) is a well-known combinatorial optimization problem. It has variety of practical applications. We propose the algorithm to solve both 0–1 problem (KP) and Multidimensional Problem (MKP) by fusing Binary Particle Swarm Optimization (BPSO) Simulated Annealing (SA) with maximum profit objective. main contribution develop novel approach hybridizing BPSO at local optimum simulated annealing help escape from reach global optimum. results indicate that fusion outperforms individual implementation binary particle swarm annealing.
06931496.pdf 参考文章(16)
S. Al-Shihabi, S. Ólafsson, A hybrid of Nested Partition, Binary Ant System, and Linear Programming for the multidimensional knapsack problem Computers & Operations Research. ,vol. 37, pp. 247- 255 ,(2010) , 10.1016/J.COR.2009.04.015
Feng-Tse Lin, Solving the knapsack problem with imprecise weight coefficients using genetic algorithms European Journal of Operational Research. ,vol. 185, pp. 133- 145 ,(2008) , 10.1016/J.EJOR.2006.12.046
Zhi-gang Ren, Zu-ren Feng, Ai-min Zhang, Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem Information Sciences. ,vol. 182, pp. 15- 29 ,(2012) , 10.1016/J.INS.2011.07.033
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing Science. ,vol. 220, pp. 671- 680 ,(1983) , 10.1126/SCIENCE.220.4598.671
Esra Bas, Surrogate relaxation of a fuzzy multidimensional 0-1 knapsack model by surrogate constraint normalization rules and a methodology for multi-attribute project portfolio selection Engineering Applications of Artificial Intelligence. ,vol. 25, pp. 958- 970 ,(2012) , 10.1016/J.ENGAPPAI.2011.09.015
Kazuo Iwama, Guochuan Zhang, Online knapsack with resource augmentation Information Processing Letters. ,vol. 110, pp. 1016- 1020 ,(2010) , 10.1016/J.IPL.2010.08.013
Alexandre Salles da Cunha, Laura Bahiense, Abilio Lucena, Cid Carvalho de Souza, A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem Electronic Notes in Discrete Mathematics. ,vol. 36, pp. 623- 630 ,(2010) , 10.1016/J.ENDM.2010.05.079
Jens Egeblad, David Pisinger, Heuristic approaches for the two- and three-dimensional knapsack packing problem Computers & Operations Research. ,vol. 36, pp. 1026- 1049 ,(2009) , 10.1016/J.COR.2007.12.004
S. Michel, N. Perrot, F. Vanderbeck, Knapsack Problems with Setups European Journal of Operational Research. ,vol. 196, pp. 909- 918 ,(2009) , 10.1016/J.EJOR.2008.05.001
Christiaan V. Henkel, Thomas Bäck, Joost N. Kok, Grzegorz Rozenberg, Herman P. Spaink, DNA computing of solutions to knapsack problems BioSystems. ,vol. 88, pp. 156- 162 ,(2007) , 10.1016/J.BIOSYSTEMS.2006.06.001