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

Advertisement

Springer Nature Link
Log in

A hybrid grey wolf optimizer for solving the product knapsack problem

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

The product knapsack problem (PKP) is a new variation of the knapsack problem which arises in social choice computation. Although some deterministic algorithms have been reported to handle small-scale problems, the solution to the middle and large-scale problems is still lack of progress. For efficiently solving this problem, a new ideal of solving PKP by evolutionary algorithms is proposed in the paper. Firstly, an accelerated binary grey wolf optimizer (ABGWO) is proposed by modifying the transfer function, in which the original sigmoid function is replaced by a step function to reduce the computation and accelerate convergence. Secondly, a two-phase repair and optimize algorithm based on greedy strategy is proposed, which is used to handle the infeasible solutions when using evolutionary algorithm to solve PKP. In order to validate the performance of ABGWO, we use it to solve four kinds of PKP instances and compare with the performance of genetic algorithms, discrete particle swarm optimization, discrete differential evolution, and two existed binary grey wolf optimizers. Comparison results show that ABGWO is superior to others in terms of solution quality, robustness and convergence speed, and it is most suitable for solving PKP.

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

Similar content being viewed by others

Explore related subjects

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

References

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

    Book  Google Scholar 

  2. Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York

    MATH  Google Scholar 

  3. Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4(1):63–86

    MATH  Google Scholar 

  4. Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Springer, Berlin, Heidelberg, pp 132–149. https://doi.org/10.1007/BFb0120892

  5. Pisinger D (1995) A minimal algorithm for the bounded knapsack problem. Integer programming and combinatorial optimization. Springer, Berlin, Heidelberg

    MATH  Google Scholar 

  6. Guldan B (2007) Heuristic and exact algorithms for discounted knapsack problems. Master thesis, University of Erlangen-Nrnberg, Germany

  7. Goldschmidt O, Nehme D, Gang Y (2015) Note: on the set-union knapsack problem. Naval Res Logist 41(6):833–842

    MATH  Google Scholar 

  8. D’Ambrosio C, Furini F, Monaci M, Traversi E (2018) On the product knapsack problem. Optim Lett 2:1–22

    MathSciNet  MATH  Google Scholar 

  9. Pferschy U, Schauer J, Thielen C (2019) The product Knapsack problem: approximation and complexity. arXiv:1901.00695

  10. Martello S, Pisinger D, Toth P (2011) Dynamic programming and strong bounds for the 0–1 knapsack problem. Manage Sci 45(3):414–424

    MATH  Google Scholar 

  11. Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge

    MATH  Google Scholar 

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

    Google Scholar 

  13. Ashlock D (2006) Evolutionary computation for modeling and optimization. Springer, New York. https://doi.org/10.1007/0-387-31909-3

  14. Goldberg DE (1989) Genetic algorithm in search, optimization, and machine learning. Addison Wesley xiii 7:2104–2116

    Google Scholar 

  15. Kennedy J (2011) Particle swarm optimization. In: Proc. of 1995 IEEE Int. Conf. Neural Networks (Perth, Australia), Nov. 27-Dec., vol 4, no 8, pp 1942–1948

  16. Chu X, Niu B, Liang JJ, Lu Q (2016) An orthogonal-design hybrid particle swarm optimiser with application to capacitated facility location problem. Int J Bio Inspir Comput 8(5):268–285

    Google Scholar 

  17. Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359

    MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  19. Das S, Mullick SS, Suganthan PN (2016) Recent advances in differential evolution—an updated survey. Swarm Evol Comput 27:1–30

    Google Scholar 

  20. Dorigo M, Birattari M, Stützle T (2006) Ant colony optimization. IEEE Comput Intell Mag 1(4):28–39

    Google Scholar 

  21. Nie Q, Cai T, Wang N (2016) Application of improved ant colony algorithm in resource allocation of cloud computing. Comput Eng Design 37(8):2016–2020

    Google Scholar 

  22. Zhang Q, Zhou A, Jin Y (2008) Rm-meda: a regularity model-based multi-objective estimation of distribution algorithm. IEEE Trans Evol Comput 12(1):41–63

    Google Scholar 

  23. Wang J, Tang K, Lozano JA, Yao X (2016) Estimation of the distribution algorithm with a stochastic local search for uncertain capacitated arc routing problems. IEEE Trans Evol Comput 20(1):96–109

    Google Scholar 

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

  25. Ozturk C, Hancer E, Karaboga D (2015) A novel binary artificial bee colony algorithm based on genetic operators. Inf Sci 297:154–170

    MathSciNet  Google Scholar 

  26. Hakli H, Kiran MS (2020) An improved artificial bee colony algorithm for balancing local and global search behaviors in continuous optimization. Int J Mach Learn Cyber. https://doi.org/10.1007/s13042-020-01094-7

    Article  Google Scholar 

  27. Gottlieb J, Marchiori E, Rossi C (2014) Evolutionary algorithms for the satisfiability problem. Evol Comput 10(1):35–50

    Google Scholar 

  28. Beasley JE, Chu PC (1996) A genetic algorithm for the set covering problem. J Oper Res Soc 94(2):392–404

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  30. Al-Madi N, Faris H, Mirjalili S (2019) Binary multi-verse optimization algorithm for global optimization and discrete problems. Int J Mach Learn Cybern 10:3445–3465

    Google Scholar 

  31. Korkmaz S, Babalik A, Kiran MS (2018) An artificial algae algorithm for solving binary optimization problems. Int J Mach Learn Cybern 9:1233–1247

    Google Scholar 

  32. Wang L, Wang SY, Xu Y (2012) An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem. Expert Syst Appl 39(5):5593–5599

    MathSciNet  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  34. Meng T, Pan QK (2017) An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem. Appl Soft Comput 715(50):79–93

    Google Scholar 

  35. García J, Lalla-Ruiz E, Voß S, Droguett EL (2020) Enhancing a machine learning binarization framework by perturbation operators: analysis on the multidimensional knapsack problem. Int J Mach Learn Cybern. https://doi.org/10.1007/s13042-020-01085-8

    Article  Google Scholar 

  36. He YC, Wang XZ, He YL, Zhao SL, Li WB (2016) Exact and approximate algorithms for discounted 0–1 knapsack problem. Inf Sci 369:634–647

    MathSciNet  MATH  Google Scholar 

  37. He YC, Wang JH, Zhang XL, Li HZ, Liu XJ (2019) Encoding transformation-based differential evolution algorithm for solving knapsack problem with single continuous variable. Swarm Evol Comput. https://doi.org/10.1016/j.swevo.2019.03.002

    Article  Google Scholar 

  38. Yang XS (2009) Firefly algorithms for multimodal optimization. Stochastic algorithms: foundations and applications. Springer, Berlin, Heidelberg, pp 169–178

    MATH  Google Scholar 

  39. Mirjalili S (2016) SCA: a sine cosine algorithm for solving optimization problems. Knowl Based Syst 96:120–133

    Google Scholar 

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

    Google Scholar 

  41. Mirjalili S, Lewis A (2016) The Whale optimization algorithm. Adv Eng Softw 95:51–67

    Google Scholar 

  42. Tan Y, Zhu YC (2010) Fireworks algorithm for optimization. Advances in Swarm intelligence, first international conference, ICSI, Beijing, China, June, Part I. Springer, New York, pp 355–364

  43. Duan HB, Qiu HX, Fan YM (2015) Unmanned aerial vehicle close formation cooperative control based on predatory escaping pigeon-inspired optimization. Sci Sinica 45(6):559–572

    Google Scholar 

  44. Duan HB, Yang ZY (2018) Large civil aircraft receding horizon control based on cauthy mutation pigeon inspired optimization. Sci Sinica 48(3):277–288

    MathSciNet  Google Scholar 

  45. Arqub OA, Abo-Hammour Z (2014) Numerical solution of systems of second-order boundary value problems using continuous genetic algorithm. Inf Sci 279:396–415

    MathSciNet  MATH  Google Scholar 

  46. Yildiz AR, Abderezak H, Mirjalili S (2019) A comparative study of recent non-traditional methods for mechanical design optimization. Arch Comput Methods Eng. https://doi.org/10.1007/s11831-019-09343-x

    Article  Google Scholar 

  47. Kiani M, Yildiz AR (2015) A comparative study of non-traditional methods for vehicle crashworthiness and NVH optimization. Arch Comput Methods Eng 23(4):723–734. https://doi.org/10.1007/s11831-015-9155-y

    Article  MathSciNet  MATH  Google Scholar 

  48. Yildiz AR, Yıldız BS (2019) The Harris hawks optimization algorithm, SALP swarm algorithm, grasshopper optimization algorithm and dragonfly algorithm for structural design optimization of vehicle components. Mater Testing 8(61):60–70

    Google Scholar 

  49. Mohamed Imran A, Kowsalya M (2014) A new power system reconfiguration scheme for power loss minimization and voltage problem enhancement using fireworks algorithm. Int J Electr Power Energy Syst 62:312–322

    Google Scholar 

  50. Aljarah I, Faris H, Mirjalili S (2016) Optimizing connection weights in neural networks using the whale optimization algorithm. Soft Comput 22(1):1–15

    Google Scholar 

  51. Kaveh A (2017) Sizing optimization of skeletal structures using the enhanced whale optimization algorithm. Applications of Metaheuristic optimization algorithms in civil engineering. Springer, Cham

    Google Scholar 

  52. Al-Zoubi A, Faris H, Alqatawna J, Hassonah MA (2018) Evolving support vector machines using whale optimization algorithm for spam profiles detection on online social networks in different lingual contexts. Knowl Based Syst 153(8):91–104

    Google Scholar 

  53. Horng MH (2012) Vector quantization using the firefly algorithm for image compression. Expert Syst Appl 39(1):1078–1091

    Google Scholar 

  54. Yildiz AR (2019) A novel hybrid whale–Nelder–Mead algorithm for optimization of design and manufacturing problems. Int J Adv Manuf Technol. https://doi.org/10.1007/s00170-019-04532-1

    Article  Google Scholar 

  55. Tawhid MA, Ibrahim AM (2020) Feature selection based on rough set approach, wrapper approach, and binary whale optimization algorithm. Int J Mach Learn Cybern 11:573–602

    Google Scholar 

  56. Emary E, Zawbaa HM, Hassanien AE (2016) Binary gray wolf optimization approaches for feature selection. Neurocomputing 172(C):371–381

    Google Scholar 

  57. Mirjalili S (2015) How effective is the grey wolf optimizer in training multi-layer perceptrons. Appl Intell 43(1):150–161

    Google Scholar 

  58. Jayabarathi T, Raghunathan T, Adarsh B, Suganthan PN (2016) Economic dispatch using hybrid grey wolf optimizer. Energy 111:630–641

    Google Scholar 

  59. Panwar LK, Reddy S, Verma A, Panigrahi B, Kumar R (2018) Binary grey wolf optimizer for large scale unit commitment problem. Swarm Evol Comput 38(2):251–266

    Google Scholar 

  60. Hatta NM, Zain AM, Sallehuddin R (2018) Recent studies on optimisation method of Grey Wolf Optimiser (GWO): a review (2014–2017). Artif Intell Rev. https://doi.org/10.1007/s10462-018-9634-2

    Article  Google Scholar 

  61. Deshmukh AB, Usha RN (2017) Fractional-Grey wolf optimizer-based kernel weighted regression model for multi-view face video super resolution. Int J Mach Learn Cybern. https://doi.org/10.1007/s13042-017-0765-6

    Article  Google Scholar 

  62. Faris H, Mirjalili S, Aljarah I (2019) Automatic selection of hidden neurons and weights in neural networks using grey wolf optimizer based on a hybrid encoding scheme. Int J Mach Learn Cybern. https://doi.org/10.1007/s13042-018-00913-2

    Article  Google Scholar 

  63. Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: 1997 IEEE International Conference on Systems, Man, and Cybernetics, Orlando, FL, USA. IEEE Proc vol 5, pp 4104–4108. https://doi.org/10.1109/ICSMC.1997.637339

  64. He YC, Wang XZ, Kou YZ (2007) A binary differential evolution algorithm with hybrid encoding. J Comput Res Dev 44(9):1476–1484

    Google Scholar 

  65. Runarsson T, Xin Y (2000) Stochastic ranking for constrained evolutionary optimization. IEEE Trans Evol Comput 4(3):284–294

    Google Scholar 

  66. Coello CAC (2002) Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Comput Methods Appl Mech Eng 191(11):1245–1287

    MathSciNet  MATH  Google Scholar 

  67. He YC, Zhang XL, Li WB, Li X, Wu WL, Gao SG (2016) Algorithms for randomized time-varying knapsack problems. J Comb Optim 31(1):95–117

    MathSciNet  MATH  Google Scholar 

  68. He YC, Xie HR, Wong TL, Wang XZ (2018) A novel binary artificial bee colony algorithm for the set-union knapsack problem. Fut Gener Comput Syst 78:77–86. https://doi.org/10.1016/j.future.2017.05.044

    Article  Google Scholar 

  69. Eiben AE, Rau PE, Ruttkay Z (1994) Genetic algorithms with multi-parent recombination. Proc Parallel Probl Solving Nat 866:78–87

    Google Scholar 

  70. Chen WN, Zhang J, Chung H, Zhong WL, Wu WG, Shi YH (2010) A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Trans Evol Comput 14(2):278–300

    Google Scholar 

  71. Langeveld J, Engelbrecht AP (2012) Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intell 6(4):297–342

    Google Scholar 

  72. Chih M, Lin CJ, Chern MS, Ou TY (2014) Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Appl Math Model 33(2):77–102

    MathSciNet  MATH  Google Scholar 

  73. Liu XJ, He YC, Lu FJ, Wu CC, Cai XF (2018) Chaotic crow search algorithm based on differential evolution strategy for solving discount 0–1 knapsack problem. J Comput Appl 38(1):137. https://doi.org/10.11772/j.issn.1001-9081.2017061445

    Article  Google Scholar 

  74. Guo Z, Yue X, Zhang K, Wang S, Wu Z (2014) A thermodynamical selection based discrete differential evolution for the 0–1 knapsack problem. Entropy 16(12):6263–6285

    Google Scholar 

  75. Kruskal WH, Allen Wallis W (1952) Use of ranks in one-criterion variance analysis. Publ Am Stat Assoc 47(260):583–621

    MATH  Google Scholar 

  76. He YC, Wang XZ (2018) Group theory-based optimization algorithm for solving knapsack problems. Knowl Based Syst. https://doi.org/10.1016/j.knosys.2018.07.045

    Article  Google Scholar 

Download references

Acknowledgements

We thank Editor-in-Chief and anonymous reviewers whose valuable comments and suggestions help us significantly improve this article. The first author and corresponding authors contributed equally the same to this article which was supported by the Scientific Research Project of Colleges and Universities in Hebei Province (ZD2016005, ZD2018043), and the Natural Science Foundation of Hebei Province (F2016403055, F2020403013).

Author information

Authors and Affiliations

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

    Zewen Li, Yichao He, Ya Li & Xiaohu Guo

Authors
  1. Zewen Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yichao He
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ya Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiaohu Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yichao He.

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

Li, Z., He, Y., Li, Y. et al. A hybrid grey wolf optimizer for solving the product knapsack problem. Int. J. Mach. Learn. & Cyber. 12, 201–222 (2021). https://doi.org/10.1007/s13042-020-01165-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-020-01165-9

Keywords

Search

Navigation