| 求解图着色问题的量子蚁群算法 |
| |
| 引用本文： | 何小锋,马良.求解图着色问题的量子蚁群算法[J].运筹学学报,2013,17(2):19-26. |
| |
| 作者姓名： | 何小锋 马良 |
| |
| 作者单位： | 1. 上海理工大学管理学院，上海 200093 |
| |
| 基金项目： | 国家自然科学基金，上海市重点学科建设，上海市研究生创新基金，上海市一流学科建设 |
| |
| 摘 要： | 针对经典的图着色问题，在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中，较好地避免了蚁群算法搜索易陷入局部极小的缺陷，并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验，表明算法对图着色问题的求解是可行的、有效的，且具有通用性.
|
| 关 键 词： | 图着色 蚁群算法 量子计算 量子蚁群算法 |
| 收稿时间： | 2011-06-14 |
A quantum-inspired ant colony algorithm for graph coloring problem |
| |
| HE Xiaofeng
,
MA Liang.A quantum-inspired ant colony algorithm for graph coloring problem[J].OR Transactions,2013,17(2):19-26. |
| |
| Authors: | HE Xiaofeng MA Liang |
| |
| Institution: | 1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China |
| |
| Abstract: | A quantum-inspired ant colony algorithm (QACA) for the classic graph coloring problem is proposed based upon the combination of ant colony optimization and quantum computing. The quantum bits and quantum logic gates are introduced to the ant colony algorithm (ACA), and the disadvantage of getting into the local optimum can be effectively avoided. The computational speed of the algorithm is therefore significantly improved. Series of simulation instances of the graph coloring problem are tested. And the results show that the QACA is a feasible, effective and versatile method for solving the graph coloring problem. |
| |
| Keywords: | graph coloring ant colony algorithm quantum computing quantum-inspired ant colony algorithm |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
