基于改进的群论优化算法求解具有单连续变量背包问题

李香军，朱晓斌

（1.河北地质大学 信息工程学院，河北 石家庄 050031；2.石家庄文化传媒学校，河北 石家庄 050000）

0 引言

背包问题是一类重要的 NP难问题，其中包括 0-1背包问题[1]、带建制的背包问题[2]、折扣0-1背包问题[3]以及具有单连续变量背包问题（knapsack problem with a single continuous variable，KPC）[4]等多种类型的背包问题，在项目选择、网络阻截问题和资源配置等众多实际领域[5-8]都有重要的应用。KPC问题是由 Marchand和Wolsey[1]在1999年提出的一种带有连续变量的扩展 0-1背包问题，在物品生产、组织管理以及其他生产分配问题中有很高的应用价值。2011年，Lin等人[5]将 KPC问题分解为标准 0-1背包和伪背包问题，分别利用动态规划法和分支定界法进行求解。2012年，Buther和 Briskorn[6]利用构造法和启发式算法求解KPC问题。2018年，He等人[9]利用放缩法将KPC中的连续变量离散化，基于动态规划求解KPC问题。这些论文皆利用精确算法求解KPC问题，都具有时间复杂度过高的缺点。之后，He等人[10]在2018年引入了演化算法求解KPC问题的思想，建立了KPCM2和KPCM3两种新模型，并基于HBDE算法提出S-HBDE和B-HBDE算法分别求解这两种模型，此方法降低了时间复杂度，但求解效果欠佳。在 2019年，He等人[11]提出了ETDE算法，将背包的装载方案和连续变量作为一个个体，进一步提高了求解KPC问题的效率。近日，王泽昆等人[12]提出一个基于新颖S型转换函数的NBPSO算法求解KPC问题，提高了求解问题的精度与速度。利用演化算法求解KPC问题已经取得了不错的成果，所以利用演化算法求解KPC问题值得深入研究。

群论优化算法（Group theory-based optimization algorithm,GTOA）是He等人[13]在2018年提出的新颖算法，将代数群运算引入背包问题的进化过程中，将背包问题的可行解视为群的直积的一个元素，通过群的直积的乘法和逆运算来实现演化过程。……