Top

Engineering with Computers

Published in:

28-08-2019 | Original Article

An efficient binary differential evolution algorithm for the multidimensional knapsack problem

Authors: Yichao He, Xinlu Zhang, Wenbin Li, Jinghong Wang, Ning Li

Published in: Engineering with Computers | Issue 1/2021

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

search-config

AI-assisted search

Off

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.

previous article A meshless method to solve nonlinear variable-order time fractional 2D reaction–diffusion equation involving Mittag-Leffler kernel

next article Exporting water wave optimization concepts to modified simulated annealing algorithm for size optimization of truss structures with natural frequency constraints

Dont have a licence yet? Then find out more about our products and how to get one 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

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

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

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

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–206CrossRef

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

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

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–177CrossRef

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–76MathSciNetCrossRef

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

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–2121MathSciNetCrossRef

10.

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

11.

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

12.

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

13.

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

14.

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

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–1350MathSciNetCrossRef

16.

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

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–23CrossRef

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–75CrossRef

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–9805MathSciNetCrossRef

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–595CrossRef

21.

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

22.

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

23.

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

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–238CrossRef

25.

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

26.

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

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–66CrossRef

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–33MathSciNetCrossRef

29.

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

30.

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

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–1287CrossRef

32.

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

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–471MathSciNetCrossRef

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–61CrossRef

37.

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

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–2594MATH

Title: An efficient binary differential evolution algorithm for the multidimensional knapsack problem
Authors: Yichao He
Xinlu Zhang
Wenbin Li
Jinghong Wang
Ning Li
Publication date: 28-08-2019
Publisher: Springer London
Published in: Engineering with Computers / Issue 1/2021
Print ISSN: 0177-0667
Electronic ISSN: 1435-5663
DOI: https://doi.org/10.1007/s00366-019-00853-7

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2021

Postbuckling analysis of piezoelectric multiscale sandwich composite doubly curved porous shallow shells via Homotopy Perturbation Method

Solving complex Sylvester matrix equation by accelerated double-step scale splitting (ADSS) method

The numerical solution of nonlinear generalized Benjamin–Bona–Mahony–Burgers and regularized long-wave equations via the meshless method of integrated radial basis functions

Developing GEP tree-based, neuro-swarm, and whale optimization models for evaluation of bearing capacity of concrete-filled steel tube columns

Fine-tuning of neural computing using whale optimization algorithm for predicting compressive strength of concrete

Multi-objective heat transfer search algorithm for truss optimization