第８期加０９年８月
电子学报
ｖ０１．３７Ｎｏ．８
ＡＣＴＡＥＵ￡ＣｒＲＯＮＩＣＡｓｌＮＩＣＡ
Ａｕｇ．２００９
蚁群算法的几乎处处强收敛性分析
苏兆品１．－，蒋建国１，一，梁昌勇２，张国富１，３，１，夏
娜１・３
（１．合肥工业大学计算机与信息学院，安徽合肥２３０（１０９；２．合肥工业大学管理科学与工程博士后科研流动站，安徽合肥２３０００９；
３．安全关键工业测控技术教育部工程研究中心，安徽合肥２３０００９；４．特种显示技术教育部重点实验室，安徽合肥２３０００９）
摘要：蚁群算法是一种新型的模拟进化算法，已在很多组合优化问题中得到成功应用，但其收敛性分析还比
较缺乏．以ＴＳＰ问题来描述一类蚁群算法的数学模型，并通过对状态空间的分解和反射壁的构筑，从鞅理论角度论证了该类蚁群算法的几乎处处强收敛性以及能在有限步内收敛到全局最优解集，试图为蚁群算法的研究探索一条新的思路．
关键词：
蚁群算法；Ｍａｌ＇ｋｏｖ过程；鞅；几乎处处强收敛
文献标识码：
Ａ
中图分类号：ＴＰ３０１文章编号：０３７２—２１１２（２００９）０８．１６４６－０５
ＡｎＡｌｍｏｓｔＥｖｅｒｙｗｈｅｒｅＳｔｒｏｎｇＣｏｎｖｅｒｇｅｎｃｅＰｒｏｏｆｆｏｒ
ａ
ＣｌａｓｓｏｆＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍｓ
ＳＵＺｈａｏ－ｐｉｎｌ，２，ＪＩＡＮＧＪｉａｎ．ｇＬｌ０１，３，ＬＩＡＮＧＣｈａｎｇ－ｙｏｎ９２．ＺＨＡＮＧＧｕｏ－ｆｕｌ，３，４ＸＩＡＮａｌ＇３
（１．Ｓｃｈｏｏｌｏｆ
２．ＰｏｓｔｄｏｃｔｏｒａｌＰｒｏｇｒａｖｕ
３．ＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈ
ｍ讹Ｍ删蜘ａｎｄ
ｉｓ
ａ
ｃ口ｊ砷ａｎｄＩｎｆｏｒｍａｔｉｏｎ，睫向ｗｎｉｖｅｍｔｙｏｆＴｅｄｍｏｌｏｇｙ，均包．Ａｒｄｕｌｉ
Ｅｎｇｍｅｍｎｇ。Ｈｅｆｅｉ
ａｎｄ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆＴｅｃｈ咖，Ｈ４ｅｉ，Ａｎｈｕｉ
２３０００９，Ｃｈｉｎａ；
２３∞０９，Ｃｈｉｎａ；
Ｃｅｎｔｅｒ矿ｓＣ日ｔｙＣｒｉｔｉｃａｌＩｎｄｕｓｔｒｉｄＭｅａｓｕｒｅｍｅｎｔ
４．ＮａｔｉｏｎａｌＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈ
ＣｏｎｔｒｏｌＴｅｄｍｄｏｇｙ，Ｍｉｎｉｓｔｒｙ
ｏｆＥｄｕｃａｔｉｏｎ，Ｈ４ｅｉ，Ａｎｈｕｉ２３００（）９，Ｏｌｉｎａ
Ｃｅｎｔｅｒ矿Ｓｐｅｃｉａｌ删叫町Ｔｅｄｍｏｌｏｇｙ，随痧。Ａｎｌｕｄ
２３０００９，‰）
Ａｂｓｔｒａｃｔ：ｍａｎｙｃｏｍｐｌｉｃａｔｅｄｏｆ
ａ
ＡｎｔＣｏｌｏｎｙ
Ｏｐｔｉｍｉ碰ｏｎ
ｎｏｖｅｌ
ｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｗｈｉｃｈｈａｓｂｅｅｎｕｓｅｄｓｕｃｃｅｓｓｆｕｌｌｙ
ｔｏｓｏｌｖｅ
ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔＪｌｎｉｚａｌｉｏｎｐｒｏｂｌｅｍｓ，ｂｕｔｉｔｓｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｉｓｓｅｌｄｏｍｒｅｓｅａｒｃｈｅｄ．Ｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌ
ｓｔａｔｅ
ｃｌａｓｓｏｆ
ａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｓｉｓｄｅｓｃｒｉｂｅｄｂｙＴｓＰｒ，ｒｏｂｌｅｍ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｅｄｅｃｏｍｐｏｓｉｔｉｏｎｏｆｓｐａｃｅａｎｄｔｈｅ
ｃｏｎｓｔｒｕｅ—
ｄｏｎｏｆｒｅｆｌｅｃｔｉｎｇｂａｒｒｉｅｒ，ａｎａｌｍｏｓｔｅｖｅｒｙｗｈｅｒｅｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｓａｎｄｔｈｅｑｕａｌｉｔｙｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｓｔｅｅｄｌｙｃｏｎｖｅｒｇｅ
ｔｏａ
ｃａｎ
ｇｕａｒａｎ—
ｇｌｏｂａｌｏｐｔｉｍｕｎｌ
ａｎｅｗ
ｓｅｔｉｎａ
ｆｍｉｔｅｉｌｕｍｂｅｒｏｆｓｔｅｐｓ
ａｌｅ
ｄｅｍｏｎｓｔｒａｔｅｄｂｙｕｓｉｎｇｔｈｅｍａｒｔｉｎｇａｌｅｔｈｅｏｒｙ．ａｎｄ
ｔｈｅ曲一
ｔａｉｎｅｄｒｅｓｕｌｔｓｍａｙｐｒｏｖｉｄｅｍｅｔｈｏｄｏｌｏｇｙｆｏｒｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｏｆｔｈｅａｌｇｏｒｉｔｈｍｓ．
Ｋｅｙｗｏｒｄｓ：
ａｎｔ
ｃｏｌｏｎｙ０ｐｔｊｌ面ｚａｌｉｏｎ；Ｍａｒｋｏｖｐｒｍ．ｚ．ｓｓ；ｍａｒｔｉｎｇａｌｅ；ａｌｍｏｓｔｅｖｅｒｙｗｈｅｒｅｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅ
ｌ引言
Ｏｐｔｉｍｉｚａｔｉｏｎ）［１３是模拟自然界
中真实蚁群的觅食行为而形成的一种新型的启发式模
Ｃｏｌｏｎｙ
能算法【６－８ｊ还比较缺乏，在一定程度上制约了蚁群算法的进一步改进和发展．虽然已有部分学者给出一些收敛性结论旧“引，但都是在概率收敛意义下考虑的，主要还是基于Ｍａｒｋｏｖ过程和算法的遍历性展开的研究，在分析手段和方法上尚比较单调．Ｇａｔｊａ“引首先利用图论对蚁群算法的收敛性进行了研究，并提出了基于图的蚂蚁系统（Ｇｒａｐｈ．ｂａｓｅｄＡｎｔＳｙｓｔｅｍ，ＧＢＡＳ），适用于各种静态组合优化问题，但是在ＧＢＡＳ算法中，对于某个事先给定的概率，无法确定蚂蚁数和蒸发系数，从这个意义上讲，ＧＢＡＳ是不可控的．为了克服上述问题，Ｃｉｉｔｊａｈｒ［１０ｔｌｌｊ将ＧＢＡＳ发展成ＧＢＡＳ／ｔｄｅｖ和ＧＢＡＳ／ｔｄｌｂ（－－般统称为ＧＢＡＳ算法），并利用Ｍａｒｋｏｖ过程理论证明其能以概率１收敛
蚁群算法（Ａｒｔ
拟进化算法，它采用具有记忆的人工蚂蚁通过个体之间的交互和协同工作来搜索从蚁穴到食物源的最短路径．
目前蚁群算法已在旅行商（Ｔｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂ．
１ｅｌＩｌ’ＴＳＰ）、指派（ＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ，ＡＰ）及联盟生成（ＣｏａｌｉｔｉｏｎＧｅｎｅｒａｔｉｏｎＰｒｏｂｌｅｍ，ＣＧＰ）等一系列组合优化问题中得到成功应用［２－４］，但这些研究大都从实验的角度说明了蚁群算法的有效性ｂＪ，而有关蚁群算法的一般收敛性，如概率收敛、几乎处处收敛等的分析相比其他智
收稿日期：２００８—１２－２９；修回日期：２００９－０２．１２
基金项目：国家教育部博士点基金（Ｎｏ．２００６０３５９００４）；安徽省自然科学基金（Ｎｏ．０９０４１２０５８，０７０４１２０３５）；特种显示技术教育部重点实验室开放课题基金（№．２００８ＨＧＸＪ０３５０）；合肥工业大学博士专项科研资助基金（Ｎｏ．ＧＤＢＪ２００９—００３）
万方数据
第８期苏兆品：蚁群算法的几乎处处强收敛性分析
１６４７
到问题的最优解，具有较强的说服力．Ｓｔ删ｅ［１２］，Ｂ“１３】
和朱庆保¨４１等主要利用代数理论研究蚁群算法的收敛性，但相比Ｇｆｉｔｊａｈｒ，他们的证明过程显得比较弱化，说服力不够．段海滨１１５Ｊ尝试用鞅理论研究了基本蚁群算法（Ｂａｓｉｃ
Ａｎｔ
Ｃｏｌｏｎｙ
Ａｌｇｏｒｉｔｈｍ）的几乎处处收敛问题，但
其忽视了一个很重要的方面，即信息素浓度ｒ（矗）本身
并不是Ｍａｒｋｏｖ过程，在没有路径形（＿ｊ｝）的情况下，ｒ（１｜｝）不是自包容的（ｓｅｌｆ－ｃｏｎｔａｉｎｅｄ）ｍ．１１Ｉ，因此其证明过程和结论均值得商榷．
定义１【１６Ｊ设序列｛噩，ｌ｜｝＞１０｝的全局最优解集为Ｖ算∈ｓ，“菇’）≤八ｚ）｝，如果．１ｉｒａＰ｛瓦ｃｆ’｝＝１，则称｛瓦，ｋ１＞０｝依概率收敛到全局最优解集．厂‘，记
Ｄ
为五二彳。；如果Ｐ｛ｌｉｒａ（五ｃｆ＋）｝＝１，则称｛五，尼≥
０｝几乎处处强收敛到全局最优解集．厂’，记为冠当
由上述定义可知，依概率收敛属弱大数律范畴，而几乎处处收敛性明显强于依概率收敛性．因此，本文在Ｇｃ，ｔｊａｈｒ等人的工作基础上进一步研究蚁群算法的几乎处处强收敛性，我们避开使用传统的遍历性分析，而是在Ｍａｒｋｏｖ过程分析中运用鞅理论［１７］对算法进行具体分析，试图为这方面的研究探索一条新的思路．２算法模型
蚁群算法最早是用于求解ＴＳＰ问题怛Ｊ，不失一般性，为了更好的描述和分析蚁群算法，本文以求解／７，个城市的ＴＳＰ问题为例描述ＧＢＡＳ算法的模型．
定义２
ＴＳＰ可以用７１，个城市的一个有向图Ｇ＝
（Ⅳ，Ａ）表示，其中Ｎ＝｛１，２，…，ｎ｝，Ａ＝｛（ｉ，＿『）Ｉｉ，．『∈Ⅳ｝；城市间的距离Ｄ＝（也）。。。；目标函数为
—Ｌ
“形）＝∑ｄ／ｌ－１ｉｆ
（１）
其中形＝｛ｉ１，ｉ２，…，‘｝为城市１，２，…，ｔｔ的一个排列，且ｆ。＋ｌ＝ｉｌ，形中的节点构成的弧集为彬。＝｛（ｉ。，ｉｑ＋１）Ｊｉｑ∈形，ｑ＝１，２，…，疗｝．
根据上述定义，ＧＢＡＳ算法可以描述如下：
①初始化：为上述ＴＳＰ图中的每一条弧（ｉ，ｊ）赋信
１
息素浓度初值ｒＯ－（ｏ）＝斋，Ｖ（ｉ，』）∈Ａ，ｍ只蚂蚁从
同一城市ｉｏ出发．矗＝１，当前最好解为形＝｛１，２，…，／７，｝．
②外循环：如果满足算法的停止规则，停止计算并输出计算得到的最好解；否则，让蚂蚁ｓ（１≤ｓ≤ｍ）从起点ｉｏ出发，用￡（ｓ）表示蚂蚁ｓ行走的城市集合，￡
（ｓ）：⑦．
③内循环：按蚂蚁１≤ｓ≤ｍ的顺序分别计算．当蚂
万方数据
蚁ｓ在城市ｉ，若￡（ｓ）＝Ⅳ或｛ｆｆ（ｉ，ｆ）∈Ａ，Ｚ岳￡（５）｝－ｇ，完成第ｓ只蚂蚁的计算；否则，若Ｌ（ｓ）≠Ｎ且Ｔ＝｛ｚｆ（ｉ，Ｚ）∈Ａ，Ｚ《￡（５）｝一｛ｉｏ｝≠（乃，贝４ｓ以概率
铲Ｊ鞘高乐ｒ
ｇ＃：｛奢ｄ（矗一１）。～
㈤（２）
ｔｏ，
ｏｔｈｅｒｗｉｓｅ
到达＿『，Ｌ（ｓ）＝三（ｓ）Ｕ｛＿『｝，ｉ＝＿『；若Ｌ（ｓ）≠Ｎ且ｒ＝｝ＺＩ（ｉ，ｚ）∈Ａ，ｚ薯Ｌ（ｓ）｝一｛ｉｏ｝＿⑦，则ｓ到达ｉｏ，Ｌ（ｓ）＝Ｌ（ｓ）Ｕ｛ｉｏ｝，ｉ＝ｉｏ；重复③．
④信息素更新：对１≤ｓ≤ｍ，若￡（ｓ）＝Ｎ，按照￡（ｓ）中城市的顺序计算路径长度；若Ｌ（ｓ）≠Ｎ，路径长度是一个充分大的数．比较ｔｎ只蚂蚁中的路径长度，具有最短路径的蚂蚁为ｔ．若Ｊｒ（Ｌ（ｔ））≤，（１Ｆ），则形＝Ｌ．
（ｔ）．用下式
《扯｛（１－Ｐｔ－Ｉｋ＠－１）＋舒，（以ｐ∈％
【（１一ＩＤ‘一１）ｒ“（ｋ一１），ｏｔｈｅｒｗｉｓｅ
（３）
更新图中每一条弧的信息素浓度，得到新的ｑ（Ｊ｜｝），ｋ＝Ｊｉ｝＋１，重复②．
注释１Ｌ１０，１１】
式（３）中凤为挥发因子，并且对于
固定的Ｋ≥１满足ｍ≤１一ｉ高告可（矗≥Ｋ）与砉以＝
注释２［１０，１１］用数学归纳法很容易验证式（３）满
足对Ｖ＿ｊ｝≥０，有
∑ｏ（南）＝１
（４）
３收敛性分析
ＧＢＡＳ算法的每步迭代对应随机变量以＝（ｒ（ｋ），
ｇ／（五））（｜｜｝≥ｏ），ｒ（１｜｝）∈Ｒ㈨ｌ为所有弧的信息素浓度；形（知）为／１，个城市的一个排列，最多有ｒ／，！个状态，所以瓦是全状态空间Ｓ＝Ｒｌ＾Ｉ×／Ｖ中的一个元素，显然Ｉ
Ｓｌ
是有限的．
３．１依概率收敛
引理１［１１】
由状态五＝（ｒ（七），肜（Ｉ｜｝））（后≥０）所
构成的随机过程是离散时空上的有限非齐次Ｍａｒｋｏｖ过
程．
证明由Ｍｍ＇ｋｏｖ过程的性质可知，只要证明状态
五＋，的分布仅仅依赖于状态冠．注意到在第后次迭代中，第ｓ只蚂蚁的转移只由ｒ（矗一１）决定，且其行走的路径和形（＿｜｝一１）共同决定了形（七），再通过式（３）的更新原则可以进一步得到ｒ（Ｊｊ｝）．因此，状态五＋１的变化仅由五决定，而与之前的状态无关，这是一个典型的Ｍａｒｋｏｖ过程，而且由上面的分析我们也可以得到单独
ｆ‘＝｛石’Ｉ．｛４．
１６４８
电
子
的ｒ（矗）或形（∽本身并不是ｌ～Ｉａｒｋｏｖ过程，因为ｒ（后）或形（”本身不是自包容的．
设｛瓦，ｋ≥ｏ｝的一步状态转移概率为Ｐ（惫），Ｂ＝｛（ｉ口，ｉｇ＋１）Ｉｉ口∈形（七＋１），ｑ＝１，２，…，Ｔ／，｝，Ｔ。＝…（ｉ，Ｚ）∈Ａ｝，对Ｖ茗，’，∈Ｓ，我们有Ｐ（ｋ）＝Ｒ（丑＋１：ｙＩ凰＝戈）
一ＴＴ
玉！１２
一（土是口∑．Ｉ＂ｉｌ（七）一【＝ｏ，ｏｔｈｅｒｗｉｓｅ
一』＞ｏ，八形（１｜｝＋１））≤以形（＿｜｝））
（５）
因为ｒ（后）的变化要依赖于ｋ，所以随机状态转移概率Ｐ（＿｜ｃ）与豇有关，该Ｍａｒｋｏｖ过程是非齐次的．
引理２［１１］
Ｍａｒｋｏｖ过程｛丑，居≥０｝能够以概率１
收敛到一个全局最优解ｘ。ｗ－－．（ｒ。，形’），其中形’是Ｇ
中的一条最优路径，形毒＝｛（‘，‘＋ｔ）Ｉｉ，∈形’，ｑ＝１，２，
…，／７，｝，ｒ’定义如下：
争｛高椭埏％
【Ｏ．ｏｔｈｅｒｗｉｓｅ
证明Ｃ，杜ｔｊａｈｒ已在文献［１１］中给出了详细的证明，鉴于篇幅有限，这里不再列出．
命题１
｛凰，＿｜ｌ≥ｏ｝能够以概率１收敛到全局最
优解集ｆ。；｛形。ＩＶ形∈Ⅳ，八形’）≤以形）｝．
证明由引理２可知，｛五，Ｊｊ｝≥０｝能够以概率１收敛到一个全局最优状态工’：（ｒ‘，形‘）∈ｆ’，根据式（２）的状态转移概率和式（３）的信息素更新规则，系统一旦达到ｘ‘，其后续状态只可能在全局最有解集．厂‘中迁移，而不可能迁移到厂＋之外，当Ｊ｜｝一∞时，系统必然收敛到厂’．
３．２相关基本概念
定义３［撕］
称状态空间Ｃ为闭集，若对Ｖｉ∈Ｃ，
有∑＾＝１，即自Ｃ内任意一点出发，始终不能达到Ｃ外的任意状态．
定义４１１６】闭集Ｃ若无真闭子集。则称ｃ为不可约的，否则Ｃ是可约的．
定义５［坫】
设｛Ｋ，七≥０｝与｛五，ｋ≥０｝是随机过
程，称｛Ｋ，ｋ≥ｏ｝关于｛磊，丘＞１０｝是一个上（或下）鞅，如果：
①ＥｌＫｌ＜∞；
②Ｅ（Ｋ＋ｌｚ０，ｚｌ，…，乙）≤Ｋ（或Ｅ（Ｋ＋ｌｚ０，ｚＩ，
…，磊）≥Ｋ）；
③｛玩，．｜ｃ＞１０ｌ是Ｚｏ，ｚｌ’．一，乙的函数．
Ｄｏｏｂ证明了著名的下鞅收敛定理论［１６，１７］，为了分析方便，给出其结论．
引理３【１６】设｛Ｋ，Ｉｊ｝≥０｝是一个下鞅，ｓｑ陋ｌＫｌ＜
万方数据
学报
２００９钜
∞，则存在一个随机变量ｌ，’∈｛圪，矗＞／０｝，使ＥＩ
ｙ’Ｉ＜
∞，且圪当ｌ，。，即Ｐ｛ｌｉｒａＫ＝Ｙ’｝＿１．
引理４【１６Ｊ引理３的结论对上鞅也成立．证明设｛玩，克＞／０｝为上鞅，且ｓｕ凹ＩＫｌ＜∞，则由定义５可知｛一致，ｋ／＞０｝为下鞅，且ｓｕ凹Ｉ一圪｜＿ｓｕ嵋ＩＫＩ＜∞，由引理３可得，存在随机变量一ｌ，。，使得
Ｅｌ—ｙ。Ｉ＝ＥＩ
ｙ’Ｉ＜∞，且Ｐ｛ｌｉｍ（一虼）＝一Ｙ‘｝＝１，
即尸｛ｌｉｍ圪＝Ｙ’｝．１．
■—＋∞
３．３几乎处处强收敛
从直观上说，蚁群算法的目的在于找到一个最优状态五＝（ｒ（｜｜｝），驴（．｜｝）），它带有概率分布ｒ（后）偏向于一个最优排列形（｜］｝），而形（后）又对应最短路径长度．厂（形（ｋ））．因此，我们把式（１）中的目标函数改写为：Ｆ（五：（ｒ（尼），肜（后）））：黜
（ｉ．铤＾‘９”¨
这样设计的好处是兼顾了ｆ（１ｊ｝）和形（．｜｝），从而可以利用噩的Ｍａｒｋｏｖ过程的相关结论，同时又巧妙的利用ｒ（１；）在式（４）中的性质简化了计算．我们以每个状态的路径长度作为指导原则，则由于路径长度达到全局最小当且仅当找到全局最优状态，我们可以利用路径长度函数过程的收敛性来研究蚁群算法的收敛性．另外，我们可以观察到，路径长度的变化是一个单调不增的过程，因此，我们可以设法把随机过程｛，（五），Ｉ｜｝Ｉ＞０｝转变为一个上鞅来考察｛凰，ｋＩ＞０｝的收敛性．
命题２全状态空间Ｓ＝Ｒ｜＾Ｉ×．『ｖ是一个闭集．证明由引理１可知，｛五，后≥０｝为一离散时空上的有限非齐次Ｍａｒｋｏｖ过程，则由Ｍａｒｋｏｖ过程的性质ｕ６Ｊ有Ｖｉ∈Ｓ，∑心＝１，再由定义３可知｜ｓ是一个闭集．
命题３全状态空间Ｓ＝ＲＩ＾ＩＸⅣ是可约的．证明
由命题１和定义３可知，．厂。是有限的闭集，
又ｆ。ｃＳ，由定义４可知ｓ是可约的．
因为Ｓ是可约的，由Ｍａｒｋｏｖ过程的状态空间分解定理［１６Ｊ我们可以很容易把ｓ分解成两部分，一部分为｛五，Ｊ｜｝≥Ｏ｝的收敛空间Ｑ，另一部分为Ｓ—Ｑ，其中Ｑ＝｛五＋１：Ｆ（凰＋１）≤Ｆ（五）｝．
命题４收敛空间Ｑ是一个闭集．
证明
由Ｑ的定义可知，所有满足Ｆ（凰＋１）≤Ｆ
（％）的状态都被限制在Ｑ中，而所有Ｆ（凰＋。）＞Ｆ（五）的状态都被限制在Ｓ—Ｑ中，在Ｑ中不可能找到一个状态满足，（鼍＋１）＞Ｆ（以），即Ｑ中任意一个状态的后继状态只可能在Ｑ中找到，而不可能到达Ｑ外，即
ＶｉＥ
Ｑ，ｆ。善ｐ＝ｏ，所以有Ｖ
ｉ
Ｅ
Ｑ，磊乃＝１，即口为
一个闭集，且ｐｃＳ．
第８期苏兆品：蚁群算法的几乎处处强收敛性分析
１６４９
上述操作的目的是将｛ｘｋ，ｋ≥０｝构成的有限非时齐Ｍａｒｋｏｖ过程限制在其全状态空间Ｓ的闭子集ｐ中，也就是说在Ｑ之外的每一个状态都是反射壁，将其他所有满足，（五＋。）≤Ｆ（墨）的状态约束于此内，由随机过程理论我们知道，这相当于状态的限制运动边界，就像桶的边缘一样（如图１所示）．
反射壁
Ｖ＿：ｒ’Ｅｓ－Ｑ
图１反射墅的构筑
命题５随机过程｛Ｆ（咒），ｋ／＞０｝关于｛丑，后≥０｝是一个非负有界上鞅，即对Ｖｋ≥０，有Ｅ（，（孔＋１）Ｉ蜀，
Ｘｌ，…，以）≤Ｆ（五）．
证明显然｛Ｆ（凰），后≥０｝是非负有界的，根据引理１的Ｍａｒｋｏｖ性，可以得到Ｅ（Ｆ（五＋１）Ｉ蜀，Ｘｌ，…，忍）＝Ｅ（，（噩＋１）Ｉ噩），故我们只需证对Ｖ戈∈Ｓ有
Ｅ（Ｆ（五＋１）Ｉ五＝石）≤Ｆ（髫），矗≥Ｏ
（６）
又根据随机过程理论，有Ｅ（尸（咒＋１）ｌｘｋ＝髫）＝Ｙ，，．Ｆ（，，）Ｒ（孔＋ｌ＝，，ｌ冠＝石），再由Ｆ（五）的定义以及ｒ（ｋ）的性质，我们可以观察到，Ｆ（墨＋１）≤Ｆ（五）与厂（形（ｋ＋１））≤八形（七））是等价的，而这个正好是式（５）中的条件，所以式（５）中的“ｏｔｈｅｒｗｉｓｅ”所限定的状态即为反射
壁，将其他状态约束于条件八形（后＋１））≤八形（后））限
定的状态内，故有
∑，（，，）Ｒ（五＋ｌ＝，，Ｉ丑＝茗）
，∈Ｓ
＝∑，（，，）Ｐｋ（凰＋ｌ＝，，Ｉ凰＝茗）
，∈口
＋∑Ｆ（ｙ）Ｒ（五＋ｌ＝，，ｌ五＝算）
＝∑＇ｒ（ｙ）Ｐｋ（Ｘｋ＋ｌ＝ｙｌ五＝石）＋∑，（ｙ）・０
，∈口
，∈ｓ・口
＝∑Ｆ（），）Ｐｋ（甄＋１＝ｙｌ
ｘｋ＝石）
因为状态茗的任意后继状态，，，满足对Ｖ），∈Ｑ，有Ｆ（恐＋１＝），）≤Ｆ（ｘｋ＝名），所以
∑Ｆ（ｙ）Ｒ（丑＋１＝，，Ｉ五＝茁）≤∑Ｆ（算）Ｒ（五＋１＝，，ｔｘｋ＝重）＝Ｆ（聋）∑Ｒ（噩＋１＝ｙｌ鼍＝茹）
又Ｑ是闭集，所以有吕Ｒ（五＋ｌ＝ｙ
Ｉ五＝茹）＝１．
从而可以得到蓦，（），）＾（噩＋ｌ＝ｙＩ五＝戈）≤Ｆ（茁），即
矽（，，）Ｒ（瓦＋ｌ＝Ｙ
Ｉ墨＝ｘ）≤Ｆ（互）．所以有Ｅ（Ｆ
万方数据
（鼍＋１）Ｉ凰＝髫）≤，（ｚ），式（６）得证，即｛，（五），Ｊ｜｝≥０｝关于｛五，ｊ｝≥Ｏ｝是一个非负有界上鞅．
命题６｛，（五），．｜｝／＞０｝几乎处处强收敛到全局最优解集Ｆ。＝｛ｚ。ＪＶｘ∈５，，（Ｚ。）≤，（ｚ）｝．证明
由命题１可知，｛置，＿｜｝≥０｝能够以概率１收
敛到全局最优解集厂，又，（形’）≤，（形）与Ｆ（ｘ’）≤，（工）是等价的，因此｛，（五），Ｊｊ｝≥ｏ｝能够以概率１收敛到全局最优解集，。，又由命题５可得，｛，（丑），后ｔ＞０｝是一个非负有界上鞅，根据引理４，｛Ｆ（五），矗＞ｔ０｝几乎处处强收敛到全局最优解集，’．４讨论
Ｇｎｔｊａｈｒ证明了ＧＢＡＳ的概率收敛性［９－ｎ］，Ｓｔｌｌｔａｌｅ和
Ｄｏｒｉｇｏ‘１２１分析了诸如ＡｅＳ［２Ｊ和ＭＭＡＳ［１８】等一类ＡＣＯ，。的弱收敛性，但他们的工作大都要求算法迭代次数趋于
无穷大．而由本文的命题６可知，五当Ｆ‘，而且ＩＳｌ有
限，仅包含有限个不同的点，所以根据Ｆ＿粤ｏｒｏｆｆ定理［１７］可以得到｛Ｆ（噩），ｋ≥０｝具有潜在的一致收敛性，即Ｖ
ｅ＞
０，了Ｎ（￡），如果七≥Ｊ『＼ｒ（ｅ），则Ｖ工∈Ｆ。。Ｉ丑一ＸＩ＜ｅ．即五（ｅ）ｃ，。，这说明算法能够以概率１确保在有限步内（，ｖ（ｅ））收敛到问题的全局最优解，即Ｐ｛Ｕｎ（噩
月ｏｌｋ＝Ⅳ
ｃ
Ｆ’）｝－１．
另外，我们的结论是建立在式（４）的基础上，但是
在ＭＭＡＳ中式（４）不一定成立．在ｍＩ＾ｓ中信息素更新规则为
一｛（１．Ｐ）啄七．１）＋南，。＿｜Ｉ－１））。
（ｉ，．，）∈形。
ｎ砒｛（１一Ｉ口）勺（Ｊｊ｝一１），ｒｍ（ｋ—１）｝，ｏｔｈｅｒｗｉｓｅ
（７）
其中０＜ｐ＜１，ｌ＇ｍｉｎ（七一１）为实数，Ｓｍｔｚｌｅ［１２］已经证明令
ｒｍ（ｋ）＝ｉ矗等可（Ｊ｜｝≥１），曲ｃ＾＞ｏ，ＭＭＡＳ也具有引理
２的性质．再比较式（７）和式（３），只要对Ｖ七＞０，有ｒ曲
（ｋ一１）≤（１一ＪＤ）‘・音，我们很容易用数学归纳法证明
ＭＮＡＳ也满足式（４），因而我们也可以证明ＮＮＡＳ也具有命题６的性质．５结束语
本文根据ＧｎｔｊａＩｌｒ等人的工作，在对ＧＢＡＳ收敛性的
分析中引入鞅理论进行研究．通过对ＧＢＡＳ所形成序列的上鞅性分析，得出了ＧＢＡＳ几乎处处强收敛以及能在有限步内收敛到全局最优解集的结论，并推广到ＮＭＡＳ算法．但是，对于蚁群算法的深入研究还远远不够，本
１６５０
电
子
文下一步将重点研究ＡＣＳ算法的强收敛性条件．
参考文献：
［１］ＣｏｌｏｍｉＡ，ＤｏｒｉｇｏＭ，Ｍａｉｌｉｅｚｚｏ
Ｖ．Ｄｉｓｔｒｉｂｕｔｅｄ
ｏｐｔｉｌ／ｌｉｚ撕ｏｌｌ
ｂｙ
ａｎｔ
ｃｏｌｏｎｉｅｓ［Ａ］．Ｐｒｏｃ．ｏｆｔｈｅＦｉｒｓｔＥｕｒｏｐｅａｎＣｏｎｆ．ｏｎＡｒｔｉｆｉｃｉａｌ
Ⅱｆｅ［ｃ］．Ｐａｒｉｓ，Ｆｒａｌｌｃｅ：ＥｌｓｅｖｉｅｒＰｕｂｌｉｓｈｉｎｇ，１９９１．１３４—１４２．
［２］ＤｏｆｉｇｏＭ，Ｇａｍｂａｒｄｅｌ／ａ
ＬＭ．Ａｎｔ
ｃｏｌｏｎｙ
ｓｙｓｔｅｍ：ＡＣＯＯｐｅｒａｆｉｖｃ
ｌｅａｒｎｉｎｇａｐｐｒｏａｃｈｔｏ
ｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｌＪＪ．ＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｓＯｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３—
６６．
［３］Ｍｏｎｔｅｍａｎｎｉ
Ｒ，ＳｍｉｔｈＤＨ，ＡｌｌｅｎＳ
Ｍ．ＡｎＡＮＴＳａｌｇｏｒｉｔｈｍｆｏｒ
ｔｈｅｍｉｎｉｍｕｍ－ｓｐａｎｆｒｅｑｕｅｎｃｙ－ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ、】ｖｉｔＩｌｍｕｌｔｉｐｌｅ
ｉｎｔｅｒｆｅｒｅｎｃｅ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｆｏｍＯｆｆ．ＶｅｈｉｃｕｌａｒＴｅｃｈｎｏｌｏｇｙ，
２００２．５１（５）：９４９—９５３．
［４］蒋建国，夏娜，齐美彬，木春梅．一种基于蚁群算法的串行
多任务联盟生成算法［Ｊ］．电子学报，２００５，３３（１２）：２１７８—
２１８２．
ＪＩＡＮＧＪｉａｎ－ｇｕｏ，ＸＩＡ
Ｎａ，ＱＩＭｅｉ・ｂｉｎ，ＭＵＣｈｕｎ－ｍｅｉ．Ａｎａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｂａｓｅｄｍｕｌｔｉ—ｔａｓｋｃｏａｌｉｔｉｏｎｓｅｒｉａｌｇｅｎｅｒａｔｉｏｎａｌ－
ｇｏｒｉｔｈｍ［Ｊ］．ＡｃｔａＥｌｅｃｔｒｏｎｉｃａＳｉｎｉｃａ，２００５，３３（１２）：２１７８—２１８２．（ｉｎ
Ｃｌｏｓｅ）
［５］吴春明，陈治，姜明．蚁群算法中系统初始化及系统参数
的研究［Ｊ］．电子学报，２００６，３４（８）：１５３０—１５３３．ＷＵ
ｔｉ删ｏｎ
Ｃｈｕｎ－ｍｉｎｇ，ＣＨＥＮＺｈｉ，ＪＩＡＮＧ
Ｍｉｎｇ．Ｔｈｅｒｅｓｅａｒｃｈ
Ｏｉｌ
ｉｎｉ—ｏｆ
ａｎｔｓ
ｓｙｓｔｅｍａｎｄ
ｃｏｒａｉｇｕｍａｏｎｏｆ
ｐａｒａｍｅｔｅ口＇ｓ
ｆｏｒ
ｄｉｆｆｅｒｅｎｔＴＳＰｐｒｏｂｌｅｍｓｉｎ
ａｎｔ
ａｌｇｏｒｉｔｈｍｌ
Ｊ］．ＡｃｔａＥｌｅｃｔｒｏｎｉｃａ
Ｓｉｎｉｃａ，２００６，３４（８）：１５３０—１５３３．（ｉｎＣｈｉｎｅｓｅ）
——鞅方法［Ｊ］．计算机学报，２００２，２５（８）：７８５—７９３．
ＸＵＺｏｎｇ－ｂｅｎ，ＮＩＥＺａｎ－ｋａｎ，ＺＨＡＮＧ
Ｗｅｎ－ｘｉｕ．Ａｌｍｏｓｔｓｕｒｅ
ｃｏｎｖｅｒｇｅｎｃｅｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ：ａｍａｒｔｉｎｇａｌｅａｐｐｒｏａｃｈ【ＪＪ．
ＣｈｉｎｅｓｅＪｏｕｍａｌ
ｏｆ
Ｃｏｍｐｕｔｅｒｓ，２００２，２５（８）：７８５—７９３．（ｉｎ
Ｃｈｉｎｅｓｅ）
［Ｊ］．应用数学，２００３，１６（３）：１—７．ＷＡＮＧ
Ｘｉａ，ＺｈｏｕＧｕｏ－ｂｉａｏ．Ｓｔｒｏｎｇ
ｃｏｎｖｅｒｇｅｎｃｅ（ａ．ｓ．）０ｆ
ｇｌｏｂａｌａｎｎｅａｌｉｎｇ
ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＭａｔｈｅｎａｔｉｃａＡｐｐｌｉｃａｔａ，
２００３，１６（３）：１—７．（ｉｎＣｈｉｎｅｓｅ）
析及收敛速度估计［Ｊ］．电子学报，２００５，３３（１０）：１８０３一
１８０７．ＬＵＯ
Ｘｉａｏ－ｐｉｎｇ，ＷＥＩＷｅｉ．Ｔｈｅａｎａｌｙｓｉｓｏｎｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅ
（ａ．ｓ．）ａｎｄ
ｃｏｎｖｅｒｇｅｎｃｅ
ｒａｔｅ
ｅＳｔｉｌｌｌａｔｅ
ｏｆｉｎｌｌｎｌｕ］ｅｇｅｎｅｔｉｃａｌｇｏ－
ｒｉｔ埘Ｊ］．Ａｃｔａ日ｅｃ咖ｉｃａ（ｉｎａ妇）
Ｓｉｎｉｃａ，２００５，３３（１０）：１８０３—１８０７．
Ｇ硼ａｈＷ
Ｊ．Ａｇｅｎｅｒａｌｉｚｅｄｃｏｎｖｅｒｇｅｎｃｅｒｅｓｕｌｔｆｏｒｔｈｅｇｒａｐｈ
ｂａｓｅｄ
ａｎｔｓｙｓｔｅｍｍｅｔａｈｅｎｒｉｓｔｉｃ【Ｒ］．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ９９—０９，
Ａｕｓｔｒｉａ，Ｄｅｐｔ．ｏｆＳｔａｔｉｓｔｉｃｓａｎｄＤｅｃｉｓｉｏｎＳｕｐｐｏｒｔＳｙｓｔｅｍｓ，Ｕｎｉ—ｖｅｒｓｉｔｙｏｆＶｉｅｎｎａ：１９９９．
万方数据
学报
２００９焦
［１０］Ｇ叫ａｈｒＷ
Ｊ．Ａｇｒａｐｈ－ｂａｓｅｄ
ａｎｔ
ｓｙｓｔｅｍａｎｄｉｔｓｃｏｎｖｅｒｇｅｎｃｅ
［Ｊ］．ＦｕｔｕｒｅＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｉｎｇ
Ｓｙｓｔｅｍｓ，２０００，１６（９）：８７３
—８８８．
［１１］ｏａｔｊａｈＷＪ．ＡＣＯ
ａｌｇｏｒｉｔｈｍｓｗｉｔｈｇｕａｒａｎｔｅｅｄ
ｃｏｎｖｅｒｇｅｎｃｅ
ｔｏ
ｔｈｅｏｐｔｉｍａｌ
ｓｏｌｕｆｉｏｎ［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＬｅｔｔｅｒｓ，２００２，
８２（３）：１４５—１５３．［１２］Ｓｔｉｉｔｚｌｅ
Ｔ，Ｄｏｒｉｇｏ
Ｍ．Ａｓｈｏｒｔｃｏｎｖｅｒｇｅｎｃｅｐｒｏｏｆｆｏｒ
ａｃｌａｓｓｏｆ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｆｉｎｌｉｚｚｆｉｏｎａｌｇｏｒｉｔｈｍｓ［ＪＪ．ＩＥＥＥＴｒａｎｓａｃｆｉｏｍＯｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（４）：３５８—３６５．
［１３］Ｂａｄｒ
Ａ，ＦａｈｍｙＡ．Ａｐｒｏｏｆｏｆ
ｃｏｎｖｅｒｇｅｎｃｅｆｏｒａｎｔａｌｇｏｒｉｔｈｍｓ
［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｓ，２００４，１６０（１－４）：２６７—２７９．［１４］朱庆保．蚁群优化算法的收敛性分析．控制与决策［Ｊ］．
２００６，２１（７）：７６３—７６６．
ＺＨＵ
Ｑｉｎｇ－ｂａｏ．Ａｎａｌｙｓｉｓ
ｏｆ
ｃｔｍｖｅｒｇｅｎｃｅｏｆ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉ・
ｍｉｚａｔｉｏｎ
ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｃｏｎｔｒｏｌ
ａｎｄ
Ｄｅｃｉｓｉｏｎ，２００６，２１（７）：
２６７—２７９．（ｉｎＣｈｉｎｅｓｅ）
［１５］段海滨，王道波，于秀芬．基本蚁群算法的Ａ．ｓ．收敛性
研究［Ｊ］．应用基础与工程科学学报，２００６，１４（２）：２９７—
３０１．
ＤＵＡＮＨａｌ—ｂｉｎ，ＷＡＮＧ
Ｄａｏ－ｂｏ，ＹＵ
Ｘｉｕ－ｆｅｎ．Ｒｅｓｅａｒｃｈ
０１１
ｔｈｅａ．ｓ．ｃｏｎｖｅｒｇｅｎｃｅｐｔＤｐｅｒｆｉｅｓｏｆｂａｓｉｃ
ａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ
［Ｊ］．Ｊｏｕｒｎａｌ
ｏｆＢａｓｉｃＳｃｉｅｎｃｅａｎｄ
Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，１４（２）：
２９７—３０１．（ｉｎＣｈｉｎｅｓｅ）
［１６］张波，张景肖．应用随机过程［Ｍ］．北京：清华大学出版
社．２００４．
ＺＨＡＮＧＢｏ，ＺＨＡＮＧＪｉｎｇ－ｘｉａｏ．ＡｐｐｌｉｅｄＳｔｏｃｈａｓｔｉｃＰｒｏｃｅｓｓｅｓ
［Ｍ］．Ｂｅｉｊｉｎｇ：ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ
Ｐｒｅｓｓ，２００４．（ｉｎＣｈｉｎｅｓｅ）
【１７］Ｅｄｗａｒｄ
ＰＣＫ．ＡｎＩｎｔｒｏｄｕｃｔｉＯｉｌｔｏＳｔｏｃｈａｓｔｉｃ
ＰｒｏｃｅｓｓｅｓｌＭＪ．
Ｂｅｌｍｏｎｔ，Ｃａｌｉｆ．，Ｌｏｎｄｏｎ：ＯｕｘｂｕｒｙＰｒｅｓｓ，１９９７．
［１８］Ｓｔｉａｔｚｌｅ
Ｔ，ＨｃｏｓＨＨ．Ｍａｘ—Ｍｉｎ
ａｎｔ
ｓｙｓｔｅｍ［Ｊ］．ＦｕｔｕｒｅＧｅｎｅｒａ－
ｔｉｏｎＣｏｍｐｕｔｅｒ
Ｓｙｓｔｅｍ，２０００，１６（８）：８８９—９１４．
作者简介：
苏兆品女。１９８３年８月出生于山东菏泽，在站博士后．主要研究方向：智能控制、进化计算、ａｇｅｎｔ理论等．
Ｅ－ｍａｉｌ：ｓｚｐ＠ｈｆｕｔ．ｅｄｕ．ｃｎ
蒋建国男，１９５５年１０月出生于安徽黄山，教授，博士生导师．主要研究方向：分布式智能控制系统，数字图像分析与处理，ＤＳＰ技术与应用等．
Ｅ－ｍａｉｌ：ｊｊｇ＠ａｈｌ６５．ｎｅｔ
［６］徐宗本，聂赞坎，张文修．遗传算法的几乎必然强收敛性
［７］王霞，周国标．整体退火遗传算法的几乎处处强收敛性
［８］罗小平，韦巍．生物免疫遗传算法的几乎处处强收敛性分
１９Ｊ
蚁群算法的几乎处处强收敛性分析
作者：作者单位：
苏兆品， 蒋建国， 梁昌勇， 张国富， 夏娜， SU Zhao-pin， JIANG Jian-guo， LIANG Chang-yong ， ZHANG Guo-fu， XIA Na
苏兆品,SU Zhao-pin(合肥工业大学计算机与信息学院,安徽合肥,230009;合肥工业大学管理科学与工程博士后科研流动站,安徽合肥,230009)， 蒋建国,夏娜,JIANG Jian-guo,XIANa(合肥工业大学计算机与信息学院,安徽合肥,230009;安全关键工业测控技术教育部工程研究中心,安徽合肥,230009)， 梁昌勇,LIANG Chang-yong(合肥工业大学管理科学与工程博士后科研流动站,安徽合肥,230009)， 张国富,ZHANG Guo-fu(合肥工业大学计算机与信息学院,安徽合肥,230009;安全关键工业测控技术教育部工程研究中心,安徽合肥,230009;特种显示技术教育部重点实验室,安徽合肥,230009)电子学报
ACTA ELECTRONICA SINICA2009，37(8)2次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(18条)
1. Colorni A. Dorigo M. Maniezzo V Distributed optimization by ant colonies 1991
2. Dorigo M. Gambardella L M Ant colony system:A cooperative learning approach to the travelingsalesman problem 1997(01)
3. Montemanni R. Smith D H. Allen S M An ANTS algorithm for the minimum-span frequency-assignmentproblem with multiple interference 2002(05)
4. 蒋建国. 夏娜. 齐美彬. 木春梅 一种基于蚁群算法的串行多任务联盟生成算法[期刊论文]-电子学报 2005(12)5. 吴春明. 陈治. 姜明 蚁群算法中系统初始化及系统参数的研究[期刊论文]-电子学报 2006(08)6. 徐宗本. 聂赞坎. 张文修 遗传算法的几乎必然强收敛性--鞅方法[期刊论文]-计算机学报 2002(08)7. 王霞. 周国标 整体退火遗传算法的几乎处处强收敛性[期刊论文]-应用数学 2003(03)
8. 罗小平. 韦巍 生物免疫遗传算法的几乎处处强收敛性分析及收敛速度估计[期刊论文]-电子学报 2005(10)9. Giitjahr W J A generalized convergence result for the graph based ant systemmetaheuristic[Technical Report 99-09] 1999
10. Gǖtjahr W J A graph-based ant system and its convergence 2000(09)
11. Gǖtjahr W J ACO algorithms with guaranteed convergence to the optimal solution 2002(03)12. Stǖtzle T. Dorigo M A short convergence proof for a class of ant colony optimization algorithms2002(04)
13. Badr A. Fahmy A A proof of convergence for ant algorithms 2004(1-4)14. 朱庆保 蚁群优化算法的收敛性分析[期刊论文]-控制与决策 2006(07)
15. 段海滨. 王道波. 于秀芬 基本蚁群算法的A.S.收敛性研究[期刊论文]-应用基础与工程科学学报 2006(02)16. 张波. 张景肖 应用随机过程 2004
17. Edward PC K An Introduction to Stochastic Processes 199718. Stǖtzle T. Hoos H H Max-Min ant system 2000(08)
相似文献(6条)
1.期刊论文 梁亮. 郭波 基于混合蚁群算法的产品开发过程优化方法 -系统工程理论与实践2009,29(10)
通过对迭代产品开发过程的分析,提出了将产品开发过程中设计活动被首次访问视为TSP问题中蚂蚁访问城市的思想,将Markov过程建模方法与基本蚁群算法相结合,建立了混合蚁群算法对产品开发过程进行优化求解.示例表明该方法成功地将蚁群算法扩展到复杂产品开发过程优化问题,在考虑设计迭代以及设计活动完成时间服从任意分布的情况下,建立了产品开发过程优化模型,为该类问题的求解提供了一个新的思路和方法.
2.期刊论文 黄翰. 郝志峰. 吴春国. 秦勇. HUANG Han. HAO Zhi-Feng. WU Chun-Guo. QIN Yong 蚁群算法的收敛速度分析 -计算机学报2007,30(8)
蚁群算法(ACO)作为一类新型的机器学习技术,已经广泛用于组合优化问题的求解,同时也应用于工业工程的优化设计.相对于遗传算法(GA),蚁群算法的理论研究在国内外均起步较晚,特别是收敛速度的分析理论是该领域急待解决的第一大公开问题.文中的研究内容主要是针对这一公开问题而开展的.根据蚁群算法的特性,该研究基于吸收态Markov过程的数学模型,提出了蚁群算法的收敛速度分析理论.作者给出了估算蚁群算法期望收敛时间的几个理论方法,以分析蚁群算法的收敛速度,并结合著名的ACS算法作了具体的案例研究.基于该文提出的收敛速度分析理论,作者还提出ACO-难和ACO-易两类问题的界定方法;最后,利用ACS算法求解TSP问题的实验数据,验证了文中提出的分析结论,得出了初步的算法设计指导原则.
3.学位论文 刘立东 改进蚁群优化算法的研究 2007
蚁群优化算法是由意大利学者Dorigo等人受到蚂蚁觅食行为的启发提出的一种新型的智能仿生类进化算法。大量实验结果表明，它在解决许多组合优化问题时都能表现出较好的求解能力，目前此算法已经得到了比较广泛的应用。但是与其它仿生学进化算法相比，蚁群算法存在搜索时间长、易陷入局部最优等缺点。本文针对蚁群算法的这些缺点，给出了3种改进的算法，并将其用于求解旅行商问题，主要内容如下：
1.通过对基本蚁群算法初始化参数的分析，给出了一种通过自适应改变启发式因子α和期望启发式因子β的蚁群算法。当算法在连续给定代数进化后的最优解没有变化时，改进后的算法通过对启发式因子α和期望启发式因子β的自适应调整来提高全局最优解的求解质量。通过对TSP问题的仿真表明改进后的蚁群算法在求解最优解和收敛速度方面与基本蚁群算法相比存在优势。
2.通过对基本蚁群算法初始化参数的分析，给出了一种基于信息素挥发因子ρ自适应调整的蚁群算法，当算法在连续给定代数进化后的最优解没有变化时，改进后的算法通过对信息素挥发因子ρ的自适应调整来提高全局最优解的求解质量，并证明了该算法在迭代次数充分大时能以概率1收敛到全局最优解。通过对TSP问题的仿真实验表明改进后的蚁群算法在求解最优解和收敛速度上与基本蚁群算法相比存在优势。
3.对已有的融入遗传算法的混合蚁群算法进行改进。算法在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算。对优秀解公共解集的保留加快了算法收敛速度，引入交叉和变异扩大了解的搜索空间，提高了解的全局性。最后用Markov过程证明了当迭代次数充分大时算法能以概率1收敛到满意解集。通过对TSP问题的仿真表明融入遗传算法的蚁群算法在收敛速度和解的全局性上都有较大的改善。 最后，对全文的研究工作进行了总结，并展望了蚁群优化算法进一步还要研究的课题。
4.学位论文 梁亮 快速响应制造系统产品开发过程可靠性评估与优化方法 2008
快速响应制造系统是基于“快速响应”原理，面向快速多变的市场需求而提出的。提高产品开发过程可靠性对于缩短产品研制周期，保障系统的快速响应能力具有重要的意义，本文针对快速响应制造系统的产品开发过程开展了可靠性分析建模与优化方法研究。
首先，在柔性制造系统等先进制造系统可靠性研究的基础上，提出了快速响应制造系统可靠性的定义以及系统可靠度的计算方法；在此基础上针对产品开发过程，通过对任务过程的分析提出了系统可靠性建模的思路和方法；针对负指数分布在可靠性建模中的局限性，基于PH分布开展了产品开发过程可靠性建模研究，考虑研制时间服从任意分布的情形分别建立了串行、并行以及重叠关系的产品开发过程可靠性模型。
其次，考虑设计迭代的影响，开展了产品开发过程可靠性评估与优化方法研究。在可靠性评估方面，通过对考虑设计迭代的任务过程进行分析，提出了任务阶段的划分方法；在此基础上，分别针对研制时间服从负指数分布和任意分布的情形，以及设计迭代参数随迭代次数变化的情形进行研究，基于多阶段Markov过程建立了快速响应制造系统产品开发过程可靠性模型。在可靠性优化方面，针对产品开发过程规模增大时，优化模型求解中出现的NP-hard问题，提出了将Markov过程与基本蚁群算法相结合，基于混合蚂蚁群算法对可靠性优化问题进行建模求解，实例研究说明了该方法能够解决大规模产品开发过程的可靠性优化问题，为产品开发过程优化提供了有效的手段和方法。
第三，针对快速响应制造系统同时承担多个研制任务的情形，从系统可靠性评估与收益综合优化这两个方面开展研究工作。针对产品开发过程多任务可靠性评估问题，考虑设计迭代和多任务下资源冲突的影响，采用排队网络对产品开发过程进行描述，考虑研制部门有单个小组和多个小组的情形分别建立了可靠性评估模型。针对收益综合优化问题，在系统多任务可靠性建模分析的基础上，以系统接受的最大任务数量为优化变量，以系统收益最大为目标建立了优化模型，并基于半开排队网络模型对优化参数进行建模求解。实例研究与敏感性分析说明了可靠性模型和优化方法为评估多任务下产品开发过程可靠性，分析系统薄弱环节，进而改进系统，提高系统收益提供了理论方法和优化策略。
第四，针对重叠关系的产品开发过程开展了可靠性评估方法研究。考虑设计迭代和研制任务完成时间服从随机分布的情况下，提出了设计迭代参数的表示方法；通过任务过程分析，提出了任务阶段的划分方法，采用Markov过程方法建立了产品开发过程可靠性评估模型。
最后，基于仿真方法开展了快速响应制造系统可靠性评估方法研究，结合可靠性解析建模的理论研究成果进行了系统可靠性分析软件的设计与开发工作，并针对实际需求开展了应用研究。
5.期刊论文 孙焘. 王秀坤. 刘业欣. 张名举 一种简单蚂蚁算法及其收敛性分析 -小型微型计算机系统2003,24(8)
该文首先介绍了一种可用于函数优化的简单蚂蚁算法,该算法具备了传统蚂蚁算法的基本特征,并给出了变异和最优保存两点改进.然后在给定近似精度的基础上通过Markov过程分析,得出了该算法的全局收敛性.同时,通过对衰减度、变异率等参数的定性讨论,得出了参数的取值对算法性能的影响,并从理论上说明,传统蚁群算法通常的选择概率公式是有缺陷的,而具有变异机制的蚂蚁算法要好于传统蚂蚁算法.该文的实例则说明了文中所给算法的有效性和相关理论论述的正确性.
6.学位论文 张国富 基于群智能的复杂联盟机制研究 2008
基于多agent系统(Multi-agent systems、MAS)的分布式智能控制正在蓬勃兴起，以适应计算机支持的协同工作等应用需求，因而使得对MAS中的联盟研究也变得越来越重要。如何形成一个稳定均衡的联盟，使联盟朝着稳定的方向发展，是控制理论的前沿课题，已经成为迫切需要解决的关键问题。传统的研究方法仅考虑一个agent只能加入一个联盟，势必造成agent能力和资源的极大浪费，而且在很多应用场合不能满足实际系统的需要。
基于上述背景，本文提出“复杂联盟”的概念，并引入群智能技术，力图在多任务环境中实现真正意义上的一个agent可以同时加入多个联盟和一个联盟可以同时承担多个任务，从而能在一定程度上提高系统的任务求解效率和资源利用率，为解决复杂控制问题提供理论指导和方法依据。本文的主要内容及创新之处如下：
(1)提出一种基于多粒子群协同优化的复杂联盟串行生成算法。基于图论的思想，给出了“虚拟agent”的概念，旨在转移父联盟的剩余能力，由“虚拟agent”代表其父联盟参与后续任务的竞争，在一定程度上解决了agent资源和能力的浪费问题。实验结果表明，本算法对于任务较多且较简单的情形特别有效。
(2)将离散粒子群算法扩充到二维二进制编码，实现复杂联盟的并行生成。算法中设计的编码有效性检查、冲突消解策略克服了求解过程中因多个任务求解联盟同时竞争某个能力有限的agent而导致的资源冲突和联盟死锁，而且实现了真正意义上的一个agent可以参加多个联盟，在一定程度上可以提高系统的资源利用率。
(3)提出一种基于按劳分配和效用非减的效用分配策略。针对已有工作无法摆脱搭便车问题，导致联盟潜在的不稳定，采用拍卖机制对任务进行快速和有效分解，基于合同机制对联盟效用以及额外效用进行合理分配，并依据联盟机制的数学模型推导出了局部效用非减和全局效用非减应满足的条件。该策略既严格遵循按劳分配又完全符合效用非减，在具有超加性的面向任务的领域中可以形成全局最优联盟，并具有Nash均衡意义下的稳定性。
(4)基于Markov过程和鞅理论推演了蚁群算法的几乎处处强收敛性，并提出一种基于蚁群正反馈的动态联盟形成策略。利用蚁群中的信息素浓度表示熟人之间的熟悉度，以信息素更新规则作为熟悉度调整规则。仿真实验的测试及分析说明了该策略能在一定程度上降低整个系统的通信代价和资源开销，提高了系统的可靠程度。
引证文献(2条)
1. 夏娜. 徐顺安. 于春华. 唐媚 导航卫星载体姿态测量进化算法研究[期刊论文]-小型微型计算机系统 2010(5)
2. 别文群. 苏虹 基于蚁群算法的高层固定货架最短路径问题研究[期刊论文]-郑州轻工业学院学报（自然科学版）2009(6)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dianzixb200908003.aspx授权使用：广西民族大学(dxmzdx)，授权号：c3740afd-8e51-40ef-8cab-9e4500b8844e
下载时间：2010年12月7日
第８期加０９年８月
电子学报
ｖ０１．３７Ｎｏ．８
ＡＣＴＡＥＵ￡ＣｒＲＯＮＩＣＡｓｌＮＩＣＡ
Ａｕｇ．２００９
蚁群算法的几乎处处强收敛性分析
苏兆品１．－，蒋建国１，一，梁昌勇２，张国富１，３，１，夏
娜１・３
（１．合肥工业大学计算机与信息学院，安徽合肥２３０（１０９；２．合肥工业大学管理科学与工程博士后科研流动站，安徽合肥２３０００９；
３．安全关键工业测控技术教育部工程研究中心，安徽合肥２３０００９；４．特种显示技术教育部重点实验室，安徽合肥２３０００９）
摘要：蚁群算法是一种新型的模拟进化算法，已在很多组合优化问题中得到成功应用，但其收敛性分析还比
较缺乏．以ＴＳＰ问题来描述一类蚁群算法的数学模型，并通过对状态空间的分解和反射壁的构筑，从鞅理论角度论证了该类蚁群算法的几乎处处强收敛性以及能在有限步内收敛到全局最优解集，试图为蚁群算法的研究探索一条新的思路．
关键词：
蚁群算法；Ｍａｌ＇ｋｏｖ过程；鞅；几乎处处强收敛
文献标识码：
Ａ
中图分类号：ＴＰ３０１文章编号：０３７２—２１１２（２００９）０８．１６４６－０５
ＡｎＡｌｍｏｓｔＥｖｅｒｙｗｈｅｒｅＳｔｒｏｎｇＣｏｎｖｅｒｇｅｎｃｅＰｒｏｏｆｆｏｒ
ａ
ＣｌａｓｓｏｆＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍｓ
ＳＵＺｈａｏ－ｐｉｎｌ，２，ＪＩＡＮＧＪｉａｎ．ｇＬｌ０１，３，ＬＩＡＮＧＣｈａｎｇ－ｙｏｎ９２．ＺＨＡＮＧＧｕｏ－ｆｕｌ，３，４ＸＩＡＮａｌ＇３
（１．Ｓｃｈｏｏｌｏｆ
２．ＰｏｓｔｄｏｃｔｏｒａｌＰｒｏｇｒａｖｕ
３．ＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈ
ｍ讹Ｍ删蜘ａｎｄ
ｉｓ
ａ
ｃ口ｊ砷ａｎｄＩｎｆｏｒｍａｔｉｏｎ，睫向ｗｎｉｖｅｍｔｙｏｆＴｅｄｍｏｌｏｇｙ，均包．Ａｒｄｕｌｉ
Ｅｎｇｍｅｍｎｇ。Ｈｅｆｅｉ
ａｎｄ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆＴｅｃｈ咖，Ｈ４ｅｉ，Ａｎｈｕｉ
２３０００９，Ｃｈｉｎａ；
２３∞０９，Ｃｈｉｎａ；
Ｃｅｎｔｅｒ矿ｓＣ日ｔｙＣｒｉｔｉｃａｌＩｎｄｕｓｔｒｉｄＭｅａｓｕｒｅｍｅｎｔ
４．ＮａｔｉｏｎａｌＥｎｇｉｎｅｅｒｉｎｇＲｅｓｅａｒｃｈ
ＣｏｎｔｒｏｌＴｅｄｍｄｏｇｙ，Ｍｉｎｉｓｔｒｙ
ｏｆＥｄｕｃａｔｉｏｎ，Ｈ４ｅｉ，Ａｎｈｕｉ２３００（）９，Ｏｌｉｎａ
Ｃｅｎｔｅｒ矿Ｓｐｅｃｉａｌ删叫町Ｔｅｄｍｏｌｏｇｙ，随痧。Ａｎｌｕｄ
２３０００９，‰）
Ａｂｓｔｒａｃｔ：ｍａｎｙｃｏｍｐｌｉｃａｔｅｄｏｆ
ａ
ＡｎｔＣｏｌｏｎｙ
Ｏｐｔｉｍｉ碰ｏｎ
ｎｏｖｅｌ
ｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｗｈｉｃｈｈａｓｂｅｅｎｕｓｅｄｓｕｃｃｅｓｓｆｕｌｌｙ
ｔｏｓｏｌｖｅ
ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔＪｌｎｉｚａｌｉｏｎｐｒｏｂｌｅｍｓ，ｂｕｔｉｔｓｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｉｓｓｅｌｄｏｍｒｅｓｅａｒｃｈｅｄ．Ｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌ
ｓｔａｔｅ
ｃｌａｓｓｏｆ
ａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｓｉｓｄｅｓｃｒｉｂｅｄｂｙＴｓＰｒ，ｒｏｂｌｅｍ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｅｄｅｃｏｍｐｏｓｉｔｉｏｎｏｆｓｐａｃｅａｎｄｔｈｅ
ｃｏｎｓｔｒｕｅ—
ｄｏｎｏｆｒｅｆｌｅｃｔｉｎｇｂａｒｒｉｅｒ，ａｎａｌｍｏｓｔｅｖｅｒｙｗｈｅｒｅｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｓａｎｄｔｈｅｑｕａｌｉｔｙｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｓｔｅｅｄｌｙｃｏｎｖｅｒｇｅ
ｔｏａ
ｃａｎ
ｇｕａｒａｎ—
ｇｌｏｂａｌｏｐｔｉｍｕｎｌ
ａｎｅｗ
ｓｅｔｉｎａ
ｆｍｉｔｅｉｌｕｍｂｅｒｏｆｓｔｅｐｓ
ａｌｅ
ｄｅｍｏｎｓｔｒａｔｅｄｂｙｕｓｉｎｇｔｈｅｍａｒｔｉｎｇａｌｅｔｈｅｏｒｙ．ａｎｄ
ｔｈｅ曲一
ｔａｉｎｅｄｒｅｓｕｌｔｓｍａｙｐｒｏｖｉｄｅｍｅｔｈｏｄｏｌｏｇｙｆｏｒｃｏｎｖｅｒｇｅｎｃｅａｎａｌｙｓｉｓｏｆｔｈｅａｌｇｏｒｉｔｈｍｓ．
Ｋｅｙｗｏｒｄｓ：
ａｎｔ
ｃｏｌｏｎｙ０ｐｔｊｌ面ｚａｌｉｏｎ；Ｍａｒｋｏｖｐｒｍ．ｚ．ｓｓ；ｍａｒｔｉｎｇａｌｅ；ａｌｍｏｓｔｅｖｅｒｙｗｈｅｒｅｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅ
ｌ引言
Ｏｐｔｉｍｉｚａｔｉｏｎ）［１３是模拟自然界
中真实蚁群的觅食行为而形成的一种新型的启发式模
Ｃｏｌｏｎｙ
能算法【６－８ｊ还比较缺乏，在一定程度上制约了蚁群算法的进一步改进和发展．虽然已有部分学者给出一些收敛性结论旧“引，但都是在概率收敛意义下考虑的，主要还是基于Ｍａｒｋｏｖ过程和算法的遍历性展开的研究，在分析手段和方法上尚比较单调．Ｇａｔｊａ“引首先利用图论对蚁群算法的收敛性进行了研究，并提出了基于图的蚂蚁系统（Ｇｒａｐｈ．ｂａｓｅｄＡｎｔＳｙｓｔｅｍ，ＧＢＡＳ），适用于各种静态组合优化问题，但是在ＧＢＡＳ算法中，对于某个事先给定的概率，无法确定蚂蚁数和蒸发系数，从这个意义上讲，ＧＢＡＳ是不可控的．为了克服上述问题，Ｃｉｉｔｊａｈｒ［１０ｔｌｌｊ将ＧＢＡＳ发展成ＧＢＡＳ／ｔｄｅｖ和ＧＢＡＳ／ｔｄｌｂ（－－般统称为ＧＢＡＳ算法），并利用Ｍａｒｋｏｖ过程理论证明其能以概率１收敛
蚁群算法（Ａｒｔ
拟进化算法，它采用具有记忆的人工蚂蚁通过个体之间的交互和协同工作来搜索从蚁穴到食物源的最短路径．
目前蚁群算法已在旅行商（Ｔｒａｖｅｌｉｎｇ
ＳａｌｅｓｍａｎＰｒｏｂ．
１ｅｌＩｌ’ＴＳＰ）、指派（ＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ，ＡＰ）及联盟生成（ＣｏａｌｉｔｉｏｎＧｅｎｅｒａｔｉｏｎＰｒｏｂｌｅｍ，ＣＧＰ）等一系列组合优化问题中得到成功应用［２－４］，但这些研究大都从实验的角度说明了蚁群算法的有效性ｂＪ，而有关蚁群算法的一般收敛性，如概率收敛、几乎处处收敛等的分析相比其他智
收稿日期：２００８—１２－２９；修回日期：２００９－０２．１２
基金项目：国家教育部博士点基金（Ｎｏ．２００６０３５９００４）；安徽省自然科学基金（Ｎｏ．０９０４１２０５８，０７０４１２０３５）；特种显示技术教育部重点实验室开放课题基金（№．２００８ＨＧＸＪ０３５０）；合肥工业大学博士专项科研资助基金（Ｎｏ．ＧＤＢＪ２００９—００３）
万方数据
第８期苏兆品：蚁群算法的几乎处处强收敛性分析
１６４７
到问题的最优解，具有较强的说服力．Ｓｔ删ｅ［１２］，Ｂ“１３】
和朱庆保¨４１等主要利用代数理论研究蚁群算法的收敛性，但相比Ｇｆｉｔｊａｈｒ，他们的证明过程显得比较弱化，说服力不够．段海滨１１５Ｊ尝试用鞅理论研究了基本蚁群算法（Ｂａｓｉｃ
Ａｎｔ
Ｃｏｌｏｎｙ
Ａｌｇｏｒｉｔｈｍ）的几乎处处收敛问题，但
其忽视了一个很重要的方面，即信息素浓度ｒ（矗）本身
并不是Ｍａｒｋｏｖ过程，在没有路径形（＿ｊ｝）的情况下，ｒ（１｜｝）不是自包容的（ｓｅｌｆ－ｃｏｎｔａｉｎｅｄ）ｍ．１１Ｉ，因此其证明过程和结论均值得商榷．
定义１【１６Ｊ设序列｛噩，ｌ｜｝＞１０｝的全局最优解集为Ｖ算∈ｓ，“菇’）≤八ｚ）｝，如果．１ｉｒａＰ｛瓦ｃｆ’｝＝１，则称｛瓦，ｋ１＞０｝依概率收敛到全局最优解集．厂‘，记
Ｄ
为五二彳。；如果Ｐ｛ｌｉｒａ（五ｃｆ＋）｝＝１，则称｛五，尼≥
０｝几乎处处强收敛到全局最优解集．厂’，记为冠当
由上述定义可知，依概率收敛属弱大数律范畴，而几乎处处收敛性明显强于依概率收敛性．因此，本文在Ｇｃ，ｔｊａｈｒ等人的工作基础上进一步研究蚁群算法的几乎处处强收敛性，我们避开使用传统的遍历性分析，而是在Ｍａｒｋｏｖ过程分析中运用鞅理论［１７］对算法进行具体分析，试图为这方面的研究探索一条新的思路．２算法模型
蚁群算法最早是用于求解ＴＳＰ问题怛Ｊ，不失一般性，为了更好的描述和分析蚁群算法，本文以求解／７，个城市的ＴＳＰ问题为例描述ＧＢＡＳ算法的模型．
定义２
ＴＳＰ可以用７１，个城市的一个有向图Ｇ＝
（Ⅳ，Ａ）表示，其中Ｎ＝｛１，２，…，ｎ｝，Ａ＝｛（ｉ，＿『）Ｉｉ，．『∈Ⅳ｝；城市间的距离Ｄ＝（也）。。。；目标函数为
—Ｌ
“形）＝∑ｄ／ｌ－１ｉｆ
（１）
其中形＝｛ｉ１，ｉ２，…，‘｝为城市１，２，…，ｔｔ的一个排列，且ｆ。＋ｌ＝ｉｌ，形中的节点构成的弧集为彬。＝｛（ｉ。，ｉｑ＋１）Ｊｉｑ∈形，ｑ＝１，２，…，疗｝．
根据上述定义，ＧＢＡＳ算法可以描述如下：
①初始化：为上述ＴＳＰ图中的每一条弧（ｉ，ｊ）赋信
１
息素浓度初值ｒＯ－（ｏ）＝斋，Ｖ（ｉ，』）∈Ａ，ｍ只蚂蚁从
同一城市ｉｏ出发．矗＝１，当前最好解为形＝｛１，２，…，／７，｝．
②外循环：如果满足算法的停止规则，停止计算并输出计算得到的最好解；否则，让蚂蚁ｓ（１≤ｓ≤ｍ）从起点ｉｏ出发，用￡（ｓ）表示蚂蚁ｓ行走的城市集合，￡
（ｓ）：⑦．
③内循环：按蚂蚁１≤ｓ≤ｍ的顺序分别计算．当蚂
万方数据
蚁ｓ在城市ｉ，若￡（ｓ）＝Ⅳ或｛ｆｆ（ｉ，ｆ）∈Ａ，Ｚ岳￡（５）｝－ｇ，完成第ｓ只蚂蚁的计算；否则，若Ｌ（ｓ）≠Ｎ且Ｔ＝｛ｚｆ（ｉ，Ｚ）∈Ａ，Ｚ《￡（５）｝一｛ｉｏ｝≠（乃，贝４ｓ以概率
铲Ｊ鞘高乐ｒ
ｇ＃：｛奢ｄ（矗一１）。～
㈤（２）
ｔｏ，
ｏｔｈｅｒｗｉｓｅ
到达＿『，Ｌ（ｓ）＝三（ｓ）Ｕ｛＿『｝，ｉ＝＿『；若Ｌ（ｓ）≠Ｎ且ｒ＝｝ＺＩ（ｉ，ｚ）∈Ａ，ｚ薯Ｌ（ｓ）｝一｛ｉｏ｝＿⑦，则ｓ到达ｉｏ，Ｌ（ｓ）＝Ｌ（ｓ）Ｕ｛ｉｏ｝，ｉ＝ｉｏ；重复③．
④信息素更新：对１≤ｓ≤ｍ，若￡（ｓ）＝Ｎ，按照￡（ｓ）中城市的顺序计算路径长度；若Ｌ（ｓ）≠Ｎ，路径长度是一个充分大的数．比较ｔｎ只蚂蚁中的路径长度，具有最短路径的蚂蚁为ｔ．若Ｊｒ（Ｌ（ｔ））≤，（１Ｆ），则形＝Ｌ．
（ｔ）．用下式
《扯｛（１－Ｐｔ－Ｉｋ＠－１）＋舒，（以ｐ∈％
【（１一ＩＤ‘一１）ｒ“（ｋ一１），ｏｔｈｅｒｗｉｓｅ
（３）
更新图中每一条弧的信息素浓度，得到新的ｑ（Ｊ｜｝），ｋ＝Ｊｉ｝＋１，重复②．
注释１Ｌ１０，１１】
式（３）中凤为挥发因子，并且对于
固定的Ｋ≥１满足ｍ≤１一ｉ高告可（矗≥Ｋ）与砉以＝
注释２［１０，１１］用数学归纳法很容易验证式（３）满
足对Ｖ＿ｊ｝≥０，有
∑ｏ（南）＝１
（４）
３收敛性分析
ＧＢＡＳ算法的每步迭代对应随机变量以＝（ｒ（ｋ），
ｇ／（五））（｜｜｝≥ｏ），ｒ（１｜｝）∈Ｒ㈨ｌ为所有弧的信息素浓度；形（知）为／１，个城市的一个排列，最多有ｒ／，！个状态，所以瓦是全状态空间Ｓ＝Ｒｌ＾Ｉ×／Ｖ中的一个元素，显然Ｉ
Ｓｌ
是有限的．
３．１依概率收敛
引理１［１１】
由状态五＝（ｒ（七），肜（Ｉ｜｝））（后≥０）所
构成的随机过程是离散时空上的有限非齐次Ｍａｒｋｏｖ过
程．
证明由Ｍｍ＇ｋｏｖ过程的性质可知，只要证明状态
五＋，的分布仅仅依赖于状态冠．注意到在第后次迭代中，第ｓ只蚂蚁的转移只由ｒ（矗一１）决定，且其行走的路径和形（＿｜｝一１）共同决定了形（七），再通过式（３）的更新原则可以进一步得到ｒ（Ｊｊ｝）．因此，状态五＋１的变化仅由五决定，而与之前的状态无关，这是一个典型的Ｍａｒｋｏｖ过程，而且由上面的分析我们也可以得到单独
ｆ‘＝｛石’Ｉ．｛４．
１６４８
电
子
的ｒ（矗）或形（∽本身并不是ｌ～Ｉａｒｋｏｖ过程，因为ｒ（后）或形（”本身不是自包容的．
设｛瓦，ｋ≥ｏ｝的一步状态转移概率为Ｐ（惫），Ｂ＝｛（ｉ口，ｉｇ＋１）Ｉｉ口∈形（七＋１），ｑ＝１，２，…，Ｔ／，｝，Ｔ。＝…（ｉ，Ｚ）∈Ａ｝，对Ｖ茗，’，∈Ｓ，我们有Ｐ（ｋ）＝Ｒ（丑＋１：ｙＩ凰＝戈）
一ＴＴ
玉！１２
一（土是口∑．Ｉ＂ｉｌ（七）一【＝ｏ，ｏｔｈｅｒｗｉｓｅ
一』＞ｏ，八形（１｜｝＋１））≤以形（＿｜｝））
（５）
因为ｒ（后）的变化要依赖于ｋ，所以随机状态转移概率Ｐ（＿｜ｃ）与豇有关，该Ｍａｒｋｏｖ过程是非齐次的．
引理２［１１］
Ｍａｒｋｏｖ过程｛丑，居≥０｝能够以概率１
收敛到一个全局最优解ｘ。ｗ－－．（ｒ。，形’），其中形’是Ｇ
中的一条最优路径，形毒＝｛（‘，‘＋ｔ）Ｉｉ，∈形’，ｑ＝１，２，
…，／７，｝，ｒ’定义如下：
争｛高椭埏％
【Ｏ．ｏｔｈｅｒｗｉｓｅ
证明Ｃ，杜ｔｊａｈｒ已在文献［１１］中给出了详细的证明，鉴于篇幅有限，这里不再列出．
命题１
｛凰，＿｜ｌ≥ｏ｝能够以概率１收敛到全局最
优解集ｆ。；｛形。ＩＶ形∈Ⅳ，八形’）≤以形）｝．
证明由引理２可知，｛五，Ｊｊ｝≥０｝能够以概率１收敛到一个全局最优状态工’：（ｒ‘，形‘）∈ｆ’，根据式（２）的状态转移概率和式（３）的信息素更新规则，系统一旦达到ｘ‘，其后续状态只可能在全局最有解集．厂‘中迁移，而不可能迁移到厂＋之外，当Ｊ｜｝一∞时，系统必然收敛到厂’．
３．２相关基本概念
定义３［撕］
称状态空间Ｃ为闭集，若对Ｖｉ∈Ｃ，
有∑＾＝１，即自Ｃ内任意一点出发，始终不能达到Ｃ外的任意状态．
定义４１１６】闭集Ｃ若无真闭子集。则称ｃ为不可约的，否则Ｃ是可约的．
定义５［坫】
设｛Ｋ，七≥０｝与｛五，ｋ≥０｝是随机过
程，称｛Ｋ，ｋ≥ｏ｝关于｛磊，丘＞１０｝是一个上（或下）鞅，如果：
①ＥｌＫｌ＜∞；
②Ｅ（Ｋ＋ｌｚ０，ｚｌ，…，乙）≤Ｋ（或Ｅ（Ｋ＋ｌｚ０，ｚＩ，
…，磊）≥Ｋ）；
③｛玩，．｜ｃ＞１０ｌ是Ｚｏ，ｚｌ’．一，乙的函数．
Ｄｏｏｂ证明了著名的下鞅收敛定理论［１６，１７］，为了分析方便，给出其结论．
引理３【１６】设｛Ｋ，Ｉｊ｝≥０｝是一个下鞅，ｓｑ陋ｌＫｌ＜
万方数据
学报
２００９钜
∞，则存在一个随机变量ｌ，’∈｛圪，矗＞／０｝，使ＥＩ
ｙ’Ｉ＜
∞，且圪当ｌ，。，即Ｐ｛ｌｉｒａＫ＝Ｙ’｝＿１．
引理４【１６Ｊ引理３的结论对上鞅也成立．证明设｛玩，克＞／０｝为上鞅，且ｓｕ凹ＩＫｌ＜∞，则由定义５可知｛一致，ｋ／＞０｝为下鞅，且ｓｕ凹Ｉ一圪｜＿ｓｕ嵋ＩＫＩ＜∞，由引理３可得，存在随机变量一ｌ，。，使得
Ｅｌ—ｙ。Ｉ＝ＥＩ
ｙ’Ｉ＜∞，且Ｐ｛ｌｉｍ（一虼）＝一Ｙ‘｝＝１，
即尸｛ｌｉｍ圪＝Ｙ’｝．１．
■—＋∞
３．３几乎处处强收敛
从直观上说，蚁群算法的目的在于找到一个最优状态五＝（ｒ（｜｜｝），驴（．｜｝）），它带有概率分布ｒ（后）偏向于一个最优排列形（｜］｝），而形（后）又对应最短路径长度．厂（形（ｋ））．因此，我们把式（１）中的目标函数改写为：Ｆ（五：（ｒ（尼），肜（后）））：黜
（ｉ．铤＾‘９”¨
这样设计的好处是兼顾了ｆ（１ｊ｝）和形（．｜｝），从而可以利用噩的Ｍａｒｋｏｖ过程的相关结论，同时又巧妙的利用ｒ（１；）在式（４）中的性质简化了计算．我们以每个状态的路径长度作为指导原则，则由于路径长度达到全局最小当且仅当找到全局最优状态，我们可以利用路径长度函数过程的收敛性来研究蚁群算法的收敛性．另外，我们可以观察到，路径长度的变化是一个单调不增的过程，因此，我们可以设法把随机过程｛，（五），Ｉ｜｝Ｉ＞０｝转变为一个上鞅来考察｛凰，ｋＩ＞０｝的收敛性．
命题２全状态空间Ｓ＝Ｒ｜＾Ｉ×．『ｖ是一个闭集．证明由引理１可知，｛五，后≥０｝为一离散时空上的有限非齐次Ｍａｒｋｏｖ过程，则由Ｍａｒｋｏｖ过程的性质ｕ６Ｊ有Ｖｉ∈Ｓ，∑心＝１，再由定义３可知｜ｓ是一个闭集．
命题３全状态空间Ｓ＝ＲＩ＾ＩＸⅣ是可约的．证明
由命题１和定义３可知，．厂。是有限的闭集，
又ｆ。ｃＳ，由定义４可知ｓ是可约的．
因为Ｓ是可约的，由Ｍａｒｋｏｖ过程的状态空间分解定理［１６Ｊ我们可以很容易把ｓ分解成两部分，一部分为｛五，Ｊ｜｝≥Ｏ｝的收敛空间Ｑ，另一部分为Ｓ—Ｑ，其中Ｑ＝｛五＋１：Ｆ（凰＋１）≤Ｆ（五）｝．
命题４收敛空间Ｑ是一个闭集．
证明
由Ｑ的定义可知，所有满足Ｆ（凰＋１）≤Ｆ
（％）的状态都被限制在Ｑ中，而所有Ｆ（凰＋。）＞Ｆ（五）的状态都被限制在Ｓ—Ｑ中，在Ｑ中不可能找到一个状态满足，（鼍＋１）＞Ｆ（以），即Ｑ中任意一个状态的后继状态只可能在Ｑ中找到，而不可能到达Ｑ外，即
ＶｉＥ
Ｑ，ｆ。善ｐ＝ｏ，所以有Ｖ
ｉ
Ｅ
Ｑ，磊乃＝１，即口为
一个闭集，且ｐｃＳ．
第８期苏兆品：蚁群算法的几乎处处强收敛性分析
１６４９
上述操作的目的是将｛ｘｋ，ｋ≥０｝构成的有限非时齐Ｍａｒｋｏｖ过程限制在其全状态空间Ｓ的闭子集ｐ中，也就是说在Ｑ之外的每一个状态都是反射壁，将其他所有满足，（五＋。）≤Ｆ（墨）的状态约束于此内，由随机过程理论我们知道，这相当于状态的限制运动边界，就像桶的边缘一样（如图１所示）．
反射壁
Ｖ＿：ｒ’Ｅｓ－Ｑ
图１反射墅的构筑
命题５随机过程｛Ｆ（咒），ｋ／＞０｝关于｛丑，后≥０｝是一个非负有界上鞅，即对Ｖｋ≥０，有Ｅ（，（孔＋１）Ｉ蜀，
Ｘｌ，…，以）≤Ｆ（五）．
证明显然｛Ｆ（凰），后≥０｝是非负有界的，根据引理１的Ｍａｒｋｏｖ性，可以得到Ｅ（Ｆ（五＋１）Ｉ蜀，Ｘｌ，…，忍）＝Ｅ（，（噩＋１）Ｉ噩），故我们只需证对Ｖ戈∈Ｓ有
Ｅ（Ｆ（五＋１）Ｉ五＝石）≤Ｆ（髫），矗≥Ｏ
（６）
又根据随机过程理论，有Ｅ（尸（咒＋１）ｌｘｋ＝髫）＝Ｙ，，．Ｆ（，，）Ｒ（孔＋ｌ＝，，ｌ冠＝石），再由Ｆ（五）的定义以及ｒ（ｋ）的性质，我们可以观察到，Ｆ（墨＋１）≤Ｆ（五）与厂（形（ｋ＋１））≤八形（七））是等价的，而这个正好是式（５）中的条件，所以式（５）中的“ｏｔｈｅｒｗｉｓｅ”所限定的状态即为反射
壁，将其他状态约束于条件八形（后＋１））≤八形（后））限
定的状态内，故有
∑，（，，）Ｒ（五＋ｌ＝，，Ｉ丑＝茗）
，∈Ｓ
＝∑，（，，）Ｐｋ（凰＋ｌ＝，，Ｉ凰＝茗）
，∈口
＋∑Ｆ（ｙ）Ｒ（五＋ｌ＝，，ｌ五＝算）
＝∑＇ｒ（ｙ）Ｐｋ（Ｘｋ＋ｌ＝ｙｌ五＝石）＋∑，（ｙ）・０
，∈口
，∈ｓ・口
＝∑Ｆ（），）Ｐｋ（甄＋１＝ｙｌ
ｘｋ＝石）
因为状态茗的任意后继状态，，，满足对Ｖ），∈Ｑ，有Ｆ（恐＋１＝），）≤Ｆ（ｘｋ＝名），所以
∑Ｆ（ｙ）Ｒ（丑＋１＝，，Ｉ五＝茁）≤∑Ｆ（算）Ｒ（五＋１＝，，ｔｘｋ＝重）＝Ｆ（聋）∑Ｒ（噩＋１＝ｙｌ鼍＝茹）
又Ｑ是闭集，所以有吕Ｒ（五＋ｌ＝ｙ
Ｉ五＝茹）＝１．
从而可以得到蓦，（），）＾（噩＋ｌ＝ｙＩ五＝戈）≤Ｆ（茁），即
矽（，，）Ｒ（瓦＋ｌ＝Ｙ
Ｉ墨＝ｘ）≤Ｆ（互）．所以有Ｅ（Ｆ
万方数据
（鼍＋１）Ｉ凰＝髫）≤，（ｚ），式（６）得证，即｛，（五），Ｊ｜｝≥０｝关于｛五，ｊ｝≥Ｏ｝是一个非负有界上鞅．
命题６｛，（五），．｜｝／＞０｝几乎处处强收敛到全局最优解集Ｆ。＝｛ｚ。ＪＶｘ∈５，，（Ｚ。）≤，（ｚ）｝．证明
由命题１可知，｛置，＿｜｝≥０｝能够以概率１收
敛到全局最优解集厂，又，（形’）≤，（形）与Ｆ（ｘ’）≤，（工）是等价的，因此｛，（五），Ｊｊ｝≥ｏ｝能够以概率１收敛到全局最优解集，。，又由命题５可得，｛，（丑），后ｔ＞０｝是一个非负有界上鞅，根据引理４，｛Ｆ（五），矗＞ｔ０｝几乎处处强收敛到全局最优解集，’．４讨论
Ｇｎｔｊａｈｒ证明了ＧＢＡＳ的概率收敛性［９－ｎ］，Ｓｔｌｌｔａｌｅ和
Ｄｏｒｉｇｏ‘１２１分析了诸如ＡｅＳ［２Ｊ和ＭＭＡＳ［１８】等一类ＡＣＯ，。的弱收敛性，但他们的工作大都要求算法迭代次数趋于
无穷大．而由本文的命题６可知，五当Ｆ‘，而且ＩＳｌ有
限，仅包含有限个不同的点，所以根据Ｆ＿粤ｏｒｏｆｆ定理［１７］可以得到｛Ｆ（噩），ｋ≥０｝具有潜在的一致收敛性，即Ｖ
ｅ＞
０，了Ｎ（￡），如果七≥Ｊ『＼ｒ（ｅ），则Ｖ工∈Ｆ。。Ｉ丑一ＸＩ＜ｅ．即五（ｅ）ｃ，。，这说明算法能够以概率１确保在有限步内（，ｖ（ｅ））收敛到问题的全局最优解，即Ｐ｛Ｕｎ（噩
月ｏｌｋ＝Ⅳ
ｃ
Ｆ’）｝－１．
另外，我们的结论是建立在式（４）的基础上，但是
在ＭＭＡＳ中式（４）不一定成立．在ｍＩ＾ｓ中信息素更新规则为
一｛（１．Ｐ）啄七．１）＋南，。＿｜Ｉ－１））。
（ｉ，．，）∈形。
ｎ砒｛（１一Ｉ口）勺（Ｊｊ｝一１），ｒｍ（ｋ—１）｝，ｏｔｈｅｒｗｉｓｅ
（７）
其中０＜ｐ＜１，ｌ＇ｍｉｎ（七一１）为实数，Ｓｍｔｚｌｅ［１２］已经证明令
ｒｍ（ｋ）＝ｉ矗等可（Ｊ｜｝≥１），曲ｃ＾＞ｏ，ＭＭＡＳ也具有引理
２的性质．再比较式（７）和式（３），只要对Ｖ七＞０，有ｒ曲
（ｋ一１）≤（１一ＪＤ）‘・音，我们很容易用数学归纳法证明
ＭＮＡＳ也满足式（４），因而我们也可以证明ＮＮＡＳ也具有命题６的性质．５结束语
本文根据ＧｎｔｊａＩｌｒ等人的工作，在对ＧＢＡＳ收敛性的
分析中引入鞅理论进行研究．通过对ＧＢＡＳ所形成序列的上鞅性分析，得出了ＧＢＡＳ几乎处处强收敛以及能在有限步内收敛到全局最优解集的结论，并推广到ＮＭＡＳ算法．但是，对于蚁群算法的深入研究还远远不够，本
１６５０
电
子
文下一步将重点研究ＡＣＳ算法的强收敛性条件．
参考文献：
［１］ＣｏｌｏｍｉＡ，ＤｏｒｉｇｏＭ，Ｍａｉｌｉｅｚｚｏ
Ｖ．Ｄｉｓｔｒｉｂｕｔｅｄ
ｏｐｔｉｌ／ｌｉｚ撕ｏｌｌ
ｂｙ
ａｎｔ
ｃｏｌｏｎｉｅｓ［Ａ］．Ｐｒｏｃ．ｏｆｔｈｅＦｉｒｓｔＥｕｒｏｐｅａｎＣｏｎｆ．ｏｎＡｒｔｉｆｉｃｉａｌ
Ⅱｆｅ［ｃ］．Ｐａｒｉｓ，Ｆｒａｌｌｃｅ：ＥｌｓｅｖｉｅｒＰｕｂｌｉｓｈｉｎｇ，１９９１．１３４—１４２．
［２］ＤｏｆｉｇｏＭ，Ｇａｍｂａｒｄｅｌ／ａ
ＬＭ．Ａｎｔ
ｃｏｌｏｎｙ
ｓｙｓｔｅｍ：ＡＣＯＯｐｅｒａｆｉｖｃ
ｌｅａｒｎｉｎｇａｐｐｒｏａｃｈｔｏ
ｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｌＪＪ．ＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｓＯｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３—
６６．
［３］Ｍｏｎｔｅｍａｎｎｉ
Ｒ，ＳｍｉｔｈＤＨ，ＡｌｌｅｎＳ
Ｍ．ＡｎＡＮＴＳａｌｇｏｒｉｔｈｍｆｏｒ
ｔｈｅｍｉｎｉｍｕｍ－ｓｐａｎｆｒｅｑｕｅｎｃｙ－ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ、】ｖｉｔＩｌｍｕｌｔｉｐｌｅ
ｉｎｔｅｒｆｅｒｅｎｃｅ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｆｏｍＯｆｆ．ＶｅｈｉｃｕｌａｒＴｅｃｈｎｏｌｏｇｙ，
２００２．５１（５）：９４９—９５３．
［４］蒋建国，夏娜，齐美彬，木春梅．一种基于蚁群算法的串行
多任务联盟生成算法［Ｊ］．电子学报，２００５，３３（１２）：２１７８—
２１８２．
ＪＩＡＮＧＪｉａｎ－ｇｕｏ，ＸＩＡ
Ｎａ，ＱＩＭｅｉ・ｂｉｎ，ＭＵＣｈｕｎ－ｍｅｉ．Ａｎａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｂａｓｅｄｍｕｌｔｉ—ｔａｓｋｃｏａｌｉｔｉｏｎｓｅｒｉａｌｇｅｎｅｒａｔｉｏｎａｌ－
ｇｏｒｉｔｈｍ［Ｊ］．ＡｃｔａＥｌｅｃｔｒｏｎｉｃａＳｉｎｉｃａ，２００５，３３（１２）：２１７８—２１８２．（ｉｎ
Ｃｌｏｓｅ）
［５］吴春明，陈治，姜明．蚁群算法中系统初始化及系统参数
的研究［Ｊ］．电子学报，２００６，３４（８）：１５３０—１５３３．ＷＵ
ｔｉ删ｏｎ
Ｃｈｕｎ－ｍｉｎｇ，ＣＨＥＮＺｈｉ，ＪＩＡＮＧ
Ｍｉｎｇ．Ｔｈｅｒｅｓｅａｒｃｈ
Ｏｉｌ
ｉｎｉ—ｏｆ
ａｎｔｓ
ｓｙｓｔｅｍａｎｄ
ｃｏｒａｉｇｕｍａｏｎｏｆ
ｐａｒａｍｅｔｅ口＇ｓ
ｆｏｒ
ｄｉｆｆｅｒｅｎｔＴＳＰｐｒｏｂｌｅｍｓｉｎ
ａｎｔ
ａｌｇｏｒｉｔｈｍｌ
Ｊ］．ＡｃｔａＥｌｅｃｔｒｏｎｉｃａ
Ｓｉｎｉｃａ，２００６，３４（８）：１５３０—１５３３．（ｉｎＣｈｉｎｅｓｅ）
——鞅方法［Ｊ］．计算机学报，２００２，２５（８）：７８５—７９３．
ＸＵＺｏｎｇ－ｂｅｎ，ＮＩＥＺａｎ－ｋａｎ，ＺＨＡＮＧ
Ｗｅｎ－ｘｉｕ．Ａｌｍｏｓｔｓｕｒｅ
ｃｏｎｖｅｒｇｅｎｃｅｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ：ａｍａｒｔｉｎｇａｌｅａｐｐｒｏａｃｈ【ＪＪ．
ＣｈｉｎｅｓｅＪｏｕｍａｌ
ｏｆ
Ｃｏｍｐｕｔｅｒｓ，２００２，２５（８）：７８５—７９３．（ｉｎ
Ｃｈｉｎｅｓｅ）
［Ｊ］．应用数学，２００３，１６（３）：１—７．ＷＡＮＧ
Ｘｉａ，ＺｈｏｕＧｕｏ－ｂｉａｏ．Ｓｔｒｏｎｇ
ｃｏｎｖｅｒｇｅｎｃｅ（ａ．ｓ．）０ｆ
ｇｌｏｂａｌａｎｎｅａｌｉｎｇ
ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＭａｔｈｅｎａｔｉｃａＡｐｐｌｉｃａｔａ，
２００３，１６（３）：１—７．（ｉｎＣｈｉｎｅｓｅ）
析及收敛速度估计［Ｊ］．电子学报，２００５，３３（１０）：１８０３一
１８０７．ＬＵＯ
Ｘｉａｏ－ｐｉｎｇ，ＷＥＩＷｅｉ．Ｔｈｅａｎａｌｙｓｉｓｏｎｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅ
（ａ．ｓ．）ａｎｄ
ｃｏｎｖｅｒｇｅｎｃｅ
ｒａｔｅ
ｅＳｔｉｌｌｌａｔｅ
ｏｆｉｎｌｌｎｌｕ］ｅｇｅｎｅｔｉｃａｌｇｏ－
ｒｉｔ埘Ｊ］．Ａｃｔａ日ｅｃ咖ｉｃａ（ｉｎａ妇）
Ｓｉｎｉｃａ，２００５，３３（１０）：１８０３—１８０７．
Ｇ硼ａｈＷ
Ｊ．Ａｇｅｎｅｒａｌｉｚｅｄｃｏｎｖｅｒｇｅｎｃｅｒｅｓｕｌｔｆｏｒｔｈｅｇｒａｐｈ
ｂａｓｅｄ
ａｎｔｓｙｓｔｅｍｍｅｔａｈｅｎｒｉｓｔｉｃ【Ｒ］．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ９９—０９，
Ａｕｓｔｒｉａ，Ｄｅｐｔ．ｏｆＳｔａｔｉｓｔｉｃｓａｎｄＤｅｃｉｓｉｏｎＳｕｐｐｏｒｔＳｙｓｔｅｍｓ，Ｕｎｉ—ｖｅｒｓｉｔｙｏｆＶｉｅｎｎａ：１９９９．
万方数据
学报
２００９焦
［１０］Ｇ叫ａｈｒＷ
Ｊ．Ａｇｒａｐｈ－ｂａｓｅｄ
ａｎｔ
ｓｙｓｔｅｍａｎｄｉｔｓｃｏｎｖｅｒｇｅｎｃｅ
［Ｊ］．ＦｕｔｕｒｅＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｉｎｇ
Ｓｙｓｔｅｍｓ，２０００，１６（９）：８７３
—８８８．
［１１］ｏａｔｊａｈＷＪ．ＡＣＯ
ａｌｇｏｒｉｔｈｍｓｗｉｔｈｇｕａｒａｎｔｅｅｄ
ｃｏｎｖｅｒｇｅｎｃｅ
ｔｏ
ｔｈｅｏｐｔｉｍａｌ
ｓｏｌｕｆｉｏｎ［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＬｅｔｔｅｒｓ，２００２，
８２（３）：１４５—１５３．［１２］Ｓｔｉｉｔｚｌｅ
Ｔ，Ｄｏｒｉｇｏ
Ｍ．Ａｓｈｏｒｔｃｏｎｖｅｒｇｅｎｃｅｐｒｏｏｆｆｏｒ
ａｃｌａｓｓｏｆ
ａｎｔ
ｃｏｌｏｎｙ
ｏｐｆｉｎｌｉｚｚｆｉｏｎａｌｇｏｒｉｔｈｍｓ［ＪＪ．ＩＥＥＥＴｒａｎｓａｃｆｉｏｍＯｎ
Ｅｖｏｌｕｔｉｏｎａｒｙ
Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（４）：３５８—３６５．
［１３］Ｂａｄｒ
Ａ，ＦａｈｍｙＡ．Ａｐｒｏｏｆｏｆ
ｃｏｎｖｅｒｇｅｎｃｅｆｏｒａｎｔａｌｇｏｒｉｔｈｍｓ
［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｓ，２００４，１６０（１－４）：２６７—２７９．［１４］朱庆保．蚁群优化算法的收敛性分析．控制与决策［Ｊ］．
２００６，２１（７）：７６３—７６６．
ＺＨＵ
Ｑｉｎｇ－ｂａｏ．Ａｎａｌｙｓｉｓ
ｏｆ
ｃｔｍｖｅｒｇｅｎｃｅｏｆ
ａｎｔ
ｃｏｌｏｎｙｏｐｔｉ・
ｍｉｚａｔｉｏｎ
ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｃｏｎｔｒｏｌ
ａｎｄ
Ｄｅｃｉｓｉｏｎ，２００６，２１（７）：
２６７—２７９．（ｉｎＣｈｉｎｅｓｅ）
［１５］段海滨，王道波，于秀芬．基本蚁群算法的Ａ．ｓ．收敛性
研究［Ｊ］．应用基础与工程科学学报，２００６，１４（２）：２９７—
３０１．
ＤＵＡＮＨａｌ—ｂｉｎ，ＷＡＮＧ
Ｄａｏ－ｂｏ，ＹＵ
Ｘｉｕ－ｆｅｎ．Ｒｅｓｅａｒｃｈ
０１１
ｔｈｅａ．ｓ．ｃｏｎｖｅｒｇｅｎｃｅｐｔＤｐｅｒｆｉｅｓｏｆｂａｓｉｃ
ａｎｔ
ｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ
［Ｊ］．Ｊｏｕｒｎａｌ
ｏｆＢａｓｉｃＳｃｉｅｎｃｅａｎｄ
Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，１４（２）：
２９７—３０１．（ｉｎＣｈｉｎｅｓｅ）
［１６］张波，张景肖．应用随机过程［Ｍ］．北京：清华大学出版
社．２００４．
ＺＨＡＮＧＢｏ，ＺＨＡＮＧＪｉｎｇ－ｘｉａｏ．ＡｐｐｌｉｅｄＳｔｏｃｈａｓｔｉｃＰｒｏｃｅｓｓｅｓ
［Ｍ］．Ｂｅｉｊｉｎｇ：ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ
Ｐｒｅｓｓ，２００４．（ｉｎＣｈｉｎｅｓｅ）
【１７］Ｅｄｗａｒｄ
ＰＣＫ．ＡｎＩｎｔｒｏｄｕｃｔｉＯｉｌｔｏＳｔｏｃｈａｓｔｉｃ
ＰｒｏｃｅｓｓｅｓｌＭＪ．
Ｂｅｌｍｏｎｔ，Ｃａｌｉｆ．，Ｌｏｎｄｏｎ：ＯｕｘｂｕｒｙＰｒｅｓｓ，１９９７．
［１８］Ｓｔｉａｔｚｌｅ
Ｔ，ＨｃｏｓＨＨ．Ｍａｘ—Ｍｉｎ
ａｎｔ
ｓｙｓｔｅｍ［Ｊ］．ＦｕｔｕｒｅＧｅｎｅｒａ－
ｔｉｏｎＣｏｍｐｕｔｅｒ
Ｓｙｓｔｅｍ，２０００，１６（８）：８８９—９１４．
作者简介：
苏兆品女。１９８３年８月出生于山东菏泽，在站博士后．主要研究方向：智能控制、进化计算、ａｇｅｎｔ理论等．
Ｅ－ｍａｉｌ：ｓｚｐ＠ｈｆｕｔ．ｅｄｕ．ｃｎ
蒋建国男，１９５５年１０月出生于安徽黄山，教授，博士生导师．主要研究方向：分布式智能控制系统，数字图像分析与处理，ＤＳＰ技术与应用等．
Ｅ－ｍａｉｌ：ｊｊｇ＠ａｈｌ６５．ｎｅｔ
［６］徐宗本，聂赞坎，张文修．遗传算法的几乎必然强收敛性
［７］王霞，周国标．整体退火遗传算法的几乎处处强收敛性
［８］罗小平，韦巍．生物免疫遗传算法的几乎处处强收敛性分
１９Ｊ
蚁群算法的几乎处处强收敛性分析
作者：作者单位：
苏兆品， 蒋建国， 梁昌勇， 张国富， 夏娜， SU Zhao-pin， JIANG Jian-guo， LIANG Chang-yong ， ZHANG Guo-fu， XIA Na
苏兆品,SU Zhao-pin(合肥工业大学计算机与信息学院,安徽合肥,230009;合肥工业大学管理科学与工程博士后科研流动站,安徽合肥,230009)， 蒋建国,夏娜,JIANG Jian-guo,XIANa(合肥工业大学计算机与信息学院,安徽合肥,230009;安全关键工业测控技术教育部工程研究中心,安徽合肥,230009)， 梁昌勇,LIANG Chang-yong(合肥工业大学管理科学与工程博士后科研流动站,安徽合肥,230009)， 张国富,ZHANG Guo-fu(合肥工业大学计算机与信息学院,安徽合肥,230009;安全关键工业测控技术教育部工程研究中心,安徽合肥,230009;特种显示技术教育部重点实验室,安徽合肥,230009)电子学报
ACTA ELECTRONICA SINICA2009，37(8)2次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(18条)
1. Colorni A. Dorigo M. Maniezzo V Distributed optimization by ant colonies 1991
2. Dorigo M. Gambardella L M Ant colony system:A cooperative learning approach to the travelingsalesman problem 1997(01)
3. Montemanni R. Smith D H. Allen S M An ANTS algorithm for the minimum-span frequency-assignmentproblem with multiple interference 2002(05)
4. 蒋建国. 夏娜. 齐美彬. 木春梅 一种基于蚁群算法的串行多任务联盟生成算法[期刊论文]-电子学报 2005(12)5. 吴春明. 陈治. 姜明 蚁群算法中系统初始化及系统参数的研究[期刊论文]-电子学报 2006(08)6. 徐宗本. 聂赞坎. 张文修 遗传算法的几乎必然强收敛性--鞅方法[期刊论文]-计算机学报 2002(08)7. 王霞. 周国标 整体退火遗传算法的几乎处处强收敛性[期刊论文]-应用数学 2003(03)
8. 罗小平. 韦巍 生物免疫遗传算法的几乎处处强收敛性分析及收敛速度估计[期刊论文]-电子学报 2005(10)9. Giitjahr W J A generalized convergence result for the graph based ant systemmetaheuristic[Technical Report 99-09] 1999
10. Gǖtjahr W J A graph-based ant system and its convergence 2000(09)
11. Gǖtjahr W J ACO algorithms with guaranteed convergence to the optimal solution 2002(03)12. Stǖtzle T. Dorigo M A short convergence proof for a class of ant colony optimization algorithms2002(04)
13. Badr A. Fahmy A A proof of convergence for ant algorithms 2004(1-4)14. 朱庆保 蚁群优化算法的收敛性分析[期刊论文]-控制与决策 2006(07)
15. 段海滨. 王道波. 于秀芬 基本蚁群算法的A.S.收敛性研究[期刊论文]-应用基础与工程科学学报 2006(02)16. 张波. 张景肖 应用随机过程 2004
17. Edward PC K An Introduction to Stochastic Processes 199718. Stǖtzle T. Hoos H H Max-Min ant system 2000(08)
相似文献(6条)
1.期刊论文 梁亮. 郭波 基于混合蚁群算法的产品开发过程优化方法 -系统工程理论与实践2009,29(10)
通过对迭代产品开发过程的分析,提出了将产品开发过程中设计活动被首次访问视为TSP问题中蚂蚁访问城市的思想,将Markov过程建模方法与基本蚁群算法相结合,建立了混合蚁群算法对产品开发过程进行优化求解.示例表明该方法成功地将蚁群算法扩展到复杂产品开发过程优化问题,在考虑设计迭代以及设计活动完成时间服从任意分布的情况下,建立了产品开发过程优化模型,为该类问题的求解提供了一个新的思路和方法.
2.期刊论文 黄翰. 郝志峰. 吴春国. 秦勇. HUANG Han. HAO Zhi-Feng. WU Chun-Guo. QIN Yong 蚁群算法的收敛速度分析 -计算机学报2007,30(8)
蚁群算法(ACO)作为一类新型的机器学习技术,已经广泛用于组合优化问题的求解,同时也应用于工业工程的优化设计.相对于遗传算法(GA),蚁群算法的理论研究在国内外均起步较晚,特别是收敛速度的分析理论是该领域急待解决的第一大公开问题.文中的研究内容主要是针对这一公开问题而开展的.根据蚁群算法的特性,该研究基于吸收态Markov过程的数学模型,提出了蚁群算法的收敛速度分析理论.作者给出了估算蚁群算法期望收敛时间的几个理论方法,以分析蚁群算法的收敛速度,并结合著名的ACS算法作了具体的案例研究.基于该文提出的收敛速度分析理论,作者还提出ACO-难和ACO-易两类问题的界定方法;最后,利用ACS算法求解TSP问题的实验数据,验证了文中提出的分析结论,得出了初步的算法设计指导原则.
3.学位论文 刘立东 改进蚁群优化算法的研究 2007
蚁群优化算法是由意大利学者Dorigo等人受到蚂蚁觅食行为的启发提出的一种新型的智能仿生类进化算法。大量实验结果表明，它在解决许多组合优化问题时都能表现出较好的求解能力，目前此算法已经得到了比较广泛的应用。但是与其它仿生学进化算法相比，蚁群算法存在搜索时间长、易陷入局部最优等缺点。本文针对蚁群算法的这些缺点，给出了3种改进的算法，并将其用于求解旅行商问题，主要内容如下：
1.通过对基本蚁群算法初始化参数的分析，给出了一种通过自适应改变启发式因子α和期望启发式因子β的蚁群算法。当算法在连续给定代数进化后的最优解没有变化时，改进后的算法通过对启发式因子α和期望启发式因子β的自适应调整来提高全局最优解的求解质量。通过对TSP问题的仿真表明改进后的蚁群算法在求解最优解和收敛速度方面与基本蚁群算法相比存在优势。
2.通过对基本蚁群算法初始化参数的分析，给出了一种基于信息素挥发因子ρ自适应调整的蚁群算法，当算法在连续给定代数进化后的最优解没有变化时，改进后的算法通过对信息素挥发因子ρ的自适应调整来提高全局最优解的求解质量，并证明了该算法在迭代次数充分大时能以概率1收敛到全局最优解。通过对TSP问题的仿真实验表明改进后的蚁群算法在求解最优解和收敛速度上与基本蚁群算法相比存在优势。
3.对已有的融入遗传算法的混合蚁群算法进行改进。算法在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算。对优秀解公共解集的保留加快了算法收敛速度，引入交叉和变异扩大了解的搜索空间，提高了解的全局性。最后用Markov过程证明了当迭代次数充分大时算法能以概率1收敛到满意解集。通过对TSP问题的仿真表明融入遗传算法的蚁群算法在收敛速度和解的全局性上都有较大的改善。 最后，对全文的研究工作进行了总结，并展望了蚁群优化算法进一步还要研究的课题。
4.学位论文 梁亮 快速响应制造系统产品开发过程可靠性评估与优化方法 2008
快速响应制造系统是基于“快速响应”原理，面向快速多变的市场需求而提出的。提高产品开发过程可靠性对于缩短产品研制周期，保障系统的快速响应能力具有重要的意义，本文针对快速响应制造系统的产品开发过程开展了可靠性分析建模与优化方法研究。
首先，在柔性制造系统等先进制造系统可靠性研究的基础上，提出了快速响应制造系统可靠性的定义以及系统可靠度的计算方法；在此基础上针对产品开发过程，通过对任务过程的分析提出了系统可靠性建模的思路和方法；针对负指数分布在可靠性建模中的局限性，基于PH分布开展了产品开发过程可靠性建模研究，考虑研制时间服从任意分布的情形分别建立了串行、并行以及重叠关系的产品开发过程可靠性模型。
其次，考虑设计迭代的影响，开展了产品开发过程可靠性评估与优化方法研究。在可靠性评估方面，通过对考虑设计迭代的任务过程进行分析，提出了任务阶段的划分方法；在此基础上，分别针对研制时间服从负指数分布和任意分布的情形，以及设计迭代参数随迭代次数变化的情形进行研究，基于多阶段Markov过程建立了快速响应制造系统产品开发过程可靠性模型。在可靠性优化方面，针对产品开发过程规模增大时，优化模型求解中出现的NP-hard问题，提出了将Markov过程与基本蚁群算法相结合，基于混合蚂蚁群算法对可靠性优化问题进行建模求解，实例研究说明了该方法能够解决大规模产品开发过程的可靠性优化问题，为产品开发过程优化提供了有效的手段和方法。
第三，针对快速响应制造系统同时承担多个研制任务的情形，从系统可靠性评估与收益综合优化这两个方面开展研究工作。针对产品开发过程多任务可靠性评估问题，考虑设计迭代和多任务下资源冲突的影响，采用排队网络对产品开发过程进行描述，考虑研制部门有单个小组和多个小组的情形分别建立了可靠性评估模型。针对收益综合优化问题，在系统多任务可靠性建模分析的基础上，以系统接受的最大任务数量为优化变量，以系统收益最大为目标建立了优化模型，并基于半开排队网络模型对优化参数进行建模求解。实例研究与敏感性分析说明了可靠性模型和优化方法为评估多任务下产品开发过程可靠性，分析系统薄弱环节，进而改进系统，提高系统收益提供了理论方法和优化策略。
第四，针对重叠关系的产品开发过程开展了可靠性评估方法研究。考虑设计迭代和研制任务完成时间服从随机分布的情况下，提出了设计迭代参数的表示方法；通过任务过程分析，提出了任务阶段的划分方法，采用Markov过程方法建立了产品开发过程可靠性评估模型。
最后，基于仿真方法开展了快速响应制造系统可靠性评估方法研究，结合可靠性解析建模的理论研究成果进行了系统可靠性分析软件的设计与开发工作，并针对实际需求开展了应用研究。
5.期刊论文 孙焘. 王秀坤. 刘业欣. 张名举 一种简单蚂蚁算法及其收敛性分析 -小型微型计算机系统2003,24(8)
该文首先介绍了一种可用于函数优化的简单蚂蚁算法,该算法具备了传统蚂蚁算法的基本特征,并给出了变异和最优保存两点改进.然后在给定近似精度的基础上通过Markov过程分析,得出了该算法的全局收敛性.同时,通过对衰减度、变异率等参数的定性讨论,得出了参数的取值对算法性能的影响,并从理论上说明,传统蚁群算法通常的选择概率公式是有缺陷的,而具有变异机制的蚂蚁算法要好于传统蚂蚁算法.该文的实例则说明了文中所给算法的有效性和相关理论论述的正确性.
6.学位论文 张国富 基于群智能的复杂联盟机制研究 2008
基于多agent系统(Multi-agent systems、MAS)的分布式智能控制正在蓬勃兴起，以适应计算机支持的协同工作等应用需求，因而使得对MAS中的联盟研究也变得越来越重要。如何形成一个稳定均衡的联盟，使联盟朝着稳定的方向发展，是控制理论的前沿课题，已经成为迫切需要解决的关键问题。传统的研究方法仅考虑一个agent只能加入一个联盟，势必造成agent能力和资源的极大浪费，而且在很多应用场合不能满足实际系统的需要。
基于上述背景，本文提出“复杂联盟”的概念，并引入群智能技术，力图在多任务环境中实现真正意义上的一个agent可以同时加入多个联盟和一个联盟可以同时承担多个任务，从而能在一定程度上提高系统的任务求解效率和资源利用率，为解决复杂控制问题提供理论指导和方法依据。本文的主要内容及创新之处如下：
(1)提出一种基于多粒子群协同优化的复杂联盟串行生成算法。基于图论的思想，给出了“虚拟agent”的概念，旨在转移父联盟的剩余能力，由“虚拟agent”代表其父联盟参与后续任务的竞争，在一定程度上解决了agent资源和能力的浪费问题。实验结果表明，本算法对于任务较多且较简单的情形特别有效。
(2)将离散粒子群算法扩充到二维二进制编码，实现复杂联盟的并行生成。算法中设计的编码有效性检查、冲突消解策略克服了求解过程中因多个任务求解联盟同时竞争某个能力有限的agent而导致的资源冲突和联盟死锁，而且实现了真正意义上的一个agent可以参加多个联盟，在一定程度上可以提高系统的资源利用率。
(3)提出一种基于按劳分配和效用非减的效用分配策略。针对已有工作无法摆脱搭便车问题，导致联盟潜在的不稳定，采用拍卖机制对任务进行快速和有效分解，基于合同机制对联盟效用以及额外效用进行合理分配，并依据联盟机制的数学模型推导出了局部效用非减和全局效用非减应满足的条件。该策略既严格遵循按劳分配又完全符合效用非减，在具有超加性的面向任务的领域中可以形成全局最优联盟，并具有Nash均衡意义下的稳定性。
(4)基于Markov过程和鞅理论推演了蚁群算法的几乎处处强收敛性，并提出一种基于蚁群正反馈的动态联盟形成策略。利用蚁群中的信息素浓度表示熟人之间的熟悉度，以信息素更新规则作为熟悉度调整规则。仿真实验的测试及分析说明了该策略能在一定程度上降低整个系统的通信代价和资源开销，提高了系统的可靠程度。
引证文献(2条)
1. 夏娜. 徐顺安. 于春华. 唐媚 导航卫星载体姿态测量进化算法研究[期刊论文]-小型微型计算机系统 2010(5)
2. 别文群. 苏虹 基于蚁群算法的高层固定货架最短路径问题研究[期刊论文]-郑州轻工业学院学报（自然科学版）2009(6)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dianzixb200908003.aspx授权使用：广西民族大学(dxmzdx)，授权号：c3740afd-8e51-40ef-8cab-9e4500b8844e
下载时间：2010年12月7日