甘泉，王启明，时合生

基于非合作博弈模型的量子蚁群算法

甘泉，王启明，时合生

针对量子蚁群算法求解组合优化问题时易陷入局部最优和收敛速度慢的问题，提出一种基于非合作博弈模型的量子蚁群算法（quantum ant colony algorithm based on non-cooperative game theory，NGQACA），采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够产生最大效益，并得到了相应博弈过程的纳什均衡。利用三个典型的标准测试函数对此算法进行实验测试，实验结果表明本文基于非合作博弈模型的量子蚁群算法的收敛精度和稳定性均要优于量子蚁群算法（quantum ant colony algorithm，QACA）和蚁群算法(ant colony algorithm，ACA)。

非合作；博弈论；蚁群算法；位置变异；函数分析

0 引言

博弈论的最大特点是能够为相应的博弈过程找到纳什均衡点，而纳什均衡点也正是策略的最优点[1]。非合作博弈经常用于分析解决这种问题并且纳什均衡解被认为是这种博弈的解[2-3]。即使非合作博弈模型的主要目的是为了最大化所有次级用户的收益，根据所有次级用户采取的均衡解，主用户的收入也同样会被最大化[4-7]。针对量子蚁群算法求解问题的不足，根据博弈论的思想，本文提出一种基于非合作博弈模型的量子蚁群算法，采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够产生最大效益，并得到了相应博弈过程的纳什均衡。该算法设计扩大解的搜索空间，改善种群信息结构，避免搜索陷入局部最优。并将该算法与目前比较常用的一些算法进行了比较，结果表明该算法具有更好的收敛速度。……