计算机工程

作者：潘大志, 蒋妍, 刘雅文

单位：1. 西华师范大学 数学与信息学院, 四川 南充 6370092. 最优化理论与应用四川省高校重点实验室, 四川 南充 637009

关键词：多维背包问题,双种群交互进化,多维加权价值密度,相对价值概率,刺激-响应机制

基金：国家自然科学基金(11871059); 四川省教育厅自然科学基金(18ZA0469); 西华师范大学英才科研基金(17YC385)

针对传统多维背包问题的求解算法存在的修复方式单一、种群动态适应性差等问题，提出一种双决策交互差异算法（DDEA）。融合自主学习思想，设计多维加权价值密度和相对价值概率指标，双重决策确定物品选择顺序，制定相应解的修复优化策略。采用双种群交互差异进化算法，设置主群和辅助群2个种群，种群间进行信息交互，提高种群多样性，避免陷入局部最优，提高算法寻优能力。主群实施差异进化机制，依照个体优劣依次划分为3个子群，分别按照特定方式进化，并在进化过程中完成与辅助群的交互，增强算法群智能性。引入刺激-响应机制，平衡算法的全局和局部搜索能力，并加入精英库协同寻优，加快算法收敛速度。仿真结果表明，DDEA算法可求出全部最优解，平均相对误差率为3.04×10-5，相比于同类算法降低2个数量级，有效提升了多维背包问题的求解精度、效率和稳定性。

来源：2023年第7期

《计算机工程》期刊编辑部

查看计算机工程杂志2023年第7期