Mathematical modeling and improved memetic algorithm for the extended simplified discounted {0-1} knapsack problem with randomness

Zhouxi Qin; Dazhi Pan; Ke Yang; Dapeng Gao; Zhouxi Qin; Dazhi Pan; Ke Yang; Dapeng Gao

doi:10.3934/math.20251034

AIMS Mathematics

2025, Volume 10, Issue 10: 23306-23336. doi: 10.3934/math.20251034

Previous Article Next Article

Research article

Mathematical modeling and improved memetic algorithm for the extended simplified discounted {0-1} knapsack problem with randomness

1.
School of Mathematical Sciences, China West Normal University, Nanchong 637009, China
2.
Sichuan Colleges and Universities Key Laboratory of Optimization Theory and Applications, Nanchong 637009, China

Received: 08 August 2025 Revised: 15 September 2025 Accepted: 30 September 2025 Published: 14 October 2025
MSC : 90C27, 90C59

In this paper, we first extended the extended simplified discount {0-1} backpack problem (ESD {0-1} KP) and proposed the extended simplified discounted {0-1} knapsack problem with randomness (ESD {0-1} KP-R) model. Compared with the ordinary ESD {0-1} KP model, it increases the size and randomness of the term set, which is more suitable for the actual concept of "discount" and has stronger generalization. Then we used the improved memetic algorithm to solve the ESD {0-1} KP-R model. First, a greedy strategy with a relax variable was first designed to obtain the initial solution. Second, designed a crossover strategy with fuzzy sets to generate a good offspring population. Third, in order to overcome the shortcoming of memetic algorithms falling into local optimization, we designed a population diversity adjustment strategy with an information vector. This strategy combines the parent and child populations into a set of candidate solutions, and then divides all the solutions in the set into four categories according to the fitness and diversity of the solutions. Different selection methods can be used to adjust the diversity of the population while ensuring the quality of the solutions selected. In addition, based on the profit density for combinations of terms, three kinds of neighborhood structures were designed. They were used to improve the algorithm's searching ability, explore the neighborhood of local solutions, and jump out of the local optimum, respectively. The local search was performed by the variable neighborhood search algorithm. Finally, the effectiveness of the proposed improvement strategy and the feasibility of the proposed algorithm for solving the ESD {0-1} KP-R were demonstrated through experimental analysis on four types of instances.
- ESD {0-1} KP-R,
- memetic algorithm,
- population diversity adjustment strategy,
- relaxed greedy initialization,
- fuzzy crossover strategy,
- local search
Citation: Zhouxi Qin, Dazhi Pan, Ke Yang, Dapeng Gao. Mathematical modeling and improved memetic algorithm for the extended simplified discounted {0-1} knapsack problem with randomness[J]. AIMS Mathematics, 2025, 10(10): 23306-23336. doi: 10.3934/math.20251034

Related Papers:

Abstract

In this paper, we first extended the extended simplified discount {0-1} backpack problem (ESD {0-1} KP) and proposed the extended simplified discounted {0-1} knapsack problem with randomness (ESD {0-1} KP-R) model. Compared with the ordinary ESD {0-1} KP model, it increases the size and randomness of the term set, which is more suitable for the actual concept of "discount" and has stronger generalization. Then we used the improved memetic algorithm to solve the ESD {0-1} KP-R model. First, a greedy strategy with a relax variable was first designed to obtain the initial solution. Second, designed a crossover strategy with fuzzy sets to generate a good offspring population. Third, in order to overcome the shortcoming of memetic algorithms falling into local optimization, we designed a population diversity adjustment strategy with an information vector. This strategy combines the parent and child populations into a set of candidate solutions, and then divides all the solutions in the set into four categories according to the fitness and diversity of the solutions. Different selection methods can be used to adjust the diversity of the population while ensuring the quality of the solutions selected. In addition, based on the profit density for combinations of terms, three kinds of neighborhood structures were designed. They were used to improve the algorithm's searching ability, explore the neighborhood of local solutions, and jump out of the local optimum, respectively. The local search was performed by the variable neighborhood search algorithm. Finally, the effectiveness of the proposed improvement strategy and the feasibility of the proposed algorithm for solving the ESD {0-1} KP-R were demonstrated through experimental analysis on four types of instances.

References

[1]	H. Kellerer, U. Pferschy, D. Pisinger, Knapsack problems, Berlin, Heidelberg: Springer, 2004. https://doi.org/10.1007/978-3-540-24777-7
[2]	J. Guder, Discounted knapsack problems for pairs of items, Nuremberg: University of Erlangen-Nurnberg, 2005.
[3]	A. Rong, J. R. Figueira, K. Klamroth, Dynamic programming based algorithms for the discounted {0–1} knapsack problem, Appl. Math. Comput., 218 (2012), 6921–6933. https://doi.org/10.1016/j.amc.2011.12.068 doi: 10.1016/j.amc.2011.12.068
[4]	Y. C. He, X. Z. Wang, W. B. Li, X. L. Zhang, Y. Y. Chen, Research on genetic algorithms for the discounted {0–1} knapsack problem, Chin. J. Comput., 39 (2016), 2614–2630. https://doi.org/10.11897/SP.J.1016.2016.02614 doi: 10.11897/SP.J.1016.2016.02614
[5]	Z. Dai, B. Zhou, Y. Long, Z. Wang, Greedy repair strategy of particle swarm optimization for discounted {0–1} knapsack problem, Appl. Res. Comput., 29 (2022), 2363–2368. https://doi.org/10.19734/j.issn.1001-3695.2021.12.0701 doi: 10.19734/j.issn.1001-3695.2021.12.0701
[6]	Y. Yang, D. Z. Pan, Y. Li, D. L. Tan, New simplified model of discounted {0–1} knapsack problem and solution by genetic algorithm, J. Comput. Appl., 39 (2019), 656–662. https://doi.org/10.11772/j.issn.1001-9081.2018071580 doi: 10.11772/j.issn.1001-9081.2018071580
[7]	Q. Zhang, D. Z. Pan, Modeling of extended SD {0–1} KP backpack problem and solution of genetic algorithm, J. China West Norm. Univ. Nat. Sci., 42 (2020), 214–220. https://doi.org/10.16246/j.issn.1673-5072.2020.02.015 doi: 10.16246/j.issn.1673-5072.2020.02.015
[8]	H. Lin, Y. Deng, Improved greedy algorithm to solve extended simplified discounted {0–1} knapsack problem, J. Southwest China Norm. Univ. Nat. Sci. Ed., 47 (2022), 63–71. https://doi.org/10.13718/j.cnki.xsxb.2022.11.009 doi: 10.13718/j.cnki.xsxb.2022.11.009
[9]	L. M. Schmitt, Theory of genetic algorithms, Theor. Comput. Sci., 259 (2001), 1–61. https://doi.org/10.1016/S0304-3975(00)00406-0
[10]	G. Rudolph, Convergence analysis of canonical genetic algorithms, IEEE Trans. Neural Netw., 5 (1994), 96–101. https://doi.org/10.1109/72.265964 doi: 10.1109/72.265964
[11]	P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms, Caltech Concurrent Comput. Program C3P Rep., 826 (1989), 37.
[12]	H. Duan, X. Zhang, C. Xu, Biomimetic intelligent computing, Science Press, 2011.
[13]	B. Peng, Z. Lü, T. C. E. Cheng, A tabu search/path relinking algorithm to solve the job shop scheduling problem, Comput. Oper. Res., 53 (2015), 154–164. https://doi.org/10.1016/j.cor.2014.08.006 doi: 10.1016/j.cor.2014.08.006
[14]	C. Wilbaut, R. Todosijević, S. Hanafi, A. Fréville, Variable neighborhood search for the discounted {0–1} knapsack problem, Appl. Soft Comput., 131 (2022), 109821. https://doi.org/10.1016/j.asoc.2022.109821 doi: 10.1016/j.asoc.2022.109821
[15]	M. Črepinšek, S. H. Liu, M. Mernik, Exploration and exploitation in evolutionary algorithms: A survey, ACM Comput. Surv., 45 (2013), 1–33. https://doi.org/10.1145/2480741.2480752 doi: 10.1145/2480741.2480752
[16]	X. Tian, D. Ouyang, Y. Wang, H. Zhou, L. Jiang, L. Zhang, Combinatorial optimization and local search: A case study of the discount knapsack problem, Comput. Electr. Eng., 105 (2023), 108551. https://doi.org/10.1016/J.COMPELECENG.2022.108551 doi: 10.1016/J.COMPELECENG.2022.108551
[17]	H. Zhu, Y. He, X. Wang, E. C. Tsang, Discrete differential evolutions for the discounted {0–1} knapsack problem, Int. J. Bio-Inspired Comput., 10 (2017), 219–238. https://doi.org/10.1504/IJBIC.2017.087924 doi: 10.1504/IJBIC.2017.087924
[18]	Y. Feng, G. G. Wang, S. Deb, M. Lu, X. J. Zhao, Solving 0–1 knapsack problem by a novel binary monarch butterfly optimization, Neural Comput. Appl., 28 (2017), 1619–1634. https://doi.org/10.1007/s00521-015-2135-1 doi: 10.1007/s00521-015-2135-1
[19]	Y. Yang, D. Z. Pan, Y. C. He, Improved repair strategy genetic algorithm solve discount {0–1} knapsack problem, Comput. Eng. Appl., 54 (2018), 37–42. https://doi.org/10.3778/j.issn.1002-8331.1711-0255 doi: 10.3778/j.issn.1002-8331.1711-0255
[20]	X. J. Liu, Y. C. He, F. J. Lu, C. C. Wu, X. F. Cai, Chaotic crow search algorithm based on differential evolution strategy for solving discount {0–1} knapsack problem, J. Comput. Appl., 38 (2018), 137–145. https://doi.org/10.11772/j.issn.1001-9081.2017061445 doi: 10.11772/j.issn.1001-9081.2017061445
[21]	Y. C. He, X. Z. Wang, S. G. Gao, Ring theory-based evolutionary algorithm and its application to D{0–1} KP, Appl. Soft Comput. J., 77 (2019), 714–722. https://doi.org/10.1016/j.asoc.2019.01.049 doi: 10.1016/j.asoc.2019.01.049
[22]	X. P. Xu, L. Xu, F. Wang, L. Liu, Learning monkey algorithm based on lagrange interpolation to solve discounted {0–1} knapsack problem, J. Comput. Appl., 40 (2020), 3113–3118. https://doi.org/10.11772/j.issn.1001-9081.2020040482 doi: 10.11772/j.issn.1001-9081.2020040482
[23]	C. C. Wu, J. L. Zhao, Y. H. Feng, M. Lee, Solving discounted {0–1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm, Appl. Intell., 50 (2020), 1872–1888. https://doi.org/10.1007/s10489-020-01652-0 doi: 10.1007/s10489-020-01652-0
[24]	T. K. Truong, A new moth-flame optimization algorithm for discounted {0–1} knapsack problem, Math. Probl. Eng., 2021 (2021), 5092480. https://doi.org/10.1155/2021/5092480 doi: 10.1155/2021/5092480
[25]	X. Hao, Y. C. He, X. B. Zhu, Q. L. Zhai, Discrete hybrid multi-verse optimization algorithm for solving discounted {0–1} knapsack problem, Comput. Eng. Appl., 57 (2021), 103–113. https://doi.org/10.3778/j.issn.1002-8331.2008-0454 doi: 10.3778/j.issn.1002-8331.2008-0454
[26]	M. Zhang, W. H. Deng, J. Li, Y. W. Zhong, Modified ant colony optimization algorithm for discounted {0–1} knapsack problem, Comput. Eng. Appl., 57 (2021), 85–95. https://doi.org/10.3778/j.issn.1002-8331.2006-0278 doi: 10.3778/j.issn.1002-8331.2006-0278
[27]	A. Sulaiman, M. Sadiq, Y. Mehmood, M. Akram, G. A. Ali, Fitness-based acceleration coefficients binary particle swarm optimization (FACBPSO) to solve the discounted knapsack problem, Symmetry, 14 (2022), 1208. https://doi.org/10.3390/SYM14061208 doi: 10.3390/SYM14061208
[28]	H. S. Zhang, Y. C. He, J. H. Wang, F. Sun, M. L. Li, Enhanced group theory-based optimization algorithm for solving discounted {0–1} knapsack problem, J. Front. Comput. Sci. Technol., 18 (2024), 1526–1542. https://doi.org/10.3778/j.issn.1673-9418.2305055 doi: 10.3778/j.issn.1673-9418.2305055
[29]	J. T. Zhao, X. C. Luo, A population-based simulated annealing approach with adaptive mutation operator for solving the discounted {0–1} knapsack problem, Appl. Soft Comput., 181 (2025), 113480. https://doi.org/10.1016/j.asoc.2025.113480 doi: 10.1016/j.asoc.2025.113480
[30]	Z. Dai, Y. Zhang, DJAYA-RL: Discrete JAYA algorithm integrating reinforcement learning for the discounted {0–1} knapsack problem, Swarm Evol. Comput., 95 (2025), 101927. https://doi.org/10.1016/j.swevo.2025.101927 doi: 10.1016/j.swevo.2025.101927
[31]	C. A. C. Coello, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art, Comput. Methods Appl. Mech. Eng., 191 (2002), 1245–1287. https://doi.org/10.1016/S0045-7825(01)00323-1 doi: 10.1016/S0045-7825(01)00323-1
[32]	Z. Michalewicz, M. Schoenauer, Evolutionary algorithms for constrained parameter optimization problems, Evol. Comput., 4 (1996), 1–32. https://doi.org/10.1162/evco.1996.4.1.1 doi: 10.1162/evco.1996.4.1.1
[33]	D. Pisinger, Where are the hard knapsack problems?, Comput. Oper. Res., 32 (2005), 2271–2284. https://doi.org/10.1016/j.cor.2004.03.002 doi: 10.1016/j.cor.2004.03.002
[34]	Á. E. Eiben, R. Hinterding, Z. Michalewicz, Parameter control in evolutionary algorithms, IEEE Trans. Evol. Comput., 3 (1999), 124–141. https://doi.org/10.1109/4235.771166 doi: 10.1109/4235.771166
[35]	Y. He, X. Wang, W. Li, X. Zhang, Y. Chen, Research on solving discounted {0–1} knapsack problem based on genetic algorithm, Chin. J. Comput., 39 (2016), 2614–2630. https://doi.org/10.11897/SP.J.1016.2016.02614 doi: 10.11897/SP.J.1016.2016.02614

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)