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

《蚁群算法的收敛速度分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第30卷第8期计算机学报v01．30No．811竺兰!叁呈坚!些星!三!皇坚呈些垒兰呈三呈竺坠!坚三三垦!垒：!：!!!!蚁群算法的收敛速度分析黄翰”郝志峰”。’吴春国”秦勇。1’(华南理工大学计算机科学与工程学院广州510640)2’(南京大学软件新技术国家重点实验室南京210093)3’(吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室长春130012)‘’(茂名学院信息与网络中心广东茂名52500。)捕要蚁群算法(AcO)作为～类新型的机器学习技术，已经广泛用于组台优化问题的求解，同时也应用于工业工程的优化设计．相对于遗传算

2、法(GA)，蚁群算法的理论研究在国内外均起步较晚，特别是收敛速度的分析理论是该领域急待解决的第一大公开问题．文中的研究内容主要是针对这一公开问题而开展的．根据蚁群算法的特性，该研究基于吸收态Mark。v过程的数学模型，提出了蚁群算法的收敛速度分析理论．作者给出了估算蚁群算法期望收敛时间的几个理论方法，以分析蚁群算法的收敛速度，并结合著名的Acs算法作了具体的案倒研究．基于该文提出的收敛速度分析理论，作者还提出AcO一难和AC0一易两类问题的界定方法；最后，利用Acs算法求解TsP阃题的实验数据。验证了文中提出的分析结论，得出了初步的算法设计指导原则．关

3、键词蚁群算法，吸收态Markov过程；期望收敛时问；Ac0一难易问题；优化路径中圈法分类号TPl8lTheConVergenceSpeedofAntColonyoptimizationHUANGHan”HAOZhi—Fen91’埘WUChun_Gu03’QINYon94’1’(＆z如gPD，com户H￡盯sclPncf目"d凸g⋯，mgt50“施凸t扎4哳删；叫o，nc^nozo鲋，函口”脚船5】0640)o‘s把&Ke，Ln如rⅡ￡07，，0rNo刊s。^t叫比Tech加kgy，N蛐{mgUm珊H，，N曲Jtng21009∞”(c0地geo，cD抛p

4、“抛rs删㈨ndnch加fogy，K删Ld6帆2￡o叫。，曲础以＆优pu￡Ⅱf圳d划K㈣f#dgeEn舒n刚”gD，M‘nt鲫寸o，EdH∞“0^，，ifz4【ht椰2印，凸口”g矗“n130012)”(＆nf盯。，如，0rmⅡfI。俐d^■m日靠，^缸咖2ngu”㈣z廿，M口㈣“g，G瑚ngd卯g525000)AbstractAntcoloⅡyoptimization(AC0)whichlsoneofthepopularmethodsinmachinelearn—i“gisusedwidelytosolvecombinatorialoptimizat

5、ionproblems．However，therearefewtheoreti—calstudiesforACO，comparedwiththecounterpartsforgeneticalgonthm(GA)．Howtoana一1yzetheconve唱encespeedisthefirstopenproblemofAoDresearch．InthispaperthefirstopenproblemisstudiedviamodelingACOalgorithma8anabsorbingMarkovprocess，basedonwhichtheth

6、eoreticalresultsofconvergencespeedarepresented．Theconvergence8peedofA00algo—rithmisanalyzedbyestimatingtheexpectedconvergencetjme．TheauthorsproposethemethodtoestimatingtheexpectedconvergencetimeofACoaIgor“hm，andtheapproachtojudgingwhetheraTSPproblembelongstoAC0一easyclassorACO—ha

7、rdclass．Finally，theconvergencespeedofantcolonysystem(ACS)isanalyzedasanexampletodemonstratetheeffectivenessofthetheo。yproposedinthispaper．Keywordsantcolo“yoptimization；absorbingMarkov∞ocess；expectedconve。gencetlme；ACO_hardandACO—easyproblem5；optimalpath收藕日期；2007一∞一04i修改稿收到日期；2。0

8、7一05—25．本课题得到国家自然科学基金(60433020，10471045，6067302