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

• 作者: 刘雪静 吴聪聪 赵建立 陈嶷瑛
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 多维背包 差分演化算法 价值密度 反向测试搜索 精英局部搜索
• 年，卷（期）: 2018,（11）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 153-160
• 页数: 8页
• 分类号: TP18
• 字数: 7505字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1712-0355

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘雪静	河北地质大学信息工程学院	13	47	4.0	6.0
2	吴聪聪	河北地质大学信息工程学院	14	44	3.0	6.0
3	陈嶷瑛	河北地质大学信息工程学院	10	27	2.0	4.0
4	赵建立	河北地质大学信息工程学院	4	2	1.0	1.0