Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Neural Computing and Applications
Published in: Neural Computing and Applications 9/2019

28-02-2018 | Original Article

Solving 0–1 knapsack problem by binary flower pollination algorithm

Authors: Mohamed Abdel-Basset, Doaa El-Shahat, Ibrahim El-Henawy

Published in: Neural Computing and Applications | Issue 9/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Adaptive graph orthogonal discriminant embedding: an improved graph embedding method
next article Hybrid SCA–TLBO: a novel optimization algorithm for global optimization and visual tracking

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Hu TC, Kahng AB (2016) The knapsack problem. In: Linear and integer programming made easy. Springer, Berlin, pp 87–101CrossRef
2.
Weingartner HM (1966) Capital budgeting of interrelated projects: survey and synthesis. Manag Sci 12(7):485–516CrossRef
3.
Mansini R, Speranza MG (1999) Heuristic algorithms for the portfolio selection problem with minimum transaction lots. Eur J Oper Res 114(2):219–233CrossRef
4.
5.
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–266MathSciNetCrossRef
7.
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–332MathSciNetCrossRef
9.
Plateau G, Nagih A (2010) 0–1 knapsack problems. In: Paradigms of combinatorial optimization, 2nd edn, pp 215–242
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–71CrossRef
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–250CrossRef
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
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–11061MathSciNetMATH
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–418CrossRef
19.
Yang X-S (2009) Firefly algorithms for multimodal optimization. In: International symposium on stochastic algorithms. Springer, BerlinCrossRef
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–2799CrossRef
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
23.
24.
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–1634CrossRef
26.
Zhao RQ, Tang WS (2008) Monkey algorithm for global numerical optimization. J Uncertain Syst 2(3):165–176
27.
Zhou Y, Chen X, Zhou G (2016) An improved monkey algorithm for a 0–1 knapsack problem. Appl Soft Comput 38:817–830CrossRef
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–430CrossRef
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–702CrossRef
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–103CrossRef
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–1564CrossRef
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–316CrossRef
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–5355CrossRef
34.
Yang XS (2012) Flower pollination algorithm for global optimization. In: International conference on unconventional computing and natural computation. Springer, Berlin, pp 240–249CrossRef
35.
Yang XS, Karamanoglu M, He X (2014) Flower pollination algorithm: a novel approach for multiobjective optimization. Eng Optim 46(9):1222–1237MathSciNetCrossRef
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
37.
Mantegna RN (1994) Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes. Phys Rev E 49(5):4677CrossRef
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
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
Metadata
Title
Solving 0–1 knapsack problem by binary flower pollination algorithm
Authors
Mohamed Abdel-Basset
Doaa El-Shahat
Ibrahim El-Henawy
Publication date
28-02-2018
Publisher
Springer London
Published in
Neural Computing and Applications / Issue 9/2019
Print ISSN: 0941-0643
Electronic ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-018-3375-7

Other articles of this Issue 9/2019

Neural Computing and Applications 9/2019 Go to the issue

Emergence in Human-like Intelligence towards Cyber-Physical Systems

Iterative learning control for linear generalized distributed parameter system

Original Article

A solid transportation problem in uncertain environment involving type-2 fuzzy variable

Original Article

Pilot tones design using particle swarm optimization for OFDM–IDMA system

S.I. : Emergence in Human-like Intelligence towards Cyber-Physical Systems

Spark-based intelligent parameter inversion method for prestack seismic data

Original Article

Sustainable closed-loop supply chain network design with discount supposition

Original Article

Adaptive sampling for UAV tracking

Premium Partner

    Image Credits