改进的差分演化算法求解多维背包问题

作     者：吴聪聪 赵建立 刘雪静 陈嶷瑛 WU Congcong;ZHAO Jianli;LIU Xuejing;CHEN Yiying

作者机构：河北地质大学信息工程学院石家庄050031 全北国立大学电子信息工程学院韩国全州54896 

基　　金：国家社会科学基金项目(No.17BGL202) 河北省高等学校科学研究计划项目(No.ZD2016005) 河北省自然科学基金(No.F2016403055) 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2018年第54卷第11期

页      码：153-160页

摘      要：多维背包(MKP)是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法(Modified Binary Differential Evolution algorithm,MBDE)求解MKP问题,算法关键步骤可分为两部分:二进制群体生成;得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化;设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力,从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性,进行了三组实验,并和近期提出的解决MKP问题的其他启发式算法进行了比较,实验结果显示,MBDE算法求解精度更高。从算法运行时间看,求解速度快,非常适合求解大规模的MKP问题。

主 题 词：多维背包 差分演化算法 价值密度 反向测试搜索 精英局部搜索 

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

D　O　I：10.3778/j.issn.1002-8331.1712-0355

馆 藏 号：203289016...