摘要
Steiner最小树问题是组合优化中一个经典的NP难题,本文在蚁群算法的基础上结合量子计算提出一种求解欧氏Steiner最小树问题的量子蚁群算法.将量子比特、量子逻辑门以及Grover量子算法引入到蚁群算法中去,有效提高了算法的全局搜索能力,搜索速度也有显著的提高.一系列数据实例计算与比较表明,量子蚁群算法较蚁群算法在Steiner最小树问题的求解上具有更好的性能.
The Steiner tree problem is a typical NP-hard problem in combinatorial optimization. A quantum- inspired ant colony algorithm （QACA） for solving Euclidean Steiner minimum tree （ESMT） problem is pro- posed hereof based upon the combination of ant colony optimization and quantum computing. With the ant colony algorithm （ACA）, quantum bits, quantum logic gates and the Grover＇s algorithm combined, the capacity as well as the velocity of the algorithm for global search undergoes significant improvability. The computational comparisons of a series of numerical examples show that the QACA has a better performance than the ACA for solving the ESMT problem.
出处
《系统工程学报》
CSCD
北大核心
2012年第4期467-473,共7页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(70871081)
上海市重点学科建设资助项目(S30504)
关键词
欧氏Steiner最小生成树
蚁群算法
量子计算
量子蚁群算法
Euclidean Steiner minimum tree
ant colony algorithm
quantum computing
quantum-inspired ant colony algorithm
