zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A Modified Binary Particle Swarm Optimization for Knapsack Problems. (English) Zbl 1284.90062
Summary: The knapsack problems (KPs) are classical NP-hard problems in Operations Research having a number of engineering applications. Several traditional as well as population based search algorithms are available in the literature for the solution of these problems. In this paper, a new modified binary particle swarm optimization (MBPSO) algorithm is proposed for solving KPs, particularly 0-1 knapsack problems (KPs) and multidimensional knapsack problems (MKPs). Compared to the basic binary particle swarm optimization (BPSO), this improved algorithm introduces a new probability function which maintains the diversity in the swarm and makes it more explorative, effective and efficient in solving KPs. MBPSO is tested through computational experiments over benchmark problems and the results are compared with those of BPSO and a relatively recent modified version of BPSO namely genotype-phenotype modified binary particle swarm optimization (GPMBPSO). To validate our idea and to demonstrate the efficiency of the proposed algorithm for KPs, experiments are carried out with various data instances of KP and MKP and the results are compared with those of BPSO and GPMBPSO.

90C27Combinatorial optimization
90C59Approximation methods and heuristics
Full Text: DOI
[1] Dantzig, G. B.: Discrete variable extremum problems, Operations research 5, 266-277 (1957)
[2] Liu, A.; Wang, J.; Han, G.; Wang, S.; Wen, J.: Improved simulated annealing algorithm solving for 0/1 knapsack problem, Isda 02, 1159-1164 (2006)
[3] J. Thiel, S. Voss, Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms, INFOR, Canada, vol. 32, 1994, pp. 226 -- 242. · Zbl 0823.90092
[4] Chu, P. C.; Beasley, J. E.: A genetic algorithm for the multidimensional knapsack problem, Journal of heuristics 4, 63-86 (1998) · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[5] Huo, Hongwei; Xu, Jin; Bao, Zheng: Solving 0/1 knapsack problem using genetic algorithm, Journal of xidian university 26, No. 4, 493-497 (1999)
[6] P. Zhao, P. Zhao, X. Zhang, A new ant colony optimization for the knapsack problem, in: Proceedings of Seventh International Conference on Computer -- Aided Industrial Design and Conceptual Design, November 17 -- 19, 2006, pp. 1 -- 3.
[7] H. Shi, Solution to 0/1 knapsack problem based on improved ant colony algorithm, international conference on information acquisition, in: IEEE International Conference on Information Acquisition, 2006, pp. 1062 -- 1066.
[8] C. Peng, Z. Jian Li, Liu, Solving 0 -- 1 knapsack problems by a discrete binary version of differential evolution, in: Second International Symposium on Intelligent Information Technology Application, IITA ’08, vol. 2, 2008, pp. 513 -- 516.
[9] Lei, W.; Jin, P.; Licheng, J.: Immune algorithm, Acta electronica sinia 28, No. 7, 74-78 (2000)
[10] B. Ye, J. Sun, Wen-Bo Xu, Solving the hard knapsack problems with a binary particle swarm approach, ICIC 2006, LNBI 4115, 2006, pp. 155 -- 163.
[11] X. Shen, Y. Li, Wei Wang, A dynamic adaptive particle swarm optimization optimization for knapsack problem, in: Proceedings of the Sixth World Congress on Intelligent Control and Automation, June 21 -- 23, Dalian, China, 2006, pp. 3183 -- 3187.
[12] Shen, X.; Wang, W.; Zheng, P.: Modified particle swarm optimization for 0 -- 1 knapsack problem, Computer engineering 32, No. 18, 23-24 (2006)
[13] Yi-Chao He, L. Zhou, Chun-Pu Shen, A greedy particle swarm optimization for solving knapsack problem, in: International Conference on Machine Learning and Cybernetics, vol. 2, 2007, pp. 995 -- 998.
[14] Guo-Li Zhang, Yi Wei, An improved particle swarm optimization algorithm for solving 0 -- 1 knapsack problem, in: Proceedings of the Seventh International Conference on Machine Learning and Cybernetics, Kunming, 12 -- 15 July 2008, pp. 915 -- 918 .
[15] J. Puchinger, G. Raidl, U. Pferschy, The multidimensional knapsack problem, Structure and algorithms, Technical Report 006149, National ICT Australia, Melbourne, Australia, 2007. · Zbl 1243.90190
[16] Dammeyer, F.; Voss, S.: Dynamic tabu list management using reverse elimination method, Annals of operations research 41, 31-46 (1993) · Zbl 0775.90290 · doi:10.1007/BF02022561
[17] Aboudi, R.; Jornsten, K.: Tabu search for general zero-one integer programs using the pivot and complement heuristic, ORSA journal on computing 6, 82-93 (1994) · Zbl 0798.90105 · doi:10.1287/ijoc.6.1.82
[18] Battiti, R.; Tecchiolli, G.: Local search with memory: benchmarking RTS, OR spektrum 17, 67-86 (1995) · Zbl 0843.90094 · doi:10.1007/BF01719249
[19] Glover, F.; Kochenberger, G. A.: Critical event tabu search for multidimensional knapsack problem, Meta-heuristics: theory and applications, 407-427 (1996) · Zbl 0877.90055
[20] M. Vasquez, Jin-Kao Hao, A hybrid approach for the 0 -- 1 multidimensional knapsack problem, in: Proceedings of IJCAI-01, Seatle, Washington, 2001, pp. 328-333. · Zbl 1015.90056
[21] Li, V. C.: Tight oscillations tabu search for multidimensional knapsack problems with generalized upper bound constraints, Computers and operations research 32, No. 11, 2843-2852 (2005) · Zbl 1071.90051 · doi:10.1016/j.cor.2004.04.020
[22] Li, V. C.; Curry, G. L.: Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search, Computers and operations research 32, No. 4, 825-848 (2005) · Zbl 1071.90050 · doi:10.1016/j.cor.2003.08.021
[23] Khuri, S.; Back, T.; Heitkotter, J.: The zero/one multiple knapsack problem and genetic algorithm, Proceedings of the 1994 ACM symposium on applied computing (SAC’94), 188-193 (1994)
[24] Rudolph, G.; Sprave, J. A.: Cellular genetic algorithm with self-adjusting acceptance threshold, , 365-372 (1995)
[25] Cotta, C.; Troya, J. Ma.: A hybrid genetic algorithm for the 0 -- 1 multiple knapsack problem, , 250-254 (1997)
[26] Kato, K.; Sakawa, M.: Genetic algorithms with decomposition procedures for multidimensional 0 -- 1 knapsack problems with block angular structures, IEEE transactions on systems, man and cybernetics-part B: cybernetics 33, No. 3, 410-419 (2003)
[27] Hong Li, Yong-Chang Jiao, Li Zhang, Ze-Wei Gu, Genetic algorithm based on the orthogonal design for multidimensional knapsack problems, ICNC 2006, Part I, LNCS 4221, 2006, pp. 696 -- 705.
[28] Djannaty, F.; Doostdar, S.: A hybrid genetic algorithm for the multidimensional knapsack problem, International journal of contemporary mathematics sciences 3, No. 9, 443-456 (2008) · Zbl 1213.90178
[29] Kong, M.; Tian, P.; Kao, Y.: A new ant colony optimization algorithm for the multidimensional knapsack problem, Computers and operations research 35, No. 8, 2672-2683 (2008) · Zbl 1169.90435 · doi:10.1016/j.cor.2006.12.029
[30] Ji Junzhong, Huang Zhen, Chunnian Liu, An ant colony optimization algorithm for solving the multidimensional knapsack problems, in: IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2007, pp. 10 -- 16.
[31] I. Alaya, C. Solnon, K. Ghdira, Ant algorithm for the multi-dimensional knapsack problem, in: International Conference on Bioinspired Optimization Methods and their Applications (BIOMA 2004), 2004, pp. 63 -- 72.
[32] Uyar, S.; Eryigit, G.: Improvements to penalty-based evolutionary algorithms for the multi-dimensional knapsack problem using a gene-based adaptive mutation approach, Gecco, 1257-1264 (2005)
[33] Drexl, A.: A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing 40, No. 1, 1-8 (1988) · Zbl 0638.65053 · doi:10.1007/BF02242185
[34] M. Gong, L. Jiao, Ma Wenping, Gou Shuiping, Solving multidimensional knapsack problems by an immune-inspired algorithm, in: IEEE Congress on Evolutionary Computation, 2007, pp. 3385 -- 3391.
[35] Kong, M.; Tian, P.: Apply the particle swarm optimization to the multidimensional knapsack problem, Icaisc 2006 4029, 1140-1149 (2006)
[36] Hembecker, F.; Lopes, Heitor S.; Jr., Godoy Walter: Particle swarm optimization for the multidimensional knapsack problem, Adaptive and natural computing algorithms 4431, 358-365 (2007)
[37] K. Deep, J.C. Bansal, A socio-cognitive particle swarm optimization for multi-dimensional knapsack problem, in: First International Conference on Emerging Trends in Engineering and Technology ICETET, India, 2008, pp. 355 -- 360.
[38] Fleszar, K.; Hindi, K. S.: Fast, effective heuristics for the 0 -- 1 multi-dimensional knapsack problem, Computers and operations research 36, No. 5, 1602-1607 (2009) · Zbl 1179.90282 · doi:10.1016/j.cor.2008.03.003
[39] Gottlieb, J.: Permutation-based evolutionary algorithms for multidimensional knapsack problems, SAC ’00 1, 408-414 (2000)
[40] J. Kennedy, R. Eberhart, Particle swarm optimization, in: Proceedings IEEE International Conference Neural Networks, vol. 4, 1942 -- 1948, 1995.
[41] R. Eberhart, J. Kennedy, A new optimizer using particle swarm theory, in: Proceedings of Sixth International Symposium Micro Machine Human Science, 1995, pp. 39 -- 45.
[42] Banks, A.; Vincent, J.; Anyakoha, C.: A review of particle swarm optimization. Part I: Background and development, Natural computing: an international journal 6, No. 4, 467-484 (2007) · Zbl 1125.90065 · doi:10.1007/s11047-007-9049-5
[43] Banks, A.; Vincent, J.; Anyakoha, C.: A review of particle swarm optimization. Part II: Hybridisation, combinatorial, multicriteria and constrained optimization and indicative applications, Natural computing 7, No. 1, 109-124 (2008) · Zbl 1148.68375 · doi:10.1007/s11047-007-9050-z
[44] Poli, R.; Kennedy, J.; Blackwell, T.: Particle swarm optimization: an overview, Swarm intelligence 1, 33-57 (2007)
[45] J. Kennedy, R.C. Eberhart, A discrete binary version of the particle swarm optimization, in: Proceedings of the world Multiconference on Systemics, Cybernetics, Informatics, 1997, pp. 4104 -- 4109.
[46] Engelbrecht, A. P.: Fundamentals of computational swarm intelligence, (2005)
[47] Lee Chou-Yuan, Lee Zne-Jung, Su Shun-Feng, A new approach for solving 0/1 knapsack problem, IEEE International Conference on Systems, Man, and Cybernetics October 8 -- 11, Taipei, Taiwan, 2006, pp. 3138 -- 3143.
[48] J.E. Beasley, ORLib -- Operations Research Library. [http://people.brunel.ac.uk/∼mastjjb/jeb/orlib/mknapinfo.html], (2005).
[49] Senyu, S.; Toyoda, Y.: An approach to linear programming with 0 -- 1 variables, Management science 15, B196-B207 (1967)
[50] Weingartner, H. M.; Ness, D. N.: Methods for the solution of the multidimensional 0/1 knapsack problem, Operations research 15, 83-103 (1967)
[51] Shih, W.: A branch and bound method for the multiconstraint zero-one knapsack problem, Journal of operations research society 30, 369-378 (1979) · Zbl 0411.90050 · doi:10.2307/3009639
[52] Lee, Sangwook; Soak, Sangmoon; Oh, Sanghoun; Pedrycz, Witold; Jeon, Moongu: Modified binary particle swarm optimization, Progress in natural science 18, No. 9, 1161-1166 (2008)
[53] Deep, K.; Bansal, J. C.: Mean particle swarm optimisation for function optimisation, International journal of computational intelligence studies 1, No. 1, 72-92 (2009)