Skip to main content
Springer Nature Link
Log in

Set-based particle swarm optimization applied to the multidimensional knapsack problem

  • Published:
Save article
View saved research
Swarm Intelligence Aims and scope Submit manuscript

Abstract

Particle swarm optimization algorithms have been successfully applied to discrete/valued optimization problems. However, in many cases the algorithms have been tailored specifically for the problem at hand. This paper proposes a generic set-based particle swarm optimization algorithm for use in discrete-valued optimization problems that can be formulated as set-based problems. A detailed sensitivity analysis of the parameters of the algorithm is conducted. The performance of the proposed algorithm is then compared against three other discrete particle swarm optimization algorithms from literature using the multidimensional knapsack problem and is shown to statistically outperform the existing algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Algorithm 2
Algorithm 3
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. Consider a particle i in SBPSO. Because the swarm usually consists of multiple particles, movement of particles other than i can change \(\widehat{Y}_{i}(t)\) by finding a new best candidate solution. This can then cause \(\widehat{Y}_{i}(t)\) to contain an element e that was first outside of X i (t),Y i (t), and \(\widehat{Y}_{i}(t)\). So, strictly speaking, only elements that are outside of X j (t) and Y j (t) for all particles j in the swarm (and hence also outside \(\widehat{Y}_{j}(t)\) for all j) cannot be added to X i (t) by the attraction mechanism. Similarly, only an element e that is contained in X j (t) and Y j (t) for all particles j in the swarm is one that cannot be removed by the attraction mechanism.

  2. M. Berkelaar, K. Eikland, P. Notebaert, lpsolve version 5.5, http://lpsolve.sourceforge.net/5.5/.

  3. The parameter value combinations with label A are considered to be good combinations, and those with label B are considered reasonable combinations.

  4. Note that, by construction, the parameter value bins for an individual parameter contain almost the same number of parameter value combinations. For parameters c 1 and c 2, the 128 combinations were divided over 10 equally sized bins, resulting in 12 or 13 combinations in each bin. For parameters c 3, c 4, and k, the 128 combinations were divided over nine equally sized bins, resulting in 14 or 15 combinations in each bin. By dividing the results in each bin by the total number of combinations in the bin, the number of combinations with each label was changed instead into the fraction of all combinations with that label, so that results are better comparable across bins.

  5. The error is defined as the deviation from the known optimum for the small MKPs and as the deviation from the LP relaxation bound for the large MKPs.

  6. Even if all problems yield the same ranks, resulting in average rankings of 1, 2, 3, and 4 for the four algorithm-topology pairs, the post hoc Nemenyi test did not show a statistically significant difference between ranks 1 and 2, at a confidence level of α=0.05, which led to a Holm α of 0.0167 for the comparison of the two best performing pairs.

References

  • Abraham, A., Liu, H., Zhang, W., & Chang, T.-G. (2006). Scheduling jobs on computational grids using fuzzy particle swarm algorithm. In B. Gabrys, R. Howlett, & L. Jain (Eds.), Lecture notes in computer science: Vol. 4252. Knowledge-based intelligent information and engineering systems (pp. 500–507). Berlin: Springer.

    Chapter  Google Scholar 

  • Benameur, L., Alami, J., & El Imrani, A. (2009). A new discrete particle swarm model for the frequency assignment problem. In Proceedings of the IEEE/ACS international conference on computer systems and applications (pp. 139–144). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Birattari, M., Stützle, T., Paquete, L., & Varrentrapp, K. (2002). A racing algorithm for configuring metaheuristics. In Proceedings of the genetic and evolutionary computation conference (pp. 11–18). San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Bock, J., & Hettenhausen, J. (2012). Discrete particle swarm optimisation for ontology alignment. Information Sciences, 192(0), 152–173.

    Article  Google Scholar 

  • Chandrasekaran, S., Ponnambalam, S., Suresh, R., & Vijayakumar, N. (2006). A hybrid discrete particle swarm optimization algorithm to solve flow shop scheduling problems. In Proceedings of the IEEE conference on cybernetics and intelligent systems (pp. 1–6). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Chen, W.-N., Zhang, J., Chung, H., Zhong, W.-L., Wu, W.-G., & Shi, Y. (2010). A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Transactions on Evolutionary Computation, 14(2), 278–300.

    Article  Google Scholar 

  • Chu, P., & Beasley, J. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4, 63–86.

    Article  MATH  Google Scholar 

  • Clerc, M. (2004). Discrete particle swarm optimization illustrated by the traveling salesman problem. In G. Onwubolu & B. Babu (Eds.), New optimization techniques in engineering (pp. 219–239). Berlin: Springer.

    Google Scholar 

  • Correa, E., Freitas, A., & Johnson, C. (2006). A new discrete particle swarm optimization algorithm applied to attribute selection in a bioinformatics data set. In Proceedings of the genetic and evolutionary computation conference (pp. 35–42). New York: ACM Press.

    Google Scholar 

  • Du, J.-X., Huang, D.-S., Zhang, J., & Wang, X.-F. (2005). Shape matching using fuzzy discrete particle swarm optimization. In Proceedings of the IEEE swarm intelligence symposium (pp. 405–408). Piscataway: IEEE Press.

    Google Scholar 

  • Eberhart, R. C., Kennedy, J., & Shi, Y. (2001). Morgan Kaufmann series in evolutionary computation. Swarm intelligence. Amsterdam: Elsevier.

    Google Scholar 

  • Eberhart, R. C., & Shi, Y. (2001). Particle swarm optimization: developments, applications and resources. In Proceedings of the IEEE congress on evolutionary computation (Vol. 1, pp. 81–86). Piscataway: IEEE Press.

    Google Scholar 

  • Eberhart, R. C., Simpson, P. K., & Dobbins, R. W. (1996). Computational intelligence PC tools. Boston: AP Professional.

    Google Scholar 

  • Franken, N. (2009). Visual exploration of algorithm parameter space. In Proceedings of the IEEE congress on evolutionary computation (pp. 389–398). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Friedman, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32(200), 675–701.

    Article  Google Scholar 

  • Gao, F., Cui, G., Zhao, Q., & Liu, H. (2006). Application of improved discrete particle swarm algorithm in partner selection of virtual enterprise. International Journal of Computer Science and Network Security, 6(3A), 208–212.

    Google Scholar 

  • García, A., Pastor, R., & Corominas, A. (2006). Solving the response time variability problem by means of metaheuristics. Frontiers in Artificial Intelligence and Applications, 146, 187–196.

    Google Scholar 

  • Gens, G., & Levner, E. (1980). Complexity of approximation algorithms for combinatorial problems: a survey. Special Interest Group on Algorithms and Computation Theory News, 12, 52–65.

    Google Scholar 

  • Hembecker, F., Lopes, H. S., & Godoy, J. W. (2007). Particle swarm optimization for the multidimensional knapsack problem. In Proceedings of the international conference on adaptive and natural computing algorithms, part I (pp. 358–365). Berlin: Springer.

    Chapter  Google Scholar 

  • Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2), 65–70.

    MathSciNet  MATH  Google Scholar 

  • Iman, R., & Davenport, J. (1980). Approximations of the critical region of the Friedman statistic. Communications in Statistics, Part A – Theory and Methods, 9(6), 571–595.

    Article  Google Scholar 

  • Kennedy, J., & Eberhart, R. (1997). A discrete binary version of the particle swarm algorithm. In Proceedings of the world multiconference on systemics, cybernetics and informatics (Vol. 5, pp. 4101–4109). Piscataway: IEEE Press.

    Google Scholar 

  • Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimisation. In Proceedings of the IEEE international conference on neural networks (pp. 1942–1948). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Kennedy, J., & Mendes, R. (2002). Population structure and particle swarm performance. In Proceedings of the IEEE congress on evolutionary computation (Vol. 2, pp. 1671–1676). Piscataway: IEEE Press.

    Google Scholar 

  • Khan, S., & Engelbrecht, A. (2010). A fuzzy particle swarm optimization algorithm for computer communication network topology design. Applied Intelligence, 36, 1–17.

    Google Scholar 

  • Khanesar, M., Teshnehlab, M., & Shoorehdeli, M. (2007). A novel binary particle swarm optimization. In Proceedings of the Mediterranean conference on control and automation. Piscataway: IEEE Press.

    Google Scholar 

  • Khuri, S., Bäck, T., & Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the ACM symposium on applied computing (pp. 188–193). New York: ACM Press.

    Google Scholar 

  • Kong, M., & Tian, P. (2006). Apply the particle swarm optimization to the multidimensional knapsack problem. In L. Rutkowski, R. Tadeusiewicz, L. Zadeh, & J. Zurada (Eds.), Lecture notes in computer science: Vol. 4029. Proceedings of the international conference on artificial intelligence and soft computing (pp. 1140–1149). Berlin: Springer.

    Google Scholar 

  • Kong, M., Tian, P., & Kao, Y. (2008). A new ant colony optimization algorithm for the multidimensional knapsack problem. Computers & Operations Research, 35(8), 2672–2683.

    Article  MathSciNet  MATH  Google Scholar 

  • Labed, S., Gherboudj, A., & Chikhi, S. (2011). A modified hybrid particle swarm optimization algorithm for multidimensional knapsack problem. International Journal of Computer Applications, 34(2), 11–16.

    Google Scholar 

  • Langeveld, J., & Engelbrecht, A. P. (2011). A generic set-based particle swarm optimization algorithm. In Proceedings of the international conference on swarm intelligence, Cergy, France. EISTI.

    Google Scholar 

  • Li, B.-B., Wang, L., & Liu, B. (2008). An effective PSO-based hybrid algorithm for multiobjective permutation flow shop scheduling. IEEE Transactions on Systems, Man and Cybernetics. Part A. Systems and Humans, 38(4), 818–831.

    Article  Google Scholar 

  • Liu, B., Wang, L., & Jin, Y.-H. (2007). An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Transactions on Systems, Man and Cybernetics. Part B. Cybernetics, 37(1), 18–27.

    Article  Google Scholar 

  • Liu, H., & Abraham, A. (2007). An hybrid fuzzy variable neighborhood particle swarm optimization algorithm for solving quadratic assignment problems. Journal of Universal Computer Science, 13(9), 1309–1331.

    Google Scholar 

  • Liu, H., Abraham, A., & Hassanien, A. E. (2010). Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Generations Computer Systems, 26(8), 1336–1343.

    Article  Google Scholar 

  • Lorie, J. H., & Savage, L. J. (1955). Three problems in rationing capital. The Journal of Business, 28, 229.

    Article  Google Scholar 

  • Ma, C.-X., Qian, L., Wang, L., Menhas, M. I., & Fei, M.-R. (2010). Determination of the PID controller parameters by modified binary particle swarm optimization algorithm. In Proceedings of the Chinese control and decision conference (pp. 2689–2694). Piscataway: IEEE Press.

    Google Scholar 

  • Menhas, M. I., Wang, L., Fei, M.-R., & Ma, C.-X. (2011). Coordinated controller tuning of a boiler turbine unit with new binary particle swarm optimization algorithm. International Journal of Automation and Computing, 8, 185–192.

    Article  Google Scholar 

  • Neethling, C., & Engelbrecht, A. (2006). Determining RNA secondary structure using set-based particle swarm optimization. In G. Yen, S. Lucas, G. Fogel, G. Kendall, R. Salomon, B.-T. Zhang, C. Coello, & T. Runarsson (Eds.), Proceedings of the IEEE congress on evolutionary computation (pp. 1670–1677). Piscataway: IEEE Press.

    Google Scholar 

  • Nemenyi, P. (1963). Distribution-free multiple comparisons. PhD thesis, Princeton University, Princeton, NJ, USA.

  • Pampara, G., Franken, N., & Engelbrecht, A. (2005). Combining particle swarm optimisation with angle modulation to solve binary problems. In Proceedings of the IEEE congress on evolutionary computation (Vol. 1, pp. 89–96). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Pang, W., Wang, K.-P., Zhou, C.-G., & Dong, L.-J. (2004a). Fuzzy discrete particle swarm optimization for solving traveling salesman problem. In Proceedings of the IEEE international conference on computer and information technology (pp. 796–800). Piscataway: IEEE Press.

    Google Scholar 

  • Pang, W., Wang, K.-P., Zhou, C.-G., Dong, L.-J., Liu, M., Zhang, H.-Y., & Wang, J.-Y. (2004b). Modified particle swarm optimization based on space transformation for solving traveling salesman problem. In Proceedings of the international conference on machine learning and cybernetics (Vol. 4, pp. 2342–2346). Piscataway: IEEE Press.

    Google Scholar 

  • Puchinger, J., Raidl, G. R., & Pferschy, U. (2010). The multidimensional knapsack problem: structure and algorithms. INFORMS Journal on Computing, 22, 250–265.

    Article  MathSciNet  MATH  Google Scholar 

  • Shen, B., Yao, M., & Yi, W. (2006). Heuristic information based improved fuzzy discrete PSO method for solving TSP. In Proceedings of the Pacific Rim international conference on artificial intelligence (pp. 859–863). Berlin: Springer.

    Google Scholar 

  • Shen, Q., Jiang, J.-H., Jiao, C.-X., Shen, G.-L., & Yu, R.-Q. (2004). Modified particle swarm optimization algorithm for variable selection in MLR and PLS modeling: QSAR studies of antagonism of angiotensin II antagonists. European Journal of Pharmaceutical Sciences, 22(2–3), 145–152.

    Article  Google Scholar 

  • Shi, Y., & Eberhart, R. C. (1998). A modified particle swarm optimizer. In Proceedings of the IEEE international conference on evolutionary computation (pp. 69–73). Piscataway: IEEE Press.

    Google Scholar 

  • Shi, Y., & Eberhart, R. C. (2001). Fuzzy adaptive particle swarm optimization. In Proceedings of the IEEE congress on evolutionary computation (Vol. 1, pp. 101–106). Piscataway: IEEE Press.

    Google Scholar 

  • Tasgetiren, M. F., Sevkli, M., Liang, Y.-C., & Gencyilmaz, G. (2004). Particle swarm optimization algorithm for permutation flowshop sequencing problem. In M. Dorigo, M. Birattari, C. Blum, L.M. Gambardella, F. Mondada, & T. Stützle (Eds.), Lecture notes in computer science: Vol. 3172. Ant colony, optimization and swarm intelligence (pp. 366–385). Berlin: Springer.

    Chapter  Google Scholar 

  • Tu, C.-J., Chuang, L.-Y., Chang, J.-Y., & Yang, C.-H. (2008). Feature selection using PSO-SVM. IAENG International Journal of Computer Science, 33, 111–116.

    Google Scholar 

  • Veenhuis, C. (2008). A set-based particle swarm optimization method. In G. Rudolph, T. Jansen, S. Lucas, C. Poloni, & N. Beume (Eds.), Lecture notes in computer science: Vol. 5199. Proceedings of the parallel problem solving from nature conference (pp. 971–980). Berlin: Springer.

    Chapter  Google Scholar 

  • Wang, K.-P., Huang, L., Zhou, C.-G., & Pang, W. (2003). Particle swarm optimization for traveling salesman problem. In Proceedings of the international conference on machine learning and cybernetics (Vol. 3, pp. 1583–1585). Piscataway: IEEE Computer Society.

    Google Scholar 

  • Wang, L., Wang, X., Fu, J., & Zhen, L. (2008). A novel probability binary particle swarm optimization algorithm and its application. Journal of Software, 3(9), 28–35.

    Article  Google Scholar 

  • Wu, Z., Ni, Z., Gu, L., & Liu, X. (2010). A revised discrete particle swarm optimization for cloud workflow scheduling. In Proceedings of the international conference on computational intelligence and security (pp. 184–188). Piscataway: IEEE Press.

    Chapter  Google Scholar 

  • Yang, S., Wang, M., & Jiao, L. (2004). A quantum particle swarm optimization. In Proceedings of the IEEE congress on evolutionary computation (Vol. 1, pp. 320–324). Piscataway: IEEE Press.

    Google Scholar 

  • Zhang, C., Sun, J., Wang, Y., & Yang, Q. (2007). An improved discrete particle swarm optimization algorithm for TSP. In Proceedings of the IEEE/WIC/ACM international conferences on web intelligence and intelligent agent technology (pp. 35–38). Piscataway: IEEE Computer Society.

    Google Scholar 

  • Zhen, L., Wang, L., Wang, X., & Huang, Z. (2008). A novel PSO-inspired probability-based binary optimization algorithm. In Proceedings of the international symposium on information science and engineering (Vol. 2, pp. 248–251). Oulu: Academy Publisher.

    Chapter  Google Scholar 

  • Zhong, W.-L., Zhang, J., & Chen, W.-N. (2007). A novel discrete particle swarm optimization to solve traveling salesman problem. In Proceedings of the IEEE congress on evolutionary computation (pp. 3283–3287). Piscataway: IEEE Press.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Pretoria, Lynnwood Road, Hillcrest, Pretoria, South Africa

    Joost Langeveld & Andries P. Engelbrecht

Authors
  1. Joost Langeveld
    View author publications

    Search author on:PubMed Google Scholar

  2. Andries P. Engelbrecht
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Andries P. Engelbrecht.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Langeveld, J., Engelbrecht, A.P. Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intell 6, 297–342 (2012). https://doi.org/10.1007/s11721-012-0073-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11721-012-0073-4

Keywords