基于量子优化的人工蜂群算法求解旅行商问题

摘要

旅行商问题(TSP)是在运筹学界研究了近半个世纪的基本组合优化模型.它属于NP难问题.已经证明,相对于解决诸如TSP的NP难问题的传统方法,进化算法是有效且高效的.文章提出了一种基于量子激励的人工蜂群算法(QUABC)进行求解旅行商问题.在人工蜂群(ABC)优化和量子计算(QC)原理两种范式之间进行了混合.利用量子比特、态叠加和量子干涉等量子概念,并在经典的ABC算法的基础上加入量子表示的解,增强了标准ABC算法的多样性和计算能力.在一组TSPLIB的算例中对该算法进行了测试,实验结果表明,该算法能获得比较理想的结果.