基于跨鄰域搜索的連續(xù)域蟻群優(yōu)化算法

夏 媛，李 俊，周 虎

(1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢，430065；2. 武漢科技大學(xué)智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430065)

蟻群算法利用蟻群在搜索食物源的過程中所體現(xiàn)出的尋優(yōu)能力來解決離散型組合優(yōu)化問題[1]，如旅行商問題[2]、車輛路徑問題[3]、作業(yè)車間調(diào)度問題[4]等。由于越來越多的實(shí)際應(yīng)用被描述為連續(xù)域優(yōu)化問題，因此將經(jīng)典的離散型蟻群算法拓展到連續(xù)域成為一個(gè)新的研究方向。Bilchev等[5]最先提出連續(xù)域蟻群算法，通過將連續(xù)搜索空間離散成有限個(gè)區(qū)域來求解連續(xù)函數(shù)優(yōu)化問題。該算法雖然有一定的尋優(yōu)能力，但也存在容易陷入局部極值點(diǎn)、尋優(yōu)精度差的問題。

針對以上不足，國內(nèi)外研究者提出了各種改進(jìn)方法。文獻(xiàn)[6]提出的連續(xù)域蟻群優(yōu)化改進(jìn)算法首先利用全局搜索策略進(jìn)行預(yù)處理，提高算法的收斂速度和收斂精度，然后利用隨機(jī)搜索策略來增強(qiáng)搜索能力。文獻(xiàn)[7]將啟發(fā)式信息與連續(xù)域蟻群優(yōu)化算法相融合，并應(yīng)用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練中，在減小分類誤差的同時(shí)提高了收斂速度。文獻(xiàn)[8]利用混合連續(xù)域蟻群優(yōu)化技術(shù)來逼近最優(yōu)解，并根據(jù)互相學(xué)習(xí)方案中的同化、順應(yīng)、變異等操作，使群體能夠相互交換和容納群體間的部分信息，并在全局范圍內(nèi)搜索信息，擴(kuò)大搜索空間。文獻(xiàn)[9]用高斯核函數(shù)作為概率密度函數(shù)來生成新解，通過替換檔案中的解來更新信息素，利用高斯函數(shù)的隨機(jī)性擴(kuò)大種群搜索范圍，避免算法陷入局部最優(yōu)。文獻(xiàn)[10]提出了一種信息分享機(jī)制，將當(dāng)前解與其他所有解的平均距離以及當(dāng)前解與目前最優(yōu)解的距離相結(jié)合，同時(shí)采用一種新的解更新方式對檔案中的解進(jìn)行信息素?fù)]發(fā)，并且自適應(yīng)調(diào)整其揮發(fā)速率，更好地平衡收斂速度和收斂精度。文獻(xiàn)[11]提出一種人工蜂群算子在全局信息素更新過程中產(chǎn)生候選解，同時(shí)引入替代機(jī)制來選擇指導(dǎo)解，不僅可以節(jié)約計(jì)算時(shí)間，而且盡可能地保持了搜索的多樣性。

以上改進(jìn)算法或利用算法融合，或提出優(yōu)化策略，所有改進(jìn)方式的側(cè)重點(diǎn)都在每一代的較優(yōu)解上。這樣雖加強(qiáng)了逼近最優(yōu)解的能力，但探索未知區(qū)域的能力卻相對較弱，容易陷入局部極值中。為了平衡尋優(yōu)過程中逼近最優(yōu)解和探索未知區(qū)域的能力，本文提出一種基于跨鄰域搜索(across neighborhood search,ANS)的連續(xù)域蟻群優(yōu)化算法。該算法采用自適應(yīng)方式將種群劃分為多個(gè)區(qū)域，其中主體區(qū)域分為較優(yōu)解組和較差解組；其次讓較差解組根據(jù)自主選擇學(xué)習(xí)算子來選擇對象進(jìn)行學(xué)習(xí)，不斷擴(kuò)大種群規(guī)模，避免算法陷入局部最優(yōu)；再者對較優(yōu)解組采用全局跨鄰域搜索方式，引導(dǎo)螞蟻向全局最優(yōu)解靠近，加快收斂速度；最后對處理后的解檔案進(jìn)行重排序，選取最優(yōu)解做為指導(dǎo)解，并利用局部跨鄰域的方式在小范圍內(nèi)進(jìn)行細(xì)致搜索，通過貪心機(jī)制，對比新解和舊解，更新解檔案，尋找最優(yōu)解。

1 連續(xù)域蟻群優(yōu)化算法

在連續(xù)空間尋優(yōu)問題的求解中，解空間是以區(qū)域性方式而不是離散點(diǎn)來表示的，因此不能采用經(jīng)典的離散型蟻群算法。與離散型蟻群優(yōu)化算法不同的是，連續(xù)域蟻群算法的優(yōu)化目標(biāo)是所求問題的目標(biāo)函數(shù)值達(dá)到最優(yōu)，因此在信息素的更新方式和狀態(tài)選擇規(guī)則中均有所不同，其主要是根據(jù)目標(biāo)函數(shù)值來更新信息素濃度，以微調(diào)的前進(jìn)方式來代替狀態(tài)選擇規(guī)則。

連續(xù)優(yōu)化問題描述如下：設(shè)螞蟻個(gè)數(shù)為m，解個(gè)數(shù)為K，Xi=(Xi1,…,Xij,…,Xin)表示所求問題的一個(gè)解，Xij表示第i個(gè)解中第j維的值，n為問題的維數(shù)，K個(gè)解構(gòu)成一個(gè)K×n的解矩陣。連續(xù)域蟻群優(yōu)化算法要解決的是如何根據(jù)每個(gè)目標(biāo)函數(shù)值的信息素濃度，通過相應(yīng)的轉(zhuǎn)移方式不斷引導(dǎo)算法向最優(yōu)解靠近。本文提出一種基于跨鄰域搜索的改進(jìn)連續(xù)域蟻群算法(命名為ANS-Ant)來解決連續(xù)優(yōu)化問題。

2 ANS-Ant算法

2.1 自適應(yīng)種群劃分

最早提出的連續(xù)域蟻群優(yōu)化算法通過初始化隨機(jī)產(chǎn)生種群，每次迭代只將最優(yōu)解作為可行解，不好的解即被舍棄。因此，種群個(gè)體在迭代期間只會往同一個(gè)方向進(jìn)行尋優(yōu)，容易導(dǎo)致算法陷入局部最優(yōu)。文獻(xiàn)[12]指出，通過不斷獲得失敗經(jīng)驗(yàn)，可以引導(dǎo)蟻群在優(yōu)化過程中探索未知空間。因此本文提出一種自適應(yīng)劃分方式，根據(jù)當(dāng)前迭代次數(shù)來分割優(yōu)解和劣解的種群數(shù)量，具體公式如下：

(1)

式中：p為優(yōu)解的種群數(shù)量；h為劣解的種群數(shù)量；kmax為最大迭代次數(shù)；k為當(dāng)前迭代次數(shù)。

通過這種自適應(yīng)劃分方式，使得算法在迭代初始階段優(yōu)解較少，而且數(shù)量增長得較慢，這樣能保證算法在迭代初期以較快速度收斂到全局較優(yōu)解；在迭代的中后期，擴(kuò)大了優(yōu)解的數(shù)量，這樣能抑制早熟，避免算法落入局部極值點(diǎn)。同時(shí)，前期劣解數(shù)量較多，可以在一定程度上擴(kuò)大種群的探索空間；在迭代中后期，劣解數(shù)量逐漸減少，這樣能加快算法收斂。

2.2 自主選擇學(xué)習(xí)算子

自適應(yīng)種群劃分將解檔案區(qū)分為優(yōu)解和劣解。針對劣解，基于教與學(xué)算法[13]中同學(xué)之間可以互相交流學(xué)習(xí)、一個(gè)同學(xué)通過隨機(jī)選擇另一位同學(xué)進(jìn)行學(xué)習(xí)來提高成績的思想，本文讓劣解同時(shí)具有較優(yōu)解可以進(jìn)行互相學(xué)習(xí)的類似學(xué)習(xí)能力。然而，對于每一個(gè)劣解而言，如果選擇的對象也為劣解，則相互學(xué)習(xí)不僅無法提高成績，還會浪費(fèi)學(xué)習(xí)時(shí)間。故對劣解采取隨機(jī)選擇策略進(jìn)行學(xué)習(xí)的不穩(wěn)定因素太大，不僅無助于提高收斂精度，還會占據(jù)計(jì)算時(shí)間。一般來說，人們傾向于讓成績不好的學(xué)生向優(yōu)秀學(xué)生學(xué)習(xí)，以達(dá)到提升整體學(xué)習(xí)水平的目的。同理，讓劣解向最優(yōu)解進(jìn)行學(xué)習(xí)可提升解檔案的整體水平。但如果所有的劣解同時(shí)向最優(yōu)解進(jìn)行學(xué)習(xí)，算法又很容易陷入局部最優(yōu)。因此，本文提出一種自主選擇學(xué)習(xí)算子，具體公式如下：

Xnew=Xbad+rand(0,1)(Y-Xbad)

(2)

式中：Xnew為較差解經(jīng)過自主選擇學(xué)習(xí)后產(chǎn)生的新解；Xbad為h個(gè)較差解；Y為上次迭代產(chǎn)生的p個(gè)較優(yōu)解中任意一個(gè)。該算子旨在讓每一個(gè)劣解在較優(yōu)解群體中自主選擇對應(yīng)的較優(yōu)個(gè)體進(jìn)行學(xué)習(xí)，這樣能在一定程度上擴(kuò)大種群多樣性，避免產(chǎn)生局部最優(yōu)。

2.3 跨鄰域搜索機(jī)制

跨鄰域搜索是一種較新且簡便的數(shù)值優(yōu)化算法[14]，其具體方法為：以個(gè)體i與當(dāng)前最好解決方案之間的長度為搜索區(qū)域，利用高斯分布影響因子來平衡算法的開發(fā)和勘探能力。每個(gè)個(gè)體不僅可以搜索其他解周圍的鄰域，還可以搜索最優(yōu)解周圍的鄰域。結(jié)合跨鄰域搜索算法的優(yōu)點(diǎn)，本文在連續(xù)域蟻群算法中針對較優(yōu)解組引入其良好的勘探能力，針對指導(dǎo)解引入其良好的逼近最優(yōu)解能力。

2.3.1 全局搜索

擴(kuò)大種群多樣性可以避免算法陷入局部最優(yōu)，但如果只對較差解組進(jìn)行更新，則不能確保更新后的解對收斂精度的影響因子大小，換句話說，如果更新后的解優(yōu)于當(dāng)前迭代產(chǎn)生的較優(yōu)解，可能會導(dǎo)致搜索方向出現(xiàn)偏差，無法找到更好的解。為了避免這種情況的發(fā)生，本文引入全局跨鄰域搜索機(jī)制，旨在讓p個(gè)較優(yōu)解在處理了較差解組的基礎(chǔ)上分別隨機(jī)選擇一個(gè)解進(jìn)行學(xué)習(xí)，具體公式如下：

Xnew=Xgood+G(0,δ2)|Xgood-posi|

(3)

式中：Xnew為較優(yōu)解經(jīng)過全局搜索后產(chǎn)生的新解；Xgood為p個(gè)較優(yōu)解；posi為隨機(jī)選擇的任意解；G(0,δ2)為高斯分布因子，表示在高斯分布范圍內(nèi)選取鄰域，該因子提供的搜索范圍較廣，波動幅度較小，且符合連續(xù)域蟻群優(yōu)化算法的微調(diào)式前進(jìn)方式。

從式(3)可以看出，由于選擇的學(xué)習(xí)對象不同，每個(gè)個(gè)體搜索的范圍也不一致，從而實(shí)現(xiàn)了較優(yōu)解組里面的每一個(gè)解都可以在不同的鄰域范圍內(nèi)進(jìn)行探索的全局搜索模式，在確保種群多樣性的同時(shí)加快向全局最優(yōu)解的收斂。

2.3.2 局部搜索

連續(xù)域蟻群算法中以函數(shù)的適應(yīng)度值作為當(dāng)前的信息素濃度值，適應(yīng)度值越小，表示信息素濃度越大，則螞蟻更傾向于往該處的解轉(zhuǎn)移。因此要對處理后的解檔案進(jìn)行重新排序，選擇信息素濃度最大也就是適應(yīng)度值最小的解作為指導(dǎo)解，對指導(dǎo)解周圍進(jìn)行細(xì)致的局部鄰域搜索，引導(dǎo)螞蟻向最優(yōu)解靠近。具體實(shí)現(xiàn)方式如式(4)所示：

Xbest=Xobject+G(0,δ2)|Xobject-posi|

(4)

式中：Xbest是經(jīng)過局部搜索后產(chǎn)生的新解；Xobject為指導(dǎo)解；G(0,δ2)同為高斯分布因子，旨在局部范圍內(nèi)進(jìn)行范圍廣、波動幅度較小的搜索。跨鄰域局部搜索可以提高算法的收斂精度，并使其具有較好的開發(fā)能力。

2.4 ANS-Ant算法基本步驟

步驟1初始化NP個(gè)解并排序。

步驟2針對排序后的解，根據(jù)式(1)自適應(yīng)地選出當(dāng)前的較優(yōu)解組和較差解組。

步驟3根據(jù)式(2)提出的自主選擇學(xué)習(xí)算子，讓較差解組中的每個(gè)個(gè)體自主選擇較優(yōu)解組中的解進(jìn)行學(xué)習(xí)。

步驟4在執(zhí)行了較差解組的處理的基礎(chǔ)上，利用式(3)針對迭代產(chǎn)生的較優(yōu)解組進(jìn)行全局跨鄰域范圍內(nèi)的搜索，更新較優(yōu)解組。

步驟5將經(jīng)過步驟3和步驟4處理后的解檔案進(jìn)行重排序，并選取最好的解作為指導(dǎo)解。

步驟6根據(jù)式(4)對指導(dǎo)解周圍進(jìn)行局部跨鄰域細(xì)致搜索，利用貪心機(jī)制，對比舊解和新解，更新解檔案。

步驟7若達(dá)到最大迭代次數(shù)，則選取解檔案中的最優(yōu)值為最終解，否則返回步驟2。

3 算法測試及結(jié)果分析

3.1 測試函數(shù)

選擇CEC2017收錄的29個(gè)標(biāo)準(zhǔn)測試函數(shù)[15]檢驗(yàn)改進(jìn)算法ANS-Ant的有效性和適用性(函數(shù)f2穩(wěn)定性不好，被CEC2017排除，本文不對其進(jìn)行測試)，具體定義如表1所示，其中f1、f3

表1 標(biāo)準(zhǔn)測試函數(shù)

為單峰函數(shù)，f4～f10為簡單多峰函數(shù)，f11～f20為混合函數(shù)，f21～f30為復(fù)合函數(shù)。

3.2 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)中使用Matlab R2016a軟件編程，系統(tǒng)運(yùn)行環(huán)境為：Win 7雙核，Intel(R) Core(TM) i5處理器，8 GB內(nèi)存，3.2 GHz CPU。實(shí)驗(yàn)參數(shù)設(shè)置如下：種群個(gè)數(shù)NP=100，最大迭代次數(shù)itermax=10 000，問題維度分為30和50，每個(gè)函數(shù)在兩種維度下分別獨(dú)立運(yùn)行20次。通過與文獻(xiàn)[9]中提出的ACOR算法和文獻(xiàn)[11]中提出的ABC-ACOR算法在參數(shù)設(shè)定一致的情況下進(jìn)行收斂精度和速度的比較，來驗(yàn)證本文算法的優(yōu)越性。

3.3 實(shí)驗(yàn)結(jié)果及分析

3.3.1 收斂精度

為了更直觀地進(jìn)行數(shù)據(jù)對比，本文各算法的收斂精度均定義為計(jì)算得到的適應(yīng)度值Fitness減去測試函數(shù)的最優(yōu)解。表2所示為固定評價(jià)次數(shù)時(shí)3種算法的收斂精度對比，包括在30維情況下的平均值、最小值和方差，其中最好結(jié)果用粗體標(biāo)出。

表2 3種算法的收斂精度(D=30)

從表2中可以看出，本文提出的改進(jìn)算法在除f9以外的28個(gè)測試函數(shù)中取得的平均值相對于另外兩個(gè)算法來說均較優(yōu)或基本持平(f27,f28)。從最小值來看：對于單峰函數(shù)，本文算法優(yōu)于ACOR和ABC-ACOR；在簡單多峰函數(shù)中，本文算法除在函數(shù)f9上取得的值稍遜于ACOR外，其余均較優(yōu)；對于混合函數(shù)，本文算法在函數(shù)f11上取得的值稍遜于ABC-ACOR；對于復(fù)合函數(shù)，本文算法與另外兩個(gè)算法在函數(shù)f27、f28上的結(jié)果持平，在f22上的結(jié)果與ABC-ACOR持平，優(yōu)于ACOR，雖在f25、f26上稍遜于ABC-ACOR，但比ACOR要好。從方差來看，本文算法在接近一半的函數(shù)中優(yōu)于另外兩種算法，且在f3上表現(xiàn)優(yōu)異。綜上所述，本文算法在針對低維問題時(shí)總體上具有較好的尋優(yōu)能力和穩(wěn)定性。

圖1為各算法在低維情況下求解測試函數(shù)的收斂曲線，分別取單峰函數(shù)、簡單多峰函數(shù)、混合函數(shù)和復(fù)合函數(shù)中的一種作為示例。

(a)單峰函數(shù)f3

(b)簡單多峰函數(shù)f8

(c)混合函數(shù)f15

(d)復(fù)合函數(shù)f21

圖1 3種算法的收斂曲線(D=30)

Fig.1 Convergence curves of three algorithms(D=30)

從圖1可以看出，與ACOR和ABC-ACOR相比，ANS-Ant算法在這幾個(gè)函數(shù)上的尋優(yōu)能力明顯較高，且收斂較快?？偟膩砜矗珹NS-Ant解決低維連續(xù)域優(yōu)化問題時(shí)在收斂速度和精度上的優(yōu)勢明顯。

為驗(yàn)證ANS-Ant算法對高維問題的尋優(yōu)能力，對比了固定評價(jià)次數(shù)時(shí)3種算法在50維條件下的收斂精度，如表3所示，其中最好結(jié)果用粗體標(biāo)出。從最小值來看，ANS-Ant在f1、f4、f16、f23和f25上的結(jié)果不如ABC-ACOR，但兩者相差不大，在其他測試函數(shù)上，ANS-Ant的取值均優(yōu)于另外兩種算法，且在f3和f6上得到的結(jié)果幾乎接近于函數(shù)最優(yōu)解；從平均值來看，ANS-Ant只在f1、f4、f15和f25函數(shù)上稍遜一籌；從方差來看，ANS-Ant在接近40%的測試函數(shù)上占有優(yōu)勢。總體來說，在高維情況下，ANS-Ant算法依然具有較好的尋優(yōu)能力，保持了一定的穩(wěn)定性。

表3 3種算法的收斂精度(D=50)

續(xù)表3

函數(shù)編號ACOR平均值最小值方差 ABC-ACOR平均值最小值方差 ANS-Ant平均值最小值方差f217.87E+027.53E+023.10E+023.95E+023.54E+024.57E+023.12E+022.86E+022.26E+02f221.59E+041.55E+045.28E+041.35E+041.31E+047.25E+046.13E+034.74E+034.77E+05f231.05E+039.85E+027.84E+026.11E+025.07E+024.20E+035.90E+025.26E+021.43E+03f241.14E+031.09E+037.52E+027.33E+026.90E+029.51E+026.94E+026.33E+021.35E+03f254.45E+033.83E+033.27E+054.40E+024.31E+022.49E+024.83E+024.44E+026.00E+02f266.68E+036.06E+031.17E+056.92E+034.03E+031.62E+061.87E+031.37E+037.11E+04f275.00E+025.00E+022.10E-095.00E+025.00E+024.10E-095.00E+025.00E+022.70E-08f285.00E+025.00E+029.24E-095.00E+025.00E+022.67E-095.00E+025.00E+024.55E-04f291.50E+048.31E+038.25E+061.40E+038.13E+028.46E+041.01E+035.54E+027.84E+04f301.05E+095.45E+085.07E+162.07E+031.01E+037.58E+051.68E+032.92E+021.49E+06

圖2為各算法在高維情況下求解測試函數(shù)的收斂曲線，同樣各取單峰函數(shù)、簡單多峰函數(shù)、混合函數(shù)和復(fù)合函數(shù)中的一種作為示例。

(a)單峰函數(shù)f3

(b)簡單多峰函數(shù)f6

(c)混合函數(shù)f11

(d)復(fù)合函數(shù)f21

圖2 3種算法的收斂曲線(D=50)

Fig.2 Convergence curves of three algorithms(D=50)

從圖2可以看出，與ACOR和ABC-ACOR相比，ANS-Ant算法在單峰和簡單多峰函數(shù)上的尋優(yōu)能力明顯較優(yōu)，所得解與函數(shù)最優(yōu)解十分接近，且收斂較快；ANS-Ant在混合函數(shù)上也有較好的尋優(yōu)能力和較快的收斂速度；ANS-Ant在復(fù)合函數(shù)上的尋優(yōu)結(jié)果與函數(shù)最優(yōu)解的相對偏差雖然有13.6%，但相比于另外兩種算法還是有一定的優(yōu)勢?？傊珹NS-Ant應(yīng)用于高維測試函數(shù)時(shí)仍然具有較高的收斂速度和精度。

3.3.2 收斂速度

為了更加全面地檢驗(yàn)改進(jìn)算法的性能，本文采用限定精度的方法來評估其收斂速度，即在有限的評估精度內(nèi)比較各算法的進(jìn)化次數(shù)。以30維為例，針對每一個(gè)函數(shù)設(shè)置一個(gè)相應(yīng)的評估精度VTR，該值取3種優(yōu)化算法所得平均值中的最差值，如表4所示。針對每一個(gè)函數(shù)的預(yù)設(shè)收斂精度，3種算法均獨(dú)立運(yùn)行20次，設(shè)置最大迭代次數(shù)為10 000，最后將平均評估次數(shù)列于表5。

表4 預(yù)設(shè)收斂精度VTR

表5 預(yù)設(shè)收斂精度下各算法的評估次數(shù)

通過表5可以看出，相比于其他兩個(gè)算法，ANS-Ant在29個(gè)測試函數(shù)的22個(gè)中可以更快地達(dá)到預(yù)設(shè)收斂精度，表明本文提出的改進(jìn)方式有效提高了連續(xù)域蟻群優(yōu)化算法的收斂速度。

4 結(jié)語

針對連續(xù)域蟻群算法尋優(yōu)能力差、容易陷入局部最優(yōu)的問題，本文提出了一種基于跨鄰域搜索的改進(jìn)蟻群算法ANS-Ant。該算法利用不可行解不斷獲取歷史經(jīng)驗(yàn)，針對不可行解群體，利用自主選擇學(xué)習(xí)算子選擇對象進(jìn)行學(xué)習(xí)，不斷擴(kuò)大種群規(guī)模，避免算法早熟收斂。利用自適應(yīng)群體劃分方法，計(jì)算出可行解群體，并采取全局跨鄰域搜索的方式，引導(dǎo)螞蟻向全局最優(yōu)解靠近，加快收斂速度。最后對解檔案進(jìn)行重排序，并利用局部跨鄰域的方式引導(dǎo)螞蟻在小范圍內(nèi)進(jìn)行細(xì)致搜索，提高收斂精度。通過對CEC2017測試函數(shù)在低維和高維情況下的對比實(shí)驗(yàn)，證明ANS-Ant算法在解決連續(xù)優(yōu)化問題時(shí)具有較好的尋優(yōu)能力和穩(wěn)定性，能有效克服經(jīng)典蟻群算法容易陷入局部最優(yōu)的缺點(diǎn)。