计算机科学与探索

作者：张寒崧, 贺毅朝, 王静红, 孙菲, 李明亮

单位：1. 河北地质大学 信息工程学院，石家庄 0500312. 河北师范大学 计算机与网络空间安全学院，石家庄 0500243. 智能传感物联网技术河北省工程研究中心，石家庄 050031

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

群论优化算法（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的最佳算法。

来源：2024年第6期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2024年第6期