基于跨鄰域搜索的連續域蟻群優化算法

夏 媛，李 俊，周 虎

(1.武漢科技大學計算機科學與技術學院，湖北 武漢，430065；2. 武漢科技大學智能信息處理與實時工業系統湖北省重點實驗室，湖北 武漢，430065)

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

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

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

1 連續域蟻群優化算法

在連續空間尋優問題的求解中，解空間是以區域性方式而不是離散點來表示的，因此不能采用經典的離散型蟻群算法。與離散型蟻群優化算法不同的是，連續域蟻群算法的優化目標是所求問題的目標函數值達到最優，因此在信息素的更新方式和狀態選擇規則中均有所不同，其主要是根據目標函數值來更新信息素濃度，以微調的前進方式來代替狀態選擇規則。

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

2 ANS-Ant算法

2.1 自適應種群劃分

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

(1)

式中：p為優解的種群數量；h為劣解的種群數量；kmax為最大迭代次數；k為當前迭代次數。

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

2.2 自主選擇學習算子

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

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

(2)

式中：Xnew為較差解經過自主選擇學習后產生的新解；Xbad為h個較差解；Y為上次迭代產生的p個較優解中任意一個。該算子旨在讓每一個劣解在較優解群體中自主選擇對應的較優個體進行學習，這樣能在一定程度上擴大種群多樣性，避免產生局部最優。

2.3 跨鄰域搜索機制

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

2.3.1 全局搜索

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

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

(3)

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

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

2.3.2 局部搜索

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

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

(4)

式中：Xbest是經過局部搜索后產生的新解；Xobject為指導解；G(0,δ2)同為高斯分布因子，旨在局部范圍內進行范圍廣、波動幅度較小的搜索?？玎徲蚓植克阉骺梢蕴岣咚惴ǖ氖諗烤?，并使其具有較好的開發能力。

2.4 ANS-Ant算法基本步驟

步驟1初始化NP個解并排序。

步驟2針對排序后的解，根據式(1)自適應地選出當前的較優解組和較差解組。

步驟3根據式(2)提出的自主選擇學習算子，讓較差解組中的每個個體自主選擇較優解組中的解進行學習。

步驟4在執行了較差解組的處理的基礎上，利用式(3)針對迭代產生的較優解組進行全局跨鄰域范圍內的搜索，更新較優解組。

步驟5將經過步驟3和步驟4處理后的解檔案進行重排序，并選取最好的解作為指導解。

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

步驟7若達到最大迭代次數，則選取解檔案中的最優值為最終解，否則返回步驟2。

3 算法測試及結果分析

3.1 測試函數

選擇CEC2017收錄的29個標準測試函數[15]檢驗改進算法ANS-Ant的有效性和適用性(函數f2穩定性不好，被CEC2017排除，本文不對其進行測試)，具體定義如表1所示，其中f1、f3

表1 標準測試函數

為單峰函數，f4～f10為簡單多峰函數，f11～f20為混合函數，f21～f30為復合函數。

3.2 實驗參數

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

3.3 實驗結果及分析

3.3.1 收斂精度

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

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

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

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

(a)單峰函數f3

(b)簡單多峰函數f8

(c)混合函數f15

(d)復合函數f21

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

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

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

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

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

續表3

函數編號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為各算法在高維情況下求解測試函數的收斂曲線，同樣各取單峰函數、簡單多峰函數、混合函數和復合函數中的一種作為示例。

(a)單峰函數f3

(b)簡單多峰函數f6

(c)混合函數f11

(d)復合函數f21

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

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

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

3.3.2 收斂速度

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

表4 預設收斂精度VTR

表5 預設收斂精度下各算法的評估次數

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

4 結語

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