啟發式強化學習機制的異構雙種群蟻群算法*

劉中強，游曉明，劉 升

1.上海工程技術大學 電子電氣工程學院，上海201620

2.上海工程技術大學 管理學院，上海201620

1 引言

蟻群算法最初是由意大利學者Dorigo 等學者在20 世紀90年代受螞蟻覓食機制的啟發而提出的一種新型的進化計算方法。最早被提出的算法有Ant system、Ant quality、Ant destiny[1-2]，用來解決經典的旅行商和分布式優化問題。隨著對算法的深入研究，各種對算法的改進的方法也相繼被提出，文獻[3]通過提出精英螞蟻策略來對算法的收斂速度和多樣性進行改進，而文獻[4]中局部信息素更新的提出以及文獻[5]中優化算法的提出則很大程度提升了算法的性能，但是為了更好地平衡算法中多樣性和收斂速度的關系，可以進行信息交換的多種群蟻群算法[6]被提出，通過讓兩個不同種群之間進行優勢互補的信息交流，進而提高算法的性能。多種群這一概念被提出以后，有人提出通過信息熵來決定種群之間的交流策略，讓子群體中解的多樣性和收斂性達到動態平衡[7]。張鵬等人則提出了蟻群相似度這一概念，即以最優解為參照，計算出子蟻群的解與其在每條路徑上重合度的大小，進而決定種群間的交流策略和交換概率，有效提高了跳出局部最優的能力[8]，Mavrovouniotis 等人則提出用于解決動態TSP 問題（dynamic travelling salesman problem，DTSP）的多種群蟻群算法[9]，每個種群（擁有各自的信息素表）并行運行并將最優解共享給所有種群，以提高解的質量和多樣性。何雪莉等人則提出了一種基于異類雙種群的蟻群算法，將兩種信息素更新機制不同的蟻群分別獨立進行進化求解，并定期交換優良解和信息來改善解的多樣性，增強了算法跳出局部最優的能力，使算法更容易收斂到最優解[10]。朱宏偉等人則針對兩個異構種群，引入協同過濾策略，通過對最優路徑上的螞蟻進行獎賞并自適應地調整兩個種群間的交流頻率，最后引入城市失活思想降低算法的復雜度，提高收斂速度[11]。袁汪凰等人則結合MMAS（max-min ant system）算法并在信息素的更新方面引入獎懲模型，通過獎勵算子來增加收斂速度，通過懲罰算子增加多樣性，有效平衡了算法的多樣性和收斂速度[12]。張曉偉等人則通過將蟻群分工，然后進行并行搜索，互相影響，以達到多樣性和收斂性的動態平衡[13]。接著很多其他的算法和機制也都相繼被應用來改進算法，比如聚類方法和交互式機制都被引入改進的算法中，用以改進種群間的交流機制，實驗結果也證明算法在性能上有了一定的提升[14-15]。章春芳等人則提出將種群分為若干子種群，讓每個子群體的螞蟻并行地進行優化，自適應地調整交流策略[16]，以讓算法在收斂性和多樣性方面保持有效的平衡，但是正如上述專家學者所提出的那樣，有些在利用雙種群進行交互時，兩個種群間不能形成優勢互補[10]，而有些學者提出讓雙種群之間進行交流，但是在交流方式上往往比較單一，有的則是在對交流后信息素的更新策略上不能實現很好的自適應更新[11,13]，在一定程度上會影響算法的性能。

本文在結合強化學習[17]思想的基礎上，提出了一種基于啟發式強化學習的異構雙種群算法。將蟻群系統（ant colony system，ACS）作為主種群，將精英螞蟻系統（elitist ant system，EAS）作為子種群，利用啟發算子控制兩個種群間是否進行交流，充分發揮種群間的優勢互補。同時利用偏離度系數來控制解的交換方式，前期利用子種群最優解去替換主種群的隨機解，增加解的多樣性，同時利用強化學習機制對主種群最優路徑上的信息素進行一定自適應的獎賞，來保證最優公共路徑以后被選擇的概率。隨著解的構建的進行，后期則用子種群的最優解替換主種群的最差解，有效增加最優公共路徑上信息素的量，同時對主種群的最優路徑上信息素進行進一步自適應獎賞，進一步提高了算法在后期的收斂速度。

2 相關工作

2.1 精英螞蟻系統（EAS）

在EAS 算法中，通過并行地構建TSP 路徑，并且在每一次迭代完成之后給予最優路徑上的信息素以額外的獎勵，以加強最優路徑的每條邊的影響比重，從而加快收斂速度，其狀態轉移公式如式（1）所示：

信息素更新公式為：

e為一個參數，它定義了給予路徑Tbs的權值的大小，Cbs為最優路徑上的長度，由公式可知，EAS 通過在每次迭代過后給予最優路徑增加以一定權重的信息素，從而有效增加算法的收斂速度。

2.2 蟻群系統（ACS）

ACS 相對于EAS 來說，主要在幾個地方進行了改進：（1）在對下一路徑的選取規則上；（2）全局信息素的更新規則；（3）為了降低每次迭代過后最優路徑上的信息素的影響力，新增加了局部更新規則。

ACS 中下一段路徑的選擇規則如式（4）所示：

其中，q是一個分布在區間[0,1]的隨機數，并且0 ≤q0≤1，這樣就可通過調整參數q0來調節螞蟻對路徑的探索。

在信息素的全局更新上，ACS 的更新規則如下：

局部信息素更新規則如下：

式中，τ0為初始信息素的值，取值為1/nCnn，Cnn為由近鄰算法得到的路徑長度，ξ為一常數，即信息素的蒸發率，局部信息素更新規則的引入，可以防止每條邊的信息素無限累積，并且降低最優路徑上信息素的濃度，增加螞蟻探索其他路徑的可能性，從而增加了解的多樣性。

2.3 兩種群之間的優勢互補分析

EAS 算法在每次迭代完成之后，通過全局信息素的更新增加最優路徑上的信息素，這樣算法就能在前期很快尋找到較好的路徑，但是缺點就是比較容易陷入局部最優。ACS 則通過引入局部信息素更新機制有效地削弱了算法前期最優解路徑上信息素的影響力，使算法在前期能夠有效擴大搜索范圍，提高解的質量，因此EAS 與ACS 兩種算法有著較好的互補性。

2.4 強化學習算法

強化學習是指從環境狀態到動作映射的學習，以使動作獲得累積獎賞值最大，強化學習機制如圖1所示。該方法不同于監督學習技術那樣通過正例、反例來告知采取何種行為，而是通過試錯來發現最優行為策略，通常采用評估函數Qt(st,at)表示在狀態st下，執行動作at，該狀態-動作對得到的最大累積折扣回報。該函數有界且逼近Q值，每個狀態-動作對作為策略都會被訪問有限次。Q值更新規則如式（7）所示：

其中，s表示當前狀態；a表示在狀態s下采取的動作；r表示立即回報；s1為新的狀態；γ為折扣因子；α為學習率。

Fig.1 Reinforcement learning mechanism圖1 強化學習機制

3 啟發式強化學習雙種群蟻群算法

鑒于EAS 和ACS 之間優勢互補的關系，將二者放在一起組成異構的雙種群算法，將ACS 作為主種群，EAS 作為子種群。通過啟發式算法控制子種群與主種群間的交流頻率，即前期通過降低兩種群間的交流頻率，擴大種群前期的搜索空間，有效提高算法的多樣性，并通過強化學習機制對交流后主種群最優路徑上的信息素進行自適應的獎賞，讓最優公共路徑上的信息素得到累積，提高其在后期被選擇的概率。后期則自適應地提高種群間交流頻率，同時強化最優公共路徑上的信息素的量，提高算法在后期的收斂速度。

3.1 偏離度系數

在每次迭代過后，兩個種群參與解的構建的m只螞蟻都會形成各自的解集mi={m1,m2,…,mm}，mj={mi+1,mi+2,…,m2m}，為了衡量出每次迭代后兩個種群的解與TSPLIB（traveling salesman problem library）中最優解的偏離程度，以下提出了偏離度系數的概念，如式（8）所示：

其中，Lexp為期望路徑（TSPLIB 庫中的標準值）；li為種群i與種群j每只螞蟻在每次迭代過后解的值；mi、mj分別為種群i與種群j在每次迭代過后的解集。由上式可知，每次迭代后，種群中的每只螞蟻的解偏離Lexp越多并且較為分散時，σ的值也就越大；反之當解的值較優并且較為集中時，σ的值也就越小。根據每次迭代過后σ值的大小，可以有效得出并行搜索時兩個種群總體解的情況。

為了比較直觀看出δ值隨迭代次數的變化，分別對Eil51 和KroA100 實驗中δ的值與迭代次數進行擬合，得出σ的擬合曲線如圖2 所示。

由圖2 中的擬合曲線可以看出，δ的值在算法運行初期由于解的多樣性較好，因此相對最優解來說，總體的偏離度也就較大，即δ的值也相對較大。但是隨著算法迭代的進行，每次迭代過后的解則逐漸向最優解附近靠近，因此δ的值也就會出現明顯的下降，直到最后算法在達到收斂或者找到最優解后，δ的值則變得平穩，或者趨向于0。

Fig.2 Eil51 and KroA100 deviation fitting curve圖2 Eil51 和KroA100 偏離度擬合曲線

3.2 啟發式交流頻率

螞蟻在每次完成解的構建后，需要根據解的情況來判定解的交換方式，但是如果每次迭代完成后都進行解的交換，再對最優路徑上的信息素進行獎懲，就會增加算法復雜度，同時也會造成最優路徑上的信息素累積過快，使算法陷入局部最優，因此可以通過引入啟發式算法來限制兩個種群的交流頻率，以此降低算法的復雜度。

啟發式函數如式（9）所示：

其中，Q代表兩個種群間進行解的替換，則表示不進行替換，q∈rand(0,1),k為一個不確定常數。如圖3所示，圖中黑色線段部分為當k取一定值時，事情Q可能發生的臨界值，左邊的部分代表不會發生，右邊部分代表有一定的概率發生。當測試集規模較小時，偏離度σ的下降趨勢也就相對明顯，因此此時通過將常數k設置為較大的常數，來控制事情Q的發生概率。例如，在Eil51 中將k值設定為50，在算法剛開始運行時，由于kσ∈(1,+∞)，那么就不會發生解的替換，而隨著σ值的降低，事件Q就會有一定的概率發生，且發生的概率越來越大，直到最后算法達到收斂。當測試集規模較大時，前期偏離度也相對較大，此時為了控制事件Q的發生概率，則需要將k設定為較大的值，以控制事件Q發生的時間節點。

Fig.3 Threshold value of event Q圖3 事件Q 發生的臨界值

由式（9）并結合圖3 可知，由于前期解的偏離程度較大，因此事件Q發生的概率也就較小或者基本不會發生。種群此時基本不會進行解的交換，不需要對解的交流方式進行判定，雙種群間只需要各自去構建自己的解，因此更多的未知路徑就可以被探索到，有效地增加了解的多樣性并且降低了算法的復雜度。而隨著算法的運行，解的質量的改善，kσ的值也就越來越小，事件Q發生的概率也就越來越大，此時種群間會對交流的方式進行判定，通過有效的交流方式來進一步提高算法的多樣性和收斂速度。

3.3 子群體間的交流方式

為了發揮兩個種群優勢互補的優勢，讓優良的解能在兩種群之間傳播，兩種群間需要根據各自解的優劣定期地以不同的方式進行解的替換，如式（10）：

3.4 強化學習機制

EAS 和ACS 在前期完成路徑上信息素的隨機替換后，會使有些未知路徑上的信息素得到加強，增加了解的多樣性的同時，也會因為解集過多而導致最優公共路徑上信息素的影響比重下降，進而影響算法的收斂速度。并且隨著迭代的進行，EAS 用最優路徑上信息素替換ACS 最差路徑上的信息素后，使公共路徑上信息素的影響力進一步加強，其他路徑上的信息素的影響微乎其微，此時可以通過調節ACS的全局信息素更新方式來提高最優公共路徑上信息素的影響比重以及算法后期的收斂速度。提出以下基于強化學習機制的全局信息素更新公式：

其中，ρ為一常數，為最優路徑的長度，li為第i代ACS 的最優路徑長度，li-w為前w代ACS 最優路徑的長度。由式（11）可知，相隔w代后，信息素獎賞的量與w代之間解的差值成正比，即如果w代之后最優解有了明顯的改善，說明此時路徑上出現最優解的概率就越大，那么就對此時路徑的信息素給予相對較大比例的獎賞，從而有效提高最優公共路徑以后被選擇的概率。后期則由于交換頻率的加快，信息素的累積也相對較快，解的增加幅度也相對較小，從而對最優路徑上的信息素進行少量的獎賞，進一步提高算法后期的收斂速度。

3.5 算法的流程

算法ACA-HRAL for TSP

3.6 算法性能特點分析

3.6.1 時間復雜度分析

由算法流程圖可以計算出ACA-HRAL（ant colony algorithm-heuristic reinforcement learning）的時間復雜度為O((2m×(n-1)+2n)×(NC-k)+(2m×(n-1)+n)×k)，即ACA-HRAL 的時間復雜度為O(2m×n×NC)，而對于傳統的單種群算法EAS 和ACS 來說，可知其時間復雜度為O(n3)。因此對比可知，ACA-HRAL 的時間復雜度在量級上并未發生改變。

3.6.2 算法性能特點分析

ACA-HRAL 算法結合了兩種經典單種群蟻群算法的優勢，通過引入啟發式算子控制種群間的交流頻率，比如算法剛開始運行時，主要進行對未知路徑的探索，此時應該以較低的頻率去進行解的交流，以增加解的多樣性；當偏離度系數大于一定閾值時，就不需要進行交流方式的判定，從而降低算法的復雜度。

當算法達到可以進行交流的條件時，會根據偏離度的大小，選擇對應的交流方式。當偏離度較大時，說明算法主要偏重于探索未知路徑，此時用EAS的最優解替換ACS 隨機解，有效地增加主種群ACS非最優解路徑上信息素的比例，從而增加解的多樣性，再利用強化學習機制對最優路徑上信息素的量進行一定比例的強化，以增加最優公共路徑被選中的概率。當進入迭代后期時，算法偏離度則比較小，同時兩個單種群的最優路徑的重合度也比較高，此時利用EAS 的最優解去替換ACS 的最差解，再利用強化機制對最優路徑上的信息素進行更新，能夠有效增加后期的收斂速度。

綜合來看，相對于傳統的單種群蟻群算法，ACAHRAL 能夠在不增加時間復雜度的情況下，利用種群間的交流機制和對信息素的自適應強化機制，能夠有效提高前期解的多樣性和后期的收斂速度。

4 實驗仿真與分析

為了檢驗改進后雙種群蟻群算法的性能，選取標準的TSP 測試集，并與EAS、ACS 的性能進行比較。最后在Matlab2018a版本下對每個測試集進行15次實驗仿真，通過測試結果檢驗改進后算法的性能。

4.1 參數設定

在進行實驗仿真前，首先參考文獻[3]和文獻[4]，對EAS和ACS進行實驗參數設定，針對ACA-HRAL，由式（9）和式（10）可知，由于前期雙種群在完成解的替換后，公共路徑上信息素的累積相對較大，因此為了減小前期信息素的影響比重，防止過早陷入局部最優，賦予β較大的值，具體參數如表1。

Table 1 Algorithm parameters setting表1 算法參數設置

4.2 實驗結果與分析

為了測試改進后的算法性能，本實驗中選取了12個中小規模城市的TSP 測試集，如Eil51、Eil76、KroB200和Lin318等作為實驗對象，分別進行10次的測試，得出了算法在收斂性上的對比圖以及誤差率、迭代次數等具體參數，具體結果如圖4 和表2 所示。

4.2.1 整體性能分析

為了體現ACA-HRAL 在性能上的改變，選取Eil51、KroA100、KroA150、KroB150、D198、KroB200和Lin318 城市作為測試集，得出其在收斂性以及所得解的對比曲線，如圖4 所示。

Fig.4 Experimental comparison圖4 實驗對比圖

Table 2 EAS,ACS and ACA-HRAL experimental simulation data表2 EAS、ACS 和ACA-HRAL 實驗仿真數據

（1）多樣性分析

當算法前期多樣性較好時，其解集的范圍也就越大，在一定的迭代次數內找到較優解的可能性也就越大，偏離度也就相對會較小。為了比較改進后算法在前期多樣性上的改進，對前200 次迭代解的偏離度系數進行了分析比較，如表3。

Table 3 Deviation degree of the first 200 generations表3 前200 代偏離度大小

結合表3 可以看出，EAS 和ACS 在前期由于沒有發生解的替換，解的多樣性相對較差，在前200 次的迭代中，總體解的偏離度系數都要大于ACA-HRAL；ACA-HRAL 由于交流機制和信息素強化機制的存在，其在前期探索的范圍相對較廣，解的多樣性較好，能夠以較快的速度找到較優路徑的集合，因此解的偏離度系數相對其他兩種算法來說也就越小。

（2）收斂性分析

結合圖4 可以發現，在小規模的測試集Eil51 上，EAS 的收斂速度要快于ACA-HRAL，但是從結果可以發現，EAS 是由于陷入局部最優而導致收斂速度較快。在D198 的測試集上，ACS 的收斂速度也是快于ACA-HRAL，也是由于未能跳出局部最優而導致提前收斂，而ACA-HRAL 由于增加了對信息素的強化機制，使最優公共路徑上的信息素能夠在后期得到較快的累積。因此在其他的測試集中ACA-HRAL 都能以較快的速度達到收斂，并且解的質量也有著很大的提高，說明ACA-HRAL 能夠在跳出局部最優的情況下有效提高后期的收斂速度。

綜合來看，改進后的算法前期在解的多樣性方面和后期在收斂速度上都有了一定的提高。

4.2.2 具體結果分析

為了進一步得出算法在解的質量和收斂性方面的提升，依照表2 中的實驗數據，選取每種算法達到最優解時候的誤差率和達到收斂時的實驗數據，做出了如圖5 和圖6 所示的柱狀圖，分別表示每種算法在不同測試集下相對最優解的誤差率和達到最優解時的收斂次數對比。

Fig.5 Error rate of solution圖5 解的誤差率

Fig.6 Number of iterations圖6 迭代次數

由圖5 的對比可以看出，在對小規模的城市集進行測試時，ACA-HRAL 能夠有著較優的表現，都能找尋到最優解，隨著城市規模的慢慢擴大，EAS 和ACS的誤差率則越來越高，而ACA-HRAL 則可以將誤差率控制在1%左右。根據圖6 的迭代次數可以看出，前期EAS 和ACS 雖然用了較少的迭代就達到收斂，但是并未找到最優解，即算法在前期陷入了局部收斂，而ACA-HRAL 相對二者來說，雖然迭代次數較多，但是能找尋到最優解，說明其能有效跳出局部最優。另外隨著測試集規模的擴大，結合圖5 和圖6 可以看出，ACA-HRAL 在規模較大一點的測試集中不僅所取得的效果較好，而且迭代次數也相對較少，因此綜合來說，相對于經典的單種群，算法在跳出局部最優和尋優能力方面都有了很大的提高。

5 結束語

本文基于經典單種群間的優勢互補關系提出了一種基于啟發式強化學習的雙種群蟻群算法。通過啟發式算法自適應地控制種群間的交流頻率與交流方法，讓兩個種群在前期能夠充分地進行解的構建，擴大搜索空間，并引入強化學習機制對交流后的主種群最優路徑上的信息素進行強化，提高最優公共路徑以后被選中的概率，后期通過控制增加最優路徑上信息素的比例來進一步加快算法的收斂速度。實驗結果表明，算法的整體性能相較傳統單種群有了很大提高，尤其是在解決部分大規模問題上。在以后工作中，將在雙種群的基礎上進一步研究多種群蟻群算法之間的交流合作機制，以提高其在解決大規模TSP 問題上的性能，并能有效地應用到實際問題中。