蚁群算法的收敛速度分析.pdf

第30卷第8期 计 算 机 学 报 No．8 v01．30 11竺兰!叁 呈坚!些星!三!皇坚呈些垒兰呈三呈竺坠!坚三三垦! 垒：!：!!!! 蚁群算法的收敛速度分析 黄 翰” 郝志峰”。’ 吴春国”秦勇。 1’(华南理工大学计算机科学与工程学院广州510640) 2’(南京大学软件新技术国家重点实验室南京210093) 3’(吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室长春130012) ‘’(茂名学院信息与网络中心广东茂名52500。) 捕要蚁群算法(AcO)作为～类新型的机器学习技术，已经广泛用于组台优化问题的求解，同时也应用于工业 工程的优化设计．相对于遗传算法(GA)，蚁群算法的理论研究在国内外均起步较晚，特别是收敛速度的分析理论 是该领域急待解决的第一大公开问题．文中的研究内容主要是针对这一公开问题而开展的．根据蚁群算法的特性， 该研究基于吸收态Mark。v过程的数学模型，提出了蚁群算法的收敛速度分析理论．作者给出了估算蚁群算法期望 收敛时间的几个理论方法，以分析蚁群算法的收敛速度，并结合著名的Acs算法作了具体的案倒研究．基于该文 提出的收敛速度分析理论，作者还提出AcO一难和AC0一易两类问题的界定方法；最后，利用Acs算法求解TsP阃 题的实验数据。验证了文中提出的分析结论，得出了初步的算法设计指导原则． 关键词蚁群算法，吸收态Markov过程；期望收敛时问；Ac0一难易问题；优化路径 中圈法分类号TPl8l The ofAnt ConVergenceSpeed Colonyoptimization HUANGHan”HAO WUChun_Gu03’QINYon94’ Zhi—Fen91’埘 1’(＆z如gPD，com户H￡盯sclPncf目d凸g…，mgt 50“施凸t扎4哳删；叫o，nc^nozo鲋，函口”脚船5】0640) 21009∞ o‘s把Ke，Ln如rⅡ￡07，，0rNo刊s。^t叫比Tech加kgy，N蛐{mgUm珊H，，N曲Jtng ”(c0地geo，cD抛p“抛rs删㈨ndnch加fogy，K删Ld6帆2￡o叫。，曲础以＆优pu￡Ⅱf圳d划 130012) K㈣f#dgeEn舒n刚”gD，M‘nt鲫寸o，EdH∞“0^，，ifz4【ht椰2印，凸口”g矗“n 525000) ”(＆nf盯。，如，0rmⅡfI。俐d^■m日靠，^缸咖2ngu”㈣z廿，M口㈣“g，G瑚ngd卯g Abstract in Ant lsoneofthe methodsmachinelearn— coloⅡyoptimization(AC0)whichpopular isused tosolvecombinatorial are fewtheoreti— i“g widely