蟻群算法研究的新進展和展望
2007-01-01 00:00:00牛新征佘堃路綱周明天
計算機應用研究 2007年4期
摘要：在介紹蟻群算法的原理和特點后，著重分析了當前一些有代表性的蟻群算法的改進機制和應用成果，并采用比較的方式指出了這些方法的特點和主要應用范圍等，最后總結了好的蟻群算法應具有的特點以及將來的研究策略與發展趨勢。
關鍵詞：蟻群算法； 組合優化
中圖分類號：TP3016文獻標志碼：A
文章編號：10013695(2007)04001204
1蟻群算法
1.1蟻群算法的原理
蟻群算法是通過螞蟻個體在候選解的空間中獨立地搜索解，并在搜尋的解上留下一定的信息素；螞蟻間以信息素為介質進行間接、異步的信息傳遞。隨著算法的推進，較優解（較優的路徑）的信息素濃度會越來越濃，同時其他路徑上信息素濃度卻會隨著時間的消逝而削減變弱。當算法漸漸趨于收斂時，在最優解（最優路徑）上的信息素濃度應該是最大的。整個蟻群算法的最優解即最優路徑將在螞蟻個體的共同協作下求出。意大利學者Dorigo M.等人[1～3]通過模擬螞蟻尋路的群體行為最先提出了蟻群算法，并用于求解復雜的組合優化等問題，獲得了較好的效果。
1.2蟻群算法挑戰
（1）在蟻群算法中，所固有的加速收斂與防止早熟、停滯是一對矛盾。因此有研究者為了加速蟻群算法收斂的過程，提出充分利用學習機制強化最優信息的反饋；但由于強化了最優信息反饋，帶來了早熟、停滯的發生。別的研究者又考慮讓各個路徑上信息素的變化固定在一個范圍內，這樣可以有效防止早熟、停滯現象的出現；但是卻由于解的分布較分散，使蟻群算法收斂的過程變慢。
（2）算法初期的各個路徑上具有相同初始信息素的問題。面對初始路徑上相同濃度的信息素，路徑選擇一般采用貪心算法，而這次路徑選擇可能是不準確或錯誤的，因此會誤導別的螞蟻，使該路徑上的信息素得到不應該的增加。最后，收斂的結果是信息素濃度最強的路徑不是正確的最優路徑。
（3）由于利用了正反饋原理，在蟻群算法進行過程中，任何一次路徑選擇和信息素更新發生的錯誤都會誤導整個算法最優路徑的選擇，最終得到的最優解是錯誤的。
2蟻群算法的研究成果
研究者對蟻群算法進行了多方面優化。Dorigo M.等人提出稱為AntQ System的蟻群算法[4]。Stutzle T.等人為了防止在AntQ System中的早熟和停滯現象，提出了MaxMin蟻群算法[5]。Gambardella等人[6]提出了蟻群系統(Ant Colony System)；同時，他們還提出了一種混合型蟻群算法HAS[7]，目標是加大螞蟻個體自主選擇的自適應能力，提高解的多樣性。Botee H.M.等人結合遺傳算法求得參數m、α、β、ρ的最佳組合[8]。吳斌等人提出了基于蟻群算法的分段求解算法[9]。Zhang等人[10]提出了采用確定性選擇和隨機選擇相結合的策略及自適應調整選擇概率的辦法、優化算法的收斂速度和性能。同時，研究者也使用了蟻群算法來解決實際問題，并取得了較好的效果。Bilchev G.等人在解決工程設計中連續空間的優化問題時，用蟻群算法精確化其利用遺傳算法求解時所得到的初步結果[11]。Gutjahr W.J.等人提出一種以圖為基礎的蟻群系統框架，以此解決組合優化問題[12]。
3蟻群算法的改進機制分析
3.1自適應調整信息素的蟻群算法
針對蟻群算法加速收斂與早熟停滯現象的矛盾，文獻[13]提出一種基于分布均勻度的自適應蟻群算法，算法自適應地調整路徑選擇概率的確定策略和信息素更新策略。該算法引入了聚度的概念來衡量解的均勻程度，并且還引入了信息權重來限制信息素和期望程度對螞蟻選擇概率的影響程度。
以求解TSP為例：設從城市i共有r條路徑到達另外r個城市i1，i2，…，ir。首先通過聚度的公式求得城市i的聚度為sta(i)，并根據城市i的聚度sta(i)確定螞蟻在該城市時，下一步可供選擇的路徑條數為w；然后將以城市i為起點的r條路徑按其信息素由高到低地排序，序號依次存于數組rank中，并可以引用上面求出的w和數組rank，根據公式求得路徑(i， j)的信息權重ξij。螞蟻由城市i按下式的概率選擇城市j：
3.2基于信息素擴散的協作式蟻群算法
黃國銳等人[14]提出了通過建立信息素擴散模型，加大近距離的螞蟻個體間的協作。在該算法中，螞蟻個體可以改變多條路徑上的信息素濃度以提高螞蟻群體之間的合作效果。以求解TSP為例：①提出信息素擴散模型如圖1所示。其中，O點的信息素濃度為Dmax，r表示擴散范圍的半徑等。圖中的每一個點都可以通過作者提供的公式求得信息素濃度。②假設螞蟻k從城市i移動到城市j，則該螞蟻會分別在城市i和城市j向外擴散信息素。對于其他任何一個城市l，如果它在所產生的信息素擴散范圍內，則由螞蟻k所產生的擴散到城市l的信息素濃度為Dkil和Dkjl，這兩個濃度值都可以通過公式求得。③對相關路徑上的信息素濃度進行更新。
3.3具有感覺和知覺的蟻群算法
文獻[15]受感覺閾限原理的啟發，提出了一種模仿螞蟻感覺和知覺行為的新蟻群算法。該算法使螞蟻在選擇路徑時，受到顯意識和潛意識的相互作用，對于路徑的選擇更加理性，同時也支持自適應地修改路徑上的信息素。
作者提出當路徑上的信息素濃度未達到螞蟻個體自身的絕對感覺閾限時，螞蟻個體可以忽視該信息素的影響。這樣也在一定程度上優化了初始解的選擇，盡量讓螞蟻在初始階段選擇較多的不同路徑，以獲得最終的多樣化解。文中記螞蟻的絕對感覺閾限為AST。
同時，利用上述思路作者還把蟻群算法中信息素刺激強度定義在一個差別感覺閾限CST的范圍內，只有在信息素改變的數量在CST之上時才能感覺到該路徑上信息素的變化。這種辦法改變了路徑上的信息素變化，直接影響螞蟻選路的做法。除此以外，路徑選擇的概率方式也發生改變，當信息素改變的數量在CST之下時，將依據以前迭代中螞蟻選路經驗形成的潛意識作用。當大于CST的刺激強度時，螞蟻受顯意識作用，按照路徑上的信息素高低來選擇路徑。根據韋伯定律，在具體實現此過程時，CST表示為
CST=τij(t)×k
其中，k為螞蟻對信息素感覺的韋伯系數。
3.4具有隨機擾動特征的蟻群算法
文獻[16]提出在螞蟻尋路的過程中，結合采用已有信息與搜索新的路徑，以及為了防止出現解的局部極小，應該使解產生某種方式的隨機擾動的方法。作者通過兩個方向來開展他們的工作：
(1)引入遺傳算法，將蟻群算法和遺傳算法結合起來，如圖2所示。例如原始解{C0，…，Ci-1，Ci，…，Cj，Cj+1，…}變異成{C0，…，Ci-1，Cj，…，Ci，Cj+1，…}，Ci和Cj解的變異。
(2)改變全局信息素更新的原則。讓最優的m只螞蟻同時更新所經路徑上的信息素濃度，改變以前只是讓這次循環中最優的一只螞蟻進行更新的辦法。
3.5具有多種蟻群和信息素的多態蟻群算法
文獻[17]模仿了真實的蟻群世界，提出一種新的含有多種蟻群、多種信息激素的多態蟻群算法。
蟻群分為三類，即偵察蟻、搜索蟻和工蟻，每種類型的蟻群具有不同的信息素更新策略和尋路策略；同時還把搜索分為局域搜索與全局搜索。偵察蟻群的任務是以每個城市為中心作局部搜索，并且為到達該城市的搜索蟻群提供尋路的輔助信息。偵察蟻群使用偵察素來表示偵察結果。搜索蟻群的任務是作全局搜索，通過偵察蟻群的偵察素和每個城市所固有的信息素來選路，并且在找到最優解后進行標記。工蟻蟻群的任務是從搜索蟻群尋找出的最優路徑中取食物回巢。由上述可見，蟻群間的協作更加緊密，分工也更加清晰，減少了螞蟻個體的搜索范圍，還可直接使用別的蟻群提供的信息。
3.6具有變異特征的蟻群算法
文獻[18]引入變異機制，采用逆轉變異的方式，它是一種具有變異特征的蟻群算法。算法描述如下：
設某個螞蟻個體所走路徑為i0i1i2…i(n-1)(i0，i1，…，in-1∈{0，1，2，…，n-1})。如果滿足相關變異條件，就可以進行如下變異：通過運行函數inversion(s1，s2，solutioni)把個體solutioni的s1+1和s2部分顛倒過來。s1，s2∈{0，1，…，n-1}，如inversion(3，5，0123456)=0123546。
算法中變異的次數是隨機的。通過這種方法的變異，使得解的性能有所改善，并且變異過程中的運算比蟻群算法的循環尋優過程要簡單，無需額外的運算時間。
3.7其他優化的蟻群算法
文獻[19]提出一種基于云模型理論的蟻群算法。云模型是一種新的實現定性概念與定量數值之間轉換的有力工具。通過使用云模型可以有效防止陷入局部最優解，改進后的蟻群算法采用升半正態云規則進行控制。
文獻[20]提出將尋路模型分成四個部分，即螞蟻、規則集、環境和狀態空間。其中，螞蟻個體不直接與別的螞蟻通信，而是在移動過程中通過環境間接通信，并決定下一步需要到達什么樣的狀態規則集合。同時，根據不同的條件螞蟻可以選擇四種具有不同尋路方法的螞蟻行為。環境中存儲了蟻群過去尋路過程中的各種信息支撐螞蟻行為。
文獻[21]提出了通過適應度進行優化的蟻群算法。通過公式可以求出m只螞蟻尋找m條路徑的適應度函數值，然后對適應度進行排序，找到最小適應度的兩個螞蟻個體，即擁有最優兩條路徑的螞蟻。通過選擇一定的雜交點，并對這兩條路徑進行雜交，直到找到最優路徑為止。
4蟻群算法的應用分析
蟻群算法的應用領域很多，如應用于TSP、Jobshop調度問題、大規模集成電路綜合布線問題、電信網絡路由問題等。
4.1多點并行蟻群解決多限制動態組播問題
在文獻[22]中提出了一種具有QoS約束的分布式多限制動態組播路由（DMDMA）算法。該算法的思路分為兩個部分：①申請組播節點進行局部搜索，使用鄰域搜索策略進行路由信息搜索。它通過有限制的洪泛進行搜索，最外圍的節點根據自己是否是組播樹的節點，向發起洪泛報文請求的節點發送不同的確認報文；該返回報文在返回的過程中，會記錄沿途經過的節點時延、帶寬、丟失率等信息。如果該返回報文滿足發起者的需求，則路由算法結束；否則，進入部分②。②由蟻群算法組成，其中向組播源節點發送運行螞蟻算法搜索的報文MulAntSearch。由于該算法具有QoS限制，螞蟻個體除了根據本身算法的要求必須按照信息素濃度的強弱來選擇路徑以外，還必須對每個節點QoS條件進行分析。對于不滿足條件的，采用停止螞蟻的工作和剪掉低帶寬的鏈路等方法；只有滿足條件的才會對該路徑發送MulAntState報文，在目的外圍節點建立狀態向量。
4.2基于蟻群算法的碼書設計
在文獻[23]中提出了一種基于人工蟻群優化的矢量量化碼書設計新算法。該算法結合了螞蟻個體通過拾起、放下物體從而使物體聚堆的行為模式。
基于人工蟻群優化的碼書設計最核心的思路如下：①隨機產生一組初始碼書Y0。②通過如下公式確定第t次迭代后，新一次迭代開始時的一組初始碼書：
tabu(t)={xi|arg min0≤j≤J-1 d[xi，yj(t-1)]，0≤i≤N-1}
其中，tabu(t)表示t時刻螞蟻的一個禁忌列表。
③根據選擇概率公式對所有螞蟻對于xi∈Ts(t)進行聚類，計算各自碼書及相應的平均失真，并記錄當前最小的平均失真D*及所對應
的碼書Y*。其中，Ts(t)=Ts-tabu(t)，xj∈tabu(t)，xi∈Ts(t)-
tabuk(t)。通過不斷進化就可以得到最優碼書Y*。
4.3基于模式求解的蟻群算法的旅行商問題
在文獻[24]中提到使用小窗口的蟻群算法以及結合了基于模式的思路。以求解TSP為例，該算法思想如下：為每個城市建一個數組cityWin[window]，其中window表示窗口的大小，表示與該城市距離最近的城市數目。對于螞蟻個體，通過cityWin[window]來限制螞蟻路徑選擇中可以選擇的城市數目，螞蟻個體每次作選擇時，必須從cityWin[window]和tabu[k]的交集中選擇移動的城市；如果交集為空，就只從tabu[k]選擇。其中，窗口大小依據TSP的維數決定，維數越大，窗口越大。
4.4基于蟻群算法的連續空間優化問題
在文獻[25]中提出了一種求解連續空間優化問題的蟻群算法，它包括兩個主要部分，即全局搜索和局部搜索。螞蟻個體先進行局部搜索，在自己的鄰域中隨機搜索，同時還使用了確定性搜索。當螞蟻個體完成自己的局部搜索后，將決定是停留在原地不動還是轉移到別的螞蟻個體的鄰域中搜索，或是進行進一步的全局隨機搜索。
其中在使用了確定性搜索的蟻群算法中，使用了直接法。也就是在每個坐標方向上進行探測性搜索，求得目標函數的變化規律以確定其搜索方向，進行模式移動。
4.5蟻群算法的其余應用
在文獻[26]中提出把解空間分成若干子域，并通過信息素可以求得其解的子域和該子域中解的確定值。這是一種求解連續空間優化問題的方法。
在文獻[27]中提供了一種有時延約束的多播路由算法模型。有三種辦法可以利用：在每次循環結束時，保留最優解；自適應調節信息素揮發系數；引入遺傳算法的交叉算子。
5蟻群算法的研究比較和改進思路
5.1蟻群算法的改進與應用比較
研究者針對蟻群算法的缺陷提出了許多改進算法，并且把改進的蟻群算法應用到不同的新領域。改進方法及其比較如表1～3所示。
5.2蟻群算法改進的思路和應用前景
由于基本蟻群算法利用隨機選擇策略，使得進化速度較慢；同時，蟻群算法旨在利用正反饋原理和分布式計算的模式，卻未能較好地加快進化過程及避免過早收斂，反而容易出現停滯現象。針對蟻群算法加速收斂與早熟、停滯現象等的矛盾和尋找最優解的時間過長等缺點，可以從以下方向改進蟻群算法。
（1）算法的自適應性。①從選擇概率來看，可以采用不同的階段使用不同的選擇概率，在尋路的過程中動態地調整選擇概率，并且可以使用選擇概率的不同方法。②信息素更新策略的自適應，應該能對信息素進行動態更新和自適應調節。③如果把尋路過程優化為幾個不同的階段，并且在不同階段采用不同的方法，則應該自適應地分析蟻群個體進行的程度已經到哪個階段了，選擇應該執行什么樣的策略等。④蟻群算法的公式中各個參數的自適應選擇。
（2）初始解的優化。由于各個路徑上的初始信息素是相同的，初始解即第一次選擇的路徑很可能對整個蟻群的進化過程產生誤導，必須提高初始解的質量，盡量擴大在初始階段可以選擇路徑的數目，以增加解的多樣性。
（3）信息素動態更新策略。信息素的濃度強弱直接關系到螞蟻個體的尋優過程。如何讓信息素動態、自適應地更新，如何通過信息素作用的擴散和信息素種類的增加等方法來達到螞蟻間的協作，以及如何調整信息素的更新公式，都是非常重要的。
（4）路徑選擇概率的適應性調整。①應該實現選擇概率的自適應；②按照不同的應用、不同的實際環境等合理設計和調整選擇概率公式等。
（5）門檻值的設計。正如在文獻[13]中的信息權重、在文獻[15]中的感覺閾限，對于設計這種門檻值，能夠定義信息素、選擇概率等發揮作用的區間或臨界點，把蟻群算法分為不同的階段、不同的策略來實施等，也輔助了自適應的實現。
（6）螞蟻的協作。已經有較多研究提到了螞蟻間的協作，并且有研究者提出要把螞蟻分成多類，不同的類別實現不同的策略、完成不同的工作，然后再通過螞蟻間的協作達到更優的策略。正如在真實的蟻群世界中，螞蟻也是被分了類的，不同類別的螞蟻完成不同的工作。螞蟻的協作在一定程度上優化了算法，但也增加了算法的復雜性。
以上是蟻群算法中最重要的改進和優化的主要方向，當然還有蟻群算法中參數的優化，如信息素揮發系數的優化等。
6結束語
對于蟻群算法的研究一直都未停止，研究者嘗試各種策略來解決蟻群算法問題以及探索其能夠適合的各種應用場合。通過闡述蟻群算法的最新進展和應用前景，可以展示蟻群算法的發展、需要解決的問題以及為使用蟻群算法提供思考。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
