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

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

2、編程進行了優(yōu)化和改進，使之能夠更方便的用于幾種算法性能比較和同種算法不同參數(shù)的比較.【關(guān)鍵詞關(guān)鍵詞】 群智能；蟻群算法；參數(shù)選擇；TSP；可視化Experimental Analysis and Parameter Selection for the Ant Colony Optimization AlgorithmXu HuiAbstract：Swarm intelligence has been a hot spot in the field of artificial intelligence in recent years。 Among the algorithms of swarm

3、intelligence, ant colony algorithm was presented by an Italy scholar M. Dorigo learning from the behavior simulating ant colony foraging. Firstly， this paper has introduced the group intelligence and promoted the ant colony algorithm, obtained the choice regular of “m， , , ， Q” basing on the experim

4、ent, and proposed an effective method named “four steps” in the fundation of others scholars “three steps” to choose the most superior combination parameter of ant group algorithm， then analied the six kinds improved algorithm of ant colony ant colony algorithm， at the same time explained the abilit

5、y of several kinds of ant algorithm to solve the TSP question according to the experiments； obtained the most superior result according to other performance (iterative number of times， iterative time and so on) when the most superior result of TSP question optimal solution is same。 Finally, this pap

6、er also has carried on the optimization and the improvement to the visible programming of ChenYes “ant colony algorithm laboratory” to enable it more convenient to use in several algorithms performance comparison and the comparison of different parameter and homogeneous algorithm。文檔為個人收集整理，來源于網(wǎng)絡(luò)本文為互

7、聯(lián)網(wǎng)收集，請勿用作商業(yè)用途 Key words：Swarm intelligence; Ant colony algorithm； Parameter Selection; TSP； Visualization目 錄1 緒論.11。1 引言.11.2 群智能.11。3 蟻群算法的提出.21。4 本文研究工作.22 蟻群算法概述.42.1 蟻群算法基本原理.42.2 蟻群算法的優(yōu)點與不足.52。3 本章小結(jié).63 蟻群算法的參數(shù)設(shè)置研究.73。1 硬件/軟件環(huán)境平臺.73。2 螞蟻數(shù)目對基本蟻群算法的影響.73。3 信息啟發(fā)式因子和期望值啟發(fā)式因子.93.4 信息素殘留系數(shù) .103.5 總信息

8、量.113.6 本章小結(jié).124 蟻群算法實驗分析.134。1 改進的蟻群優(yōu)化算法.134。1.1 最優(yōu)解保留策略螞蟻系統(tǒng).134。1。2 蟻群系統(tǒng).134.1。3 最大-最小螞蟻系統(tǒng) .134.1.4 基于排序的螞蟻系統(tǒng).144.1.5 The Best-Worst Ant System.144。 2 實驗仿真及算法性能比較分析.154.2。1 硬件/軟件環(huán)境平臺.154。2.2 重要參數(shù)設(shè)置.154。2.3 實驗結(jié)果.154。3 本章小結(jié).175 可視化編程.185。1 “蟻群算法實驗室”的優(yōu)點與不足.185。2 最大最小蟻群算法的圖形化演示的改進.185。3.本章小結(jié)226 結(jié)論與展望.

9、23參考文獻.24致 謝.25附 錄.261 緒論自蟻群算法提出以來,就引起了國內(nèi)外學者的廣泛關(guān)注，提出了很多改進算法。參數(shù)的設(shè)置直接影響到算法的性能，所以對參數(shù)設(shè)置的研究越來越重要,而目前對它的研究大多還處于實驗分析階段。1.1 引言隨著人們對生命本質(zhì)的不斷了解，生命科學也以前所未有的速度迅猛發(fā)展，使人工智能的研究開始擺脫經(jīng)典邏輯計算的束縛，大膽探索起新的非經(jīng)典計算途徑.在這種背景下,社會性動物的自組織行為引起了人們的廣泛關(guān)注，許多學者對這種行為進行數(shù)學建模并用計算機對其進行仿真，這就產(chǎn)生了所謂的“群智能” 。受螞蟻總能找到一條從蟻巢到食物源的最短路徑的啟發(fā)，意大利學者 M. Dorigo

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

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

12、某一個或者某幾個個體的故障而影響整個問題的求解。（3） 可以不通過個體之間直接通信，而是通過非直接通信進行合作，這樣的系統(tǒng)具有更好的可擴充性(Scalability）。（4) 由于系統(tǒng)中個體的增加而增加的系統(tǒng)通信開銷在這里是十分小的，系統(tǒng)中每個個體的能力十分簡單，這樣每個個體的執(zhí)行時間比較短,并且實現(xiàn)也比較簡單，具有簡單性(Simplicity）。 1。3 蟻群算法的提出目前，群智能理論研究領(lǐng)域包括兩種主要算法:蟻群算法(Ant Colony Optimization，簡記ACO）和粒子群算法(Particle Swarm Optimization，簡記PSO)。而以蟻群算法為代表的群體智能已

13、成為當今分布式人工智能研究的一個熱點，它是由意大利學者M。 Dorigo、V. Maniez-zo、A. Colorini3，4，5等人從生物進化機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為后,于1991年首先提出的,也叫螞蟻系統(tǒng)（Ant System,AS).M. Dorigo等人充分利用蟻群搜索食物的過程與著名的旅行商問題（Traveling Salesman Problem）之間的相似性，吸收了螞蟻的行為特征，設(shè)計虛擬的“螞蟻”摸索不同的路線,并留下會隨時間逐漸消失的虛擬“信息量”2。虛擬的“信息量”會揮發(fā)，當螞蟻每次隨機選擇要走的路徑時,傾向于選擇信息量比較濃的路徑。根據(jù)“信息量濃

14、度更近”的原則，既可選擇出最佳路線。雖然蟻群算法的研究時間不長,但初步研究已顯示它在求解復雜優(yōu)化問題方面具有很大優(yōu)勢,特別是 1998 年在比利時布魯塞爾專門召開了第一屆螞蟻優(yōu)化國際研討會后,現(xiàn)在每兩年召開一次這樣的螞蟻優(yōu)化國際研討會。這標志著蟻群算法的研究已經(jīng)得到國際上的廣泛支持，使得這種新興的智能進化仿生算法展現(xiàn)出了勃勃生機6。1.4 本文研究工作本文圍繞蟻群算法的原理、改進及其應(yīng)用展開研究,全文共分六章,各章內(nèi)容安排如下：第一章：緒論本章首先對群智能進行介紹，然后闡述蟻群算法產(chǎn)生的背景.第二章:蟻群算法概述本章詳細介紹蟻群算法原理及其優(yōu)缺點。第三章：蟻群算法的參數(shù)設(shè)置研究本章針對參數(shù)設(shè)置

15、進行大量實驗,并對實驗結(jié)果做出研究分析,得出參數(shù)m，Q 的選擇規(guī)律，在此基礎(chǔ)上，提出新的有效方法對蟻群算法最優(yōu)組合參數(shù)進行選擇.第四章：蟻群算法實驗分析本章分析幾種改進的蟻群算法，并采用國際上通用的測試問題庫 TSPLIB中的對稱 TSP 問題作為測試對象，通過仿真試驗對六種算法各自求解 TSP 問題的性能進行比較,得出當 TSP 問題最優(yōu)解相同時，可依據(jù)其他性能（迭代次數(shù)、迭代時間等)得出 TSP 問題的最優(yōu)結(jié)果. 第五章：可視化編程針對陳燁的“蟻群算法實驗室”進行優(yōu)化和改進。第六章:結(jié)論與展望總結(jié)本文工作，提出展望。 2 蟻群算法概述 下面詳細介紹蟻群算法原理及其優(yōu)缺點.2.1 蟻群算法基

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

17、的螞蟻選擇此路徑,這條路徑上的外激素就會越來越強，選擇此路徑的螞蟻也越來越多.直到最后，幾乎所有的螞蟻都選擇這條最短的路徑.蟻群算法可以表述如下:在算法的初始時刻，將 m 只螞蟻隨機地放到 n 座城市，同時，將每只螞蟻的禁忌表的第一個元素設(shè)置為它當前所在的城市.此時各路徑上的信息素量相等，設(shè) ij(0) = C(C 為一較小的常數(shù))，接下來，每只螞蟻根據(jù)路徑上殘留的信息素量和啟發(fā)式信息（兩城市間的距離）獨立地選擇下一座城市，在時刻 t,螞蟻 k 從城市 i 轉(zhuǎn)移到城市 j 的概率(t)為: kijp (2. k( )( )( ), if jJ ( )( )( ) 0, otherwisekij

18、ijkisisijsJittitpt1）其中，Jk(i）= 1,2，n- tabuk 表示螞蟻 k 下一步允許選擇的城市集合.列表 tabuk記錄了螞蟻 k 當前走過的城市。當所有 n 座城市都加入到 tabuk中時，螞蟻 k 便完成了一次周游，此時螞蟻 k 所走過的路徑便是 TSP 問題的一個可行解。 （2. 1）式中的 ij 是一個啟發(fā)式因子，表示螞蟻從城市 i 轉(zhuǎn)移到城市 j 的期望程度.在 AS 算法中,ij 通常取城市 i 與城市 j 之間距離的倒數(shù).和 分別表示信息素和啟發(fā)式因子的相對重要程度。當所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)（2。 2)式更新。 (2. 2)ijij

19、ijtnt)()1 ( (2. 3)mkkijij1其中 （0 1）表示路徑上信息素的蒸發(fā)系數(shù)，1- 表示信息素的持久性系數(shù)；ij表示本次迭代邊 ij 上信息素的增量.kij表示第 k 只螞蟻在本次迭代中留在邊 ij 上的信息素量。如果螞蟻 k 沒有經(jīng)過邊 ij,則kij的值為零.kij表示為: （2. 4), kij0, kKijQL若螞蟻在本次周游中經(jīng)過邊 否則其中，Q 為正常數(shù)，Lk 表示第 k 只螞蟻在本次周游中所走過路徑的長度.M。 Dorigo 提出了 3 種 AS 算法的模型 7, 式 （2。4) 稱為 ant-cycle,另外兩個模型分別稱為 antquantity 和 ant

20、-density，其差別主要在 (2. 4） 式,即:在 ant-quantity 模型中為： , kij0, ijkijQd螞蟻在時刻t 和t +1經(jīng)過邊否則（2。 5) 在 ant-density 模型中為： , kij0, kijQ螞蟻在時刻t 和t +1經(jīng)過邊 否則 (2。 6)AS 算法實際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法.在選擇路徑時，螞蟻不僅利用了路徑上的信息素,而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。實驗結(jié)果表明，ant-cycle 模型比 ant-quantity 和 antdensity 模型有更好的性能.這是因為 antcycle 模型利用全局信息更新路徑上的

21、信息素量，而 ant-quantity 和 ant-density 模型使用局部信息。AS 算法的時間復雜度為（NC*n2*m） ,算法的空間復雜度為 S(n)=O（n2)+O(nm) ，其中 NC 表示迭代的次數(shù)，n 為城市數(shù)，m 為螞蟻的數(shù)目。2。2 蟻群算法的優(yōu)點與不足眾多研究已經(jīng)證明 AS 算法具有很強的發(fā)現(xiàn)較好解的能力，這是因為該算法不僅利用了正反饋原理，在一定程度上可以加快進化過程,而且是一種本質(zhì)上并行的算法。它有如下優(yōu)點8:(1） 較強的魯棒性：對蟻群算法模型稍加修改,便可以應(yīng)用于其它問題。(2) 分布式計算：蟻群算法是一種基于種群的進化算法,具有本質(zhì)的并行性，易于實現(xiàn)。(3）

22、易于與其他方法結(jié)合：蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能.同時它也存在一些缺陷：(1)限于局部最優(yōu)解，從算法解的性質(zhì)而言，蟻群算法也是在尋找一個比較好的局部最優(yōu)解，而不是強求是全局最優(yōu)解。（2)工作過程的中間停滯問題（stagnation behaviour）,和算法開始時收斂速度快一樣，在算法工作過程當中，迭代到一定次數(shù)后，螞蟻也可能在某個或某些局部最優(yōu)解的鄰域附近產(chǎn)生停滯。(3）較長的搜索時間,盡管和其他算法相比,蟻群算法在迭代次數(shù)和解的質(zhì)量上都有一定的優(yōu)勢,但對于目前計算機網(wǎng)絡(luò)的實際情況，還是需要較長的搜索時間.雖然計算機計算速度的提高和蟻群算法的并行性在一定程度上可以緩

23、解這一問題，但是對于大規(guī)模復雜的計算機網(wǎng)絡(luò)，這還是一個很大的障礙.2。3 本章小結(jié) 本章主要介紹了蟻群算法基本原理,并針對其優(yōu)缺點，進行了介紹和討論.螞蟻通過釋放一種特殊的分泌物-信息素來尋找路徑，螞蟻個體之間也通過信息素進行交流與合作。蟻群算法的優(yōu)勢主要體現(xiàn)在魯棒性,分布式，移植性等方面，而其缺陷,就目前來說，主要在局部最優(yōu)，工作停滯,搜索時間長等方面。3 蟻群算法的參數(shù)設(shè)置研究蟻群算法在TSP 問題應(yīng)用中取得了良好的效果,但也存在下列不足： （1) 如果參數(shù)、m、Q等設(shè)置不當,會導致求解速度很慢且所得解的質(zhì)量特別差;（2） 基本蟻群算法計算量大，求解所需的時間較長；（3) 基本蟻群算法中理

24、論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路;但在實際計算中，在給定一定循環(huán)次數(shù)的條件下很難實現(xiàn)這種情況. 另一方面，在其他的實際應(yīng)用中，如圖像處理中尋求最優(yōu)模板問題，并不要求所有的螞蟻都能找到最優(yōu)模板，而只需要一只找到即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計算效率。目前，對基本蟻群算法的參數(shù)設(shè)置和屬性的研究大多還處于實驗階段,M。 Dorigo 3,4 等人通過大量的實驗對螞蟻系統(tǒng)的參數(shù)和基本屬性進行了探討。討論的參數(shù)包括：m 螞蟻數(shù)目； -信息素的相對重要程度； 啟發(fā)式因子的相對重要程度; 信息素蒸發(fā)系數(shù)（1-）表示信息素的持久性系數(shù)）;Q -螞蟻釋放的信息素量。在

25、實驗中，為了觀察某個參數(shù)對算法性能的影響，在測試該參數(shù)時，其它參數(shù)取缺省值。各參數(shù)的缺省值為 m = n1/4(本文中為 21）， =1， =5， = 0。 5，Q =100.在實驗中,本實驗每組數(shù)據(jù)試驗5次取平均和最優(yōu)作比較，試驗中所用的TSP 問題數(shù)據(jù)來源于Eil51 城市問題，迭代次數(shù)100次.3.1 硬件/軟件環(huán)境平臺 本實驗采用的硬件/軟件環(huán)境分別為：CPU 2。 4GHz，內(nèi)存 256 M,硬盤容量 80G,安裝的是 Microsoft windows XP(Service Pack 2）操作系統(tǒng)，開發(fā)平臺是Microsoft Visual C+ 6。 0 。3.2 螞蟻數(shù)目對基本

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

27、，容易出現(xiàn)過早停滯現(xiàn)象.關(guān)于蟻群算法中螞蟻數(shù)量m 的選擇，也應(yīng)該綜合考慮算法的全局搜索能力和收斂速度兩項指標,針對具體問題的應(yīng)用條件和實際要求，在全局搜索能力和收斂速度兩方面作出合理或折衷的選擇。關(guān)于螞蟻數(shù)目m對算法性能的影響及其在實際應(yīng)用中的選擇，本文通過計算機仿真實驗來分析和確定,本文使螞蟻數(shù)目變化為5、7、9、11、13、15、17、19、21、23、25、27、29、31,螞蟻數(shù)目m對算法性能的影響仿真結(jié)果如表3-1和圖3-1所示。 表 31 螞蟻數(shù)目 m 對算法性能的影響的結(jié)果螞蟻數(shù)目最優(yōu)(最短）路徑長度運行的時間（s）5463。 9870768。 8287465。 00919914

28、. 119457. 0014789. 78111453. 74132713。 18713452. 82271614. 17215456. 11601113. 53117451。 11732112。 7519445。 62417714。 18721446. 07869513。 18823447. 00173113。 92125452。 29920213。 1127446. 07869521. 46829451。 22320414. 17131450。 77665913。 515最優(yōu)（最短）路徑長度435440445450455460465470579 11 13 15 17 19 21 23 2

29、5 27 29 31螞蟻數(shù)目最優(yōu)（最短）路徑長度圖 3-1 螞蟻數(shù)目 m 對算法性能的影響的仿真結(jié)果關(guān)于蟻群算法中螞蟻數(shù)量 m 的選擇,要綜合考慮算法的全局搜索能力和收斂速度兩項指標，針對具體問題的應(yīng)用條件和實際要求,在全局搜索能力和收斂速度兩方面做出合理或折衷的選擇,圖 31 為實驗所得的結(jié)果，其中橫軸表示螞蟻數(shù)，縱軸表示發(fā)現(xiàn)最優(yōu)解。從圖中可以看出當 m 在 1/42/5 之間時,蟻群算法可以找到最優(yōu)解，通過本實驗和其他學者的研究，本文最終得出螞蟻數(shù)目應(yīng)該在 1/42/5 之間，而且當城市數(shù)目規(guī)模較小時螞蟻數(shù)目 m 應(yīng)該盡量靠近2/5（如果很小可以考慮 m=n）,當城市數(shù)目規(guī)模較大時螞蟻數(shù)目

30、 m 應(yīng)該盡量靠近 1/4,因為這樣綜合考慮了算法的全局搜索能力和收斂速度兩項指標，可以使得找到最優(yōu)解并且全局搜索能力和收斂速度都是比較好，算法的各項性能相對平穩(wěn)。3.3 信息啟發(fā)式因子和期望值啟發(fā)式因子信息啟發(fā)式因子反映螞蟻在運動過程中所積累的信息量(即殘留信息量ij（t）)在指導蟻群搜索中的相對重要程度,期望值啟發(fā)式因子反映螞蟻在運動過程中啟發(fā)信息（即期望值ij ）在指導蟻群搜索中的相對重要程度9.期望值啟發(fā)式因子的大小反映了蟻群在路徑搜索中先驗性、確定性因素作用的強度，其值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大,雖然搜索的收斂速度得以加快,但是,蟻群在最優(yōu)路徑的搜索過程中隨

31、機性減弱易于陷入局部最優(yōu)；而信息啟發(fā)式因子的大小則反映了蟻群在路徑搜索中隨機性因素作用的強度，其值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機性減弱，當值過大也會使蟻群的搜索過早陷于局部最優(yōu)。蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過程必須有很強的隨機性；而蟻群算法的快速收斂性能，又要求蟻群的搜索過程必須要有較高的確定性。因此兩者對蟻群算法性能的影響和作用是相互配合、密切相關(guān)的.要想得到好的結(jié)果應(yīng)該適當選擇 和 的取值范圍，一般=0。 55，=159。因為兩者相互配合、密切相關(guān)，本文對和采用組合方式討論其對蟻群算法性能的影響。取為0。 5、1、2、5，為1、2、5，進行組合仿真實驗，

32、實驗結(jié)果如表32和圖3-2所示。本文為互聯(lián)網(wǎng)收集，請勿用作商業(yè)用途個人收集整理，勿做商業(yè)用途表 3-2 和 組合方式對算法性能結(jié)果信息素濃度影響力參數(shù) a啟發(fā)式信息影響力參數(shù) b最優(yōu)（最短)路徑長度運行的時間0. 51703. 90315614. 2650. 52531. 14289119。 2030. 55458. 38247917。 79711481. 41578817. 71812461。 26314915。 6415447。 00173112。 09321475。 70565223. 70322458. 0605112。 06225459。 59041712. 40651538。 12

33、448712。 70352465。 84123324. 2555465. 76743524. 375最優(yōu)（最短）路徑長度02004006008001251251251250.5 0.50.5 111222555和組合最優(yōu)（最短）路徑長度圖 3-2 和組合方式對算法性能的仿真結(jié)果以上實驗告訴我們，如果要增加蟻群算法的快速收斂性能,而且又要求蟻群的搜索過程必須要有較高的確定性，就要同時選擇好 和 ,因為它們對蟻群算法性能的影響和作用是相互配合、密切相關(guān)的。而本文在大量實驗的基礎(chǔ)上得出，要想得到更優(yōu)的結(jié)果則選擇 =1, =5.3。4 信息素殘留系數(shù)在蟻群算法中，隨著時間的推移，螞蟻留下的信息素會逐漸

34、消逝。在算法模型中用參數(shù) 1- 表示信息消逝程度（或稱信息素揮發(fā)度)，而 就是信息素殘留系數(shù)。蟻群算法與遺傳算法等各種模擬進化算法一樣,也存在著收斂速度慢、易于陷入局部最優(yōu)等缺陷。而信息素揮發(fā)度 1 的大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度：由于信息素揮發(fā)度 1- 的存在，當要處理的問題規(guī)模比較大時,會使那些從來未被搜索到的路徑（可行解）上的信息量減小到接近于 0,因而降低了算法的全局搜索能力，而且當 1 過大時以前搜索過的路徑被再次選擇的可能性過大，也會影響到算法的隨機性能和全局搜索能力;反之，通過減小信息素揮發(fā)度 1- 雖然可以提高算法的隨機性能和全局搜索能力，但又會使算法的收斂

35、速度降低.蟻群算法中信息素揮發(fā)度 1 的選擇，必須綜合考慮算法的全局搜索能力和收斂速度兩項性能指標，針對具體問題的應(yīng)用條件和實際要求，在全局搜索能力和收斂速度兩方面作出合理或折衷的選擇。為了使算法的性能比較穩(wěn)定和一致,搜索的全局性和收斂速度都比較好，本文通過計算機仿真實驗來分析和確定,本文使信息素殘留系數(shù) 變化為0. 1、0。 2、0。 3、0。 4、0。 5、0. 6、0. 7、0。 8、0。 9、0。 95、0。 99,信息素殘留系數(shù) 對算法性能的影響仿真結(jié)果如表 3-3 和圖 3-3 所示。文檔為個人收集整理,來源于網(wǎng)絡(luò)本文為互聯(lián)網(wǎng)收集，請勿用作商業(yè)用途表 3-3 信息素衰減因子對算法性

36、能的結(jié)果路徑上信息素衰減因子 p最優(yōu)（最短）路徑長度運行的時間0. 1448. 31777722。 50. 2453。 84862338. 0460。 3444. 56850716。 0160。 4455. 27027115。 9530。 5445. 62417714。 1870。 6448。 12365612. 7030. 7454。 30351917。 6560。 8448. 31777714。 0470. 9448. 38414111。 9070. 95449. 377717150。 99449. 79384313. 125最優(yōu)（最短）路徑長度4384404424444464484504

37、524544564580.10.20.30.40.50.60.70.80.90.950.99最優(yōu)（最短）路徑長度圖 3-3 信息素衰減因子對算法性能的仿真結(jié)果為了對蟻群算法中信息素揮發(fā)度 1- 進行選擇，必須綜合考慮算法的全局搜索能力和收斂速度兩項性能指標，針對具體問題的應(yīng)用條件和實際要求，在全局搜索能力和收斂速度兩方面做出合理或折衷的選擇。為了使算法的性能比較穩(wěn)定和一致，搜索的全局性和收斂速度都比較好，通過上述實驗可以知道要想得到好的結(jié)果本文建議 =0。 5（1=0。 5）.3.5 總信息量在蟻群模型中總信息量 Q 為螞蟻循環(huán)一周時釋放在所經(jīng)過的路徑上的信息素總量一般的理解是：總信息量 Q

38、越大則在螞蟻已經(jīng)走過的路徑上信息素的累積加快,可以加強蟻群搜索時的正反饋性能，有助于算法的快速收斂。由于在蟻群算法中各個算法參數(shù)的作用實際上是緊密耦合的,其中對算法性能起著主要作用的應(yīng)該是信息啟發(fā)式因子 、期望啟發(fā)式因子 和信息殘留常數(shù) 等三個參數(shù)?？傂畔⒘?Q 對算法性能的影響則有賴于 、 和 三個參數(shù)的配置以及算法模型的選取，例如在蟻周模型和蟻密模型中總信息量 Q 對算法性能的影響情況有較大的差異.總信息量對蟻周模型蟻群算法的性能沒有明顯的影響，一般取 Q =10010.3。6 本章小結(jié)本章通過大量實驗說明了信息素殘留因子 1-、信息啟發(fā)式因子 、期望啟發(fā)式因子 、信息素強度 Q、螞蟻數(shù)目

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

40、，即調(diào)整數(shù)值范圍較大的信息素強度 Q 參數(shù)（以 10 或更大的數(shù)為單位調(diào)整） ，已得到較理想的解,要想得到好的結(jié)果本文建議 Q=100。4 蟻群算法實驗分析 下面對目前最流行的幾種蟻群算法進行性能比較分析。4.1 改進的蟻群優(yōu)化算法為了克服AS的問題，很多學者對其進行研究，并提出了一些改進措施，下面將介紹五種蟻群優(yōu)化算法。 4。1.1 最優(yōu)解保留策略螞蟻系統(tǒng)通過使用最優(yōu)螞蟻可以提高螞蟻系統(tǒng)中解的質(zhì)量7。在最優(yōu)解保留策略螞蟻系統(tǒng)（Elitist Ant System,簡稱 EAS）中,每次迭代完成后,全局最優(yōu)解得到更進一步的利用，即在對信息素進行更新時，就好像有許多的最優(yōu)螞蟻選擇了該路徑.與 A

41、S 算法相比,ASelite算法在信息素更新時加強了對全局最優(yōu)解的利用，其信息素更新策略為： (0, 1） *)(*)1 () 1(ijijijijtt（4。 1） (4. 1mkijijk2） （4. , k ij 0, kKijQL如 果 螞 蟻 經(jīng) 過 邊 否 則3） (4。 *, 0, gbijQL如 果 邊 （i j ） 是 當 前 最 優(yōu) 解 的 一 部 分 否 則4）其中ij 為最優(yōu)螞蟻在邊(i, j）上增加的信息素量， 為最優(yōu)螞蟻數(shù)，Lgb 為全局最優(yōu)解。4.1.2 蟻群系統(tǒng)蟻群系統(tǒng)（Ant Colony System，簡稱 ACS）11是 AS 最成功的后續(xù)算法之一，與 AS

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

43、散,加快收斂速度。另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力，是目前解決 TSP、QAO 等問題最好的蟻群算法。4.1。4 基于排序的螞蟻系統(tǒng)基于排序的螞蟻系統(tǒng)（Rankbased Version of Ant System，簡稱 RAS）是Bernd Bullnheimer13等提出的 AS 的又一擴展算法。RAS 在每次迭代完成后，螞蟻所經(jīng)路徑將按從小到大的順序排列，即 L1（t） L2(t)Lm（t）,并根據(jù)路徑長度賦予不同的權(quán)重，路徑長度越短權(quán)重越大。全局最優(yōu)解的權(quán)重為 w，第 r 個最優(yōu)解的權(quán)重為 max0, wr ，按（3。 19）式更新各路徑上的信

44、息素: （0, 1） )()()()()1 () 1(11twtrwttgbijrijwrijij（4。 5）其中,rij(t)=1/ Lr（t） ，gbij (t)=1/ Lgb4。1.5 The Best-Worst Ant System,BWASBWAS 模型試著用進化算法概念提高 ACO 模型的性能,提出的 BWAS 用的是 AS 轉(zhuǎn)移規(guī)則： （4。 k( ), if sJ ( , )0, otherwise KrsrsrrJrPS6）rs是邊界（r， s)的信息素值，rs使啟發(fā)值，Jk（r) 是留下來被螞蟻K訪問的節(jié)點集，, 實值的權(quán)。常用的AS揮發(fā)規(guī)則rs (1）rs, r， s，

45、 0, 1，是信息素揮發(fā)參數(shù)。另外，BWAS考慮下面三個新進程的作用，下面就是對他們的深入分析5：性能更新規(guī)則：這種規(guī)則是基于 PBIL 的概率數(shù)組更新規(guī)則，信息素更新如下所示: （4. ( (), ( , ), where 0, otherwiseglobal bestglobal bestrsrsrsrsf c Sif r sS7)f（C(Sglobalbest)） 是要被全局最好的螞蟻存放的信息素數(shù)量，隨著全局最優(yōu)螞蟻算法聚集了大量的信息素，依靠形成的解決方案C(Sglobalbest） 。信息素痕跡突變: 信息素痕跡在研究介紹相異性時遇到突變,就像PopulationBased Inc

46、remental Learning（PBIL）14這樣，信息素矩陣的每一排被改變，概率Pm如下: (4. ( ,), if =0 ( ,), if 0 rsthresholdrsrsthresholdmut itmut it8）它是 0 到 1 之間的隨機值，也是當前的迭代，Tthreshold 是組成全局最優(yōu)解決方案的臨界的信息素跟蹤的平均值，mut(。 ）是隨著迭代記數(shù)的增長,變異增強的函數(shù). 當與當前最優(yōu)和最差解決方案不同的臨界值的數(shù)字比特定的百分比少時,本文要把所有的信息素痕跡矩陣組成更新為 T0，然后循環(huán)。4. 2 實驗仿真及算法性能比較分析同 AS 算法相比，以上算法的共同之處在于

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

48、4。2。1 硬件/軟件環(huán)境平臺 本實驗采用的硬件/軟件環(huán)境分別為：CPU 3。 0 GHz，內(nèi)存 512 M，硬盤容量 80G，安裝的是Microsoft windows XP(Service Pack 2）操作系統(tǒng)，開發(fā)平臺 Microsoft Visual C+ 6. 0 。4.2。2 重要參數(shù)設(shè)置本實驗中重要參數(shù)設(shè)置如下：信息素濃度影響力參數(shù)：所有算法設(shè)為1。0啟發(fā)式信息影響力參數(shù)：所有算法設(shè)為5。0信息素蒸發(fā)系數(shù)（1-)表示信息素的持久性系數(shù)）：所有算法設(shè)為0. 5(1即為0. 5)。螞蟻數(shù)目m：本文將m設(shè)為問題規(guī)模n的1/4即m=n*1/4在算法開始時螞蟻隨機分布在各個城市上.此外，

49、對于EAS，精英螞蟻的數(shù)目的個數(shù)e取100（n為其中TSP問題中后面的數(shù)字，如Eil51中51即為n值）。在MMAS中初始信息素濃度 0設(shè)定為與max相等, 路經(jīng)信息素濃度下限min設(shè)定為小于max的一常數(shù),并且根據(jù)式4. 16進行更新。4。2.3 實驗結(jié)果表41是MMAS，ACS,EAS，RAS,BWAS 與 AS 算法求解不同 TSP 實例的比較結(jié)果(問題的最優(yōu)解用黑體加粗顯示），各算法迭代 100次，再重復迭代10次，取10次中的最優(yōu)進行比較后再進行平均。表41 MMAS，ACS,EAS,RAS，BWAS 與 AS 算法求解不同 TSP 實例的結(jié)果比較問題問題ASEASRASMMASBW

50、ASACS最優(yōu)解最優(yōu)解426426426426426426迭代次數(shù)迭代次數(shù)111111迭代時間迭代時間000000平均解平均解428。 3427. 8428. 0428. 0427。 9428。 5平均迭代時間（平均迭代時間（s)0。 0031000。 0016000。 0016000。 0061000. 0032000. 001500Eil51平均總時間（平均總時間（s）0. 0188000。 0171000。 0181900. 0217000. 0172000. 007900最優(yōu)解最優(yōu)解212822128221282212822128221282迭代次數(shù)迭代次數(shù)111111迭代時間迭代時間

51、00。 01500000。 01600000平均解平均解21311。 621317. 021285. 321317. 021307. 621323. 7平均時間（平均時間（s)0. 0126000。 0156000。 0124000。 0141000。 0079000。 014100KroA100平均總時間（平均總時間（s)0. 0188000. 0250000. 0249000. 0235000。 0188000. 017200最優(yōu)解最優(yōu)解158581585315829158361584715847迭代次數(shù)迭代次數(shù)111111迭代時間迭代時間0. 0160000。 0310000. 0160

52、000。 0320000。 0150000. 025000平均解平均解15952. 016093. 016037. 915959. 016075. 816113. 2平均時間（平均時間（s）0. 0186000。 0173000. 0175000。 0190000。 0180000。 015400d198平均總時間（平均總時間（s）0。 0250000. 0250000。 0220000。 0220000. 0218000. 021800最優(yōu)解最優(yōu)解421554202942029420294202942029迭代次數(shù)迭代次數(shù)5331614646迭代時間迭代時間0。 6570003。 14100

53、01. 5780001. 7190000。 6250005。 016000平均解平均解42209. 942088。 342098. 242087。 242101. 242117。 7平均時間（平均時間（s)4。 6924005. 5423001。 5423003. 2844002。 6297006。 282700Lin318平均總時間平均總時間(s）10. 0484009。 3547006。 8156007. 13140014。 85630011. 437500最優(yōu)解最優(yōu)解511345105851000508075078551146迭代次數(shù)迭代次數(shù)452950503424迭代時間迭代時間9。

54、5620006. 3120009. 8430009. 7340006. 0000006。 844000平均解平均解51222。 051151。 151104. 750922. 950927. 451238. 9平均時間（平均時間（s）6。 9653006。 2342007。 2342007。 4293004。 3124005. 634500Pcb422平均總時間平均總時間(s)10. 07500010. 08730010. 11710010. 10310010。 10310010。 140700最優(yōu)解最優(yōu)解281462811328138280552809628112迭代次數(shù)迭代次數(shù)111111

55、迭代時間迭代時間0。 5160000. 4680000。 5630000. 4530000。 4690000. 531000平均解平均解28205. 828195. 728199. 528170。 028218。 028216. 1平均時間（平均時間（s)0。 5142000. 5030000。 5181200。 4561000。 5814000. 548900Att532平均總時間平均總時間(s)0. 5390000。 5500000。 5932800。 1470000. 5922000。 510300最優(yōu)解最優(yōu)解903890239035902690339014迭代次數(shù)迭代次數(shù)111111迭

56、代時間迭代時間0. 8900000. 8440000。 8440000。 8750000. 9220000. 938000平均解平均解9066. 79063。 99062. 99050。 29054。 59053。 1平均時間（平均時間（s）0. 9298000。 8720000。 8657000。 8707000。 9625000。 935800Rat783平均總時間平均總時間(s）0. 9562000. 8906000. 8782000。 8844000. 9765000。 940600最優(yōu)解最優(yōu)解242961242840242370242706240898243314迭代次數(shù)迭代次數(shù)12

57、3332迭代時間迭代時間4。 5000008。 73500013. 7660002。 81440011。 8910009。 750000平均解平均解243367。 4243149。 7243462. 9243879。 3241922。 4244079。 7平均時間（平均時間（s）9. 12500010. 55310010. 9313009。 45320010. 7376008。 733000Vm1084平均總時間平均總時間(s)12。 71090012。 38600011。 76880010. 76880010. 76260012. 645000最優(yōu)解最優(yōu)解583015822857895579

58、955775058435迭代次數(shù)迭代次數(shù)454572迭代時間迭代時間7. 5310009. 2500007. 1880009。 31300011。 0000004。 815000平均解平均解58443. 558401。 958217. 258295. 358002. 058660. 9平均時間平均時間(s）7。 5486007。 2281008。 64060010。 52040010. 2982007. 715700Pcb1173平均總時間（平均總時間（s)10. 60400011。 06720011。 16790011. 03130010. 60000011. 070500最優(yōu)解最優(yōu)解515

59、555148251213514835099751758迭代次數(shù)迭代次數(shù)546555迭代時間迭代時間8。 3590007。 31400011. 0870009. 1250008。 65200011. 641000平均解平均解51681。 751682. 151395。 751807。 551398。 252080. 5平均時間平均時間(s)6。 9875007。 7469009. 40140010。 04850010。 3189008。 906000d1291平均總時間平均總時間(s)10. 86090010。 68590011。 02190010. 85600011. 10630011。 18

60、7400最優(yōu)解最優(yōu)解257189256805257359257262253938258066迭代次數(shù)迭代次數(shù)223133迭代時間迭代時間10。 9300006. 96900010. 5000005。 32907011。 32800013. 938000平均解平均解258689。 6258796。 4258393. 7259087。 8255995。 6259374。 5平均時間（平均時間（s）9。 8064009. 2045009. 2340008。 46720010。 51400010. 267300rl1304平均總時間（平均總時間（s）12。 23280011。 28440011。 01