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

摘要： 群论优化算法（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}背包问题, 随机变异