基于非合作博弈模型的量子蚁群算法-论文.pdf

《基于非合作博弈模型的量子蚁群算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Micr0computerAppIicati0nsVo1．31，No．6，2015研究与设计微型电脑应用2015年第31卷第6期文章编号：1007—757X(2015)06—0026—03基于非合作博弈模型的量子蚁群算法甘泉，王启明，时合生摘要：针对量子蚁群算法求解组合优化问题时易陷入局部最优和收敛速度慢的问题，提出一种基于非合作博弈模型的量子蚁群算法(quantumantcolonyalgorithmbasedonnon-cooperativegametheory，NGQACA)，采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够

2、产生最大效益，并得到了相应博弈过程的纳什均衡。利用三个典型的标准测试函数对此算法进行实验测试，实验结果表明本文基于非合作博弈模型的量子蚁群算法的收敛精度和稳定性均要优于量子蚁群算法(quantumantcolonyalgorithm，QACA)和蚁群算法(antcolonyalgorithm，ACA)。关键词：非合作；博弈论；蚁群算法；位置变异；函数分析中图分类号：TP393文献标志码：AQuantumAntColonyAlgorithmBasedonNon—cooperativeGameTheoryGanQuan，WangQiming，ShiHe

3、sheng(SchoolofComputerScienceandTechnologyDepartment，PingdingshanUniversity,Pingdingshan467002，China)Abstract：QuantumantcolonyalgorithmiSeasytofallintothesituationoflocaloptimumandslowconve唱enceratewhensolvingcombinatorialoptimizationproblem．Thispaperputsforwardaquantumantcolo

4、nyalgorithmbasedonnon·cooperativegametheory(NGQACA)．Adoptedinthisalgorithm，therepeatedgamemodelcanproduceagamesequencetomakeeverygameproducemaximumbenefit，andthenitcaI1getthecorrespondinggameprocessofNashequilibrium．Thetheretypicaltestfunctionsareusedfortestingtheperformanceof

5、NGQACAalgorithmoptimization．TheexperimentalresultsshowthattheconvergenceprecisionandstabilityofNGQACAarebetterthanQACAandACAalgorithm．Keywords：Non—cooperative；GameTheory；AntColonyAlgorithm；PositionVariationFunctionAnalysis0引言不同模型，分别称之为蚂蚁循环系统(ant—cyclcsystem)、蚂蚁数量系统(ant—quantit

6、ysystem)、蚂蚁密度系统博弈论的最大特点是能够为相应的博弈过程找到纳什(ant—densitysystem)[10-15]。它们的差别在于公式的不同均衡点，而纳什均衡点也正是策略的最优点[II。非合作博弈在蚂蚁数量系统模型中如公式(1)：经常用于分析解决这种问题并且纳什均衡解被认为是这种Ie博弈的解_2_]。即使非合作博弈模型的主要目的是为了最大化所有次级用户的收益，根据所有次级用户采取的均衡解，△){若蚂蚁在时刻研眦州之间经过，主用户的收入也同样会被最大化[4·7J。针对量子蚁群算法求解问题的不足，根据博弈论的思想，本文提出一种基于非合作博

7、弈模型的量子蚁群算法，采用重复博弈模型，在重复博弈中产生一个博弈序列，使得每次博弈都能够产生最大效益，并得到了相应博弈过程的纳什均衡。该算法设计扩大解△c={若蚂蚁在时刻研口t+l之间经过(i，j)(2)的搜索空间，改善种群信息结构，避免搜索陷入局部最优。并将该算法与目前比较常用的一些算法进行了比较，结果表这3种模型的区别在于后两种模型中利用的是局部信明该算法具有更好的收敛速度。息，而前者利用的是全局信息，经过实验对比，在求解问题时蚂蚁循环系统性能较好，因而本文采用它作为基本模型。1量子蚁群算法算法停止条件可以用固定循环次数或者当解的变化不明显时便

8、停止计算。一量子蚁群算法是基于量子计算原理的一种蚁群算法，将基本蚁群算法实现步骤如下：量子计算与蚁群算法相结合的量子蚁群算