第36卷 第14期 Vo己36 No．14 计算机工程 Computer Engineering 2010年7月 July 2010 ·人工智能及识别技术· 文章编号z l硼卜。428(20lo)14珈16扣m 文献标识码：A 中圈分类号：TPl8 基于改进蚁群算法的纳什均衡求解 壬志勇1，韩旭1，许维胜1，杨继君2 (1．同济大学电子与信息工程学院，上海201804；2．同济大学经济与管理学院，上海201804) 囊曩：在基本蚁群算法寻优机制的基础上，提出一种用于求解有限n人非合作博弈的纳什均衡解的改进蚁群算法。在全局搜索中，引入 遗传算法中的交叉和变异操作提高算法的拿局搜索能力。在局部搜索中，嵌入动态随机搜索技术使算法加速收敛到最优解。并通过引入控 制步长调整随机搜索向量，保证蚁群始终在混合策略空间内。算例测试结果表明，与传统的遗传算法相比，该算法具有更好的计算性能。 关嘲：蚁群算法；非合作博奔；纳什均衡 Nash Equilibrium Solution Based on Improved Ant Colony Algorithm WANG Zhi-yon91，HAN Xul，XU W：ei-shen91，YANG Ji-junz (1．School ofElectronics and Information Engineering，Tongji University,Shanghai 201804； 2．School of Economic&Management．Tongji University,Shanghai 201 804) [Abstractl This paper presents an improved ant colony algorithm for solving Nash equilibrium of n persons’non-cooperative games，using the basic principle of ACO algorithm．In the global search phase．crossover operation and mutation operation of GA眦incorporated to improve global exploring ability．During the local search phase，dynamic random search technique is embedded tO accelerate the convergence to the optimal solution．and the random search vector is aajusted by controlling step length to ensuI℃search in the mixed strategy profile space．Numerical experiments show that the proposed algorithm has better performance than the traditional genetic algorithm． [Key wordsl ant colony algorithm；non-cooperative game；Nash equilibrium 1概述 的进化思想，将这种方法拓展到纳什均衡的求解问题中。 博弈论已经渗透到国民经济的各行各业，特别是为政府、 2问题描述 企业和个人决策提供了一套有力的分析工具。纳什均衡求解 假设一个有限盯人非合作博弈，局中人i(1≤f≤九)的纯 问题是博弈论中的一项重要研究内容。John Nash于20世纪 50年代首先提出了“纳什均衡”的概念，并证明了纳什均衡 解的存在，但他并没有提供一种统一的求解纳什均衡解的方 法。目前的几何图形算法、Lemke—Howsom算法和同伦路径 法在纳什均衡求解中都存在一定的局限性。 生物群体内个体的合作与竞争产生的群体智能为博弈论 中纳什均衡求解问题提供了一条新的解决途径。人们可以从 群体智能的角度来模拟经济模型中参与人的决策行为，用自 然界中的生物进化理论与生物行为规律去分析和解决博弈论 中纳什均衡问题。文献111将遗传基因理论引入到博弈问题的 计算中，提出了一种求解n人非合作博弈的纳什均衡解的遗 传算法，但是算法中二进制编码存在冗余，求解效率不高。 文献【2】探讨了不同的群智能计算方法在求解纳什均衡解中 的计算性能。文献【3】将“Repulsion”技术和“Stretching”技 术融入到粒子群算法中用于求解多个纳什均衡解问题。文 献【4】为求解纳什均衡设计了一种粒子群优化算法，通过初始 粒子的可行化以及迭代步长的控制，避免了无效解的产生， 策略集为有限集，记作S‘=(《，s：，…，《)，共混合策略为 一=(彳，毫，…。《)，且J：满足‘≥0，艺工净1。即：局中人 尸I i以工i，的概率选择纯策略s：(1≤J≤M)，那么博弈的混合局 势可记为x=(工1，工2，…，，)，在此混合局势下，局中人i的支 付期望为E(x)=芝芝…叁只(s：，％，…，屯域吒…．，其中， 付期望为E(x)=艺艺…￡只(s：，5∥一，sf．域工^…『-，其中， n2 2选择 只(s：。％，…，s：)是在i-局=1中人l选2择s：、局中X人n2 ji、……、局中人，l选择s：时局中人i的收益。 2 n 特别地，对于二人双矩阵博弈F(x。y；A，曰)，A、B分别 为局中人1和局中人2的mXn维支付矩阵，在混合局势(工，y) 下，局中人l和局中人2的收益分别为 巨(工，y)=xAyl，易(工，y)=xnyl 定义1混合局势x’是有限n人非合作博弈的一个纳什 均衡解，如果x’满足E(x’¨j‘)≤巨(x。)，其中，x‘¨工‘表 示只有局中人i把混合局势x’中自己的策略替换为了‘，其他 提高了粒子群的搜索效率，但是种群进化过程缓慢。 局中人的混合策略不变。 蚁群优化算法是由意大利学者Dorigo等人于20世纪 性质混合局势x‘是有限H人非合作博弈的一个纳什均 90年代初首先提出的p1，它由自然界中蚂蚁的觅食行为抽象 而来，是一种新型的群体智能进化算法。蚁群算法已经成功 基金疆日：国家自然科学基金资助项目(70871091) 作者筒介：壬志勇(1984一)，男，硕士研究生，主研方向：优化算法， 地应用于货郎问题、二次分配问题、车辆路径问题等离散空 智能控制；韩旭，博士；许维胜，教授、博士、博士生导师； 间优化领域上。目前国内一些学者将蚁群算法向连续空间进 杨继君，博士 行延伸，已经取得一定的成果m母‘。本文借鉴了基本蚁群算法 --16t卜一 收藕日期：2010-02·23 E-nlail：wzyl9840102@163．corn ˝ • ‰ ˚ 

衡解的充分必要条件是：对任意局中人i的每个纯策略 芝月名0，i=l，2，…，行，算法中每只蚂蚁按照公式 s：U=l，2，…，嘲)，其中，％是局中人i的纯策略个数，都有： ，=l 臣(x‘l|s：)≤E(x‘) i=1，2，…，盯 特别地，对于双矩阵博弈，混合局势(x‘，J，‘)为双矩阵博 弈厂的纳什均衡解的充分必要条件为【l oJ 4．J，“≤x。。和” i=l，2，…，，玎 x‘置，≤x‘J印” J=l，2，…，疗 3改进蚁群算法的设计 将蚁群算法拓展到纳什均衡求解问题，需要先对基本蚁 群算法进行必要的延伸和修改。每只蚂蚁首先进行全局大范 围搜索。然后在各自的邻域范围内进行局部随机搜索，得到 局部最优解。完成一次进化后，每只蚂蚁根据各自所在位置 更新信息素强度。 3．1全局搜索 各蚂蚁根据当前的信息素强度和适应度函数计算转移概 率，并按式(2)、式(3)生成子代蚁群。 定义2根据文献[4】，定义蚁群算法的适应度函数如下： ，(x)=Xmax{E,(x II s：)一EAX)，olJ=l，2，…，mi} E=I ■(g+1)=xj(g)+叫·R‘进行迭代搜索，t=l，2，…，历(tY／为蚁 群规模)，其中，w{∈【o，1】是使得墨(g+1)保持在Q= {xk≥o，i=l，2，…，刀；．，=l，2，…，他}内的最大步长，则可保证 蚁群在进化过程中始终保持在博弈的混合策略组合空间内。 上述定理证明思路见文献【4】，在此限于篇幅不加赘述。 动态随机搜索技术：该技术可解决算法的慢收敛性，改 善算法的寻优性能，从全局搜索过程中得到的解出发，通过 缩小随机搜索空间进一步得到在该解邻域内的最优解或结果 更好的近似解。它的核心思想是：在[一r'r】之间产生一组随 机向量用来调整变量的移动步长，r随着迭代次数的增加不 断减小，得到的解也越来越精确…J。 具体的搜索规则如F； Stepl k卜0，Set gMax，ro； Step2 g÷-O；Load Xbcn，fbc“；XⅫ∞l=Xb。n Step3 Generate R random vector within【-rt，rk】range Step4 fn。=f(x。一。l+R) If f：哪GenMax或者当前最优解达到指定精度要求则 ■(g+1)=墨(g)+R。 (4) 停止，否则转(4)输出最优解。 其中，Z(g)表示第g次迭代蚂蚁，搜索到的局中人i的解策 上述算法用Matlab7．6语言编程，在PC系列微机的 略；R。表示[_，’r】之间的一组随机搜索向量。 根据文献【4】，有以下定理： Windows XP环境下运行通过。 3．4算法性能评价 定理若初始化的每只蚂蚁在混合策略组合的空间内，即 作为一种仿生优化算法，蚁群算法与遗传算法有很多相 兰工≯1，石；≥0，i=l，2，…，撑，且随机搜索向量掣满足 似之处，因此，算法性能的评价可以借鉴由文献【12】为分析 遗传算法性能而提出的定量分析方法。本文以离线性能来衡 一167— ˝ • ‰ ˚ 

量算法性能的优劣。 该博弈的唯一纳什均衡解为(113，113，1／3；1／3，I／3，l，3)。文 定义5设￡(j)为环境e下策略5的离线性能，厂(f)为 献【l】采用的遗传算法计算400代后得到纳什均衡解。本文算 蓟f代为止相应于环境e的最佳适应度，则有 法平均进化73代即得到该博弈的近似解(o．333 3，0．333 3， (6) 0．333 3：O．333 3，O．333 3，0．333 3】。 在图l一图3中，GA曲线是遗传算法的离线性能，ACO 曲线是改进后蚁群算法的离线性能。可以看出，改进后的蚁 群优化算法优于遗传算法，表现出更好的收敛性能。 圈1 ACO与GA求解博奔矩阵f的膏线性酋比较 暮 掣 卷f 艇 ■2 ACO与GA求解博彝矩阵厂2的膏线性嚣比较 翟 掣 舞 谴 ■3 ACO与GA求解博彝矩阵正的膏线性能比较 5结束语 蚁群算法自提出以后已得到越来越广泛的应用。本文借 鉴了经典蚁群算法的基本思想。在局部搜索与全局搜索上做 了适当改进，将其应用于求解有限_r1人非合作博弈的纳什均 衡解的问题中。仿真结果表明，该算法能很快收敛到精度较 高的近似解，较之遗传进化算法，表现出更好的计算性能和 求解效率。进一步的工作是对该纳什均衡求解算法的收敛性 证明以及相关参数设置的深入研究。 参考文献 …陈士俊，孙永广，吴宗鑫．一种求解Nash均衡解的遗传算法【J】． 系统工程，2001，19(5)：67—70． 121 Pavlidis N G Parsopoulos K E，Vrahatis M N．Computing Nash Equilibria Through Computational Intelligence Methods[J]．Journal ofComputational andApplied Mathematics，2005．175(1)：113—136． 【3】Parsopouios K E，'Vrahatis M N．On the Computation of All Global Minimizers Through Particle Swarm OptimizationlJ]．IEEE Transactions On Evolutionary Computation，2004，8(3)：21 1-224． 【4J余谦，壬先甲．基于粒子群优化求解纳什均衡的演化算法【J1． 武汉大学学报：理学版，2006，52(1)：25—29． (下转第171页) E(s)=圭∑，‘(t) 1 r 』t=l 即离线性能表示了算法运行过程中各进化代的最佳性能 的累积平均，反映的是算法的收敛性能。 4数值算例 本文选取3个双矩阵博弈问题，采用上述算法求解其纳 什均衡解，5次计算结果如表l一表3所示。选取第5次计算 的结果画出本文算法求解这3个博弈问题的离线性能，并与 遗传算法的求解结果相比较。 表1博彝矩阵f求解结果 表2博彝矩阵f求解结果 计算次数 进化代数 适应鹰甬致最优值 47 45 46 45 48 6．424 7e．5 9．647 9e．5 B．147 0e一5 7．203 lc．5 7 978 2e．5 表3博弈矩阵f求解结果 参数设置：取蚂蚁规模m为20，精度要求为10_4，最大 进化代数GenMax为1 000、gMax=10、巴=0．2、b=0．5、 碉1选取文献【131中的三维双矩阵博弈 f兰，其支付矩阵如下： ^=㈧蜂㈥ 均进化81代后得到该博弈的纳什均衡近似解 仞2求解文献【141中的双矩阵博弈厂2兰，其支付矩阵如下： 如=[；i|]如㈥ 平均进化46代后得到该博弈的唯一纳什均衡解 仞3考虑文献111中的三维双矩阵博弈厂3-----．，其支付矩阵如下： ^=㈧弦㈥10 小l：埘耻∽_ ～168一 ˝ • ‰ ˚ 

(6)入度大于等于2的节点的处理 检查链路列表中每一个节点是否有入度大于等于2的， 即2条或2条以上链路的尾节点是否相同，如果存在相同的 尾节点，=ISame并且不是Null节点的链路J=JSame，则在 节点表格中新增加一个Null节点，节点编号为 ，=lMaxNum，插入一条链路J=JMaxNum，其中， S=IMaxNurn；E=ISame。把链路编号表格中所有￡=ISame 分别改成E=IMaxNum，IMaxNum=IMaxNum+1 o (7)在节点列表中将节点编号，=M修改成，=IMaxNum。 把链路列表中所有S=M和E=M分男q改成S=lMaxNum和 E=1MaxNum。 在firststepnet．txt中，按照节点插入算法，插入节点 W=d5，修改后的识别网络为finalnet．txt，语音识别网络如 图5所示。 4实验 实验采用的训练集和测试集都是前面所建立的语料库。 特征参数为13维的MFCC(MFCC—E—A—D)，包括12阶的频 谱值加上对数能量，并取其一阶差分和二阶差分，共39维。 选择音节作为识别单元，状态数取6，并采用1个Stream， 搭建汉语连续数字串识别系统。使用原始语音识别网络和优 化后的语音识别网络分别测试该识别系统100次，每次识别 45旬连续数字，其在测试中所花的时间如表4所示。 表4时问复杂度比较 一般地，FA是从识别语言甸子的角度定义语言，原识别 网络对应NFA，优化后的识别网络是DFA。在每一步，NFA 可能处于若干状态，而DFA只能处于一个状态。由于对于任 (上接第168页) 意给定的NFA，存在一个DFA与之等价pJ，将NFA化为等 价的DFA，也就是将NFA的“树状”计算变成DFA的“线 状”计算【5J。因此，避免了搜索时因不可达所导致的“回溯 (回过头来，重新进行选择)”所用的时间，从而提高了系统 的效率。 在连续语音识别中，使用优化后的语音识别网络来减少 搜索时间是呵行的。将待识别的语句与自动机联系起来，应． 用自动机理论的知识来指导原始语音识别网络的优化，然后 用实验证明了它的正确性。由于只是为了测试识别网络对语 音识别系统的影响，因此测试所用到的语音与训练所用到的 语音数据是一样。通过表4可以看出，在保证识别效果的前 提下，优化后的语音识别网络识别100次所花的时间为 83．031 s，比原始语音识别网络少花了9．578 s。 5结束语 大词汇量连续语音识别系统是语音识别 技术应用的一个发展方向，主要应用于基于 PC处理平台的听写机以及与电话网或者互 联网相结合的语音信息查询服务系统。这些 系统都需要较大规模的运算平台实现，如果 在该系统中应用优化后的语音识别网络，将 会减少系统运行时Viterbi搜索的搜索空间 和计算量，从而大大提高系统的执行速度，对于那些对系统 的实时性有要求的系统，无疑也是有益的。 参考文献 【l】Young S，Evermann G Gales M．The Hidden Markov Model Toolkit[EB／OL]．f2005—10—20)．http：／／htk．eng．cam．ac．uk／． 【2】Jang R．Audio Signal Processing and Recognition[Z]．(2009—05·30)． http：Hneural．CS．nthu．edu．tw／jang／books／audioSignalProcessing／． 【3】蒋宗礼，姜守旭．形式语言与自动机理论[M】．2版．北京：清华 大学出版社，2007． 【4】陈文字，欧齐，程炼．形式语言与自动机【M】．北京：人民邮 电出版社，2005． ． 【5J张立昂．可计算性与计算复杂性导引【M】．2版．北京：北京大学 出版社，2004． 编辑索书志 【5】Dofigo M，Gambardella L M．Ant Colony System：A Cooperative Mathematics and Computation．2009，21 1(1)：75·84． Learning Approach to the Traveling Salesman Problem[J1．IEEE 【10】谢政．对策论【M1．长沙：国防科技大学出版社，2004． Transactions on Evolutionary Computation，1997，1(1)：53-66． f6】马良．基于蚂蚁算法的函数优化【J】．控制与决策，2002，17(Z1)： 7 19—726． 【7】Drto J，Siarry P．An Ant Colony Algorithm Aimed at Dynamic Continuous OptimizationlJl．Applied MathematiCS and Computation， 【1 1 1 Hamzacebi C．Improving Genetic Algorithms’Performance by Local Search for Continuous Function Optimization[J]．Applied MathematiCS and Computation，2008，196(1)：309—317． 【12】Dejong K A．Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]．Ann Arbor,USA：University of Michigan， 2006，181(1)：457·467． 1975． 【8】Krzysztof S，Dongo M．Ant Colony Optimization for Continuous f13】Weibull J w．Evolutionary Game Thoory[M]．Cambridge，MA, DomainsIJl．European Journal of Operational Research，2006， USA：MIT Press，t995． 185(3)：1155一1173． 【14】Gibbons R．A Primer in Game Theory[M]．New York,USA： 【9】Baskan O，Haldenbilen S，Ceylan H．A New Soluton Algorithm for Harvester Wheatsheaf,1992． Improving Performance ofAnt Colony OptimizationiH．Applied 编辑任吉慧 ～171— ˝ • ‰ ˚