×

Novel binary differential evolution algorithm for knapsack problems. (English) Zbl 1475.90077

Summary: The capability of the conventional differential evolution algorithm to solve optimization problems in continuous spaces has been well demonstrated and documented in the literature. However, differential evolution has been commonly considered inapplicable for several binary/permutation-based real-world problems because of its arithmetic reproduction operator. Moreover, many limitations of the standard differential evolution algorithm, such as slow convergence and becoming trapped in local optima, have been defined. In this paper, a novel technique which makes a simple differential evolution algorithm suitable and very effective for solving binary-based problems, such as binary knapsack ones, is proposed. It incorporates new components, such as representations of solutions, a mapping method and a diversity technique. Also, a new efficient fitness evaluation approach for calculating and, at the same time, repairing knapsack candidate solutions, is introduced. To assess the performance of this new algorithm, four datasets with a total of 44 instances of binary knapsack problems are considered. Its performance and those of 22 state-of-the-art algorithms are compared, with the experimental results demonstrating its superiority in terms of both the quality of solutions and computational times. It is also capable of finding new solutions which are better than the current best ones for five large knapsack problems.

MSC:

90C27 Combinatorial optimization
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Storn, R.; Price, K., Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11, 341-359 (1997) · Zbl 0888.90135
[2] Zhou, Y.; Zhao, Z.; Cheng, D., Cluster structure prediction via revised particle-swarm optimization algorithm, Comput. Phys. Commun., 247, Article 106945 pp. (2020)
[3] S. Panda, “Joint User Patterning and Power Control Optimization of MIMO-NOMA Systems,” Wireless Personal Communications, pp. 1-17, 2020.
[4] Dragoi, E. N.; Curteanu, S., The use of differential evolution algorithm for solving chemical engineering problems, Rev. Chem. Eng., 32, 149-180 (2016)
[5] Buba, A. T.; Lee, L. S., A differential evolution for simultaneous transit network design and frequency setting problem, Expert Syst. Appl., 106, 277-289 (2018)
[6] V. Plagianakos, D. Tasoulis, and M. Vrahatis, “A review of major application areas of differential evolution,” in Advances in differential evolution, ed: Springer, 2008, pp. 197-238.
[7] Du, D.-Z.; Ko, K.-I.; Hu, X., Design and analysis of approximation algorithms, vol. 62 (2011), Springer Science & Business Media
[8] Mavrotas, G.; Diakoulaki, D.; Kourentzis, A., Selection among ranked projects under segmentation, policy and logical constraints, Eur. J. Oper. Res., 187, 177-192 (2008) · Zbl 1133.90353
[9] Peeta, S.; Salman, F. S.; Gunnec, D.; Viswanath, K., Pre-disaster investment decisions for strengthening a highway network, Comput. Oper. Res., 37, 1708-1719 (2010) · Zbl 1188.90052
[10] Yaseen, Z. M.; Sulaiman, S. O.; Deo, R. C.; Chau, K.-W., An enhanced extreme learning machine model for river flow forecasting: State-of-the-art, practical applications in water resource engineering area and future research direction, J. Hydrol., 569, 387-408 (2019)
[11] Vanderster, D. C.; Dimopoulos, N. J.; Parra-Hernandez, R.; Sobie, R. J., Resource allocation on computational grids using a utility model and the knapsack problem, Future Gen. Computer Systems, 25, 35-50 (2009)
[12] Senju, S.; Toyoda, Y., An approach to linear programming with 0-1 variables, Manage. Sci., B196-B207 (1968)
[13] Shih, W., A branch and bound method for the multiconstraint zero-one knapsack problem, J. Operat. Res. Soc., 369-378 (1979) · Zbl 0411.90050
[14] Toth, P., Dynamic programming algorithms for the zero-one knapsack problem, Computing, 25, 29-45 (1980) · Zbl 0431.90076
[15] Zenarosa, G. L.; Prokopyev, O. A.; Pasiliao, E. L., On exact solution approaches for bilevel quadratic 0-1 knapsack problem, Ann. Oper. Res. (2018)
[16] Soukaina, L.; Mohamed, N.; Hassan, E. A.; Boujemâa, A., A hybrid genetic algorithm for solving 0/1 Knapsack Problem, (Proceedings of the International Conference on Learning and Optimization Algorithms: Theory and Applications (2018)), 51
[17] Ali, I. M.; Essam, D.; Kasmarik, K., An efficient differential evolution algorithm for solving 0-1 Knapsack Problems, IEEE Cong. Evolution. Comput. (CEC), 2018, 1-8 (2018)
[18] Lin, C.-J.; Chern, M.-S.; Chih, M., A binary particle swarm optimization based on the surrogate information with proportional acceleration coefficients for the 0-1 multidimensional knapsack problem, J. Indust. Product. Eng., 33, 77-102 (2016)
[19] Feng, Y.; Wang, G.-G.; Wang, L., Solving randomized time-varying knapsack problems by a novel global firefly algorithm, Eng. Computers, 34, 621-635 (2018)
[20] Feng, Y.; Wang, G.-G.; Gao, X.-Z., A novel hybrid cuckoo search algorithm with global harmony search for 0-1 knapsack problems, Int. J. Comput. Intell. Systems, 9, 1174-1190 (2016)
[21] Zouari, W.; Alaya, I.; Tagina, M., A hybrid ant colony algorithm with a local search for the strongly correlated knapsack problem, (Proceeding Computer Systems and Applications (AICCSA), 2017 IEEE/ACS 14th International Conference on (2017)), 527-533
[22] El-Shafei, M.; Ahmad, I.; Alfailakawi, M. G., Hardware accelerator for solving 0-1 knapsack problems using binary harmony search, Int. J. Parallel Emergent Distrib. Syst., 33, 87-102 (2018)
[23] Feng, Y.; Yang, J.; Wu, C.; Lu, M.; Zhao, X.-J., Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with Gaussian mutation, Memetic Comput., 10, 135-150 (2018)
[24] Feng, Y.; An, H.; Gao, X., The importance of transfer function in solving set-union knapsack problem based on discrete moth search algorithm, Mathematics, 7, 17 (2019)
[25] Ali, I. M.; Essam, D.; Kasmarik, K., A novel design of differential evolution for solving discrete traveling salesman problems, Swarm Evol. Comput., 52, Article 100607 pp. (2020)
[26] Myszkowski, P. B.; Olech, Ł. P.; Laszczyk, M.; Skowroński, M. E., Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained project scheduling problem, Appl. Soft Comput., 62, 1-14 (2018)
[27] Zhou, B.-H.; Hu, L.-M.; Zhong, Z.-Y., A hybrid differential evolution algorithm with estimation of distribution algorithm for reentrant hybrid flow shop scheduling problem, Neural Comput. Appl., 30, 193-209 (2018)
[28] Ali, I. M.; Elsayed, S. M.; Ray, T.; Sarker, R. A., Memetic algorithm for solving resource constrained project scheduling problems, Proceeding IEEE Congress on Evolutionary Computation (CEC), 2015, 2761-2767 (2015)
[29] Rahman, H. F.; Chakrabortty, R. K.; Ryan, M. J., Memetic algorithm for solving resource constrained project scheduling problems, Autom. Constr., 111, Article 103052 pp. (2020)
[30] Caraffini, F.; Kononova, A. V.; Corne, D., Infeasibility and structural bias in differential evolution, Information Sci., 496, 161-179 (2019) · Zbl 1451.68362
[31] Yaman, A.; Iacca, G.; Caraffini, F., “A comparison of three differential evolution strategies in terms of early convergence with different population sizes”, in proceeding, AIP Conf. Proc., Article 020002 pp. (2019)
[32] Qing, A., Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems, IEEE Trans. Geosci. Remote Sens., 44, 116-125 (2005)
[33] Ali, I. M.; Essam, D.; Kasmarik, K., A novel differential evolution mapping technique for generic combinatorial optimization problems, Appl. Soft Comput., 80, 297-309 (2019)
[34] Liang, J.; Xu, W.; Yue, C.; Yu, K.; Song, H.; Crisalle, O. D.; Qu, B., Multimodal multiobjective optimization with differential evolution, Swarm Evol. Comput., 44, 1028-1059 (2019)
[35] Mohamed, A. W., A new modified binary differential evolution algorithm and its applications, Appl. Math. Inform. Sci., 10, 1965-1969 (2016)
[36] Bhattacharjee, K. K.; Sarmah, S. P., Shuffled frog leaping algorithm and its application to 0/1 knapsack problem, Appl. Soft Comput., 19, 252-263 (2014)
[37] N. Abd-Alsabour, Investigating the influence of adding local search to search algorithms, in: Proceeding Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2017 18th International Conference on, 2017, pp. 145-150.
[38] Wikipedia. (2019, Broyden-Fletcher-Goldfarb-Shanno algorithm - Wikipedia. Available: https://en.wikipedia.org/wiki/Broyden
[39] Zhang, L.; Zhang, B., Good point set based genetic algorithm, Chin. J. Computers, 24, 917-922 (2001)
[40] He, Y.; Liu, K.; Zhang, C.; Zhang, W., Greedy genetic algorithm for solving knapsack problems and its applications, Computer Eng. Design, 28, 2655-2657 (2007)
[41] S. Jun and L. Jian, “Solving 0-1 knapsack problems via a hybrid differential evolution,” in proceeding Intelligent Information Technology Application, 2009. IITA 2009. Third International Symposium on, 2009, pp. 134-137.
[42] Feng, Y.; Wang, G.-G.; Deb, S.; Lu, M.; Zhao, X.-J., Solving 0-1 knapsack problem by a novel binary monarch butterfly optimization, Neural Comput. Appl., 28, 1619-1634 (2017)
[43] Chen, Y.; Xie, W.; Zou, X., A binary differential evolution algorithm learning from explored solutions, Neurocomputing, 149, 1038-1047 (2015)
[44] Gong, T.; Tuson, A. L., Differential evolution for binary encoding, (Soft Computing In Industrial Applications (2007), Springer), 251-262 · Zbl 1278.90377
[45] A. R. Hota and A. Pat, “An adaptive quantum-inspired differential evolution algorithm for 0-1 knapsack problem,” in Proceeding Nature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on, 2010, pp. 703-708.
[46] Peng, H.; Wu, Z.; Shao, P.; Deng, C., Dichotomous binary differential evolution for knapsack problems, Math. Problems Eng., 2016 (2016) · Zbl 1400.90225
[47] J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in proceeding Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on, 1997, pp. 4104-4108.
[48] Bansal, J. C.; Deep, K., A modified binary particle swarm optimization for knapsack problems, Appl. Math. Comput., 218, 11042-11061 (2012) · Zbl 1284.90062
[49] R. Woolson, “Wilcoxon signed‐rank test,” Wiley encyclopedia of clinical trials, pp. 1-3, 2007.
[50] Friedman, M., A comparison of alternative tests of significance for the problem of m rankings, Ann. Math. Stat., 11, 86-92 (1940) · JFM 66.1305.08
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.