增强型群论优化算法求解折扣{0-1}背包问题

doi:10.3778/j.issn.1673-9418.2305055

摘要/Abstract

摘要： 群论优化算法（GTOA）是基于群论方法提出的一个离散演化算法，非常适于求解以整型向量为可行解的组合优化问题。为了进一步提高GTOA求解折扣{0-1}背包问题（D{0-1}KP）的性能，首先指出了它的随机线性组合算子（RLCO）未能充分考虑当前个体位置信息的不足，基于个体基因保留策略对其进行改进。然后，在随机反向变异算子（IRMO）中引入增强0分量变异策略，用于处理因个体0分量无法及时变异而导致的解的质量下降、种群多样性降低等问题。在改进上述两个算子的基础上，提出了增强型GTOA（EGTOA），并基于它给出求解D{0-1}KP的新方法。随后，将改进策略应用于二进制GTOA（GTOA-2），提出了增强型GTOA-2（EGTOA-2）及其求解D{0-1}KP的新方法。为了验证EGTOA和EGTOA-2的性能提高程度与优异性，分别利用它们求解四类大规模D{0-1}KP实例，通过与GTOA、GTOA-2以及求解D{0-1}KP的已有8个最先进算法的比较表明：EGTOA和EGTOA-2求得最优解的能力比GTOA和GTOA-2提高了至少1.14倍，比8个最先进算法提高了5%~60%，它们的平均性能比GTOA、GTOA-2以及8个最先进算法的性能更佳。因此，EGTOA和EGTOA-2是当前求解D{0-1}KP的最佳算法。

关键词: 群论优化算法, 组合优化问题, 折扣{0-1}背包问题, 随机变异

Abstract: The group theory-based optimization algorithm (GTOA) is a discrete evolutionary algorithm designed by group theory methods, which is very suitable for solving combinatorial optimization problems with integer vectors as feasible solutions. In order to further improve the performance of GTOA for solving the discounted {0-1}knapsack problem (D{0-1}KP), firstly, this paper points out the deficiency of its random linear combination operator (RLCO) which fails to fully consider the current individual position information, and improves it based on the individual gene retention strategy. Then, the enhanced 0-component mutation strategy is introduced into the random inverse mutation operator (IRMO), which is used to deal with problems such as the decline in the quality of the solution and the decrease of population diversity caused by the failure of the individual 0-component to mutate in time. Based on the improvement of the two operators mentioned above, an enhanced GTOA (EGTOA) is proposed, and a new method for solving D{0-1}KP is proposed based on it. Subsequently, the improved strategies are applied to binary GTOA (GTOA-2), and an enhanced GTOA-2 (EGTOA-2) and a new method for solving D{0-1}KP are proposed. In order to verify the degree of performance improvement and superiority of EGTOA and EGTOA-2, they are used to solve four types of large-scale D{0-1}KP instances. The comparison with GTOA, GTOA-2, and 8 state-of-the-art algorithms of solving D{0-1}KP shows that the ability of EGTOA and EGTOA-2 to obtain optimal solutions is at least 1.14 times higher than that of GTOA and GTOA-2, and 5% to 60% higher than that of the existing 8 state-of-the-art algorithms. At the same time, their average performance is also better than GTOA, GTOA-2, and the 8 advanced algorithms. Therefore, EGTOA and EGTOA-2 are currently the best algorithms for solving D{0-1}KP.

Key words: group theory-based optimization algorithm, combinatorial optimization problems, discounted {0-1} knapsack problem, random mutation

张寒崧, 贺毅朝, 王静红, 孙菲, 李明亮. 增强型群论优化算法求解折扣{0-1}背包问题[J]. 计算机科学与探索, 2024, 18(6): 1526-1542.

ZHANG Hansong, HE Yichao, WANG Jinghong, SUN Fei, LI Mingliang. Enhanced Group Theory-Based Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(6): 1526-1542.

参考文献

[1] KELLERER H, PFERSCHY U, PISINGER D. Knapsack pro-blems[M]. Berlin Heidelberg: Springer, 2004.
[2] ROBERT P R, HARALD V H. Robust optimization of the 0-1 knapsack problem: balancing risk and return in assortment optimization[J]. European Journal of Operational Research, 2016, 250(5): 842-854.
[3] FELIX B, STEFAN N. The air cargo load planning problem—a consolidated problem definition and literature review on related problems[J]. European Journal of Operational Research, 2019, 275(6): 399-410.
[4] PETER J. Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic[J]. Annals of Operations Research, 2013, 241(1/2): 1-25.
[5] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Nuremberg: University of Erlangen-Nuremberg, 2007: 1-78.
[6] 贺毅朝, 王熙照, 李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报, 2016, 39(12): 2614-2630.
HE Y C, WANG X Z, LI W B, et al. Research on genetic algo-rithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016, 39(12): 2614-2630.
[7] RONG A Y, FIGUEIRA J R, KLAMROTH K. Dynamic pro-gramming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics and Computation, 2012, 218(12): 6921-6933.
[8] HE Y C, WANG X Z, HE Y L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences, 2016, 369: 634-647.
[9] 贺毅朝, 王熙照, 赵书良, 等. 基于编码转换的离散演化算法设计与应用[J]. 软件学报, 2018, 29(9): 2580-2594.
HE Y C, WANG X Z, ZHAO S L, et al. Design and applications of discrete evolutionary algorithm based on encoding transformation[J]. Journal of Software, 2018, 29(9): 2580-2594.
[10] 吴聪聪, 贺毅朝, 陈嶷瑛, 等. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5): 1292-1299.
WU C C, HE Y C, CHEN Y Y, et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2017, 37(5): 1292-1299.
[11] 吴聪聪, 贺毅朝, 赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
WU C C, HE Y C, ZHAO J L. New genetic algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2020, 56(7): 57-66.
[12] ZHU H, HE Y C, WANG X Z, et al. Discrete differential evolutions for the discounted {0-1} knapsack problem[J]. International Journal of Bio-Inspired Computation, 2017, 10(4): 219-238.
[13] 刘雪静, 贺毅朝, 路凤佳, 等. 基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(2): 433-442.
LIU X J, HE Y C, LU F J, et al. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications, 2018, 38(2): 433-442.
[14] 刘雪静, 贺毅朝, 吴聪聪, 等. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
LIU X J, HE Y C, WU C C, et al. Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack pro-blem[J]. Computer Engineering and Applications, 2018, 54(18): 139-146.
[15] 冯艳红, 杨娟, 贺毅朝, 等. 差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J]. 电子学报, 2018, 46(6): 1343-1350.
FENG Y H, YANG J, HE Y C, et al. Monarch butterfly optimization algorithm with differential evolution for the discounted {0-1} knapsack problem[J]. Acta Electronica Sinica, 2018, 46(6): 1343-1350.
[16] 杨洋, 潘大志, 刘益, 等. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用, 2019, 39(3): 656-662.
YANG Y, PAN D Z, LIU Y, et al. New simplified model of discounted {0-1} knapsack problem and solution by genetic algorithm[J]. Journal of Computer Applications, 2019, 39(3): 656-662.
[17] 史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
SHI W X, YANG Y, BAO S L. Greedy core acceleration dynamic programming algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2019, 39(7): 1912-1917.
[18] HE Y C, WANG X Z, GAO S G. Ring theory-based evolutionary algorithm and its application to D{0-1} KP[J]. App-lied Soft Computing Journal, 2019, 77: 714-722.
[19] WU C C, ZHAO J L, FENG Y H, et al. Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm[J]. Applied Intelligence, 2020, 50(12): 1-7.
[20] LI Y, HE Y C, LIU X J, et al. A novel discrete whale optimization algorithm for solving knapsack problems[J]. Applied Intelligence, 2020, 50: 3350-3366.
[21] 张发展, 贺毅朝, 刘雪静, 等. 新颖的离散差分演化算法求解D{0-1}KP问题[J]. 计算机科学与探索, 2022, 16(2): 468-479.
ZHANG F Z, HE Y C, LIU X J, et al. Novel discrete differential evolution algorithm for solving D{0-1}KP problem[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 468-479.
[22] TRAN V N, TRUONG T K. A binary social spider algorithm for discounted {0-1} knapsack problem[J]. ICIC Express Letters, 2021, 15(3): 257-264.
[23] 郝翔, 贺毅朝, 朱晓斌, 等. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
HAO X, HE Y C, ZHU X B, et al. Discrete hybrid multi-verse optimization algorithm for solving discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[24] WANG R, ZHANG Z. Set theory based operator design in evolutionary algorithms for solving knapsack problems[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1133-1147.
[25] WILBAUT C, TODOSIJEVIC R, HANAFI S, et al. Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem[J]. European Journal of Operational Research, 2023, 304(3): 901-911.
[26] WILBAUT C, TODOSIJEVI? R, HANAFI S, et al. Variable neighborhood search for the discounted {0-1} knapsack problem[J]. Applied Soft Computing Journal, 2022, 131: 109821.
[27] TRUONG T K. A new moth-flame optimization algorithm for discounted {0-1} knapsack problem[J]. Mathematical Pro-blems in Engineering, 2021. DOI: 10.1155/2021/5092480.
[28] KANG Y, WANG H N, PU B. et al. TMHSCA: a novel hybrid two-stage mutation with a sine cosine algorithm for discounted {0-1} knapsack problems[J]. Neural Computing & Applications, 2023, 35(4): 12691-12713.
[29] HE Y C, WANG X Z. Group theory-based optimization algorithm for solving knapsack problems[J]. Knowledge-Based Systems, 2018, 219(3): 104445.
[30] WANG R, ZHANG Z C, NG W W Y, et al. An improved group theory-based optimization algorithm for discounted 0-1 knap-sack problem[J]. Advances in Computational Intelligence, 2021, 1(5): 1-11.
[31] ZHAI Q L, HE Y C, WANG G G, et al. A general approach to solving hardware and software partitioning problem based on evolutionary algorithms[J]. Advances in Engineering Soft-ware, 2021, 159(9): 102998.
[32] LI Z W, ZHANG Q S, HE Y C. Modified group theory-based optimization algorithms for numerical optimization[J]. Applied Intelligence, 2022, 52(8): 11300-11323.
[33] ZHANG F Z, HE Y C, OUYANG H B, et al. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem[J]. Expert Systems with Applications, 2023, 213: 118978.
[34] 耿素云, 屈婉玲, 王捍贫. 离散数学教程[M]. 北京: 北京大学出版社, 2002: 253-255.
GENG S Y, QU W L, WANG H P. Discrete mathematics course[M]. Beijing: Peking University Press, 2002: 253-255.
[35] RAJEEV M, PRABHAKAR R. Randomized algorithms[M]. Cambridge: Cambridge University Press, 1995.
[36] JOAQUíN D, SALVADOR G, DANIEL M, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
[37] 张寒崧, 贺毅朝. 增强型GTOA与求解D{0-1}KP最先进算法的计算结果比较[EB/OL]. [2023-03-31]. https://www.researchgate.net/publication/371165730_zengqiangxingGTOA-yuqiujieD0-1KPzuixianjinsuanfadejisuanjieguobijiao.
ZHANG H S, HE Y C. Comparison of calculation results of enhanced GTOA and state-of-the-art algorithms for D{0-1}KP[EB/OL]. [2023-03-31]. https://www.researchgate.net/publication/371165730_zengqianxingGTOAyuqiujieD0-1KPzuixianjinsuanfadejisuanjieguobijiao.
[38] 杨新花, 周昱帆, 沈爱玲, 等. 基于拉马克进化的差分进化算法求解KPC问题[J]. 计算机工程与应用, 2022, 58(10): 162-171.
YANG X H, ZHOU Y F, SHEN A L, et al. Lamarckian evolution-based differential evolution algorithm for solving KPC problem[J]. Computer Engineering and Applications, 2022, 58(10): 162-171.
[39] 李香军, 朱晓斌. 基于改进的群论优化算法求解具有单连续变量背包问题[J]. 新一代信息技术, 2021, 4(10): 42-49.
LI X J, ZHU X B. Improved group theory optimization algorithm for knapsack problem with a single continuous variable[J]. New Generation of Information Technology, 2021, 4(10): 42-49.