| 多维背包问题的二进制蚂蚁算法 |
| |
| 引用本文： | 孔明,田澎,李想勇.多维背包问题的二进制蚂蚁算法[J].管理科学学报,2009(2). |
| |
| 作者姓名： | 孔明 田澎 李想勇 |
| |
| 作者单位： | 上海交通大学管理学院,上海,中国,200052 |
| |
| 摘 要： | 针对著名的多维背包问题(MKP), 在蚁群优化系统高维立方体结构的基础上,提出了一种二进制蚂蚁算法(BAS).与其他求解MKP问题的蚂蚁算法不同,BAS根据二进制解的结构设计了特殊的信息素放置方式,同时在算法的迭代过程中允许非可行解的产生,并通过基于问题特征信息的修改算子修复每次迭代所产生的非可行解.BAS算法采用了特殊的信息素更新规则,使得各个选择路径上的信息素可以直接作为选择概率,同时,为了避免算法陷入早熟,BAS设计了简单的局部搜索法,并根据算法所处的不同收敛状况,采用了不同的信息素更新规划和信息素重新初始化的方法.针对MKP基准问题的实验结果表明,BAS具有超越其他蚂蚁算法的求解结果,其求解不同基准测试问题的能力表明了BAS具有解决超大规模MKP问题的潜力.
|
| 关 键 词： | 蚁群优化 二进制蚂蚁算法 组合优化 多维背包问题 |
Binary ant system for multidimensional knapsack problem |
| |
| KONG Min,TIAN Peng,LI Xiang-yong.Binary ant system for multidimensional knapsack problem[J].Journal of Management Sciences in China,2009(2). |
| |
| Authors: | KONG Min TIAN Peng LI Xiang-yong |
| |
| Institution: | KONG Min,TIAN Peng,LI Xiang-yongSchool of Management,Shanghai Jiaotong University,Shanghai 200052,China. |
| |
| Abstract: | This paper proposes a binary ant system(BAS),an improved hyper cubeframework of ant colony optimization(ACO) applied to multidimensional knapsack problem(MKP).Different to other Ant Systems applied to MKP,BAS designs a specialpheromone laying method based on the binary solution structure,admits infeasible solution during the solution construction procedure,and uses a problem specifc repairing operator to repair those infeasible solutions generated in each iteration.BAS uses aspecial pheromone update rule,in... |
| |
| Keywords: | ant colony optimization binary ant system combinatorial optimization multidimensional knapsack problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《管理科学学报》浏览原始摘要信息 |
| 点击此处可从《管理科学学报》下载免费的PDF全文 |
|
