蟻群優(yōu)化算法的收斂性分析與研究

趙世安

摘 要： 蟻群算法本身存在收斂速度慢、容易陷入局部最優(yōu)解的缺陷，針對(duì)該缺陷提出一些改進(jìn)的蟻群優(yōu)化算法。主要討論蟻群優(yōu)化算法的收斂性理論及應(yīng)用，得出蟻群系統(tǒng)和最大最小螞蟻系統(tǒng)的性能好于螞蟻系統(tǒng)，而且最大最小螞蟻系統(tǒng)的性能最好，蟻群系統(tǒng)和最大最小螞蟻系統(tǒng)是值收斂的，一種特殊的[ACOgs，ρ（θ）]算法是解收斂的。

關(guān)鍵詞： 蟻群優(yōu)化算法； 收斂性； 蟻群系統(tǒng)； 解收斂

中圖分類(lèi)號(hào)： TN911.1?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）19?0173?04

Analysis and research on convergence of ant colony optimization algorithm

ZHAO Shian

（School of Mathematics & Statics， Baise University， Baise 533000， China）

Abstract： The ant colony algorithm has the defect of slow convergence speed and is easy to fall into the local optimal solution， so some improved ant colony optimization algorithms are proposed to elimanite the defect. The convergence theory and application of the ant colony optimization （ACO） algorithm are discussed mainly in this paper. It is obtained that the performance of the ant colony systen and min?max ant system is higher than that of the ant system， in which the min?max ant system has the highest performance， the ant colony system and min?max ant system are convergent， and a special [ACOgs，ρ（θ）] algorithm is solution convergent.

Keywords： ant colony optimization algorithm； convergence； ant colony system； solution convergence

0 引 言

隨著科學(xué)技術(shù)和現(xiàn)代化生產(chǎn)的快速發(fā)展，優(yōu)化問(wèn)題在各行各業(yè)中顯得越來(lái)越重要，然而傳統(tǒng)的優(yōu)化方法對(duì)函數(shù)性質(zhì)的要求比較高，如要求函數(shù)連續(xù)、可微等，而實(shí)際問(wèn)題中，很多函數(shù)都不具有上述性質(zhì)，因此在應(yīng)用上有很大的局限性，而且實(shí)際問(wèn)題往往很復(fù)雜，所以需要尋求新的優(yōu)化方法[1?2]。隨著計(jì)算機(jī)技術(shù)和人工智能技術(shù)的發(fā)展，人們提出了蟻群算法、遺傳算法、粒子群算法等群智能算法，這些算法一個(gè)很重要的特點(diǎn)就是群集智能特性[3]。

與大多數(shù)傳統(tǒng)確定性全局算法不同，群集算法依靠的是概率搜索方法，即不是每一步迭代都能夠讓算法得到更好的解[4?5]。雖然概率搜索方法需要依靠比較多的評(píng)價(jià)函數(shù)，以及需要大量的迭代步數(shù)，但是它的優(yōu)點(diǎn)也是顯著的：

（1） 群體中相互合作的個(gè)體是分布式的；

（2） 沒(méi)有中心的控制，這樣的系統(tǒng)更加具有魯棒性；

（3） 不需要通過(guò)不同個(gè)體之間的通信，而通過(guò)非直接通信進(jìn)行合作。這樣的系統(tǒng)具有非常好的擴(kuò)展性；

（4） 系統(tǒng)中每個(gè)個(gè)體的能力十分簡(jiǎn)單，執(zhí)行的時(shí)間也非常短。實(shí)踐證明，這些智能算法對(duì)解決實(shí)際問(wèn)題具有很好的效果，本文主要討論蟻群優(yōu)化算法的收斂性理論及應(yīng)用。

1 收斂性概述

螞蟻系統(tǒng)（Ant System，AS）是第一個(gè)ACO算法，被稱(chēng)為基本的ACO算法，目前對(duì)于ACO算法的理論研究主要集中在算法收斂性上，在這方面文獻(xiàn)[6]開(kāi)創(chuàng)性地提出一種基于圖的螞蟻系統(tǒng)元啟發(fā)式這一ACO的通用模型，該模型能夠在一定條件下以任意接近1的概率收斂到最優(yōu)解。但是這種模型對(duì)于條件的要求很苛刻，很難應(yīng)用到實(shí)際當(dāng)中去。

蟻群優(yōu)化算法的收斂性包括值收斂和解收斂，值收斂評(píng)估的是任意一個(gè)最優(yōu)解至少出現(xiàn)一次的可能性，即至少有一只螞蟻能夠找到最優(yōu)解的概率；解收斂評(píng)估的是算法到達(dá)某個(gè)可以持續(xù)生產(chǎn)相同最優(yōu)解的狀態(tài)的可能性，即任意一只螞蟻都可以找到最優(yōu)解的概率。

文獻(xiàn)[6]首先對(duì)蟻群優(yōu)化算法的收斂性進(jìn)行研究，提出基于圖的螞蟻系統(tǒng)（GBAS）。這是一種更為特殊的蟻群優(yōu)化算法，適用于各種靜態(tài)組合優(yōu)化問(wèn)題，用到的主要工具是馬爾可夫過(guò)程理論，證明了算法的迭代過(guò)程是一個(gè)馬爾可夫過(guò)程，并得到了如下結(jié)果：

（1） 對(duì)于固定的信息素蒸發(fā)系數(shù)，只要迭代次數(shù)足夠多，某只螞蟻找到最優(yōu)解的概率會(huì)任意接近1；

（2） 對(duì)于一定量的螞蟻和足夠小的信息素蒸發(fā)系數(shù)，只要迭代次數(shù)足夠多，某只螞蟻找到最優(yōu)解的概率任意接近1。

但是由于GBAS算法對(duì)于條件的要求太高，如要求問(wèn)題只能有一個(gè)最優(yōu)解等，而且是一種從來(lái)沒(méi)有實(shí)現(xiàn)過(guò)的算法。上面提到的收斂指的是值收斂，Gutjahr隨后又提出了GBAS算法的變種算法，GBAS/tdlb（信息素的下界與時(shí)間相關(guān)）和GBAS/tdev（信息素的蒸發(fā)速率與時(shí)間相關(guān)），并證明了它們是解收斂的。

之后，文獻(xiàn)[7]給出兩種特殊蟻群優(yōu)化算法（即[ACObs，τmin]和[ACObs，τmin（θ）]）收斂性的證明。本文主要證明最大最小螞蟻系統(tǒng)算法（MMAS）和蟻群系統(tǒng)（ACS）算法是值收斂的，并且證明一種特殊的蟻群優(yōu)化算法[ACOgs，ρ（θ）]是解收斂的。

2 收斂性證明

2.1 MMAS和ACS收斂性的證明

首先證明最大最小螞蟻系統(tǒng)算法是值收斂的。

命題1：在最大最小螞蟻系統(tǒng)算法中，任意的一個(gè)部分解[xh]選擇任意一個(gè)可行節(jié)點(diǎn)的概率[pmin>0。]

證明：在最大最小螞蟻系統(tǒng)算法中，信息素[τij]的上下界分別為[τmax]和[τmin，]并且對(duì)于啟發(fā)式因子[ηij]有，[0<ηij<∞，]由于[ηij]的個(gè)數(shù)有限，因此[ηij]有上下界，分別記為[ηmax]和[ηmin]。

假設(shè)螞蟻已經(jīng)生成了部分解[xh，]則對(duì)于下一個(gè)可選節(jié)點(diǎn)，最壞的情形就是[xh]的最后一個(gè)節(jié)點(diǎn)和該節(jié)點(diǎn)之間的邊上，[ταijηβij=ταminτβmin，][xh]的最后一個(gè)節(jié)點(diǎn)和其余可選節(jié)點(diǎn)組成的邊上[ταijηβij=ταmaxτβmax，]并且其余節(jié)點(diǎn)都是可選節(jié)點(diǎn)。因此，螞蟻選擇任意一個(gè)可行節(jié)點(diǎn)的概率[pmin]有如下關(guān)系：

[pmin≥pmin=ταminτβminNc-1ταmaxτβmax+ταminτβmin>0] （1）

式中：[Nc]表示節(jié)點(diǎn)的總數(shù)。因此，對(duì)于任意的一個(gè)部分解[xh]的選擇，任意一個(gè)可行節(jié)點(diǎn)的概率[pmin>0。]

定理1：在最大最小螞蟻系統(tǒng)算法中，令[p*（θ）]表示算法在前[θ]次迭代中至少有一次得到最優(yōu)解的概率。那么，對(duì)于任意的[ε>0]和一個(gè)充分大的[θ，]以下不等式成立：[p*（θ）≥1-ε，]即[limθ→∞p*（θ）=1]。

證明：記螞蟻生成任意一個(gè)可行解（包括最優(yōu)解[s*]）的概率為[p，]由命題1可知，[p≥pnmin，]其中[n]表示可行解的長(zhǎng)度。由于每次迭代生成最優(yōu)解是相互獨(dú)立的，因此，迭代[θ]后得到最優(yōu)解的概率[p*（θ）]有一個(gè)下限為：[p*（θ）=1-（1-p）θ，]因此[p*（θ）≤p*（θ）≤1。]顯然[limθ→∞p*（θ）=1]，所以[limθ→∞p*（θ）=1，]命題成立，最大最小螞蟻系統(tǒng)算法是值收斂的。

現(xiàn)在證明蟻群系統(tǒng)算法也是值收斂的。蟻群系統(tǒng)算法與最大最小螞蟻系統(tǒng)有很大的區(qū)別，主要表現(xiàn)在蟻群系統(tǒng)算法中引入了偽隨機(jī)比例規(guī)則，并且蟻群系統(tǒng)算法中，局部信息素更新規(guī)則和全局信息素更新規(guī)則交替進(jìn)行[8]。盡管不像最大最小螞蟻系統(tǒng)算法那樣對(duì)信息素的值設(shè)置了界限，但是可以證明，蟻群系統(tǒng)算法中信息素的值也有上下界。

命題2：在蟻群系統(tǒng)算法中，信息素[τij]的一個(gè)下界為[τ0]，一個(gè)上界為[qf（s*）]，其中[s*]表示全局最優(yōu)解，[qf（?）]是一個(gè)取正值的遞減函數(shù)，[sbestθ+1]表示第[θ+1]次迭代后得到的迄今為止最好的解。

證明：首先，在蟻群系統(tǒng)算法中，信息素的局部更新規(guī)則為：

[τij（θ+1）=（1+ε）?τij（θ）+ε?τ0] （2）

信息素的全局更新規(guī)則為：

[τij（θ+1）=（1-ρ）?τij（θ）+ρ?qf（sbestθ+1）] （3）

顯然式（2）和式（3）具有相同的形式：

[a（θ+1）=1-ξ?a（θ）+ξ?b] （4）

由式（4）可得：

[a（θ）=1-ξθ?a（0）+b?1-1-ξθ] （5）

顯然，當(dāng)[a（0）>b]時(shí)，[a（θ）]是單調(diào)遞減的，當(dāng)[a（0）≤b]時(shí)，[a（θ）]是單調(diào)遞增的，并且[limθ→∞a（θ）=b]。用數(shù)學(xué)歸納法可以證明只要取[τ0

當(dāng)[θ=1]時(shí)：

[τij（1）=（1-ρ）?τ0+ρ?qf（sbest1）<（1-ρ）?qf（s*）+ρ?qf（s*）=qf（s*）] （6）

所以當(dāng)[θ=1]時(shí)，假設(shè)成立。假設(shè)[θ=n]時(shí)，假設(shè)成立。

當(dāng)[θ=n+1]時(shí)：

[τij（n+1）=（1-ρ）?τij（n）+ρ?qf（sbest1）<（1-ρ）?qf（s*）+ρ?qf（s*）=qf（s*）] （7）

當(dāng)[θ=n+1]時(shí)，假設(shè)也成立。所以[τij]的一個(gè)上界為[qf（s*）]。

命題3：在蟻群系統(tǒng)算法中，任意的一個(gè)部分解[xh]選擇任意一個(gè)可行節(jié)點(diǎn)的概率[pmin>0。]

證明：在蟻群系統(tǒng)算法中，由于引入了偽隨機(jī)比例規(guī)則，因此如果在邊[（i，j）]上，[ταij，][τβij]不是最大的，那么在最壞的情形下，螞蟻選擇這條邊的概率為：

[pmin≥pmin=（1-q0）?τα0τβminNc-1?qαf（s*）?ηβmax+τα0τβmin>0] （8）

式中：[q0]為偽隨機(jī)比例規(guī)則中的隨機(jī)數(shù)。所以，任意的一個(gè)部分解[xh]選擇任意一個(gè)可行節(jié)點(diǎn)的概率[pmin>0。]

定理2：在螞蟻系統(tǒng)算法中，令[p*（θ）]表示算法在前[θ]次迭代中至少有一次得到最優(yōu)解的概率。那么，對(duì)于任意的[ε>0]和一個(gè)充分大的[θ，]以下不等式成立：[p*（θ）≥1-ε，]即[limθ→∞p*（θ）=1]。

證明：記螞蟻第[θ]次迭代，生成任意一條可行路徑（包括最優(yōu)路徑）的概率為[pθ，]記[p*min=min（pmin，q0），]可知[pθ≥qm0?pn-mmin>p*minn>0]，其中，[m]表示生成一條可行路徑過(guò)程中，偽隨機(jī)比例選擇的次數(shù)，且[0≤m≤n，][n]是解序列的長(zhǎng)度。則：

[1-（1-p*min）θ≤1-i=1θ（1-pi）≤p*（θ）≤1] （9）

顯然[limθ→∞1-（1-p*min）θ=1，]所以，[limθ→∞p*（θ）=1，]蟻群系統(tǒng)算法是值收斂的。

通過(guò)以上證明可知，最大最小螞蟻系統(tǒng)算法和蟻群系統(tǒng)算法都是值收斂的，但不是解收斂的。

2.2 [ACOgs，ρ（θ）]算法收斂性的證明

最大最小螞蟻系統(tǒng)算法和蟻群系統(tǒng)算法都屬于[ACObest，τmin]類(lèi)型的算法，即信息素有一個(gè)下界，而且揮發(fā)系數(shù)不隨著迭代次數(shù)的改變而改變，只在當(dāng)前最優(yōu)解的路徑上增加信息素。上面已經(jīng)證明了它們都是值收斂的。[ACObest，τmin（θ）]算法是對(duì)[ACObest，τmin]算法的一種改進(jìn)，即信息素的最小值可以根據(jù)迭代次數(shù)進(jìn)行調(diào)整，并且允許信息素的最小值能夠隨著時(shí)間的推移減少到零，但是這個(gè)過(guò)程必須要足夠緩慢以保證能夠找到最優(yōu)解。[ACOgs，ρ（θ）]算法同[ACObest，τmin]算法的思想有些類(lèi)似，但它是通過(guò)改變信息素的揮發(fā)速度使信息素的值緩慢減小到0。在[ACOgs，ρ（θ）]算法中，信息素的增加同樣僅僅發(fā)生在當(dāng)前最優(yōu)解的路徑上，并且當(dāng)?shù)螖?shù)[θ≤θ0]時(shí)，信息素的揮發(fā)系數(shù)是常數(shù)[ρ，]當(dāng)?shù)螖?shù)[θ>θ0]時(shí)，信息素的揮發(fā)系數(shù)為[ρθ，]且滿(mǎn)足：

[ρθ≤1-ln（θ）ln（θ+1）， θ=1∞ρθ=∞]

首先證明[ACOgs，ρ（θ）]是值收斂的。

定理3：[ACOgs，ρ（θ）]算法是值收斂的。

證明：考慮最壞的情形，信息素只揮發(fā)不增加。則經(jīng)過(guò)[θ（θ>θ0）]次迭代之后，邊[（i，j）]上的信息素濃度[τij（θ）]有如下表達(dá)式：

[τij（θ）=i=1θ（1-ρi）?τij（0）≥（1-ρ）θ0?i=θ0+1θln（i）ln（i+1）?τij（0）] （10）

記[a=（1-ρ）θ0τij（0）ln（θ0+1）]，則：

[τij（θ）≥aln（θ+1）] （11）

由于在[ACOgs，ρ（θ）]算法中信息素的全局更新規(guī)則為：

[τij（θ+1）=（1-ρθ）?τij（θ）+ρθ?qf（sbestθ+1）] （12）

很容易用數(shù)學(xué)歸納法證明[τij（θ）≤qf（s*）]，因此：

[aln（θ+1）≤τij（θ）≤qf（s*）] （13）

下面證明不能找到最優(yōu)解的概率上限為0。記事件[Fθ]為第[θ]次迭代找到了最優(yōu)解，則[θ=1∞?Fθ]就表示算法從來(lái)沒(méi)有找到最優(yōu)解，這意味著從來(lái)沒(méi)有找到過(guò)任何一個(gè)最優(yōu)解[s*。]因此p（[s*] is never traversed）是[p（θ=1∞?Fθ）]的一個(gè)上界。由式（13）可知螞蟻選擇任意一可選擇節(jié)點(diǎn)的概率為：

[pmin（θ）≥pmin（θ）=ταmin（θ）τβminNc-1?ταmax（θ）?ηβmax+ταmin（θ）τβmin≥ταmin（θ）?ηβminNc?ταmax（θ）?ηβmax]

其中，[τmin≥aln（θ+1），][τmax≤qf（s*），]記[p′min（θ）=][ταmin（θ）τβminNc?ταmax（θ）?ηβmax，]則[pmin（θ）≥p′min（θ）]。因此螞蟻構(gòu)建一個(gè)可行解的概率[p（θ）≥p′min（θ）n，]因此：

[ps* is never traversed≤θ=1∞1-p′min（θ） =θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn] （14）

只要證明無(wú)窮乘積[θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=0]即可，為此只要證明級(jí)數(shù)[θ=1∞ln1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=-∞]即可。

[θ=1∞ln1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=θ=1∞ln1-aln（θ+1）α?ηβminNc?ταmax（θ）?ηβmaxn] （15）

記[c=aαηβminNc?ταmax（θ）?ηβmax]，則：

[θ=1∞ln1-aln（θ+1）α?ηβminNc?ταmax（θ）?ηβmaxn=θ=1∞ln1-cln（θ+1）αn] （16）

因?yàn)閷?duì)于任意的[x<1，][ln（1-x）≤-x]，所以：

[θ=1∞ln1-cln（θ+1）αn≤-cnθ=1∞1ln（θ+1）nα] （17）

而正項(xiàng)級(jí)數(shù)[θ=1∞1ln（θ+1）nα]發(fā)散，所以：

[ln1-cln（θ+1）αn==∞] （18）

[θ=1∞1-ταmin（θ）?ηβminNc?ταmax（θ）?ηβmaxn=0] （19）

所以，[pθ=1∞?Fθ=0，]即能夠找到最優(yōu)解的概率極限為1，因此，該算法是值收斂的。

下面證明算法是解收斂的，即任何一只螞蟻找到最優(yōu)解的概率極限都為1。

命題4：假設(shè)某只螞蟻在第[θ*]次迭代中第一次找到最優(yōu)解[s*]，則對(duì)任意的[τij（θ），（i，j）?s*，][limθ→∞τij（θ）=0]。

證明：假設(shè)某只螞蟻在第[θ*]次迭代后找到了最優(yōu)解[s*]，則對(duì)于任意的邊[（i，j）?s*，]它上面的信息素只揮發(fā)不增加，所以再經(jīng)過(guò)[k]次迭代后，這些邊上的信息素[τij（θ*+k）=i=θ*+1θ*+k（1-ρi）?τij（θ*）]，因此只需要證明當(dāng)[k→∞]時(shí)，[τij（θ*+k）→∞]。考慮級(jí)數(shù)[i=θ*+1∞ln（1-ρi）+lnτij（θ*）]，由于對(duì)任意的[x<1，][ln（1-x）≤-x，]所以[i=θ*+1∞ln（1-ρi）+lnτij（θ*）≤-i=θ*+1∞ρi+lnτij（θ*），]而已知[θ=1∞ρθ=∞，]所以[i=θ*+1∞ln（1-ρi）+lnτij（θ*）=-∞，][limk→∞τij（θ*+k）=0，]即[limθ→∞τij（θ）=0]。

命題5：假設(shè)某只螞蟻在第[θ*]次迭代中第一次找到最優(yōu)解[s*，]則對(duì)于任意的[τij（θ），（i，j）?s*，θ≥θ*，][τij（θ）]的極限存在。

證明：對(duì)于[（i，j）?s*，]信息素的更新方式為：

[τij（θ+1）=（1-ρθ+1）?τij（θ）+ρθ+1?qf（s*）] （20）

[τij（θ+1）-τij（θ）=ρθ+1?qf（s*）-τij（θ）>0] （21）

前面已經(jīng)證明了[τij（θ）≤qf（s*）]，因此由式（21）可知[τij（θ）]是遞增的，而且有上界，因此[τij（θ）]的極限存在，記為[τij]。

定理4：設(shè)[θ*]為得到最優(yōu)解的迭代次數(shù)，令[p（s*，θ，k）]為任意一只螞蟻k在第[θ]次迭代中得到最優(yōu)解的概率，其中[θ>θ*]。那么有：[limθ→∞p（s*，θ，k）=1]。

證明：假設(shè)螞蟻[k]位于節(jié)點(diǎn)[i]上，并且邊[（i，j）]是[s*]中的邊。那么螞蟻[k]選擇[（i，j）]的概率為：[p*ij（θ）=τ*ij（θ）α?ηijβτ*ij（θ）α?ηijβ+（i，h）?s*τ*ih（θ）α?ηihβ] （22）

[p*ij=limθ→∞p*ij（θ）=limθ→∞τ*ijθα?ηijβlimθ→∞τ*ijθα?ηijβ+limθ→∞（i，h）?s*τ*ih（θ）α?ηihβ=ταij?ηβijταij?ηβij+0=1]

所以，任意給定一只螞蟻，它找出最優(yōu)解的概率極限都為1，因此該算法是解收斂的。由上面的證明過(guò)程可以看出，能夠保證信息素的值足夠緩慢地減少到0是證明的關(guān)鍵。隨著計(jì)算機(jī)計(jì)算能力的提高，在用蟻群優(yōu)化算法解決實(shí)際問(wèn)題時(shí)，為了避免解陷入局部最優(yōu)，可以根據(jù)上面的思路去設(shè)計(jì)一些具有解收斂性質(zhì)的算法。

3 結(jié) 論

目前ACO算法有很多的應(yīng)用，當(dāng)ACO算法的性能不斷提高，同時(shí)從理論上對(duì)其工作原理的理解不斷加深時(shí)，依然有許多領(lǐng)域處于研究的初始階段，有待于人們?nèi)ヅμ剿?。本文主要證明最大最小螞蟻系統(tǒng)算法（MMAS）和蟻群系統(tǒng)（ACS）算法是值收斂的，并且證明一種特殊的蟻群優(yōu)化算法[ACOgs，ρ（θ）]是解收斂的。

隨著互聯(lián)網(wǎng)技術(shù)和社會(huì)經(jīng)濟(jì)的快速發(fā)展，越來(lái)越多的問(wèn)題都可以歸結(jié)為復(fù)雜網(wǎng)絡(luò)的組合優(yōu)化問(wèn)題，傳統(tǒng)優(yōu)化算法的局限性越來(lái)越明顯，蟻群優(yōu)化算法等智能算法在求解這些組合優(yōu)化問(wèn)題的優(yōu)勢(shì)將會(huì)越來(lái)越明顯，這必將會(huì)帶來(lái)可觀的經(jīng)濟(jì)效益。目前蟻群優(yōu)化算法的應(yīng)用領(lǐng)域主要是靜態(tài)的、離散的優(yōu)化問(wèn)題，將蟻群優(yōu)化算法應(yīng)用到動(dòng)態(tài)問(wèn)題、隨機(jī)問(wèn)題和多目標(biāo)問(wèn)題上去將會(huì)是未來(lái)的發(fā)展趨勢(shì)，同時(shí)蟻群優(yōu)化算法理論性的工作也會(huì)是一個(gè)重點(diǎn)。

參考文獻(xiàn)

[1] 夏小云，周育人.蟻群優(yōu)化算法的理論研究進(jìn)展[J].智能系統(tǒng)學(xué)報(bào)，2016，11（1）：27?36.

[2] 劉景巍，張迪，唐向輝，等.結(jié)合局部?jī)?yōu)化的蟻群優(yōu)化算法的研究與實(shí)現(xiàn)[J].價(jià)值工程，2014（29）：227?229.

[3] COLORNI A， DORIGO M， MAFFIOLI F， et al. Heuristics from nature for hard combinatorial optimization problems [J]. International transactions in operational research， 1996， 3（1）： 1?21.

[4] 王芳.基于蟻群算法的TSP問(wèn)題研究與實(shí)現(xiàn)[J].科學(xué)中國(guó)人，2014（4）：1?2.

[5] 王勝訓(xùn)，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學(xué)學(xué)報(bào)，2013（6）：840?844.

[6] GUTJAHR W J. A graph?based ant system and its convergence [J]. Future generation computer systems， 2000， 16（8）： 873?888.

[7] ST?TZLE T， DORIGO M. A short convergence proof for a class of ant colony optimization algorithms [J]. IEEE transactions on evolutionary computation， 2002， 6（4）： 358?365.

[8] 鄭恩興，劉冉冉.蟻群算法收斂性驗(yàn)證系統(tǒng)的研究與實(shí)現(xiàn)[J].電子科技，2013，26（1）：138?141.

[9] 吳華鋒，陳信強(qiáng)，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP問(wèn)題[J].通信學(xué)報(bào)，2013（4）：165?170.

[10] 申鉉京，劉陽(yáng)陽(yáng)，黃永平，等.求解TSP問(wèn)題的快速蟻群算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2013，43（1）：147?151.