多维背包问题的二进制蚂蚁算法

• 作者: 孔明 李想勇 田澎
• 来源期刊: 管理科学学报
• 学科: 数学
• 关键词: 蚁群优化 二进制蚂蚁算法 组合优化 多维背包问题
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 论文
• 页码范围: 44-53
• 页数: 10页
• 分类号: O22
• 字数: 7872字
• 语种: 中文
• DOI: 10.3321/j.issn:1007-9807.2009.02.005

摘要

针对著名的多维背包问题(MKP), 在蚁群优化系统高维立方体结构的基础上,提出了一种二进制蚂蚁算法(BAS).与其他求解MKP问题的蚂蚁算法不同,BAS根据二进制解的结构设计了特殊的信息素放置方式,同时在算法的迭代过程中允许非可行解的产生,并通过基于问题特征信息的修改算子修复每次迭代所产生的非可行解.BAS算法采用了特殊的信息素更新规则,使得各个选择路径上的信息素可以直接作为选择概率,同时,为了避免算法陷入早熟,BAS设计了简单的局部搜索法,并根据算法所处的不同收敛状况,采用了不同的信息素更新规划和信息素重新初始化的方法.针对MKP基准问题的实验结果表明,BAS具有超越其他蚂蚁算法的求解结果,其求解不同基准测试问题的能力表明了BAS具有解决超大规模MKP问题的潜力.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	田澎	上海交通大学管理学院	140	4464	39.0	63.0
2	孔明	上海交通大学管理学院	19	194	8.0	13.0
3	李想勇	上海交通大学管理学院	1	6	1.0	1.0