啟發(fā)式強(qiáng)化學(xué)習(xí)機(jī)制的異構(gòu)雙種群蟻群算法*

劉中強(qiáng)，游曉明，劉 升

1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海201620

1 引言

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

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

2 相關(guān)工作

2.1 精英螞蟻系統(tǒng)（EAS）

在EAS 算法中，通過并行地構(gòu)建TSP 路徑，并且在每一次迭代完成之后給予最優(yōu)路徑上的信息素以額外的獎(jiǎng)勵(lì)，以加強(qiáng)最優(yōu)路徑的每條邊的影響比重，從而加快收斂速度，其狀態(tài)轉(zhuǎn)移公式如式（1）所示：

信息素更新公式為：

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

2.2 蟻群系統(tǒng)（ACS）

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

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

其中，q是一個(gè)分布在區(qū)間[0,1]的隨機(jī)數(shù)，并且0 ≤q0≤1，這樣就可通過調(diào)整參數(shù)q0來調(diào)節(jié)螞蟻對(duì)路徑的探索。

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

局部信息素更新規(guī)則如下：

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

2.3 兩種群之間的優(yōu)勢(shì)互補(bǔ)分析

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

2.4 強(qiáng)化學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)是指從環(huán)境狀態(tài)到動(dòng)作映射的學(xué)習(xí)，以使動(dòng)作獲得累積獎(jiǎng)賞值最大，強(qiáng)化學(xué)習(xí)機(jī)制如圖1所示。該方法不同于監(jiān)督學(xué)習(xí)技術(shù)那樣通過正例、反例來告知采取何種行為，而是通過試錯(cuò)來發(fā)現(xiàn)最優(yōu)行為策略，通常采用評(píng)估函數(shù)Qt(st,at)表示在狀態(tài)st下，執(zhí)行動(dòng)作at，該狀態(tài)-動(dòng)作對(duì)得到的最大累積折扣回報(bào)。該函數(shù)有界且逼近Q值，每個(gè)狀態(tài)-動(dòng)作對(duì)作為策略都會(huì)被訪問有限次。Q值更新規(guī)則如式（7）所示：

其中，s表示當(dāng)前狀態(tài)；a表示在狀態(tài)s下采取的動(dòng)作；r表示立即回報(bào)；s1為新的狀態(tài)；γ為折扣因子；α為學(xué)習(xí)率。

Fig.1 Reinforcement learning mechanism圖1 強(qiáng)化學(xué)習(xí)機(jī)制

3 啟發(fā)式強(qiáng)化學(xué)習(xí)雙種群蟻群算法

鑒于EAS 和ACS 之間優(yōu)勢(shì)互補(bǔ)的關(guān)系，將二者放在一起組成異構(gòu)的雙種群算法，將ACS 作為主種群，EAS 作為子種群。通過啟發(fā)式算法控制子種群與主種群間的交流頻率，即前期通過降低兩種群間的交流頻率，擴(kuò)大種群前期的搜索空間，有效提高算法的多樣性，并通過強(qiáng)化學(xué)習(xí)機(jī)制對(duì)交流后主種群最優(yōu)路徑上的信息素進(jìn)行自適應(yīng)的獎(jiǎng)賞，讓最優(yōu)公共路徑上的信息素得到累積，提高其在后期被選擇的概率。后期則自適應(yīng)地提高種群間交流頻率，同時(shí)強(qiáng)化最優(yōu)公共路徑上的信息素的量，提高算法在后期的收斂速度。

3.1 偏離度系數(shù)

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

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

為了比較直觀看出δ值隨迭代次數(shù)的變化，分別對(duì)Eil51 和KroA100 實(shí)驗(yàn)中δ的值與迭代次數(shù)進(jìn)行擬合，得出σ的擬合曲線如圖2 所示。

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

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

3.2 啟發(fā)式交流頻率

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

啟發(fā)式函數(shù)如式（9）所示：

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

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

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

3.3 子群體間的交流方式

為了發(fā)揮兩個(gè)種群優(yōu)勢(shì)互補(bǔ)的優(yōu)勢(shì)，讓優(yōu)良的解能在兩種群之間傳播，兩種群間需要根據(jù)各自解的優(yōu)劣定期地以不同的方式進(jìn)行解的替換，如式（10）：

3.4 強(qiáng)化學(xué)習(xí)機(jī)制

EAS 和ACS 在前期完成路徑上信息素的隨機(jī)替換后，會(huì)使有些未知路徑上的信息素得到加強(qiáng)，增加了解的多樣性的同時(shí)，也會(huì)因?yàn)榻饧^多而導(dǎo)致最優(yōu)公共路徑上信息素的影響比重下降，進(jìn)而影響算法的收斂速度。并且隨著迭代的進(jìn)行，EAS 用最優(yōu)路徑上信息素替換ACS 最差路徑上的信息素后，使公共路徑上信息素的影響力進(jìn)一步加強(qiáng)，其他路徑上的信息素的影響微乎其微，此時(shí)可以通過調(diào)節(jié)ACS的全局信息素更新方式來提高最優(yōu)公共路徑上信息素的影響比重以及算法后期的收斂速度。提出以下基于強(qiáng)化學(xué)習(xí)機(jī)制的全局信息素更新公式：

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

3.5 算法的流程

算法ACA-HRAL for TSP

3.6 算法性能特點(diǎn)分析

3.6.1 時(shí)間復(fù)雜度分析

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

3.6.2 算法性能特點(diǎn)分析

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

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

綜合來看，相對(duì)于傳統(tǒng)的單種群蟻群算法，ACAHRAL 能夠在不增加時(shí)間復(fù)雜度的情況下，利用種群間的交流機(jī)制和對(duì)信息素的自適應(yīng)強(qiáng)化機(jī)制，能夠有效提高前期解的多樣性和后期的收斂速度。

4 實(shí)驗(yàn)仿真與分析

為了檢驗(yàn)改進(jìn)后雙種群蟻群算法的性能，選取標(biāo)準(zhǔn)的TSP 測(cè)試集，并與EAS、ACS 的性能進(jìn)行比較。最后在Matlab2018a版本下對(duì)每個(gè)測(cè)試集進(jìn)行15次實(shí)驗(yàn)仿真，通過測(cè)試結(jié)果檢驗(yàn)改進(jìn)后算法的性能。

4.1 參數(shù)設(shè)定

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

Table 1 Algorithm parameters setting表1 算法參數(shù)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試改進(jìn)后的算法性能，本實(shí)驗(yàn)中選取了12個(gè)中小規(guī)模城市的TSP 測(cè)試集，如Eil51、Eil76、KroB200和Lin318等作為實(shí)驗(yàn)對(duì)象，分別進(jìn)行10次的測(cè)試，得出了算法在收斂性上的對(duì)比圖以及誤差率、迭代次數(shù)等具體參數(shù)，具體結(jié)果如圖4 和表2 所示。

4.2.1 整體性能分析

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

Fig.4 Experimental comparison圖4 實(shí)驗(yàn)對(duì)比圖

Table 2 EAS,ACS and ACA-HRAL experimental simulation data表2 EAS、ACS 和ACA-HRAL 實(shí)驗(yàn)仿真數(shù)據(jù)

（1）多樣性分析

當(dāng)算法前期多樣性較好時(shí)，其解集的范圍也就越大，在一定的迭代次數(shù)內(nèi)找到較優(yōu)解的可能性也就越大，偏離度也就相對(duì)會(huì)較小。為了比較改進(jìn)后算法在前期多樣性上的改進(jìn)，對(duì)前200 次迭代解的偏離度系數(shù)進(jìn)行了分析比較，如表3。

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

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

（2）收斂性分析

結(jié)合圖4 可以發(fā)現(xiàn)，在小規(guī)模的測(cè)試集Eil51 上，EAS 的收斂速度要快于ACA-HRAL，但是從結(jié)果可以發(fā)現(xiàn)，EAS 是由于陷入局部最優(yōu)而導(dǎo)致收斂速度較快。在D198 的測(cè)試集上，ACS 的收斂速度也是快于ACA-HRAL，也是由于未能跳出局部最優(yōu)而導(dǎo)致提前收斂，而ACA-HRAL 由于增加了對(duì)信息素的強(qiáng)化機(jī)制，使最優(yōu)公共路徑上的信息素能夠在后期得到較快的累積。因此在其他的測(cè)試集中ACA-HRAL 都能以較快的速度達(dá)到收斂，并且解的質(zhì)量也有著很大的提高，說明ACA-HRAL 能夠在跳出局部最優(yōu)的情況下有效提高后期的收斂速度。

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

4.2.2 具體結(jié)果分析

為了進(jìn)一步得出算法在解的質(zhì)量和收斂性方面的提升，依照表2 中的實(shí)驗(yàn)數(shù)據(jù)，選取每種算法達(dá)到最優(yōu)解時(shí)候的誤差率和達(dá)到收斂時(shí)的實(shí)驗(yàn)數(shù)據(jù)，做出了如圖5 和圖6 所示的柱狀圖，分別表示每種算法在不同測(cè)試集下相對(duì)最優(yōu)解的誤差率和達(dá)到最優(yōu)解時(shí)的收斂次數(shù)對(duì)比。

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

Fig.6 Number of iterations圖6 迭代次數(shù)

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

5 結(jié)束語

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