资源描述：
《蚁群算法原理与应用课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、自然计算与群体智能计算机应用技术研究所1蚁群算法赵林亮计算机应用技术研究所zhaoll@acm.org2参考文献APPEAREDINPROCEEDINGSOFECAL91-EUROPEANCONFERENCEONARTIFICIALLIFE,PARIS,FRANCE,ELSEVIERPUBLISHING,134–142.DistributedOptimizationbyAntColoniesAlbertoColorni,MarcoDorigo,VittorioManiezzoDipartimentodiElettronica,Polit
2、ecnicodiMilanoPiazzaLeonardodaVinci32,20133Milano,ItalyIEEETransactionsonSystems,Man,AndCybernetics-PartB:Cybernetics,Vol.26,No.1,Feb1996.29-41AntSystem:OptimizationbyaColonyofCooperatingAgentsMarcoDorigo,Member,IEEE,VittorioManiezzo,andAlbertoColornihttp://iridia.ulb.ac
3、.be/~mdorigo/HomePageDorigo/3Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.4Fig.2.Anexamplewithartificialan
4、tsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.5双桥实验(GossS,1989)Naturwissenschaften76,579-5
5、81(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles6Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):p
6、hotostaken4and8minafterplacementofthebridge7双桥实验数学模型假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目mA+mB=m当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：8参数h和k用以匹配真实实验数据第m+1只蚂蚁首先计算然后生成一个在区间[0,1]上均匀分布的
7、随机数若，则选择桥A，否则选择桥B9基本蚁群算法的数学模型10P、NP、NP-C、NP-hard问题P类问题所有可用DTM(Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合。简记为O(p(n))即P={L:存在一个多项式时间DTM程序M，是的L=LM},其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题Π，即L[Π,e]∈P,则称该判定问题属于P类问题。11P、NP、NP-C、NP-hard问题NP类问题(Non-determinist
8、icPolynomial)若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I)),其中d(I)为I的输入长度，且验证算法中S为I的“是
