Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Solving 0–1 knapsack problem by binary flower pollination algorithm

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

In this paper, we propose a new binary version of the flower pollination algorithm (BFPA) for solving 0–1 knapsack problem. The standard flower pollination algorithm (FPA) is used for the continuous optimization problems. So, a transformation function is used to convert the continuous values generated from FPA into binary ones. A penalty function is added to the evaluation function to give negative values for the infeasible solutions. The infeasible solutions are treated by using a two-stage repair operator called flower repair. Experimental results have proved the superiority of BFPA over other 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+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Hu TC, Kahng AB (2016) The knapsack problem. In: Linear and integer programming made easy. Springer, Berlin, pp 87–101

    Chapter  Google Scholar 

  2. Weingartner HM (1966) Capital budgeting of interrelated projects: survey and synthesis. Manag Sci 12(7):485–516

    Article  Google Scholar 

  3. Mansini R, Speranza MG (1999) Heuristic algorithms for the portfolio selection problem with minimum transaction lots. Eur J Oper Res 114(2):219–233

    Article  Google Scholar 

  4. Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14(6):1045–1074

    Article  MathSciNet  Google Scholar 

  5. De Vries S, Vohra RV (2003) Combinatorial auctions: a survey. INFORMS J Comput 15(3):284–309

    Article  MathSciNet  Google Scholar 

  6. Ferreira CE, Martin A, de Souza CC, Weismantel R, Wolsey LA (1996) Formulations and valid inequalities for the node capacitated graph partitioning problem. Math Program 74(3):247–266

    Article  MathSciNet  Google Scholar 

  7. Johnson EL, Mehrotra A, Nemhauser GL (1993) Min-cut clustering. Math Program 62(1–3):133–151

    Article  MathSciNet  Google Scholar 

  8. Martello S, Pisinger D, Toth P (2000) New trends in exact algorithms for the 0–1 knapsack problem. Eur J Oper Res 123(2):325–332

    Article  MathSciNet  Google Scholar 

  9. Plateau G, Nagih A (2010) 0–1 knapsack problems. In: Paradigms of combinatorial optimization, 2nd edn, pp 215–242

    Google Scholar 

  10. Osaba E, Yang XS, Diaz F, Lopez-Garcia P, Carballedo R (2016) An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intell 48:59–71

    Article  Google Scholar 

  11. Gong QQ, Zhou YQ, Yang Y (2011) Artificial glowworm swarm optimization algorithm for solving 0–1 knapsack problem. In: Advanced materials research, vol 143. Trans Tech Publications, pp 166–171

  12. Lim TY, Al-Betar MA, Khader AT (2016) Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm. Expert Syst Appl 54:241–250

    Article  Google Scholar 

  13. Ma Y, Wan J (2011) Improved hybrid adaptive genetic algorithm for solving knapsack problem. In: 2011 2nd international conference on intelligent control and information processing (ICICIP), vol 2. IEEE, pp 644–647

  14. Gupta M (2013) A fast and efficient genetic algorithm to solve 0–1 knapsack problem. Int J Digit Appl Contemp Res 1(6):1–5

    Google Scholar 

  15. Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science, 1995. MHS’95. IEEE, pp 39–43

  16. Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: 1997 IEEE international conference on systems, man, and cybernetics, 1997. Computational cybernetics and simulation, vol 5. IEEE, pp 4104–4108

  17. Bansal JC, Deep K (2012) A modified binary particle swarm optimization for knapsack problems. Appl Math Comput 218(22):11042–11061

    MathSciNet  MATH  Google Scholar 

  18. Nguyen PH, Wang D, Truong TK (2016) A new hybrid particle swarm optimization and greedy for 0-1 knapsack problem. Indones J Electr Eng Comput Sci 1(3):411–418

    Article  Google Scholar 

  19. Yang X-S (2009) Firefly algorithms for multimodal optimization. In: International symposium on stochastic algorithms. Springer, Berlin

    Chapter  Google Scholar 

  20. Zouache D, Nouioua F, Moussaoui A (2016) Quantum-inspired firefly algorithm with particle swarm optimization for discrete optimization problems. Soft Comput 20(7):2781–2799

    Article  Google Scholar 

  21. Feng Y, Wang GG (2015) An improved hybrid encoding firefly algorithm for randomized time-varying knapsack problems. In: 2015 second international conference on soft computing and machine intelligence (ISCMI). IEEE, pp 9–14

  22. Wang GG, Deb S, Cui Z (2015) Monarch butterfly optimization. Neural Comput Appl 28(3):1–20

    Google Scholar 

  23. Wang GG, Deb S, Zhao X, Cui Z (2016) A new monarch butterfly optimization with an improved crossover operator. Oper Res. https://doi.org/10.1007/s12351-016-0251-z

    Article  Google Scholar 

  24. Feng Y, Yang J, Wu C, Lu M, Zhao XJ (2016) Solving 0–1 knapsack problems by chaotic monarch butterfly optimization algorithm with Gaussian mutation. Memetic Comput. https://doi.org/10.1007/s12293-016-0211-4

    Article  Google Scholar 

  25. Feng Y, Wang GG, Deb S, Lu M, Zhao XJ (2017) Solving 0–1 knapsack problem by a novel binary monarch butterfly optimization. Neural Comput Appl 28(7):1619–1634

    Article  Google Scholar 

  26. Zhao RQ, Tang WS (2008) Monkey algorithm for global numerical optimization. J Uncertain Syst 2(3):165–176

    Google Scholar 

  27. Zhou Y, Chen X, Zhou G (2016) An improved monkey algorithm for a 0–1 knapsack problem. Appl Soft Comput 38:817–830

    Article  Google Scholar 

  28. Zhou Y, Li L, Ma M (2016) A complex-valued encoding bat algorithm for solving 0–1 knapsack problem. Neural Process Lett 44(2):407–430

    Article  Google Scholar 

  29. Zhou Y, Bao Z, Luo Q, Zhang S (2017) A complex-valued encoding wind driven optimization for the 0–1 knapsack problem. Appl Intell 46(3):684–702

    Article  Google Scholar 

  30. Lv J, Wang X, Huang M, Cheng H, Li F (2016) Solving 0–1 knapsack problem by greedy degree and expectation efficiency. Appl Soft Comput 41:94–103

    Article  Google Scholar 

  31. Zou D, Gao L, Li S, Wu J (2011) Solving 0–1 knapsack problem by a novel global harmony search algorithm. Appl Soft Comput 11(2):1556–1564

    Article  Google Scholar 

  32. Zou D, Gao L, Wu J, Li S, Li Y (2010) A novel global harmony search algorithm for reliability problems. Comput Ind Eng 58(2):307–316

    Article  Google Scholar 

  33. Kong X, Gao L, OuYang H, Li S (2015) A simplified binary harmony search algorithm for large scale 0–1 knapsack problems. Expert Syst Appl 42(12):5337–5355

    Article  Google Scholar 

  34. Yang XS (2012) Flower pollination algorithm for global optimization. In: International conference on unconventional computing and natural computation. Springer, Berlin, pp 240–249

    Chapter  Google Scholar 

  35. Yang XS, Karamanoglu M, He X (2014) Flower pollination algorithm: a novel approach for multiobjective optimization. Eng Optim 46(9):1222–1237

    Article  MathSciNet  Google Scholar 

  36. Rodrigues D, Yang XS, De Souza AN, Papa JP (2015) Binary flower pollination algorithm and its application to feature selection. In: Recent advances in swarm intelligence and evolutionary computation. Springer, Berlin, pp 85–100

    Google Scholar 

  37. Mantegna RN (1994) Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes. Phys Rev E 49(5):4677

    Article  Google Scholar 

  38. Kulkarni AJ, Krishnasamy G, Abraham A (2017) Solution to 0–1 knapsack problem using cohort intelligence algorithm. In: Cohort intelligence: a socio-inspired optimization method. Springer, Berlin, pp 55–74

    Google Scholar 

  39. Sonuc E, Sen B, Bayir S (2016) A parallel approach for solving 0/1 knapsack problem using simulated annealing algorithm on CUDA platform. Int J Comput Sci Inf Secur 14(12):1096

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Operations Research, Faculty of Computers and Informatics, Zagazig University, Zagazig, Egypt

    Mohamed Abdel-Basset

  2. Computer Science Department, Faculty of Computers and Informatics, Zagazig University, El-Zera Square, Zagazig, Sharqiyah, Egypt

    Doaa El-Shahat & Ibrahim El-Henawy

Authors
  1. Mohamed Abdel-Basset
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Doaa El-Shahat
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ibrahim El-Henawy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohamed Abdel-Basset.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this paper.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abdel-Basset, M., El-Shahat, D. & El-Henawy, I. Solving 0–1 knapsack problem by binary flower pollination algorithm. Neural Comput & Applic 31, 5477–5495 (2019). https://doi.org/10.1007/s00521-018-3375-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-018-3375-7

Keywords

Search

Navigation