資源描述：
《求解復(fù)雜tsp問(wèn)題的隨機(jī)擾動(dòng)蟻群算法new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、2002年9月系統(tǒng)工程理論與實(shí)踐第9期 文章編號(hào):100026788(2002)0920088204求解復(fù)雜TSP問(wèn)題的隨機(jī)擾動(dòng)蟻群算法121郝 晉,石立寶,周家啟(1重慶大學(xué)電氣工程學(xué)院,重慶400044;2.上海交通大學(xué)電子信息與電氣工程學(xué)院,上海200030)摘要:針對(duì)基本蟻群算法,設(shè)計(jì)出一種新穎的隨機(jī)擾動(dòng)蟻群算法,并將其應(yīng)用于求解復(fù)雜TSP問(wèn)題L該算法包含了兩個(gè)重要方面:一是提出了采用倒指數(shù)曲線來(lái)描述的擾動(dòng)因子;二是設(shè)計(jì)出了相應(yīng)的隨機(jī)選擇策略和擾動(dòng)策略L數(shù)值模擬表明:該算法可以有效地克服基本蟻群算法的計(jì)算時(shí)間較長(zhǎng)和容易出現(xiàn)停滯現(xiàn)象
2、的缺陷,具有更好的全局搜索能力L此外,還對(duì)該算法中參數(shù)的取值范圍及選取方法進(jìn)行了研究和探討L關(guān)鍵詞:蟻群算法;隨機(jī);擾動(dòng)策略;TSP問(wèn)題中圖分類號(hào):TP18文獻(xiàn)標(biāo)識(shí)碼:AAnAntSystemAlgorithmwithRandomPerturbationBehaviorforComplexTSPProblemHAOJin,SHILi2bao,ZHOUJia2qi(1.ElectricalEngineeringCollege,ChongqingUniversity,Chongqing400044,China;2.ElectronicInfo
3、rmationandElec2tricalEngineeringCollege,ShanghaiJiaotongUniversity,Shanghai200030,China)Abstract:BasedontheBasicAntSystem(BAS)algorithm,anovelAntSystemwithRandomPertur2bationBehavior(RPAS)ispresentedinthispaper,anditisappliedtosolvecomplexTSPproblem.Thenewalgorithminclude
4、stwoimportantaspects:aperturbationfactorformulatedbyinverseexponentfunctionisdeveloped,ontheotherhand,correspondingtransitionstrategywithrandomselectionandperturbationbehaviorisdesigned.Numericalsimulationdemonstratesthatthenewalgorithmpossessesmorestrongglobaloptimizatio
5、ncapability,andbringsaboutsomegoodresultsonreducingCPUtime,preventingsearchfrombeinginstagnationbehavior.Furthermore,numericareaandselectionmethodofparametersinthenewalgorithmareexploringlystudied.Keywords:antsystemalgorithm;random;perturbationstrategy;TSPproblem1 引言自20世紀(jì)
6、50年代中期創(chuàng)立了仿生學(xué)以來(lái),人們從生物進(jìn)化的機(jī)理中受到啟發(fā),提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的方法,如基因算法、蟻群算法等L其中,蟻群算法(AntSystemalgorithm)是由意大利學(xué)者[1]M.Dorigo近幾年才提出的一種新型的模擬進(jìn)化算法L該算法即是模擬自然界中真實(shí)蟻群的覓食行為而形成的一種模擬進(jìn)化算法L它采用有記憶的人工螞蟻,通過(guò)個(gè)體之間的信息交流與相互協(xié)作來(lái)找到從蟻穴到食物源的最短路徑L目前蟻群算法在求解旅行推銷商(TSP)、指派(assignmentproblem)、job2shop調(diào)度等優(yōu)化問(wèn)題中,得到了一系列較好的應(yīng)
7、用L在M.Dorigo提出的基本蟻群算法(BasicAntSystem,BAS)中,給出了三種不同的模型,分別稱為[1]Ant2CycleSystem,Ant2QuantitySystem,Ant2DensitySystem,它們之間的區(qū)別在于:后兩種模型利用的是局部信息,而前者為整體信息,求解優(yōu)化問(wèn)題時(shí)性能較好,通常將其作為蟻群算法基本模型L眾多研究已經(jīng)證明蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力,這是因?yàn)樵撍惴ú粌H利用了正反饋原理,在一定程度上[2,3]加快進(jìn)化進(jìn)程,而且是一種本質(zhì)并行算法L但算法本身也存在一些缺陷,如搜索時(shí)間較長(zhǎng),而且容易
8、出收稿日期:2001203226?1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第9期求解復(fù)雜TSP問(wèn)題的隨機(jī)擾動(dòng)
