求解多维背包问题的双决策交互差异算法

作     者：潘大志 蒋妍 刘雅文 PAN Dazhi;JIANG Yan;LIU Yawen

作者机构：西华师范大学数学与信息学院四川南充637009 最优化理论与应用四川省高校重点实验室四川南充637009 

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

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2023年第49卷第7期

页      码：21-33,54页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

D　O　I：10.19678/j.issn.1000-3428.0066578

馆 藏 号：203122603...