群智能是近年來(lái)人工智能研究的一個(gè)熱點(diǎn)話題蟻群算法作....doc

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

2、編程進(jìn)行了優(yōu)化和改進(jìn)，使之能夠更方便的用于幾種算法性能比較和同種算法不同參數(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。文檔為個(gè)人收集整理，來(lái)源于網(wǎng)絡(luò)本文為互

7、聯(lián)網(wǎng)收集，請(qǐ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)點(diǎn)與不足.52。3 本章小結(jié).63 蟻群算法的參數(shù)設(shè)置研究.73。1 硬件/軟件環(huán)境平臺(tái).73。2 螞蟻數(shù)目對(duì)基本蟻群算法的影響.73。3 信息啟發(fā)式因子和期望值啟發(fā)式因子.93.4 信息素殘留系數(shù) .103.5 總信息

8、量.113.6 本章小結(jié).124 蟻群算法實(shí)驗(yàn)分析.134。1 改進(jìn)的蟻群優(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 實(shí)驗(yàn)仿真及算法性能比較分析.154.2。1 硬件/軟件環(huán)境平臺(tái).154。2.2 重要參數(shù)設(shè)置.154。2.3 實(shí)驗(yàn)結(jié)果.154。3 本章小結(jié).175 可視化編程.185。1 “蟻群算法實(shí)驗(yàn)室”的優(yōu)點(diǎn)與不足.185。2 最大最小蟻群算法的圖形化演示的改進(jìn).185。3.本章小結(jié)226 結(jié)論與展望.

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

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

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

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

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

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

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

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

17、的螞蟻選擇此路徑,這條路徑上的外激素就會(huì)越來(lái)越強(qiáng)，選擇此路徑的螞蟻也越來(lái)越多.直到最后，幾乎所有的螞蟻都選擇這條最短的路徑.蟻群算法可以表述如下:在算法的初始時(shí)刻，將 m 只螞蟻隨機(jī)地放到 n 座城市，同時(shí)，將每只螞蟻的禁忌表的第一個(gè)元素設(shè)置為它當(dāng)前所在的城市.此時(shí)各路徑上的信息素量相等，設(shè) ij(0) = C(C 為一較小的常數(shù))，接下來(lái)，每只螞蟻根據(jù)路徑上殘留的信息素量和啟發(fā)式信息（兩城市間的距離）獨(dú)立地選擇下一座城市，在時(shí)刻 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 當(dāng)前走過(guò)的城市。當(dāng)所有 n 座城市都加入到 tabuk中時(shí)，螞蟻 k 便完成了一次周游，此時(shí)螞蟻 k 所走過(guò)的路徑便是 TSP 問(wèn)題的一個(gè)可行解。 （2. 1）式中的 ij 是一個(gè)啟發(fā)式因子，表示螞蟻從城市 i 轉(zhuǎn)移到城市 j 的期望程度.在 AS 算法中,ij 通常取城市 i 與城市 j 之間距離的倒數(shù).和 分別表示信息素和啟發(fā)式因子的相對(duì)重要程度。當(dāng)所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)（2。 2)式更新。 (2. 2)ijij

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

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

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

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

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

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

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

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

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

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

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

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

32、實(shí)驗(yàn)結(jié)果如表32和圖3-2所示。本文為互聯(lián)網(wǎng)收集，請(qǐng)勿用作商業(yè)用途個(gè)人收集整理，勿做商業(yè)用途表 3-2 和 組合方式對(duì)算法性能結(jié)果信息素濃度影響力參數(shù) a啟發(fā)式信息影響力參數(shù) b最優(yōu)（最短)路徑長(zhǎng)度運(yùn)行的時(shí)間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)（最短）路徑長(zhǎng)度02004006008001251251251250.5 0.50.5 111222555和組合最優(yōu)（最短）路徑長(zhǎng)度圖 3-2 和組合方式對(duì)算法性能的仿真結(jié)果以上實(shí)驗(yàn)告訴我們，如果要增加蟻群算法的快速收斂性能,而且又要求蟻群的搜索過(guò)程必須要有較高的確定性，就要同時(shí)選擇好 和 ,因?yàn)樗鼈儗?duì)蟻群算法性能的影響和作用是相互配合、密切相關(guān)的。而本文在大量實(shí)驗(yàn)的基礎(chǔ)上得出，要想得到更優(yōu)的結(jié)果則選擇 =1, =5.3。4 信息素殘留系數(shù)在蟻群算法中，隨著時(shí)間的推移，螞蟻留下的信息素會(huì)逐漸

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

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

36、能的結(jié)果路徑上信息素衰減因子 p最優(yōu)（最短）路徑長(zhǎng)度運(yùn)行的時(shí)間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)（最短）路徑長(zhǎng)度4384404424444464484504

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

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

39、 m 等都是非常重要的參數(shù)，其選區(qū)方式和選區(qū)原則直接影響到蟻群算法的全局收斂性和求解效率，還通過(guò)實(shí)驗(yàn)得出這些參數(shù)的選擇規(guī)律，并提出了這種“四步走”來(lái)選擇蟻群算法最優(yōu)組合參數(shù)的有效方法：（1）確定螞蟻數(shù)目 m,根據(jù) 城市規(guī)模 / 螞蟻數(shù)目 1/42/5 的選擇策略來(lái)確定螞蟻的總數(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ù)值范圍較大的信息素強(qiáng)度 Q 參數(shù)（以 10 或更大的數(shù)為單位調(diào)整） ，已得到較理想的解,要想得到好的結(jié)果本文建議 Q=100。4 蟻群算法實(shí)驗(yàn)分析 下面對(duì)目前最流行的幾種蟻群算法進(jìn)行性能比較分析。4.1 改進(jìn)的蟻群優(yōu)化算法為了克服AS的問(wèn)題，很多學(xué)者對(duì)其進(jìn)行研究，并提出了一些改進(jìn)措施，下面將介紹五種蟻群優(yōu)化算法。 4。1.1 最優(yōu)解保留策略螞蟻系統(tǒng)通過(guò)使用最優(yōu)螞蟻可以提高螞蟻系統(tǒng)中解的質(zhì)量7。在最優(yōu)解保留策略螞蟻系統(tǒng)（Elitist Ant System,簡(jiǎn)稱(chēng) EAS）中,每次迭代完成后,全局最優(yōu)解得到更進(jìn)一步的利用，即在對(duì)信息素進(jìn)行更新時(shí)，就好像有許多的最優(yōu)螞蟻選擇了該路徑.與 A

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

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

43、散,加快收斂速度。另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力，是目前解決 TSP、QAO 等問(wèn)題最好的蟻群算法。4.1。4 基于排序的螞蟻系統(tǒng)基于排序的螞蟻系統(tǒng)（Rankbased Version of Ant System，簡(jiǎn)稱(chēng) RAS）是Bernd Bullnheimer13等提出的 AS 的又一擴(kuò)展算法。RAS 在每次迭代完成后，螞蟻所經(jīng)路徑將按從小到大的順序排列，即 L1（t） L2(t)Lm（t）,并根據(jù)路徑長(zhǎng)度賦予不同的權(quán)重，路徑長(zhǎng)度越短權(quán)重越大。全局最優(yōu)解的權(quán)重為 w，第 r 個(gè)最優(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 模型試著用進(jìn)化算法概念提高 ACO 模型的性能,提出的 BWAS 用的是 AS 轉(zhuǎn)移規(guī)則： （4。 k( ), if sJ ( , )0, otherwise KrsrsrrJrPS6）rs是邊界（r， s)的信息素值，rs使啟發(fā)值，Jk（r) 是留下來(lái)被螞蟻K訪問(wèn)的節(jié)點(diǎn)集，, 實(shí)值的權(quán)。常用的AS揮發(fā)規(guī)則rs (1）rs, r， s，

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

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

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

48、4。2。1 硬件/軟件環(huán)境平臺(tái) 本實(shí)驗(yàn)采用的硬件/軟件環(huán)境分別為：CPU 3。 0 GHz，內(nèi)存 512 M，硬盤(pán)容量 80G，安裝的是Microsoft windows XP(Service Pack 2）操作系統(tǒng)，開(kāi)發(fā)平臺(tái) Microsoft Visual C+ 6. 0 。4.2。2 重要參數(shù)設(shè)置本實(shí)驗(yàn)中重要參數(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è)為問(wèn)題規(guī)模n的1/4即m=n*1/4在算法開(kāi)始時(shí)螞蟻隨機(jī)分布在各個(gè)城市上.此外，

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

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

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

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

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

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

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

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

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

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

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

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