群智能是近年來人工智能研究的一個熱點話題蟻群算法作

1、PAGE PAGE 28摘 要要群智能是近近年來人工工智能研究究的一個熱熱點話題。蟻群算法法作為群智智能算法的的一個熱點點，是意大利利學(xué)者M. Dorrigo通通過模擬蟻蟻群覓食行行為提出的的。本文首先先介紹了群群智能，然后詳細細介紹蟻群群算法原理理及其優(yōu)缺缺點。接著依據(jù)大量實驗對對參數(shù)m、Q的選擇進行行研究，得出其選選擇規(guī)律，并在以前學(xué)學(xué)者“三步走”的基礎(chǔ)上上提出了一種“四步走”的有效方方法來選擇擇蟻群算法法最優(yōu)組合合參數(shù)，然后對蟻群群改進算法法進行分析析，同時以實驗驗的方式對對這幾種算算法各自求求解TSPP問題的性性能進行了了對比分析析，得出性能能結(jié)果排名名，并發(fā)現(xiàn)當(dāng)TTSP問題題最優(yōu)解相

2、相同時還可可以依據(jù)其其他性能（迭迭代次數(shù)、迭代時間間等）得出出最優(yōu)結(jié)果果，最后還對對陳燁的“蟻群算法法實驗室”的可視化化編程進行行了優(yōu)化和和改進，使之能夠夠更方便的的用于幾種種算法性能能比較和同同種算法不不同參數(shù)的的比較?！娟P(guān)鍵詞】 群智能；蟻群算法法；參數(shù)選選擇；TSSP；可視視化Experrimenntal Analyysis and Parammeterr Sellectiion ffor tthe AAnt Colonny Optimmizattion AlgoorithhmXu HHuiAbstrract：Swarmm inttelliigencce haas beeen aa ho

3、tt spoot inn thee fieeld oof arrtifiiciall inttelliigencce inn reccent yearrs. Amongg thee alggoritthms of sswarmm inteelliggencee, ant coloony aalgorrithmm wass preesentted bby ann Itaaly sschollar MM. Doriigo llearnning fromm thee behhavioor siimulaatingg antt collony foraagingg. Fiirstlly, thiss

4、papper hhas iintrooduceed thhe grroup inteelliggencee andd proomoteed thhe ant ccolonny allgoriithm, obtaainedd thee chooice reguular of “m, , , , Q” bbasinng onn thee expperimment, andd prooposeed ann efffectiive mmethood naamed “fourr steeps” in the funddatioon off othhers schoolarss “threee sttep

5、s” to chooose tthe mmost supeeriorr commbinaationn parrametter oof annt grroup algoorithhm, thenn anaaliedd thee sixx kinnds iimprooved algoorithhm off antt collony ant ccolonny allgoriithm, at the samee timme exxplaiined the abillity of sseverral kkindss of ant algoorithhm too sollve tthe TTSP qque

6、sttion accoordinng too thee expperimmentss; obbtainned tthe mmost supeeriorr ressult accoordinng too othher pperfoormannce (iterrativve nuumberr of timees, iiteraativee timme annd soo on) wheen thhe moost ssuperrior resuult oof TSSP quuestiion ooptimmal ssoluttion is ssame. Finnallyy, thhis ppaperr

7、alsso haas caarrieed onn thee opttimizzatioon annd thhe immprovvemennt too thee vissiblee proogrammmingg of ChennYes “antt collony algoorithhm laaboraatoryy” to eenablle itt morre coonvennientt to use in sseverral aalgorrithmms peerforrmancce coomparrisonn andd thee commpariison of ddiffeerentt parr

8、ametter aand hhomoggeneoous aalgorrithmm. Key wwordss：Swarmm inttelliigencce; AAnt ccolonny allgoriithm; Parrametter SSelecctionn; TSSP; Vissualiizatiion目 錄錄TOC o 1-3 h z u HYPERLINK l _Toc169866178 1 緒論 PAGEREF _Toc169866178 h 1 HYPERLINK l _Toc169866179 1.1 引言 PAGEREF _Toc169866179 h 1 HYPERLINK l

9、 _Toc169866180 1.2 群智能 PAGEREF _Toc169866180 h 1 HYPERLINK l _Toc169866181 1.3 蟻群算法法的提出 PAGEREF _Toc169866181 h 2 HYPERLINK l _Toc169866182 1.4 本文研究究工作 PAGEREF _Toc169866182 h 2 HYPERLINK l _Toc169866183 2 蟻群群算法概述述 PAGEREF _Toc169866183 h 4 HYPERLINK l _Toc169866184 2.1 蟻蟻群算法基基本原理 PAGEREF _Toc169866

10、184 h 4 HYPERLINK l _Toc169866185 2.2 蟻蟻群算法的的優(yōu)點與不不足 PAGEREF _Toc169866185 h 5 HYPERLINK l _Toc169866186 2.3 本章小結(jié)結(jié) PAGEREF _Toc169866186 h 6 HYPERLINK l _Toc169866187 3 蟻群群算法的參參數(shù)設(shè)置研研究 PAGEREF _Toc169866187 h 7 HYPERLINK l _Toc169866188 3.1 硬件/軟件環(huán)境境平臺 PAGEREF _Toc169866188 h 7 HYPERLINK l _Toc16986618

11、9 3.2 螞蟻數(shù)目目對基本蟻蟻群算法的的影響 PAGEREF _Toc169866189 h 7 HYPERLINK l _Toc169866190 3.3 信息啟發(fā)發(fā)式因子和和期望值啟啟發(fā)式因子子 PAGEREF _Toc169866190 h 9 HYPERLINK l _Toc169866191 3.4 信息素殘殘留系數(shù) PAGEREF _Toc169866191 h 10 HYPERLINK l _Toc169866192 3.5 總信息量量 PAGEREF _Toc169866192 h 11 HYPERLINK l _Toc169866193 3.6 本章小結(jié)結(jié) PAGEREF

12、_Toc169866193 h 12 HYPERLINK l _Toc169866194 4 蟻群群算法實驗驗分析 PAGEREF _Toc169866194 h 13 HYPERLINK l _Toc169866195 4.1 改進的蟻蟻群優(yōu)化算算法 PAGEREF _Toc169866195 h 13 HYPERLINK l _Toc169866196 4.1.11 最優(yōu)優(yōu)解保留策策略螞蟻系系統(tǒng) PAGEREF _Toc169866196 h 13 HYPERLINK l _Toc169866197 4.1.22 蟻群群系統(tǒng) PAGEREF _Toc169866197 h 13 HYPER

13、LINK l _Toc169866198 4.1.33 最大大-最小螞蟻蟻系統(tǒng) PAGEREF _Toc169866198 h 13 HYPERLINK l _Toc169866199 4.1.44 基于于排序的螞螞蟻系統(tǒng) PAGEREF _Toc169866199 h 14 HYPERLINK l _Toc169866200 4.1.55 Thhe Beest-WWorstt Antt Sysstem PAGEREF _Toc169866200 h 14 HYPERLINK l _Toc169866201 4. 2 實驗仿仿真及算法法性能比較較分析 PAGEREF _Toc169866201

14、 h 15 HYPERLINK l _Toc169866202 4.2.11 硬件件/軟件環(huán)境境平臺 PAGEREF _Toc169866202 h 15 HYPERLINK l _Toc169866203 4.2.22 重要要參數(shù)設(shè)置置 PAGEREF _Toc169866203 h 15 HYPERLINK l _Toc169866204 4.2.33 實驗驗結(jié)果 PAGEREF _Toc169866204 h 15 HYPERLINK l _Toc169866205 4.3 本章小結(jié)結(jié) PAGEREF _Toc169866205 h 17 HYPERLINK l _Toc16986620

15、6 5 可視視化編程 PAGEREF _Toc169866206 h 18 HYPERLINK l _Toc169866207 5.1 “蟻群算法法實驗室”的優(yōu)點與與不足 PAGEREF _Toc169866207 h 18 HYPERLINK l _Toc169866208 5.2 最最大最小蟻蟻群算法的的圖形化演演示的改進進 PAGEREF _Toc169866208 h 18 HYPERLINK l _Toc169866209 5.3本本章小結(jié) PAGEREF _Toc169866209 h 22 HYPERLINK l _Toc169866210 6 結(jié)論與與展望 PAGEREF _T

16、oc169866210 h 23 HYPERLINK l _Toc169866211 參考文獻 PAGEREF _Toc169866211 h 24 HYPERLINK l _Toc169866212 致 謝謝 PAGEREF _Toc169866212 h 25 HYPERLINK l _Toc169866213 附 錄錄 PAGEREF _Toc169866213 h 26江西財經(jīng)大學(xué)本科畢業(yè)設(shè)計1 緒論自蟻群算法法提出以來來,就引起了了國內(nèi)外學(xué)學(xué)者的廣泛泛關(guān)注，提出了很很多改進算算法。參數(shù)數(shù)的設(shè)置直直接影響到到算法的性性能，所以對參參數(shù)設(shè)置的的研究越來來越重要，而目前對對它的研究究大多還

17、處處于實驗分分析階段。1.1 引言隨著人們對對生命本質(zhì)質(zhì)的不斷了了解，生命科學(xué)學(xué)也以前所所未有的速速度迅猛發(fā)發(fā)展，使人工智智能的研究究開始擺脫脫經(jīng)典邏輯輯計算的束束縛，大膽探索索起新的非非經(jīng)典計算算途徑。在在這種背景景下，社會性動動物的自組組織行為引引起了人們們的廣泛關(guān)關(guān)注，許多學(xué)者者對這種行行為進行數(shù)數(shù)學(xué)建模并并用計算機機對其進行行仿真，這就產(chǎn)生生了所謂的的“群智能”。受螞蟻總能能找到一條條從蟻巢到到食物源的的最短路徑徑的啟發(fā)，意大利學(xué)學(xué)者M. Doriigo與220世紀(jì)990年代提提出了一種種新型的智智能優(yōu)化算算法蟻群優(yōu)化化算法（AAnt CColonny Opptimiizatiion，

18、ACO）1。在不長長的時間里里，蟻群算法法得到了不不斷發(fā)展和和完善，而且被用用于解決大大多數(shù)優(yōu)化化問題或者者能夠轉(zhuǎn)化化為優(yōu)化求求解的問題題，現(xiàn)在其應(yīng)應(yīng)用領(lǐng)域已已擴展到多多目標(biāo)優(yōu)化化、數(shù)據(jù)分分類、數(shù)據(jù)據(jù)聚類、模模式識別、電信QooS管理、生物系統(tǒng)統(tǒng)建模、流流程規(guī)劃、信號處理理、機器人人控制、決決策支持以以及仿真和和系統(tǒng)辯識識等方面。1.2 群智能群智能指的的是“無智能的的主體通過過合作表現(xiàn)現(xiàn)出智能行行為的特性性”2，是一種基基于生物群群體行為規(guī)規(guī)律的計算算技術(shù)。它它受社會昆昆蟲，例如螞蟻蟻、蜜蜂和和群居脊椎椎動物，又如鳥群群、魚群和和獸群等的的啟發(fā)，解決分布布式問題。它在沒有集集中控制并并且不提

19、供供全局模型型的前提下下，為尋找復(fù)復(fù)雜的分布布式問題的的解決方案案提供了一一種新的思思路。 有些專家在在研究自然然界的生物物群體系統(tǒng)統(tǒng)時，驚奇地發(fā)發(fā)現(xiàn)社會昆昆蟲和群居居的脊椎動動物能發(fā)現(xiàn)新的的食物源、在群體內(nèi)內(nèi)部產(chǎn)生勞勞動分工，建筑龐大大復(fù)雜的巢巢穴、跨越越幾千公里里遷徙到指指定地區(qū)和和在狹窄的的空間內(nèi)協(xié)協(xié)調(diào)調(diào)度等等。這些社社會性動物物的自組織織行為引起起了人們廣廣泛的關(guān)注注，許多學(xué)者者對這種行行為進行數(shù)數(shù)學(xué)建模并并用計算機機對其進行行仿真，發(fā)現(xiàn)群智智能有如下下特點和優(yōu)優(yōu)點2：(1) 群群體中相互互合作的個個體是分布布的(Diistriibuteed)，這樣更能能夠適應(yīng)當(dāng)當(dāng)前網(wǎng)絡(luò)環(huán)環(huán)境下的工工

20、作狀態(tài)。(2) 沒沒有中心的的控制與數(shù)數(shù)據(jù)，這樣的系系統(tǒng)更具有有魯棒性(Robuust)，不會由于于某一個或或者某幾個個個體的故故障而影響響整個問題題的求解。(3) 可可以不通過過個體之間間直接通信信，而是通過過非直接通通信進行合合作，這樣的系系統(tǒng)具有更更好的可擴擴充性(SScalaabiliity)。(4) 由由于系統(tǒng)中中個體的增增加而增加加的系統(tǒng)通通信開銷在在這里是十十分小的，系統(tǒng)中每每個個體的的能力十分分簡單，這樣每個個個體的執(zhí)執(zhí)行時間比比較短，并且實現(xiàn)現(xiàn)也比較簡簡單，具有簡單單性(Siimpliicityy)。 1.3 蟻群算法法的提出目前，群智智能理論研研究領(lǐng)域包包括兩種主主要算法：

21、蟻群算法法(Antt Collony Optiimizaationn，簡記ACCO)和粒粒子群算法法(Parrticlle Swwarm Optiimizaationn，簡記PSSO)。而而以蟻群算算法為代表表的群體智智能已成為為當(dāng)今分布布式人工智智能研究的的一個熱點點，它是由意大大利學(xué)者MM. Dorrigo、V. Manniez-zo、AA. Collorinni3,4,5等人從生物物進化機制制中受到啟啟發(fā)，通過模擬擬自然界螞螞蟻搜索路路徑的行為為后，于19991年首先先提出的，也叫螞蟻系統(tǒng)統(tǒng)（Antt Sysstem，AS）。M. Dorrigo等等人充分利利用蟻群搜搜索食物的的過程與著

22、名的旅旅行商問題題（Traaveliing SSalessman Probblem）之之間的相似似性，吸收了螞螞蟻的行為為特征，設(shè)計虛擬擬的“螞蟻”摸索不同同的路線，并留下會會隨時間逐逐漸消失的的虛擬“信息量”2。虛擬的的“信息量”會揮發(fā)，當(dāng)螞蟻每次次隨機選擇擇要走的路路徑時，傾向于選選擇信息量量比較濃的的路徑。根根據(jù)“信息量濃濃度更近”的原則，既可選擇擇出最佳路線線。雖然蟻群算算法的研究究時間不長長，但初步研研究已顯示示它在求解解復(fù)雜優(yōu)化化問題方面面具有很大大優(yōu)勢，特別是19998年在在比利時布布魯塞爾專專門召開了了第一屆螞螞蟻優(yōu)化國國際研討會會后，現(xiàn)在每兩兩年召開一一次這樣的的螞蟻優(yōu)化化國

23、際研討討會。這標(biāo)標(biāo)志著蟻群群算法的研研究已經(jīng)得得到國際上上的廣泛支支持，使得這種種新興的智智能進化仿仿生算法展展現(xiàn)出了勃勃勃生機6。1.4 本文研究究工作本文圍繞蟻蟻群算法的的原理、改進及其應(yīng)應(yīng)用展開研研究，全文共分分六章，各章內(nèi)容容安排如下下：第一章：緒緒論本章首先對對群智能進進行介紹，然后闡述述蟻群算法法產(chǎn)生的背背景。第二章：蟻蟻群算法概概述本章詳細介介紹蟻群算算法原理及及其優(yōu)缺點點。第三章：蟻蟻群算法的的參數(shù)設(shè)置置研究本章針對參參數(shù)設(shè)置進進行大量實實驗，并對實驗驗結(jié)果做出出研究分析析，得出參數(shù)數(shù)m，Q的選擇規(guī)規(guī)律，在此基礎(chǔ)礎(chǔ)上，提出新的有效方方法對蟻群算法法最優(yōu)組合合參數(shù)進行行選擇。第四

24、章：蟻蟻群算法實實驗分析本章分析幾幾種改進的的蟻群算法法，并采用國際上上通用的測測試問題庫庫TSPLLIB中的的對稱TSSP問題作作為測試對對象，通過仿真試驗對六種種算法各自自求解TSSP問題的的性能進行行比較，得出當(dāng)TTSP問題題最優(yōu)解相相同時，可依據(jù)其其他性能（迭迭代次數(shù)、迭代時間間等）得出TSSP問題的的最優(yōu)結(jié)果果。 第五五章：可視化化編程針對陳燁的的“蟻群算法法實驗室”進行優(yōu)化和和改進。第六章：結(jié)結(jié)論與展望望總結(jié)本文工工作，提出展望望。 2 蟻群群算法概述述 下面詳細介介紹蟻群算算法原理及及其優(yōu)缺點點。2.1 蟻蟻群算法基基本原理現(xiàn)實生活中中單個螞蟻蟻的能力和和智力非常常簡單，但他們能

25、能通過相互互協(xié)調(diào)、分分工、合作作來完成筑筑巢、覓食食、遷徙、清掃蟻穴穴等復(fù)雜行行為，尤其以螞螞蟻總能找找到一條從從蟻巢到食食物源的最最短路徑而而令人驚嘆嘆。根據(jù)仿生學(xué)學(xué)家的長期期研究發(fā)現(xiàn)現(xiàn)：螞蟻雖雖沒有知覺覺，但運動時時會通過在在路徑上釋釋放出一種種特殊的分分泌物-信息素來來尋找路徑徑。螞蟻個體之之間就是利利用信息素作為介質(zhì)質(zhì)來相互交交流、合作作的。某條條路上經(jīng)過過的螞蟻越越多，信息素的強強度就會越大，而螞蟻能感知知路上信息息素的存在在和強度，它們傾向向于選擇外外激素強度度大的方向向，因為通過過較短路徑徑往返于食食物和巢穴穴之間的螞螞蟻能以更更短的時間間經(jīng)過這條條路徑上的的點，所以這些些點上的

26、外外激素就會會因螞蟻經(jīng)經(jīng)過的次數(shù)數(shù)增多而增增強，這樣就會會有更多的的螞蟻選擇擇此路徑，這條路徑徑上的外激激素就會越越來越強，選擇此路路徑的螞蟻蟻也越來越越多。直到最后后，幾乎所有有的螞蟻都都選擇這條條最短的路路徑。蟻群算法可可以表述如如下：在算算法的初始始時刻，將m只螞螞蟻隨機地地放到 nn 座城市市，同時，將每只螞螞蟻的禁忌忌表的第一一個元素設(shè)設(shè)置為它當(dāng)當(dāng)前所在的的城市。此此時各路徑徑上的信息息素量相等等，設(shè)ij(0) = CC（C 為為一較小的的常數(shù)），接下來，每只螞蟻蟻根據(jù)路徑徑上殘留的的信息素量量和啟發(fā)式式信息（兩兩城市間的的距離）獨獨立地選擇擇下一座城城市，在時刻 t，螞蟻 kk 從

27、城市市i轉(zhuǎn)移到到城市j 的概率(t)為： (2. 1)其中，Jkk(i)= 1，2，n- tabuuk 表示螞螞蟻 k 下一步允允許選擇的的城市集合合。列表ttabukk記錄了螞螞蟻 k 當(dāng)前走過過的城市。當(dāng)所有 n 座城城市都加入入到tabbuk中時，螞蟻 kk 便完成成了一次周周游，此時螞蟻蟻 k 所所走過的路路徑便是 TSP 問題的一一個可行解解。(2. 1)式中的ij 是一一個啟發(fā)式式因子，表示螞蟻蟻從城市 i 轉(zhuǎn)移移到城市 j 的期期望程度。在 ASS 算法中中，ij 通常常取城市 i 與城城市 j 之間距離離的倒數(shù)。和分別表示示信息素和和啟發(fā)式因因子的相對對重要程度度。當(dāng)所有有螞蟻

28、完成成一次周游游后，各路徑上上的信息素素根據(jù)（22. 2）式式更新。 (2. 2) (2. 3)其中(00 1)表示路徑徑上信息素素的蒸發(fā)系系數(shù)，1- 表示信信息素的持持久性系數(shù)數(shù)；ij表示本本次迭代邊邊 ij 上信息素素的增量。kij表示第第 k 只只螞蟻在本本次迭代中中留在邊iij 上的的信息素量量。如果螞螞蟻 k 沒有經(jīng)過過邊 ijj，則kij的值為為零。kij表示為為： (2. 4)其中，Q 為正常數(shù)數(shù)，Lk 表示第第 k 只只螞蟻在本本次周游中中所走過路路徑的長度度。M. Doorigoo 提出了了 3 種種 AS 算法的模模型 7， 式 (2.4) 稱為 aant-ccyclee，

29、另外兩個個模型分別別稱為 aant-qquanttity 和 annt-deensitty，其差別主主要在 (2. 4) 式，即：在 ant-quanntityy 模型中中為： (2. 5) 在 ant-denssity 模型中為為： (2. 6)AS算法實實際上是正正反饋原理理和啟發(fā)式式算法相結(jié)結(jié)合的一種種算法。在在選擇路徑徑時，螞蟻不僅僅利用了路路徑上的信信息素，而且用到到了城市間間距離的倒倒數(shù)作為啟啟發(fā)式因子子。實驗結(jié)結(jié)果表明，ant-cyclle 模型型比 annt-quuantiity 和和 antt-dennsityy 模型有有更好的性性能。這是是因為 aant-ccyclee 模

30、型利利用全局信信息更新路路徑上的信信息素量，而 annt-quuantiity 和和ant-denssity 模型使用用局部信息息。AS 算法的時時間復(fù)雜度度為(NC*n2*m) ，算法的空空間復(fù)雜度度為S(nn)=O(n2)+O(n*m) ，其中 NNC 表示迭迭代的次數(shù)數(shù)，n 為城城市數(shù)，m為螞蟻蟻的數(shù)目。2.2 蟻蟻群算法的的優(yōu)點與不不足眾多研究已已經(jīng)證明 AS 算算法具有很很強的發(fā)現(xiàn)現(xiàn)較好解的的能力，這是因為為該算法不不僅利用了了正反饋原原理，在一定程程度上可以以加快進化化過程，而且是一一種本質(zhì)上上并行的算算法。它有如下優(yōu)優(yōu)點8：(1) 較較強的魯棒棒性：對蟻蟻群算法模模型稍加修修改，

31、便可以應(yīng)應(yīng)用于其它它問題。(2) 分分布式計算算：蟻群算算法是一種種基于種群群的進化算算法，具有本質(zhì)質(zhì)的并行性性，易于實現(xiàn)現(xiàn)。(3) 易易于與其他他方法結(jié)合合：蟻群算算法很容易易與多種啟啟發(fā)式算法法結(jié)合，以改善算算法的性能能。同時它也存存在一些缺缺陷：(1)限于于局部最優(yōu)優(yōu)解，從算法解解的性質(zhì)而而言，蟻群算法法也是在尋尋找一個比比較好的局局部最優(yōu)解解，而不是強強求是全局局最優(yōu)解。(2)工作作過程的中中間停滯問問題（sttagnaationn behhavioour），和算法開開始時收斂斂速度快一一樣，在算法工工作過程當(dāng)當(dāng)中，迭代到一一定次數(shù)后后，螞蟻也可可能在某個個或某些局局部最優(yōu)解解的鄰域附

32、附近產(chǎn)生停停滯。(3)較長長的搜索時時間，盡管和其其他算法相相比，蟻群算法法在迭代次次數(shù)和解的的質(zhì)量上都都有一定的的優(yōu)勢，但對于目目前計算機機網(wǎng)絡(luò)的實實際情況，還是需要要較長的搜搜索時間。雖然計算算機計算速速度的提高高和蟻群算算法的并行行性在一定定程度上可可以緩解這這一問題，但是對于于大規(guī)模復(fù)復(fù)雜的計算算機網(wǎng)絡(luò)，這還是一一個很大的的障礙。2.3 本章小結(jié)結(jié) 本本章主要介介紹了蟻群群算法基本本原理，并并針對其優(yōu)優(yōu)缺點，進進行了介紹紹和討論。螞蟻通過過釋放一種種特殊的分分泌物-信信息素來尋尋找路徑，螞螞蟻個體之之間也通過過信息素進進行交流與與合作。蟻蟻群算法的的優(yōu)勢主要要體現(xiàn)在魯魯棒性，分分布式，

33、移移植性等方方面，而其其缺陷，就就目前來說說，主要在在局部最優(yōu)優(yōu)，工作停停滯，搜索索時間長等等方面。3 蟻群群算法的參參數(shù)設(shè)置研研究蟻群算法在在TSP 問題應(yīng)用用中取得了了良好的效效果，但也存在在下列不足： (1) 如如果參數(shù)、m、Q等設(shè)置不當(dāng)當(dāng)，會導(dǎo)致求解解速度很慢慢且所得解解的質(zhì)量特特別差；(2) 基基本蟻群算算法計算量量大，求解所需需的時間較較長；(3) 基基本蟻群算算法中理論論上要求所所有的螞蟻蟻選擇同一一路線，該線路即即為所求的的最優(yōu)線路路；但在實際際計算中，在給定一一定循環(huán)次次數(shù)的條件件下很難實實現(xiàn)這種情情況。 另一方面，在其他的的實際應(yīng)用用中，如圖像處處理中尋求求最優(yōu)模板板問題，

34、并不要求求所有的螞螞蟻都能找找到最優(yōu)模模板，而只需要要一只找到到即可。如如果要求所所有的螞蟻蟻都找到最最優(yōu)模板，反而影響響了計算效效率。目前，對基基本蟻群算算法的參數(shù)數(shù)設(shè)置和屬屬性的研究究大多還處處于實驗階階段，M. Doriigo 3,4 等人通通過大量的的實驗對螞螞蟻系統(tǒng)的的參數(shù)和基基本屬性進進行了探討討。討論的的參數(shù)包括括：m 螞螞蟻數(shù)目； 信信息素的相相對重要程程度； 啟啟發(fā)式因子子的相對重重要程度； 信信息素蒸發(fā)發(fā)系數(shù)（(1-)表示信信息素的持持久性系數(shù)數(shù)）；Q 螞螞蟻釋放的的信息素量量。在實驗中，為了觀察察某個參數(shù)數(shù)對算法性性能的影響響，在測試該該參數(shù)時，其它參數(shù)數(shù)取缺省值值。各參

35、數(shù)數(shù)的缺省值值為m = n*1/4（本本文中為221）， =1， =5， = 0. 5，Q =1100。在實驗中，本實驗每組組數(shù)據(jù)試驗驗5次取平均均和最優(yōu)作作比較，試驗中所所用的TSSP 問題題數(shù)據(jù)來源源于Eill51 城城市問題，迭代次數(shù)數(shù)100次次。3.1 硬件/軟件環(huán)境境平臺 本實驗采用用的硬件/軟件環(huán)境境分別為：CPU 2. 4GHHz，內(nèi)存 2556 M，硬盤容量量 80GG，安裝的是是Micrrosofft winddows XP（SServiice PPack 2）操作作系統(tǒng)，開發(fā)平臺臺是Micrrosofft Viisuall C+ 6. 0 。3.2 螞蟻數(shù)目目對基本蟻蟻群算

36、法的的影響對于 TSSP 問題題，單個螞蟻蟻在一次循循環(huán)中所經(jīng)經(jīng)過的路徑徑，表現(xiàn)為問問題可行解解集中的一一個解，m 只螞螞蟻在一次次循環(huán)中所所經(jīng)過的路路徑，則表現(xiàn)為為問題可行行解集中的的一個子集集。顯然，子集大(即螞蟻數(shù)數(shù)量多)就就可以提高高蟻群算法法的全局搜搜索能力以以及算法的的穩(wěn)定性；但是，螞蟻數(shù)目目增大后，會使大量量的曾被搜搜索過的解解(路徑)上的信息息量的變化化比較平均均，信息正反反饋的作用用不明顯，搜索的隨隨機性盡管管得到了加加強，但收斂速速度減慢；反之，子集較小小(即蟻群群數(shù)量少)，特別是當(dāng)當(dāng)要處理的的問題規(guī)模模比較大時時，會使那些些從來未被被搜索到的的解(路徑徑)上的信信息量減小

37、小到接近于于 0，搜索的隨隨機性減弱弱，雖然收斂斂速度加快快，但會使算算法的全局局性能降低低，算法的穩(wěn)穩(wěn)定性差，容易出現(xiàn)現(xiàn)過早停滯滯現(xiàn)象。關(guān)關(guān)于蟻群算算法中螞蟻蟻數(shù)量m 的選擇，也應(yīng)該綜綜合考慮算算法的全局局搜索能力力和收斂速速度兩項指指標(biāo)，針對具體體問題的應(yīng)應(yīng)用條件和和實際要求求，在全局搜搜索能力和和收斂速度度兩方面作作出合理或或折衷的選選擇。關(guān)于螞蟻數(shù)數(shù)目m對算算法性能的的影響及其其在實際應(yīng)應(yīng)用中的選選擇，本文通過過計算機仿仿真實驗來來分析和確確定，本文使螞螞蟻數(shù)目變變化為55、7、99、11、13、115、177、19、21、223、255、27、29、331，螞蟻數(shù)目目m對算法法性能的

38、影影響仿真結(jié)結(jié)果如表33-1和圖3-1所示。 表3-1 螞蟻數(shù)目目m對算法法性能的影影響的結(jié)果果螞蟻數(shù)目最優(yōu)（最短短）路徑長長度運行的時間間（s）5463. 98700768. 82287465. 009119914. 1119457. 00144789. 788111453. 741332713. 118713452. 822771614. 117215456. 116001113. 553117451. 117332112. 77519445. 624117714. 118721446. 078669513. 118823447. 001773113. 992125452. 2992202

39、13. 11127446. 078669521. 446829451. 223220414. 117131450. 776665913. 5515圖3-1 螞蟻數(shù)目目m對算法法性能的影影響的仿真真結(jié)果關(guān)于蟻群算算法中螞蟻蟻數(shù)量m 的選擇，要綜合考考慮算法的的全局搜索索能力和收收斂速度兩兩項指標(biāo)，針對具體體問題的應(yīng)應(yīng)用條件和和實際要求求，在全局搜搜索能力和和收斂速度度兩方面做做出合理或或折衷的選選擇，圖 3-1 為實實驗所得的的結(jié)果，其中橫軸軸表示螞蟻蟻數(shù)，縱軸表示示發(fā)現(xiàn)最優(yōu)優(yōu)解。從圖圖中可以看看出當(dāng)m在在1/42/5之之間時，蟻群算法法可以找到到最優(yōu)解，通過本實實驗和其他他學(xué)者的研研究，本文最

40、終終得出螞蟻蟻數(shù)目應(yīng)該該在1/442/55之間，而且當(dāng)城城市數(shù)目規(guī)規(guī)模較小時時螞蟻數(shù)目目m應(yīng)該盡盡量靠近22/5（如如果很小可可以考慮mm=n），當(dāng)城市數(shù)數(shù)目規(guī)模較較大時螞蟻蟻數(shù)目m應(yīng)應(yīng)該盡量靠靠近1/44，因為這樣樣綜合考慮慮了算法的的全局搜索索能力和收收斂速度兩兩項指標(biāo)，可以使得得找到最優(yōu)優(yōu)解并且全全局搜索能能力和收斂斂速度都是是比較好，算法的各各項性能相相對平穩(wěn)。3.3 信息啟發(fā)發(fā)式因子和和期望值啟啟發(fā)式因子子信息啟發(fā)式式因子反映螞蟻蟻在運動過過程中所積積累的信息息量(即殘殘留信息量量ij(t)在指導(dǎo)導(dǎo)蟻群搜索索中的相對對重要程度度，期望值啟啟發(fā)式因子子反映螞蟻蟻在運動過過程中啟發(fā)發(fā)信息

41、(即即期望值ij )在在指導(dǎo)蟻群群搜索中的的相對重要要程度9。期望值值啟發(fā)式因因子的大小反反映了蟻群群在路徑搜搜索中先驗驗性、確定定性因素作作用的強度度，其值越大大，螞蟻在某某個局部點點上選擇局局部最短路路徑的可能能性越大，雖然搜索索的收斂速速度得以加加快，但是，蟻群在最最優(yōu)路徑的的搜索過程程中隨機性性減弱易于于陷入局部部最優(yōu)；而而信息啟發(fā)發(fā)式因子的大小則則反映了蟻蟻群在路徑徑搜索中隨隨機性因素素作用的強強度，其值越大大，螞蟻選擇擇以前走過過的路徑的的可能性越越大，搜索的隨隨機性減弱弱，當(dāng)值過大也也會使蟻群群的搜索過過早陷于局局部最優(yōu)。蟻群算法法的全局尋尋優(yōu)性能，首先要求求蟻群的搜搜索過程必必

42、須有很強強的隨機性性；而蟻群群算法的快快速收斂性性能，又要求蟻蟻群的搜索索過程必須須要有較高高的確定性性。因此兩兩者對蟻群群算法性能能的影響和和作用是相相互配合、密切相關(guān)關(guān)的。要想想得到好的的結(jié)果應(yīng)該該適當(dāng)選擇擇 和 的取值值范圍，一般=0. 55，=1559。因為兩者者相互配合合、密切相相關(guān)，本文對和采用組合合方式討論論其對蟻群群算法性能能的影響。取為0. 5、1、2、5，為1、2、5，進行組合合仿真實驗驗，實驗結(jié)果果如表3-2和圖3-2所示。表3-2 和組合方式式對算法性性能結(jié)果信息素濃度度影響力參參數(shù)a啟發(fā)式信息息影響力參參數(shù)b最優(yōu)（最短短）路徑長長度運行的時間間0. 51703. 90

43、3115614. 22650. 52531. 142889119. 22030. 55458. 382447917. 779711481. 415778817. 771812461. 263114915. 66415447. 001773112. 009321475. 705665223. 770322458. 06055112. 006225459. 590441712. 440651538. 124448712. 770352465. 841223324. 22555465. 767443524. 3375圖3-2 和組合方式式對算法性性能的仿真真結(jié)果以上實驗告告訴我們，如果要增加加蟻群算

44、法法的快速收收斂性能，而且又要要求蟻群的的搜索過程程必須要有有較高的確確定性，就要同時時選擇好和，因為它們們對蟻群算算法性能的的影響和作作用是相互互配合、密密切相關(guān)的的。而本文文在大量實實驗的基礎(chǔ)礎(chǔ)上得出，要想得到到更優(yōu)的結(jié)結(jié)果則選擇擇 =1， =5。3.4 信息素殘殘留系數(shù)在蟻群算法法中，隨著時間間的推移，螞蟻留下的的信息素會會逐漸消逝逝。在算法法模型中用用參數(shù)1-表示信息息消逝程度度(或稱信信息素揮發(fā)發(fā)度)，而就是信息息素殘留系系數(shù)。蟻群群算法與遺遺傳算法等等各種模擬擬進化算法法一樣，也存在著著收斂速度度慢、易于于陷入局部部最優(yōu)等缺缺陷。而信信息素揮發(fā)發(fā)度1-的大小直直接關(guān)系到到蟻群算法法

45、的全局搜搜索能力及及其收斂速速度：由于于信息素揮揮發(fā)度1-的存在，當(dāng)要處理理的問題規(guī)規(guī)模比較大大時，會使那些些從來未被被搜索到的的路徑(可可行解)上上的信息量量減小到接接近于 00，因而降低低了算法的的全局搜索索能力，而且當(dāng)11-過大時以以前搜索過過的路徑被被再次選擇擇的可能性性過大，也會影響響到算法的的隨機性能能和全局搜搜索能力；反之，通過減小小信息素揮揮發(fā)度1- 雖然可可以提高算算法的隨機機性能和全全局搜索能能力，但又會使使算法的收收斂速度降降低。蟻群群算法中信信息素揮發(fā)發(fā)度1- 的選擇擇，必須綜合合考慮算法法的全局搜搜索能力和和收斂速度度兩項性能能指標(biāo)，針對具體體問題的應(yīng)應(yīng)用條件和和實際

46、要求求，在全局搜搜索能力和和收斂速度度兩方面作作出合理或或折衷的選選擇。為了了使算法的的性能比較較穩(wěn)定和一一致，搜索的全全局性和收收斂速度都都比較好，本文通過過計算機仿仿真實驗來來分析和確確定，本文使信信息素殘留留系數(shù) 變化為0. 1、00. 2、00. 3、00. 4、00. 5、00. 6、00. 7、00. 8、00. 9、00. 95、0. 99，信息素殘殘留系數(shù) 對算法性性能的影響響仿真結(jié)果果如表3-3和圖3-3所示。表3-3信信息素衰減減因子對算法性性能的結(jié)果路徑上信息息素衰減因因子p最優(yōu)（最短短）路徑長長度運行的時間間0. 1448. 317777722. 550. 2453.

47、848662338. 00460. 3444. 568550716. 00160. 4455. 270227115. 99530. 5445. 624117714. 11870. 6448. 123665612. 77030. 7454. 303551917. 66560. 8448. 317777714. 00470. 9448. 384114111. 99070. 955449. 3777717150. 999449. 793884313. 1125圖3-3 信息素衰衰減因子對算法性性能的仿真真結(jié)果為了對蟻群群算法中信信息素揮發(fā)發(fā)度1-進行選擇擇，必須綜合合考慮算法法的全局搜搜索能力和和收

48、斂速度度兩項性能能指標(biāo)，針對具體體問題的應(yīng)應(yīng)用條件和和實際要求求，在全局搜搜索能力和和收斂速度度兩方面做做出合理或或折衷的選選擇。為了了使算法的的性能比較較穩(wěn)定和一一致，搜索的全全局性和收收斂速度都都比較好，通過上述述實驗可以以知道要想想得到好的的結(jié)果本文文建議=0. 5（11-=0. 5）。3.5 總信息量量在蟻群模型型中總信息息量Q為螞螞蟻循環(huán)一一周時釋放放在所經(jīng)過過的路徑上上的信息素素總量一般般的理解是是：總信息息量Q越大大則在螞蟻蟻已經(jīng)走過過的路徑上上信息素的的累積加快快，可以加強強蟻群搜索索時的正反反饋性能，有助于算算法的快速速收斂。由由于在蟻群群算法中各各個算法參參數(shù)的作用用實際上

49、是是緊密耦合合的，其中對算算法性能起起著主要作作用的應(yīng)該該是信息啟啟發(fā)式因子子 、期望望啟發(fā)式因因子 和信息殘殘留常數(shù)等三個參參數(shù)。總信信息量Q對對算法性能能的影響則則有賴于、和三個參數(shù)數(shù)的配置以以及算法模模型的選取取，例如在蟻蟻周模型和和蟻密模型型中總信息息量Q對算算法性能的的影響情況況有較大的的差異?？偪傂畔⒘繉ο佒苣Ｐ托拖伻核惴ǚǖ男阅軟]沒有明顯的的影響，一般取QQ =100010。3.6 本章小結(jié)結(jié)本章通過大大量實驗說說明了信息息素殘留因因子1-、信息啟啟發(fā)式因子子、期望啟啟發(fā)式因子子、信息素素強度Q、螞蟻數(shù)目目m等都是是非常重要要的參數(shù)，其選區(qū)方方式和選區(qū)區(qū)原則直接接影響到蟻蟻群算

50、法的的全局收斂斂性和求解解效率，還通過實實驗得出這這些參數(shù)的的選擇規(guī)律律，并提出了這種“四步走”來選擇蟻蟻群算法最最優(yōu)組合參參數(shù)的有效效方法：(1)確定定螞蟻數(shù)目目m，根據(jù) 城城市規(guī)模 / 螞蟻數(shù)數(shù)目 1/42/5的的選擇策略略來確定螞螞蟻的總數(shù)數(shù)目。(2)參數(shù)數(shù)微調(diào)，即調(diào)整數(shù)數(shù)值范圍較較小的信息息素殘留因因子1-（以0. 1為單位位調(diào)整），要想得到到好的結(jié)果果本文建議議1-= 0. 5。(3)參數(shù)數(shù)中調(diào)，即調(diào)整數(shù)數(shù)值范圍適適中的信息息啟發(fā)式因因子、期望啟啟發(fā)式因子子（以1為為單位調(diào)整整），并且和要使用組組合方式才才可以得到到較理想的的解，要想得到到好的結(jié)果果本文建議議 =1， =5。(4)參

51、數(shù)數(shù)粗調(diào)，即調(diào)整數(shù)數(shù)值范圍較較大的信息息素強度QQ參數(shù)（以以10或更更大的數(shù)為為單位調(diào)整整），已得到較較理想的解解，要想得到到好的結(jié)果果本文建議議Q=1000。4 蟻群群算法實驗驗分析 下面面對目前最流行行的幾種蟻蟻群算法進進行性能比比較分析。4.1 改進的蟻群群優(yōu)化算法為了克服AAS的問題題，很多學(xué)者者對其進行行研究，并提出了了一些改進進措施，下面將介介紹五種蟻蟻群優(yōu)化算算法。 4.1.11 最優(yōu)解解保留策略略螞蟻系統(tǒng)統(tǒng)通過使用最最優(yōu)螞蟻可可以提高螞螞蟻系統(tǒng)中中解的質(zhì)量量7。在最優(yōu)優(yōu)解保留策策略螞蟻系系統(tǒng)（Ellitisst Annt Syystemm，簡稱 EEAS）中中，每次迭代代完成后

52、，全局最優(yōu)優(yōu)解得到更更進一步的的利用，即在對信信息素進行行更新時，就好像有有許多的最最優(yōu)螞蟻選選擇了該路路徑。與 AS 算算法相比，ASeliite算法法在信息素素更新時加加強了對全全局最優(yōu)解解的利用，其信息素素更新策略略為： (0, 1) (4. 1) (4. 2) (4. 3) (4. 4)其中*ij 為最最優(yōu)螞蟻在在邊(i, j)上上增加的信信息素量，為最優(yōu)螞螞蟻數(shù)，Lgb 為全全局最優(yōu)解解。4.1.22 蟻群系統(tǒng)統(tǒng)蟻群系統(tǒng)（AAnt CColonny Syystemm，簡稱 AACS）11是 ASS 最成功功的后續(xù)算算法之一，與 ASS 算法的的主要區(qū)別別在于：（1）在選擇下一座城市時

53、，ACS 算法更多地利用了當(dāng)前的較好解；（2）只在全局最優(yōu)解所屬的邊上增加信息素；（3）每次當(dāng)螞蟻從城市 i 轉(zhuǎn)移到城市 j 時，邊 ij 上的信息素將會適當(dāng)?shù)臏p少。4.1.33 最大-最最小螞蟻系系統(tǒng)MAX-MMIN AAnt SSysteem 12從另外的的角度對AS進行直直接完善：修改了ASS的信息素素更新方式式，僅將每一一代中的最最好個體所所走路徑上上的信息量量進行調(diào)整整，加快收斂斂速度，并將各條條路徑上的的信息素濃濃度被限制制在tminn, tmax 范圍內(nèi)，這樣就可可以有效的的避免某條條路徑上的的信息量遠遠大于或遠遠小于其余余路徑情況況的發(fā)生，使得所有有的螞蟻都都集中到同同一條路徑

54、徑上，從而使算算法不再擴擴散，加快收斂斂速度。另另外，信息素的的初始值被被設(shè)為其取取值上限，這樣有助助于增加算算法初始階階段的搜索索能力，是目前解解決TSPP、QAOO等問題最最好的蟻群群算法。4.1.44 基于排排序的螞蟻蟻系統(tǒng)基于排序的的螞蟻系統(tǒng)統(tǒng)（Rannk-baased Verssion of AAnt SSysteem，簡稱 RRAS）是是Bernnd Buullnhheimeer13等提出的AS的又又一擴展算算法。RAAS在每次次迭代完成成后，螞蟻所經(jīng)經(jīng)路徑將按按從小到大大的順序排排列，即L1(t) L2(t)Lm(t)，并根據(jù)路路徑長度賦賦予不同的的權(quán)重，路徑長度度越短權(quán)重重越大

55、。全全局最優(yōu)解解的權(quán)重為為 w，第 r個個最優(yōu)解的的權(quán)重為mmax00, w-r，按（3. 19）式更新新各路徑上上的信息素素： （00, 1） (4. 5)其中，rij(t)=1/ Lr(t)，gbij (tt)=1/ Lgbb4.1.55 The Bestt-Worrst AAnt SSysteem,BWASSBWAS模模型試著用用進化算法法概念提高高ACO模模型的性能能，提出的BBWAS用用的是ASS轉(zhuǎn)移規(guī)則則： (4. 6)rs是邊邊界（r, s）的信息息素值，rs使啟發(fā)發(fā)值，Jk(r) 是留下下來被螞蟻蟻K訪問的的節(jié)點集， 實值的的權(quán)。常用用的AS揮揮發(fā)規(guī)則rs (1)rs， r,

56、s, 0, 1，是信息素素揮發(fā)參數(shù)。另外，BWASS考慮下面面三個新進進程的作用用，下面就是是對他們的的深入分析析5：性能更新規(guī)規(guī)則：這種種規(guī)則是基基于PBIIL的概率率數(shù)組更新新規(guī)則，信息素更新新如下所示示： (4. 7)f(C(SSglobbalbbest) 是要要被全局最最好的螞蟻蟻存放的信信息素數(shù)量量，隨著全局局最優(yōu)螞蟻蟻算法聚集集了大量的的信息素，依靠形成成的解決方方案C(SSglobbalbestt)。信息素痕痕跡突變： 信息素素痕跡在研研究介紹相相異性時遇遇到突變，就像Poppulattion-Baseed Inncremmentaal Leearniing(PPBIL)14這樣

57、，信息素矩矩陣的每一一排被改變變，概率Pm如下： (4. 8)它是0到11之間的隨隨機值，也是當(dāng)前前的迭代，Tthreesholld 是組組成全局最最優(yōu)解決方方案的臨界界的信息素素跟蹤的平平均值，mut(. )是隨隨著迭代記記數(shù)的增長長，變異增強強的函數(shù)。 當(dāng)與當(dāng)前最最優(yōu)和最差差解決方案案不同的臨臨界值的數(shù)數(shù)字比特定定的百分比比少時，本文要把所所有的信息息素痕跡矩矩陣組成更更新為T00，然后循環(huán)環(huán)。4. 2 實驗仿真及算法法性能比較較分析同 AS 算法相比比，以上算法法的共同之之處在于加加強了對最最優(yōu)解的利利用。如在在 ACSS算法和 MMASS 算法中中，只有最優(yōu)優(yōu)解（全局局最優(yōu)或本本次迭代

58、最最優(yōu)）所屬屬路徑上的的信息素允允許增強。在 RAAS算法中中，根據(jù)每次次迭代路經(jīng)經(jīng)的長短賦賦予不同的的權(quán)重，即對較短短的路徑賦賦予較大的的權(quán)重。這這樣最優(yōu)解解包含的路路徑將會有有更多的機機會被下一一次選中。但是，加強對最最優(yōu)解的利利用將會導(dǎo)導(dǎo)致搜索中中的停滯現(xiàn)現(xiàn)象。在 ACS 算法中通通過增加局局部信息素素更新來減減少路徑上上的信息素素量，從而使后后面的螞蟻蟻選擇該路路徑的可能能性減少；在 MMMAS 算算法中，通過限制制信息量的的范圍，使路徑上上的信息量量不會小于于某一最小小值，從而避免免了所有螞螞蟻選擇同同一條路經(jīng)經(jīng)的可能性性，即避免了了搜索中的的停滯現(xiàn)象象，下面我們們用實驗來來比較各種

59、種算法的優(yōu)優(yōu)越性。4.2.11 硬件/軟件環(huán)境境平臺 本實驗采用用的硬件/軟件環(huán)境境分別為：CPU 3. 0 GGHz，內(nèi)存 5112 M，硬盤容量量 80GG，安裝的是是Micrrosofft winddows XP（SServiice PPack 2）操作作系統(tǒng)，開發(fā)平臺臺 Miicrossoft Visuual CC+ 66. 0 。4.2.22 重要參數(shù)數(shù)設(shè)置本實驗中重重要參數(shù)設(shè)設(shè)置如下：信息素濃度度影響力參參數(shù)：所有算法法設(shè)為1.0啟發(fā)式信息息影響力參參數(shù)：所有算法法設(shè)為5.0信息素蒸發(fā)發(fā)系數(shù)（1-)表示信信息素的持持久性系數(shù)數(shù)）：所有有算法設(shè)為0. 5（1-即為0. 5）。螞蟻數(shù)目

60、mm：本文將將m設(shè)為問問題規(guī)模nn的1/44即m=nn*1/44在算法開開始時螞蟻蟻隨機分布布在各個城城市上。此此外，對于EAAS，精英螞蟻蟻的數(shù)目的的個數(shù)e取取100（nn為其中TTSP問題題中后面的的數(shù)字，如Eil551中51即為nn值）。在MMASS中初始信信息素濃度度 0設(shè)定為與與max相等等， 路經(jīng)信息素素濃度下限限min設(shè)定定為小于max的一一常數(shù)，并且根據(jù)據(jù)式4. 16進進行更新。4.2.33 實驗結(jié)果果表4-1是是MMASS，ACS，EAS，RAS，BWASS 與 AAS 算法法求解不同同 TSPP 實例的的比較結(jié)果果（問題的的最優(yōu)解用用黑體加粗粗顯示），各算法迭迭代 1000