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

An efficient binary differential evolution algorithm for the multidimensional knapsack problem

  • Original Article
  • Published:
Engineering with Computers Aims and scope Submit manuscript

Abstract

This paper proposes a novel approach for the multidimensional knapsack problem (MDKP) using differential evolution. Firstly, the principle and the pseudo-code of binary differential evolution with hybrid encoding (HBDE) are presented. On the basis of the existing repair operator 2 (RO2), an improved repair operator 3 (RO3) for handling the infeasible solutions of MDKP is developed. Then, combine HBDE with RO3, an efficient algorithm (HBDE-RO3) for MDKP is proposed. Finally, the experiment results of the 138 well-known MDKP benchmarks show that RO3 is advantageous to deal with the infeasible solutions than RO2, and the proposed algorithm HBDE-RO3 has superior performance for solving MDKP than the state-of-the-art 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

Similar content being viewed by others

References

  1. Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin

    Book  Google Scholar 

  2. Fréville A (2004) The multidimensional 0–1 knapsack problem: an overview. Eur J Oper Res 155:1–21

    Article  MathSciNet  Google Scholar 

  3. Meier H, Christofides N, Salkin G (2001) Capital budgeting under uncertainty—an integrated approach using contingent claims analysis and integer programming. Oper Res 49:196–206

    Article  Google Scholar 

  4. Shih W (1979) A branch and bound method for the multiconstraint zero-one knapsack problems. J Oper Res Soc 30:369–378

    Article  Google Scholar 

  5. Beaujon G, Martin S, McDonald C (2001) Balancing and optimizing a portfolio of r&d projects. Naval Res Log 48:18–40

    Article  MathSciNet  Google Scholar 

  6. Wu C, Wang X, Lin J (2014) Optimizations in project scheduling: a state-of-art survey. In: Xu H, Wang X (eds) Optimization and control methods in industrial engineering and construction. Springer, Dordrecht, pp 161–177

    Chapter  Google Scholar 

  7. Balev S, Yanev N, Fréville A, Andonov R (2008) A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem. Eur J Oper Res 186:63–76

    Article  MathSciNet  Google Scholar 

  8. Puchinger J, Raidl G, Pferschy U (2010) The multidimensional knapsack problem: structure and algorithms. INFORMS J Comput 22:250–265

    Article  MathSciNet  Google Scholar 

  9. Li Vincent C, Liang Yun-Chia, Chang Huan-Fu (2012) Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method. Comput Oper Res 39:2111–2121

    Article  MathSciNet  Google Scholar 

  10. Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge

    Book  Google Scholar 

  11. Ding-zhu Du, Ko Ker-I, Xiaodong Hu (2012) Design and analysis of approximation algorithms. Springer, Berlin

    MATH  Google Scholar 

  12. Chu P, Beasley J (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4:63–86

    Article  Google Scholar 

  13. Xue-Cai YU, ZHANG Tian-Wen (2008) An improved ant algorithm for multidimensional knapsack problem. Chin J Comput 31:810–819

    MathSciNet  Google Scholar 

  14. Ling W, Sheng-yao W, Chen F (2011) A hybrid distribution estimation algorithm for solving multidimensional knapsack problem. Control Decis 26:1121–1125

    MATH  Google Scholar 

  15. Chih M, Lin CJ, Chern MS, Ouc TY (2014) Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Appl Math Model 38:1338–1350

    Article  MathSciNet  Google Scholar 

  16. Chih M (2015) Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem. Appl Soft Comput 26:378–389

    Article  Google Scholar 

  17. Wang L, long Zheng X, yao Wang S (2013) A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowl Based Syst 48:17–23

    Article  Google Scholar 

  18. Mak A, Amac R, Emgp F (2014) Improved binary artificial fish swarm algorithm for the 0–1 multidimensional knapsack problems. Swarm Evol Comput 14:66–75

    Article  Google Scholar 

  19. Liu J, Wu C, Cao J, Wang X, Teo KL (2016) A binary differential search algorithm for the 0–1 multidimensional knapsack problem. Appl Math Model 40(23–24):9788–9805

    Article  MathSciNet  Google Scholar 

  20. Zhang X, Wu C, Li J, Wang X, Yang Z, Lee J-M, Jung K-H (2016) Binary artificial algae algorithm for multidimensional knapsack problems. Appl Soft Comput 43:583–595

    Article  Google Scholar 

  21. Chih M (2018) Three pseudo-utility ratio-inspired particle swarm optimization with local search for multidimensional knapsack problem. Swarm Evol Comput 39:279–296

    Article  Google Scholar 

  22. Storn R, Price K (1997) Differential evolutiona simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359

    Article  Google Scholar 

  23. He Y, Wang X, Kou Y (2007) A binary differential evolution algorithm with hybrid encoding. J Comput Res Dev 44:1476–1484

    Article  Google Scholar 

  24. Zhu H, He Y, Wang X, Tsang E (2017) Discrete differential evolution for the discounted 0–1 knapsack problem. Int J Bio-inspired Comput 10:219–238

    Article  Google Scholar 

  25. Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13:398–417

    Article  Google Scholar 

  26. Das S, Abraham A, Chakraborty UK, Konar A (2009) Differential evolution using a neighborhood-basedmutation operator. IEEE Trans Evol Comput 13:526–553

    Article  Google Scholar 

  27. Wang Y, Cai Z, Zhang Q (2011) Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans Evol Comput 15:55–66

    Article  Google Scholar 

  28. Yu Y, Yao X, Zhou Z (2012) On the approximation ability of evolutionary optimization with application to minimum set cover. Artif Intell 180–181:20–33

    Article  MathSciNet  Google Scholar 

  29. Gottlieb J, Marchiori E, Rossi C (2002) Evolutionary algorithms for the satisifiability problem. Evol Comput 10:35–50

    Article  Google Scholar 

  30. Runarsson TP, Yao X (2000) Stochastic ranking for constrained evolutionary optimization. IEEE Trans Evol Comput 4:284–294

    Article  Google Scholar 

  31. Coello CA (2002) Theoretial and numerical constraint-handling techniques used with evolutionary algorithm—a survey of the state of art. Comput Methods Appl Mech Eng 191:1245–1287

    Article  Google Scholar 

  32. Michalewicz Z, Schoenauer M (1996) Evolutionary algorithms for pararmeter optimization problems. Evol Comput 4:1–32

    Article  Google Scholar 

  33. Beasley JE (2017) Orlib-operations research library. http://people.brunel.ac.uk/mastjjb/jeb/ orlib/mknapinfo.html

  34. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39:459–471

    Article  MathSciNet  Google Scholar 

  35. Tan Y, Zhu Y (2010) Fireworks algorithm for optimization. In: International conference in swarm intelligence, pp 355–364

  36. Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61

    Article  Google Scholar 

  37. Haibin D, Fei Y (2017) Progresses in pigeon-inspired optimization algorithms. J Beijing Univ Technol (Nat Sci Ed) 43:1–7

    MathSciNet  MATH  Google Scholar 

  38. He Y, Wang X, Zhao S, Zhang X (2018) The design and applications of discrete evolutionary algorithms based on encoding transformation. J Softw 9:2580–2594

    MATH  Google Scholar 

Download references

Acknowledgements

This article was supported by National Natural Science Foundations of China (11471097), Scientific Research Project Program of Colleges and Universities in Hebei Province (ZD2016005), and Natural Science Foundation of Hebei Province (F2016403055),and Scientific and Technological Research Projects of Colleges and Universities in Hebei Province (QN2019075).

Author information

Authors and Affiliations

  1. College of Information and Engineering, Hebei GEO University, Shijiazhuang, 050031, China

    Yichao He, Wenbin Li & Ning Li

  2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang, 050024, China

    Xinlu Zhang & Jinghong Wang

Authors
  1. Yichao He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xinlu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenbin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jinghong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ning Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Yichao He or Wenbin Li.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

He, Y., Zhang, X., Li, W. et al. An efficient binary differential evolution algorithm for the multidimensional knapsack problem. Engineering with Computers 37, 745–761 (2021). https://doi.org/10.1007/s00366-019-00853-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00366-019-00853-7

Keywords

Search

Navigation