| 基于变异和信息素扩散的多维背包问题的蚁群算法 |
| |
| 引用本文： | 冀俊忠,黄振,刘椿年.基于变异和信息素扩散的多维背包问题的蚁群算法[J].计算机研究与发展,2009,46(4). |
| |
| 作者姓名： | 冀俊忠 黄振 刘椿年 |
| |
| 作者单位： | 北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室,北京,100124 |
| |
| 基金项目： | 国家自然科学基金重大项目，北京市自然科学基金，北京市教育委员会科技发展基金 |
| |
| 摘 要： | 针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.
|
| 关 键 词： | 多维背包问题 蚁群算法 关联距离 扩散模型 变异策略 |
An Ant Colony Optimization Algorithm Based on Mutation and Pheromone Diffusion for the Multidimensional Knapsack Problems |
| |
| Ji Junzhong,Huang Zhen,Liu Chunnian.An Ant Colony Optimization Algorithm Based on Mutation and Pheromone Diffusion for the Multidimensional Knapsack Problems[J].Journal of Computer Research and Development,2009,46(4). |
| |
| Authors: | Ji Junzhong Huang Zhen Liu Chunnian |
| |
| Affiliation: | Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology;College of Computer Science and Technology;Beijing University of Technology;Beijing 100124 |
| |
| Abstract: | Ant colony optimization (ACO) algorithm is a metaheuristic and stochastic search technology, which has been one of the effective tools for solving discrete optimization problems. The multidimensional knapsack problem (MKP) is a classical combinatorial optimization problem, whose goal is to find a subset of objects that maximizes the total profit while satisfying some resource constraints. There are many algorithms to effectively solve MKPs, where ACO algorithm is a new and robust method. However, there are ... |
| |
| Keywords: | multidimensional knapsack problem ant colony optimization association distance diffusion model mutation strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
