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

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

来源：计算机科学与探索, 2023, 1-19.

• 群论优化算法
• 组合优化问题
• 折扣{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的最佳算法。

• 单位
  河北地质大学; 河北师范大学