基于模运算的新颖离散差分演化算法求解多背包问题.pdf

收稿日期：；修回日期：基金项目：河北省自然科学基金资助项目（）；河北省高等学校科学技术研究项目（）；河北省高等学校科学技术研究项目青年基金资助项目（）；河北地质大学 年国家预研资助项目（）作者简介：王丽娜（），女，河北唐山人，硕士研究生，主要研究方向为演化算法及其应用；张寒崧（），男，河北邯郸人，硕士研究生，主要研究方向为演化算法与组合优化；孙菲（），女，河北邢台人，硕士研究生，主要研究方向为演化算法与组合优化；高泽贤（），女，河北石家庄人，硕士研究生，主要研究方向为演化算法及其应用；贺毅朝（），男（通信作者），河北晋州人，教授，硕导，主要研究方向为演化算法、组合优化（）基于模运算的新颖离散差分演化算法求解多背包问题王丽娜，张寒崧，孙菲，高泽贤，贺毅朝，（河北地质大学 信息工程学院；大数据与计算智能实验室，石家庄 ）摘要：多背包问题（）是一个求解难度极大的背包问题。为了基于差分演化（）求解 ，首先建立了 的整数规划模型，在利用模运算构造简单且有效的新型传递函数基础上，提出了一个新颖离散差分演化算法 ；基于贪心策略提出了消除 不可行解的一个有效算法 ，由此利用 给出了求解 的一种新方法。最后，利用 求解 个国际通用的 实例，通过与四个代表性演化算法的比较表明，不仅计算结果优，而且算法的稳定性强，是求解 的一个高效算法。关键词：演化算法；差分演化；多背包问题；模运算中图分类号：文献标志码：文章编号：（）：，（，）：（）（），：；引言背包问题 ，是一类经典的 难问题，也是一类著名的组合优化问题，在资源分配、车辆装载、资金预算以及整数规划和财务管理等领域 具有广泛应用。多背包问题（，）是一种典型的背包问题，因求解难度极大，求解算法主要有精确算法和启发式算法。精确算法虽然能够求得 的最优解，但时间复杂度是指数阶的，当问题的规模增大时会出现“组合爆炸”，导致算法消耗过多的时间而不适用于实时性要求较高的应用。启发式算法虽然不能保证求得最优解，但在较短的时间内可以得到一个很好的近似解，而且能够满足实际应用中对求解时间的严格限制。求解 的精确算法主要包括分支定界法和动态规划法。例如，等人 提出了基于“”的树搜索技术，利用该技术确定决策树中的分支，从而提出了求解 的精确算法 。提出了一种新的可分离动态规划算法 ，该算法不仅比 快，而且稳定性高。等人 基于物品分配到背包之间的支配性标准来修剪树的节点，提出了求解 的一个新的分支定界算法。利用优势标准和对称性破环策略与文献 提出的边界和边界法技术相结合，提出了一种改进的分支定界算法。基于多准则动态规划策略开发了求解 的一个动态规划算法。求解 的启发式算法主要是演化算法（，）。例如，等人 提出了利用遗传算法求解 的可行方法；改进了文献 的工作，提出了利用遗传算法求解 的一种新方法，但该方法能提高物品价值与重量高度相关的 实例的求解效果。等人 重新设计了粒子群优化的速度和位置更新方程，提出了利用离散粒子群优化求解 的一个可行方法。等人 基于整数编码方法表示个体，探讨了利用人工鱼群算法（，）求解 的可行性和有效性。李迎等人 在 算法中引入了动态视野与步长调整策略提高算法的精度，给出了利用 求解 的一种可行方法。是一种基于自然选择和遗传变异等生物进化机制的全局搜索算法，具有自组织、自适应、自学习的特点，在不要求目标函数连第 卷第 期 年 月计 算 机 应 用 研 究 续、可微与单峰的情况下能较快地求得问题的一个极好的近似解。常见的 有遗传算法（，）、差分演化算法（，）、粒子群优化算法（，）等，它们已被成功应用于求解背包问题 、可满足性问题 和旅行商问题 等组合优化问题。目前，利用 求解 的研究成果不仅匮乏，而且已有方法存在稳定性差、求解效果不佳甚至是极差的缺陷。导致这些问题的原因主要有两点：）大多是针对连续优化问题提出的，虽然存在可行的离散化方法，但对于以整型向量为可行解的组合优化问题，现有离散化方法的效果不佳；）在利用 求解 的已有方法中，缺少对 不可行解进行处理的有效方法，甚至有些从未考虑过处理 的不可行解。因此，利用 高效求解 是一个值得深入研究的课题，本文首先基于模运算提出一个新的离散 ，然后提出处理 不可行解的有效算法 ，最后基于离散 与 相结合给出求解 的一个新的高效方法。背景知识 定义与数学模型将 个物品分配到 个可用背包中。每个物品 都有一个重量 和一个价值。每个背包 有一个容量。每个物品最多只能分配到一个背包中。的目标是在每个背包容量的约束下将物品分配到不同背包中，使得所有背包中物品的利润和最大。根据上述定义，给出了 的 数学模 型（记 为 ），其描述如下：（）（），（），（），；，（）其中：（）是一个 阶 矩阵，表示 的一个可行解，即 表示第 个物品装入了第 个背包中；表示第 个物品没有装入第 个背包中。容易看出，中可行解的取值范围为 。同时，如果利用 矩阵 表示个体编码，由约束条件式（）可知，这样的 矩阵必然是一个稀疏矩阵，势必会增大算法的时间和空间复杂度，大大降低了算法的求解效率。为此建立了 的一个整数规划模型 如下：（）?（）：，（），（）其中：?表示取不小于 的最小整数；，表示 的一个可行解，当 时表示第 个物品不装入任何背包中，当 时表示第 个物品装入了第 个背包中。由模型 可知，是离散域 ，上的组合优化问题，在利用 求解时个体编码为 ，上的一个整型向量。注意到 ，的基数为（），（），因此 基于模型 求解 比基于模型 求解不仅使个体的编码简单，而且大大缩小了 的搜索范围，有助于提高求解效率。差分演化算法 是 等人 于 年提出的著名演化算法，具有结构简单、容易实现、收敛快速和鲁棒性强等特点。在第一届国际演化计算（）竞赛中，被证明是速度最快且效果极佳的演化算法，引起了国内外学者的极大关注，目前已被广泛应用于数值优化、机器制造、电力系统和人工神经网络等领域 。下面基于 的 模式简述其算法原理。不失一般性，设 （），是一个连续优化问题，其中 ，是解空间，且为实数。的一次迭代进化由变异操作、交叉操作和选择操作共同完成，它们的实现方法如下：）变异操作。设 ，是当前种群 中的第 个个体，和 ，是 中不同于 的任意三个不同个体，则 基于 模式进行变异操作的公式为 （）（）其中：，表示变异操作产生的临时个体，；（，）为缩放因子。）交叉操作。算法有指数交叉和二项式交叉两种交叉方法。下面利用式（）的二项式交叉方式对 和 进行交叉操作，生成对应 的中间个体 ，。（）其中：表示（，）中的一个随机数；为 ，中的一个随机整数，用于保证至少有一个交叉位；（，）为交叉因子（也称交叉概率）。）选择操作。采用贪婪选择策略，当 中每一个个体均产生中间个体 后，利用式（）从 和 中选择适应度最佳的作为新一代种群中的第 个个体（仍记为）。（）（）（）反复执行 ）实现进化，直到满足终止条件为止。最后，输出当前种群中适应度最大个体对应的可行解，即为 求得 （）的最好结果。基于模运算的离散差分演化算法基本 是针对实数域上的连续优化问题提出的，不能直接用于求解离散域 ，上组合优化问题（如 和 ），因此需要对它进行离散化，使其能够产生或处理 ，上的元素。为了保持离散 具有基本 的进化模式，在离散进化方程中必须体现个体差异向量的作用。综合考虑这些因素，本文借鉴文献 中基于模运算构造离散演化算法的思路，提出一个简单高效的新型传递函数 ，利用它将实向量转换为 ，上的整型向量，由此提出了一个可用于求解 ，上组合优化问题的新颖离散 算法，记做 。不失一般性，设 （），是一个组合优化问题。记 ，为 的当前种群 中第 个个体，为种群规模，是一个给定的正实数。记 ，为 求得的当前最好解，下面基于 （）给出 的进化原理和伪代码描述。新型传递函数定义新型传递函数 ：，：对于 ，：（）?（）（）其中：为 的绝对值；?为底函数，表示不超过 的最大整数；表示 除以 的余数；是大于 的正实数。第 期王丽娜，等：基于模运算的新颖离散差分演化算法求解多背包问题 利用传递函数 将 维实向量 转换为 维整型向量 ，（），（），（），作为 （）的一个可行解（或候选解）。种群初始化在 中，首先利用式（）随机产生 的初始种群 中的 个个体 ，（），有 （）其中：为（，）中的随机数，。然后利用传递函数 求出每个（）对应的 维整型向量 ，其中 （），并计算（）的值作为个体 的适应度，确定当前最好解。的进化原理 在产生第 （）代种群的第 次迭代进化中，对当前的第 代种群 中的每一个个体 ，首先利用变异式（）得到它的临时个体 ，；然后利用交叉式（）对 和 进行交叉操作，生成 的中间个体 ，；再利用传递函数 求得 对应的整型向量 ，其中?（）；计算（）作为中间个体 的适应度；最后利用式（）选择 和 中适应度更优的个体作为下一代种群中的第 个个体（不妨仍记为）。（，）（，）（）（）（，）（）当第 代种群 的所有个体（）均完成上述操作后，就产生了 的第 代种群。此时，确定当前最好解 （），即完成了 的第 次迭代进化。重复上述进化过程，直到满足终止条件为止，输出当前最好解，结束算法。的算法伪代码记 是 的迭代次数，对于组合优化问题 （），的算法伪代码如算法 所示。算法 输入：（）的一个实例；参数 、和 。输出：，和 （）。随机产生初始种群 ，；利用 求（）的可行解 并计算 （），确定；（）（）；?（）；（）（）；根据 （）（）的值确定；（，（）在算法 中，步骤 的时间复杂度为 （）；步骤 的时间复杂度为 （），其中 （）是 （）的计算时间复杂度；步骤 的时间复杂度为 （）。因此，的时间复杂度为（）（）（）（）。当 、和 （）是关于 的一次多项式时，（）（）。容易看出，对于维数 ，在传递函数 中 分别取值（），则 可求解一般离散域 ，上的组合优化问题。特殊地，在传递函数 中 时，是一个可求解 ，上二元优化问题的二进制 。利用 求解 由于 是一个约束优化问题，是一个具有随机性的非确定性算法，在基于模型 利用 求解 时，生成的新个体对应的整型向量不可避免地会出现不满足式（）约束的情况，即新个体是一个非正常编码个体，它对应的整型向量是一个不可行解。为了解决这一问题，下面提出一个基于贪心策略的修复优化算法（记为 ）。包括修复阶段和优化阶段。在修复阶段，当候选解不满足约束条件式（）时，即 为不可行解时，意味着当背包出现了超重，此时 根据物品的价值密度 的大小，从这样的背包中取出价值密度最小的物品，直到它们均不超重为止，即完成了对候选解 的修复处理。在优化阶段，为了提高可行解 的质量，按照背包载重从小到大的顺序对尚未装入当前背包而且也未被尝试装入的物品，根据物品的价值密度由大到小的次序依次尝试该物品是否能装入当前背包，若能则装入，否则考虑下一个物品。直到所有背包均被如此处理一遍为止，即完成对可行解 的优化。将 实例中的物品按照价值密度 从大到小的顺序排序，并按照排序后的顺序将物品下标 存入数组 中，即满足 。将 实例的所有背包按照其载重从小到大的顺序排序，并按照排序后的顺序将背包下标 存入数组 中，即 。令数组 用于存储 个背包中的物品重量之和，集合 记录已经被优化过的背包下标，变量 记录当前超重的背包个数，则 的伪代码如算法 所示。算法 输入：候选解 ，数组 和 。输出：可行解 ，及其目标函数值 （）。；修复阶段开始 （）；）；修复阶段完成 ；优化阶段开始 ；（）；优化阶段完成 （，（）在算法 中，步骤 和步骤 的时间复杂度均为（），步骤 和 的时间复杂度均为 （），步骤计 算 机 应 用 研 究 第 卷 的时间复杂度为 （），所以算法 的时间复杂度为 （）（）（）（）。例 给定三个容量分别为 、和 的背包，现将八个物品装入这三个背包中，物品的重量集为 ，价值集为 ，。下面借例 说明 的作用。设 ，为 求得上述实例的一个候选解，显然第二个背包超重了，即 不满足模型 的约束条件式（），是一个不可行解。利用 对 进行修复与优化的过程如图 所示。图 是对 修复与优化前的方案，图 是修复后的方案，图 是修复与优化后的方案。图 修复与优化前的方案 图 修复后的方案 图 修复与优化后的方案 从图 不难看出，修复与优化完成后即可得到最好解 ，。在利用 求解 时，由于使用 消除了不可行解，需要对数组 和 进行预处理，可以利用快速排序算法实现。在 求解 的过程中，只要利用传递函数产生个体对应的候选解，就立刻调用 对其进行处理，由此获得该个体的一个高质量可行解；同时，计算可行解的目标函数值作为该个体的适应度。容易看出，在使用 消除不可行解时，利用 求解 的计算复杂度为 （）（）。计算结果和比较 实验环境所有计算均在 和 的微型计算机上进行。所有算法均采用 语言编程实现，编译环境为 。使用 绘制图形，编译环境为 。三类 的实例所有的 实例均取自公开的 实例，下载地址为 ：。实例分为三类，它们的命名规则为“”，其中“”分别为 、，表示实例的相关性，即“”表示不相关类实例，“”表示弱相关类实例，“”表示强相关类实例；“”的值分别为 、和 ，依次表示来自实例组 、和 的实例；“”为背包个数 ；“”为物品数量 。例如，“”表示 组中的一个 和 的不相关 实例。算法参数设置本 节 对 、，、和 算法求解 个 实例的计算结果进行比较，其他四个算法均与 一样使用 处理 的不可行解。所有算法的种群规模均设为 ，算法迭代次数设为 。对于每个 实例，所有算法都独立计算 次。在 中，是缩放因子，是交叉因子，为个体编码的实向量的取值空间。在 中，是惯性权重，和 是加速度常数；在 中，个体采用整型向量编码，利用单点交叉，交叉概率为；采用按位随机变异（即单位随机变异其他值），变异概率为；在 和 中，是变异概率。、和 的参数值如表 所示。表 、和 的参数取值 ，算法参数取值 ，为了方便做图，所有 实例均设定一个编号，不相关实例编号为 ，弱相关实例编号为 ，强相关实例编号为 。实例名称与其编号的对应关系如表 所示。表 实例名称与其对应编号 实例 实例 计算结果与比较记 、和 分别为算法 次独立计算得到结果的最好值、平均值和标准差。在表 中列出了各算法求解三类 实例的结果，其中的黑色加粗部分代表计算结果最好。由表 可以看出，对于 个 类实例，在 方面，有 个实例的结果最好，和 有 个实例的结果最好，和 只有 个实例的结果最好；在 方面，有 个实例的结果最好，和 有 个实例的结果最好，而 和 只有 个实例的结果最好。由表 可以看出，对于 个 类实例，在 方面，有 个实例的结果最好，有 个实例的结果最好，而 、和 只有 个实例的结果最好；在 方面，有 个实例的结果最好，有 个实例的第 期王丽娜，等：基于模运算的新颖离散差分演化算法求解多背包问题结果最好，而 、和 只有 个实例的结果最好。由表 可以看出，对于 个 类实例，在 方面，有 个实例的结果最好，有 个实例的结果最好，而 、和 只有 个实例的结果最好；在 方面，有 个实例的结果最好，而 、和 只有 个实例的结果最好。表 、和 求解 类实例的计算结果 ，算法指标 表 、和 求解 类实例的计算结果 ，算法指标 表 、和 求解 类实例的计算结果 ，算法指标 为了比较 、和 求解三类 实例的平均性能，图 中利用 秩和检验 对它们的 值进行比较，从中不难看出，求解 实例的结果明显优于 、和 。在图 中，利用直方图对 、和 的 进行了比较。从图 可以看出，对于 个 类实例，有 个实例的 值为 ，而 、和 只有个实例的 值为，虽然对编号 的实例 的稳定性较差，但是对于其他 个实例，的 值均比其他算法小，所以 稳定性明显要比其他算法的优。从图 不难看出，对于 类的 个实例，有 计 算 机 应 用 研 究 第 卷个实例的 值为 ，而 、和 只有 个实例的 值为 ；虽然对编号 的实例，的稳定性不是最好的，但是对于其他 个实例，的 值均比其他算法小，稳定性明显要比其他算法更优。图 实例的 检验 图 实例的 检验 图 实例的 检验 图 实例的标准差 图 实例的标准差 图 实例的标准差 从图 可以看出，对于 类的 个实例，的 值都是最小的，所以 的算法稳定性比 、和 的均优。综上所述，对于 ，比 、和 的求解结果更优，算法的稳定性更佳。因此，是一种非常适于求解 的高效演化算法。结束语本文基于模运算提出了求解 ，上组合优化问题的一种新型离散差分演化算法 ，在建立了 的整数规划模型基础上，提出了一种消除不可行解的贪心修复优化算法 ，由此给出了利用 求解 的一个新方法。通过与 、和 等离散演化算法对三类 实例的计算结果比较表明，是一个适用于求解 的高效演化算法。注意到折扣 背包问题 ，是一个建模在 ，上的组合优化问题，适合利用 求解，因此如何基于 高效求解折扣 背包问题是一个值得今后研究的问题。此外，由于 可用于求解 ，上的优化问题，自然可用于求解具有单连续变量的背包问题 ，和集合覆盖问题 等二元优化问题。如何利用 高效求解这两个问题也是一个值得今后研究与探讨的问题。参考文献：，：，：，王熙照，贺毅朝求解背包问题的演化算法 软件学报，（）：（，（）：），（）：，（）：，（）：，（）：，（）：，（）：，：，：，：，：，：，：，（）：李迎，张瞡，刘庆，等求解大规模多背包问题的高级人工鱼群算法 系统工程与电子技术，（）：（，（）：）陈国良，王熙法，庄镇泉，等遗传算法及其应用 北京：人民邮电出版社，（，：，），（）：，：，：，（）：贺毅朝，王熙照，李文斌，等基于遗传算法求解折扣 背包问题的研究 计算机学报，（）：（，（）：）张发展，贺毅朝，刘雪静，等 新颖的离散差分演化算法求解 问题 计算机科学与探索，（）：（，（）：），（）：（下转第 页）第 期王丽娜，等：基于模运算的新颖离散差分演化算法求解多背包问题 ，（）：）刘博，徐晓敏政企协同视角下应急物资储备库选址优化研究 北京信息科技大学学报：自然科学版，（）：（，：，（）：）彭大江，叶春明，万孟然基于模糊需求的应急物资中心选址路径问题的算法研究 计算机应用研究，（）：（，（）：），（）：，（）：，（）：宋英华，苏贝贝，霍非舟，等考虑动态需求的应急物资配送中心快速选址研究 中国安全科学学报，（）：（，（）：）胡少龙，范婷睿基于机器学习的样本均值近似算法求解应急物资配置问题 管理现代化，（）：（，（）：）谭正园，李嘉丽，唐琳婕，等新冠肺炎疫情下应急物资储备仓库选址研究 以南宁市为例 中国物流与采购，（）：（，：，（）：）张敏，黄钧考虑关键交通路段失效情景的中央储备库选址评估 运筹与管理，（）：（，（）：）姜凯凯，高尘，孙洁依托便利店构建生活物资应急配送终端体系 以日本便利店的灾后救援经验为例 国际城市规划，（）：（，：，（）：）运筹学 教材编写组运筹学 版北京：清华大学出版社，：（“”：，：），（）：（上接第 页），（）：，（）：，（）：，：，（）：，：（），（）：，（）：，（）：贺毅朝，王熙照，赵书良，等基于编码转换的离散演化算法设计与应用 软件学报，（）：（，（）：），（）：，（）：，（）：王泽昆，贺毅朝，李焕哲，等基于新颖 型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题 计算机应用，（）：（，（）：），（）：计 算 机 应 用 研 究 第 卷