资源描述：
《蚁群算法的收敛速度分析_黄翰.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第30卷第8期计算机学报Vol.30No.82007年8月CHINESEJOURNALOFCOMPUTERSAug.2007蚁群算法的收敛速度分析1)1),2)3)4)黄翰郝志峰吴春国秦勇1)(华南理工大学计算机科学与工程学院广州510640)2)(南京大学软件新技术国家重点实验室南京210093)3)(吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室长春130012)4)(茂名学院信息与网络中心广东茂名525000)摘要蚁群算法(ACO)作为一类新型的机器学习技术,已经广泛用于组合优化问题的求解,同时也应
2、用于工业工程的优化设计.相对于遗传算法(GA),蚁群算法的理论研究在国内外均起步较晚,特别是收敛速度的分析理论是该领域急待解决的第一大公开问题.文中的研究内容主要是针对这一公开问题而开展的.根据蚁群算法的特性,该研究基于吸收态Markov过程的数学模型,提出了蚁群算法的收敛速度分析理论.作者给出了估算蚁群算法期望收敛时间的几个理论方法,以分析蚁群算法的收敛速度,并结合著名的ACS算法作了具体的案例研究.基于该文提出的收敛速度分析理论,作者还提出ACO2难和ACO2易两类问题的界定方法;最后,利用ACS算法求解TSP问题的
3、实验数据,验证了文中提出的分析结论,得出了初步的算法设计指导原则.关键词蚁群算法;吸收态Markov过程;期望收敛时间;ACO2难易问题;优化路径中图法分类号TP181TheConvergenceSpeedofAntColonyOptimization1)1),2)3)4)HUANGHanHAOZhi2FengWUChun2GuoQINYong1)(CollegeofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510640
4、)2)(StateKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,Nanjing210093)3)(CollegeofComputerScienceandTechnology,KeyLaboratoryofSymbolComputationandKnowledgeEngineeringofMinistryofEducation,JilinUniversity,Changchun130012)4)(CenterofInformationandNetwork
5、,MaomingUniversity,Maoming,Guangdong525000)AbstractAntcolonyoptimization(ACO)whichisoneofthepopularmethodsinmachinelearn2ingisusedwidelytosolvecombinatorialoptimizationproblems.However,therearefewtheoreti2calstudiesforACO,comparedwiththecounterpartsforgeneticalgo
6、rithm(GA).Howtoana2lyzetheconvergencespeedisthefirstopenproblemofACOresearch.InthispaperthefirstopenproblemisstudiedviamodelingACOalgorithmasanabsorbingMarkovprocess,basedonwhichthetheoreticalresultsofconvergencespeedarepresented.TheconvergencespeedofACOalgo2rith
7、misanalyzedbyestimatingtheexpectedconvergencetime.TheauthorsproposethemethodtoestimatingtheexpectedconvergencetimeofACOalgorithm,andtheapproachtojudgingwhetheraTSPproblembelongstoACO2easyclassorACO2hardclass.Finally,theconvergencespeedofantcolonysystem(ACS)isanal
8、yzedasanexampletodemonstratetheeffectivenessofthetheoryproposedinthispaper.Keywordsantcolonyoptimization;absorbingMarkovprocess;expectedconvergencetime;ACO2har
