【導(dǎo)讀】的變量組合問題，是運(yùn)籌學(xué)中的一個(gè)經(jīng)典且重要的分支，其經(jīng)典難題為旅行商問題。進(jìn)行改進(jìn)，提高解的質(zhì)量并加速蟻群算法收斂速度。

　　

【正文】 蟻群算法改進(jìn)算法 螞蟻系統(tǒng)在解決一些小規(guī)模的 TSP 問題時(shí)的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴(kuò)大，螞蟻系統(tǒng)很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解來。針對(duì)螞蟻系統(tǒng)的這些不足，研究者進(jìn)行了大量的改進(jìn)工作，使得蟻群優(yōu)化算法在很多重要的問題上躋身于最好的算法行列（李士勇， 2021） [10]。對(duì)蟻群算法進(jìn)行改進(jìn)和發(fā)展已經(jīng)成了近年來該領(lǐng)域研究的趨勢(shì)，以下 是 一些較為成功的改進(jìn)算法。 精英螞蟻系統(tǒng)（ EAS）是對(duì)基本螞蟻系統(tǒng)算法的一次改進(jìn)，它的主要思想是對(duì)從搜索開始起找到的最優(yōu)路進(jìn)行強(qiáng)化，增加它被再次選擇的概率，提高解的收斂速度。記這條目前為止的最優(yōu)路徑為 ??????（ bestsofar tour），則精英螞蟻系統(tǒng)信息素的更新方式為： ??????(??+ 1) = ??????(??) +∑????????? + ?????????????????=1 () 其中，參數(shù) ??表示的是路徑 ??????的權(quán)值大 小， ???????????為經(jīng)營策略相應(yīng)的信息素，它可以表示為： ??????????? = {1/??????， (??， ??)∈ ??????0， (??， ??)? ?????? () 其中， ??????表示 ??????的長度?？梢钥闯?， ??????和 ??影響經(jīng)營策略的兩個(gè)要素， ??????是問題的最優(yōu)解，由問題和算法決定，而 ??是決定經(jīng)營策略程度大小的參數(shù)，可以人為控制。 Dorigo（ 1992）和 Dorigo 等（ 1991a， 1996）的文章中的計(jì)算結(jié)果表明，使用精英策略并選取一個(gè)合適的 ??值不但能使 AS 算法獲得更好的解，而且能在更少的迭代次數(shù)下得到更好的解。此外，在使用精英螞蟻系統(tǒng)時(shí)，需要選取適當(dāng)?shù)奈浵仈?shù)量。 2. 優(yōu)化排列螞蟻系統(tǒng) Bullnheimer 等（ 1999） [23]提出的優(yōu)化排列螞蟻系統(tǒng)（ ASrank）的基本思想是：對(duì)所有螞蟻按其生成路徑的長度排序，路徑越短，排名越靠前，如果路徑長度相同，則對(duì)這部分隨機(jī)排序。螞蟻對(duì)信息素信息的更新的貢獻(xiàn)根據(jù)螞蟻的排名進(jìn)行加權(quán)，對(duì)前一定數(shù)量的螞蟻經(jīng)過的邊給予一定的額外信息素，其量正比 于該螞蟻的排名。只有排名在最前的 ( ?1)只螞蟻和生成了最優(yōu)路徑的螞蟻才有資格釋放信息素。生成最優(yōu)路的螞蟻釋放最多的信息素，其權(quán)值為 ，而在排名前 ( ?1)中排名第 的螞蟻將根據(jù) 1/?? 乘以 ( ? )來更新它的信息素。這是一種精英和排序的混合策略，它的信息素更新機(jī)制可以表示為： ??????(??+??) = ?????? + ∑( ? )??????? + ??????????? 1 =1 () 其中， ??????? = 1/?? ， ??????????? = 1/??????， 而 ?? 和 ??????分別為第 只螞蟻搜索的完整路徑和目前為止最優(yōu)的一條完整路徑。 Bullnheimer 等（ 1999） [23]的實(shí)驗(yàn)結(jié)果表明， ASrank 的性能略優(yōu)于 EAS，而明顯優(yōu)于 AS。 3. 最大最小螞蟻系統(tǒng) 將螞蟻的搜索行為集中到最優(yōu)解附近可以提高解的質(zhì)量和收斂速度，但這樣的搜索方式容易導(dǎo)致早熟收斂現(xiàn)象。 Stutzle 等人（ 1997） [6]提出最大最小螞蟻系統(tǒng)（ MMAS）以防止早熟收斂現(xiàn)象的發(fā)生。 在現(xiàn)存的改進(jìn)蟻群算法中，最大 最小螞蟻系統(tǒng)（ maxmin ant system，MMAS）算法被證明是目前為止求解 TSP 類問題最好的蟻群算法模型 [24]。 與普通螞蟻系統(tǒng)相比，最大最小螞蟻系統(tǒng)的特點(diǎn)有： （ 1）在螞蟻系統(tǒng)中，所有螞蟻?zhàn)哌^的路徑都進(jìn)行信息素更新；而在 MMAS 中，只對(duì)找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻或者找出全局最優(yōu)解的螞蟻?zhàn)哌^的路徑進(jìn)行更新。它的信息素更新機(jī)制與 AS 算法形式上相似，不過具體內(nèi)容有很大差別： ??????(??+??) = ??????(??)+??????????? () 其中， ??????????? = 1/??????或 1/??????， ??????為算法目前為止最優(yōu)路徑長度， ??????為當(dāng)前迭代的最優(yōu)路徑長度。這兩種規(guī)則的選擇可以影響算法的導(dǎo)向性，選擇 ??????規(guī)則會(huì)能使算法快速收斂，較適用于大規(guī)模問題；選擇 ??????規(guī)則會(huì)使算法更傾向于進(jìn)行路徑探索，較適用于小規(guī)模問題。當(dāng)然，這兩種規(guī)則也可以交替使用。 Stutzle（ 1999） [25]提出一種優(yōu)化機(jī)制，逐年增加 使用 ??????規(guī)則的頻率。 （ 2）螞蟻系統(tǒng)中，所有路徑上的信息素信息不被限制，從而使一些路徑上的量遠(yuǎn)大于其他路徑，阻礙了進(jìn)一步搜索更優(yōu)解的行為；而在 MMAS 中，每條邊的信息素信息量都被限制在 ,????????， ???? 范 圍內(nèi)，從而防止不同路徑間信息素量差距過大。 （ 3）相比螞蟻系統(tǒng)，最大最小螞蟻系統(tǒng)的路徑選擇概率也有了一定的變化，被限制在 ,????????， ???? 之內(nèi)，其中 0 ???????? ?????? ???? 1。只有當(dāng)螞蟻只剩下一個(gè)城市可以選擇時(shí)，才會(huì)有 ?????? =???? = 1。限定概率的目的同樣是避免路徑間被選擇的概率太過懸殊，從而防止過早收斂。 （ 4）為使螞蟻在算法的初始階段能夠更多的搜索新的解決方案，將信息素信息初始化為 ???? = 1/????????。這種將信息素初始化為上限值的方式，聯(lián)同一個(gè)較小的信息素蒸發(fā)率，可以有效地減緩不同路徑之間信息素差距的擴(kuò)大，強(qiáng)化路徑探索。此外，當(dāng)算法接近停滯狀態(tài)或在一定數(shù)量的迭代中未能改進(jìn)解的質(zhì)量時(shí)，會(huì)達(dá)到信息素重初始化的條件而觸發(fā)信息素的重初始化。這樣做也是為了增強(qiáng)路徑探索。 4. 最優(yōu)最差螞蟻系統(tǒng) 除了國外的學(xué)者對(duì)蟻群算法的改進(jìn)進(jìn)行了廣泛的研究，國內(nèi)學(xué)者同樣對(duì)此進(jìn)行了大量的工作。研究表明，不論是真實(shí)蟻群還是人工蟻群，通常情況下，信息量最強(qiáng)的路徑與所需要 的最優(yōu)路徑比較接近。然而，當(dāng)某一次循環(huán)利用的信息較平均地分布在各個(gè)方向上，這次循環(huán)所釋放的信息素就可能對(duì)以后蟻群的決策產(chǎn)生誤導(dǎo)。 針對(duì)這種情況，李士勇 [10]等人（ 2021）提出了最優(yōu)最差螞蟻系統(tǒng)（ BWAS）。該改進(jìn)算法在蟻群算法的基礎(chǔ)上進(jìn)一步增強(qiáng)了搜索過程的指導(dǎo)性，使得螞蟻的搜索更集中于到當(dāng)前循環(huán)為止所找出的最好路徑的領(lǐng)域內(nèi)。該算法的思想就是對(duì)最 優(yōu)解進(jìn)行更大限度的增強(qiáng)，而對(duì)最差解進(jìn)行削弱，使得屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息素量差異進(jìn)一步增大，從而使螞蟻的搜索行為更集中于最優(yōu)解的附近。它的主要改進(jìn)在于信息素?fù)]發(fā)的機(jī)制，如下所示： ?? ??(??+??) = (1???)?? ??(??)? ???? ???? () 其中， ?? ??表示當(dāng)前迭代中最差路徑的一條邊 ( ， )上的信息素， ???? 和 ??????分別表示當(dāng)前循環(huán)中最差的路徑解和最好的路徑解， 為 控制該規(guī)則的參數(shù)?？梢钥闯?，最差解與最好解的差距越大，它包含的路徑受到的信息素削弱就越大，從而起到排斥最差解的目的。 5. 蟻群系統(tǒng) 之前的集中改進(jìn) ACO 算法都是基于 AS 算法的基本框架，主要針對(duì)信息素更新及揮發(fā)機(jī)制進(jìn)行了不同程度的修改。事實(shí)證實(shí)，這些改進(jìn)大大提高了蟻群算法的性能。與這些方法不同的是，蟻群算法的創(chuàng)始人 Dorigo 開發(fā)了一種不同于 AS 算法基本框架的蟻群算法，稱為蟻群系統(tǒng)（ ACS） [9]。 ACS 算法和 AS 算法的不同主要體現(xiàn)在 3 個(gè)方面： （ 1）采用了不同的路徑選擇規(guī)則，從而可以更好地利用螞蟻累積 的搜索經(jīng)驗(yàn)。以 TSP問題為例，在 ACS 中，位于城市 ??的螞蟻 ??根據(jù)偽隨機(jī)比例規(guī)則選擇城市 ??作為下一個(gè)訪問的城市。這個(gè)規(guī)則可以表示為： ?? = { ???? {?????, ?????}， ， () 其中， 是在區(qū)間 [0， 1]上均勻分布的一個(gè)隨機(jī)變量， (0 1)是一個(gè)參數(shù)， 為一個(gè)隨機(jī)變量?？梢钥闯?， 的作用是控制偽隨機(jī)選擇和概率搜索之間的比重，調(diào)節(jié)算法對(duì)新路徑的探索度，從而決定算法是集中于已得到的最優(yōu)路徑附近，還是探索新的區(qū)域。 （ 2） ACS 的信息素更新機(jī)制與 AS 不同， ACS 只允許找到目前為止最優(yōu)路徑的螞蟻釋放信息素，同時(shí)，也只有這條最優(yōu)路徑會(huì)有信息素?fù)]發(fā)現(xiàn)象?？偟男畔⑺馗乱?guī)則可以表示為： ??????(??+??) = (1???)??????(??)+?????????????， ?(??， ??) ∈?????? () 其中， ??表示信息素的揮發(fā)率。實(shí)驗(yàn)證明，在大規(guī)模 TSP 問題中，這種信息素更新規(guī)則的表現(xiàn)遠(yuǎn)優(yōu)于 AS 算法的更新規(guī)則。 （ 3）與前面提到的 ACO 算法不同， ACS 算法同時(shí)采取了信息素的全局更新和局部更新。在螞蟻構(gòu)建路徑的過程中，它每經(jīng)過一條邊 (??， ??)，就立刻根據(jù)信息素局部更新規(guī)則對(duì)這條邊上的信息素進(jìn)行更新。這種規(guī)則表示為： ??????(??+1) =(1? )??????(??)+ ?? () 其中， 和 ?? 是兩個(gè)參數(shù)， 0 1， ?? 是信息素量的初始值。局部更新的作用在于，螞蟻每經(jīng) 過一條邊，該邊的信息素就會(huì)發(fā)生揮發(fā)現(xiàn)象，從而使這條邊被再次選中的機(jī)會(huì)相對(duì)減少（要增加被選中的概率的方法是稱為最優(yōu)路徑，獲得釋放的信息素）。這種規(guī)則可以強(qiáng)化螞蟻的路徑探索行為，增加其他路徑被搜索的概率，從而避免算法過早收斂而陷入停滯狀態(tài)。此外， Dorigo 和 Gambardella（ 1997）指出，在 ACS 算法中，并行構(gòu)建和順序構(gòu)建的解構(gòu)建方法不再等價(jià)，他們使用的一直都是并行構(gòu)建方法，盡管還沒有證據(jù)證明究竟哪一種構(gòu)建方式更好。 （五） 雙（多）蟻群算法 前文已介紹了多種改進(jìn)的蟻群算法，均是基于單種群的蟻群算法優(yōu)化，而對(duì) 蟻群算法的優(yōu)化可從另一角度進(jìn)行 ——雙（多）種群蟻群算法。 （多）蟻群算法介紹 雙蟻群系統(tǒng)由 KAWAMURA 于 2021 年提出，通過蟻群間的互動(dòng)分享信息素，在充分利用局部最優(yōu)解的同時(shí)擴(kuò)大搜索空間，經(jīng)證明雙蟻群系統(tǒng)比單蟻群系統(tǒng)效果更佳 [8]。國內(nèi)，2021 年郟宣耀和滕少華也曾提出一種雙種群改進(jìn)蟻群算法，將兩個(gè)螞蟻群體分別獨(dú)立金華，并定期交換信息素，這一方法緩解了因信息素濃度失衡而造成的局部收斂，有效改進(jìn)算法的搜索性能，實(shí)驗(yàn)結(jié)果表明該算法有效可行 [15]。 雙（多）種群蟻群算法主要在基礎(chǔ)蟻群算法的基礎(chǔ) 上增加一個(gè)或多個(gè)螞蟻種群，以基本蟻群算法為標(biāo)準(zhǔn)構(gòu)建多個(gè)螞蟻種群，通過多個(gè)螞蟻種群分別進(jìn)行路徑搜索，從而使得搜索的不確定性增加，螞蟻的路徑探索效應(yīng)增加，最終達(dá)到提高最優(yōu)解的概率。同時(shí)，多種群蟻群算法增加了各蟻群間的 “互動(dòng) ”以加快其收斂速度，主要表現(xiàn)為信息素的交互媒介效應(yīng) ——正效應(yīng)與負(fù)效應(yīng)：信息素的正效應(yīng)使螞蟻傾向于將本種群搜索所得較優(yōu)解分享給其他種群，以便其他種群進(jìn)行信息素更新；信息素的負(fù)效應(yīng)使螞蟻傾向于不受其他種群解的影響，也不與 其他種群分享本種群搜索獲得的解空間。 2. 多種群蟻群算法 —— 以旅行商問題（ TSP） 為例 根據(jù)上節(jié)介紹，多種群蟻群算法具有信息素的交互媒介效應(yīng)，故算法需要設(shè)置專門參數(shù)以控制信息素的正效應(yīng)及負(fù)效應(yīng)的強(qiáng)弱。本節(jié)以旅行商問題 （ TSP） 為例介紹多種群蟻群算法，對(duì)以下符號(hào)進(jìn)行定義： 表 TSP 問題多種群蟻群算法符號(hào)定義 符號(hào) 說明 ?? 每個(gè)匯總?cè)褐形浵伒膫€(gè)數(shù) ?? 螞蟻種群的個(gè)數(shù) ????(??) ??時(shí)刻位于城市 ??的螞蟻的個(gè)數(shù) ?????? 城市 ??與城市 ??之間的距離 ????? 路徑 (??， ??)的能見度，即為啟發(fā)信息 ?????? 路徑 (??， ??)上的信息素強(qiáng)度，即信息素信息 ??????? 螞蟻 ??在路徑 (??， ??)上釋放的信息素量 ???????? 螞蟻 ??從城市 ??移動(dòng)到城市 ??的概率 （ 1） 信息素更新機(jī)制 多種群蟻群系統(tǒng)基于單種群蟻群系統(tǒng)，需對(duì)多個(gè)種群分別進(jìn)行信息素更新，其更新機(jī)制可表現(xiàn)為： ???????? (??+n) =???????? (??) +∑???????????(??， ??+??) ????=1 () 其中， ???????????(??， ??+??)表示第 ??個(gè)種群的第 ??只螞蟻在完成從 ??到 ??的路徑后在路徑 (??， ??)上釋放的信息素，它的大小根據(jù)完整路徑的質(zhì)量而定，路徑越短，釋放的信息素越多，表示為： ???????????(??， ??+??) = {??/?????? ， 如果 (??， ??)在路徑 ??????上0，否則 () 其中， ??為一正常數(shù)， ??????