蚁群算法的几乎处处强收敛性分析  

An Almost Everywhere Strong Convergence Proof for a Class of Ant Colony Algorithms

作　　者：苏兆品[1,2] 蒋建国[1,3] 梁昌勇[2] 张国富[1,3,4] 夏娜[1,3] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009 [2]合肥工业大学管理科学与工程博士后科研流动站,安徽合肥230009 [3]安全关键工业测控技术教育部工程研究中心,安徽合肥230009 [4]特种显示技术教育部重点实验室,安徽合肥230009

出　　处：《电子学报》2009年第8期1646-1650,共5页Acta Electronica Sinica

基　　金：国家教育部博士点基金(No.20060359004);安徽省自然科学基金(No.090412058;070412035);特种显示技术教育部重点实验室开放课题基金(No.2008HGXJ0350);合肥工业大学博士专项科研资助基金(No.GDBJ2009-003)

摘　　要：蚁群算法是一种新型的模拟进化算法,已在很多组合优化问题中得到成功应用,但其收敛性分析还比较缺乏.以TSP问题来描述一类蚁群算法的数学模型,并通过对状态空间的分解和反射壁的构筑,从鞅理论角度论证了该类蚁群算法的几乎处处强收敛性以及能在有限步内收敛到全局最优解集,试图为蚁群算法的研究探索一条新的思路.Ant Colony Optimization is a novel simulated evolutionary algorithm which has been used successfully to solve many complicated combinatorial optimization problems, but its convergence analysis is seldom researched. The mathematical model of a class of ant colony algorithms is described by TSP problem. On the basis of the decomposition of state space and the construedon of reflecting battier, an almost everywhere strong convergence of the algorithms and the quality that the algorithms can guarante.edly converge to a global optimum set in a finite number of steps are demonstrated by using the martingale theory, and the obtained results may provide a new methodology for convergence analysis of the algorithms.

关 键 词：蚁群算法 MARKOV过程 鞅 几乎处处强收敛 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]