基于分級思想的多級蟻態蟻群改進算法

劉書勇，劉 峰

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

0 引言

蟻群優化(Ant Colony Optimization, ACO)算法是由Dorigo等[1]從自然界螞蟻覓食中獲取靈感而提出的一種啟發式全局優化算法,廣泛地應用于旅行商問題(Travelling Salesman Problem,TSP),但其容易陷入局部最優且存在收斂速度較慢等問題。由于其具備較強的魯棒性,易與其他算法相結合[2],因此作為眾多學者的算法改進的焦點。劉雨青等[3]對信息素更新策略進行改進,張玉茹等[4]對路徑規劃算法進行改進,基于傳統ACO算法進行更新。Stodola等[5]融合模擬退火思想,提高解的質量。Zhang等[6]采用反向路徑構造方法,避免陷入過早成熟現狀,但增加了信息素更新的復雜性。徐巍等[7]融入遺傳算法突變因子強化傳統蟻群的局部變異性。陳琴等[8]引入禁忌搜索算法思想,增強全局搜索能力。Caprio等[9]引入模糊數,切換概念進行權重優化,以快速達到收斂狀態,但是在蟻群的分工協作上略有不足。馮振輝等[10]引入了一種不依賴于信息素搜索路徑的擴展螞蟻,實現抑制算法向局部最優的收斂速度,但降低了算法搜索的速度。文獻[11-12]將蟻群劃分多級蟻態,以提高優質解與非優質解路徑上的信息素濃度差距,證明了分級思想應用于ACO的可行性。

基于此,本文引入人工蜂群(Artificial Bee Colony,ABC)分級思想[13],提出了一種多級蟻態蟻群改進(Multistage State Ant Colony Optimization,MSACO)算法,主要工作如下:

①基于適應度算子將蟻群分為王蟻、被雇傭蟻與非雇傭蟻;

②提出一種限制因子動態平衡蟻態;

③引入加權因子改進信息素更新模型;

④提出一種應用于局部優化的鄰域因子與固定鄰域優化算法。

1 ACO算法

真實世界中的螞蟻在移動中會釋放信息素,當遇到未經過的岔路口時會隨機選擇,并釋放與路徑長度有關的信息素[14]。隨著移動次數的增加,蟻群會偏向于選擇信息素濃度高的方向進行移動,意味著選擇該路徑會經過更少的路程,因此信息素濃度與路徑長度成反比。后來的螞蟻再次路過該岔路口時,會有更大的幾率被選擇,最優路徑上的信息素濃度逐漸增大,較其他路徑上的信息素濃度差距變大,直到找到全局最優的覓食路徑。

針對于TSP,蟻群算法對基本的覓食行為進行改進。初始化信息素濃度如式(1)所示:

(1)

式中:τij(0)為節點i到節點j邊上的信息素初始濃度,τ0為信息素濃度常數。

設定禁忌表強制螞蟻進行合法周游,在每次迭代開始前,會隨機將m只螞蟻隨機分配在n個節點上作為初始位置。隨后進行算法核心的迭代操作,可概括為兩部分:路徑構建與信息素更新。

1.1 路徑構建

ACO算法模型規定在每次迭代中,當前第k只螞蟻從節點i移動的下一個節點j的是基于偽隨機概率規則的輪盤賭算法選擇的,如式(2)所示:

(2)

本文提出的MSACO算法延用了ACO用于構建路徑時所采用的偽隨機規則,其優勢在于:在算法初期,基于路徑上的信息素濃度與期望啟發式,可以快速構建有效路徑,通過修正啟發式因子改變信息素對路徑規劃的引導能力,α值越大,信息素濃度對路徑選擇起著越關鍵的作用;通過修正期望啟發因子改變期望度對于路徑規劃的引導能力,β值越大,螞蟻會以越大的概率轉移到距離短的城市,如果節點過于密集則適當增大期望啟發因子,會生成更加優質的路線。

1.2 信息素更新

ACO算法模型規定在算法每次迭代后都會對所有路徑上的信息素濃度進行更新,包括信息素揮發與信息素補充,如式(3)～式(4)所示:

依據不同的增量方式可以將信息素更新模型劃分為:蟻周模型(Ant-Cycle Model)、蟻量模型(Ant-Quantity Model)與蟻密模型(Ant-Density Model)這3類[15]。

①蟻周模型:在第k只螞蟻完成一次迭代操作之后,會對線路上所有路徑上的信息素濃度進行更新,信息素增量與本次搜索的整體路線有關,因此屬于全局信息更新,如式(5)所示:

(5)

②蟻量模型:在蟻群前進過程中每完成一步移動之后會對單步路徑上的信息素濃度進行更新,信息素增量與單步路徑有關,屬于局部信息更新,如式(6)所示:

(6)

③蟻密模型:與蟻量模型類似,也屬于局部信息更新,但是信息素增量固定,如式(7)所示:

(7)

2 MSACO算法

2.1 引入分級策略

2.1.1 ABC算法分級策略

ABC算法是由Karaboga等[16]提出的一種新穎的基于群智能的全局優化算法,其直觀背景來源于蜂群的采蜜行為,蜜蜂根據各自分工執行相應工作,并實現信息的共享和交流,從而找到問題的最優解[17]。該算法的三大角色,分別為蜜源、被雇傭的蜜蜂和未被雇傭的蜜蜂。蜜源即為吸引蜜蜂采蜜的地方,相當于優化問題的可行解。被雇傭的蜜蜂也稱為引領蜂。有多少個蜜源就對應著多少個引領蜂。引領蜂具有記憶功能,將自己搜索到的蜜源信息進行存儲,并以一定的概率分享給跟隨蜂。非雇傭蜂有2種,分別為偵察蜂和跟隨蜂,偵查蜂會在搜索空間中尋找新蜜源,而跟隨蜂會隨機選擇引領蜂的蜜源進行跟隨或者進行局部優化。

2.1.2 引入適應度分級算子

傳統ACO算法中的蟻群個體根據式(2)構建路徑、式(3)更新信息素,并不能充分體現啟發式算法的多樣性,因此本文通過引入ABC算法的分級策略,發揮引領蜂即被雇傭蜂能夠尋找優良蜜源的作用,采用非雇傭蜂偵查新蜜源跳出局部最優的策略,二者相輔相成,構建完整的蜂巢系統。

基于以上思想,本文將傳統蟻群劃分為被雇傭蟻、非雇傭蟻與王蟻。被雇傭蟻對應被雇傭蜂,采用ACO路徑規劃策略尋找路徑,集中優勢路徑使用高濃度動態的信息素增量進行更新策略,用以加速算法的收斂速度。非雇傭蟻對應非雇傭蜂,負責偵查新食物源,使算法能夠盡量避免陷入局部最優的狀態,保證了算法的多樣性。王蟻用以累計保存最優解,采用最高加權系數的信息素更新策略,用以突出最優解路徑與非最優解路徑的上的信息素濃度的差距,能夠加快算法的收斂速度。在ABC算法中,基于適應度算子計算目標函數權值對應的適應度fit用以判斷該蜜源的優劣,本文借鑒適應度的概念,將其作為蟻群分級的指標,用以平衡算法的多樣性與收斂速度。適應度算子如式(8)～式(9)所示:

式中:distancek為當前第k只螞蟻探索路徑的歐氏距離,distanceaverage為蟻群探索的所有路徑的平均距離,fitk為當前第只螞蟻探索的路徑適應度,采用指數級擴展,這種變換的基本思想來源于模擬退火(Simulated Annealing,SA)[18]過程,經變換后fitk的大小范圍鎖定在(0,1),使得復制的強度就趨向于那些具有最大適應度的個體。

根據fitk將蟻群劃分為3個等級typek,適應度最高的即為本次迭代的最優解,授予其王蟻身份king,在剩余螞蟻分配中,本文提出一種限制因子LIMIT,適應度在LIMIT和最高適應度fitmax范圍內時授予其被雇傭蟻身份hired,其余均為非雇傭蟻身份non-hired。

要注意如果LIMIT值過小,則被雇傭蟻數量占比更多,在初期算法未收斂,由于被雇傭蟻采用ACO路徑規劃策略產生食物源,非雇傭蟻數量過少,使算法喪失了一部分局部優化策略,可能會使得收斂速度變慢。如果LIMIT值過大,則非雇傭蟻占比更多,被雇傭蟻數量過少會導致算法獲取有效解迅速變少從而使算法快速達到假收斂狀態,喪失了算法的動態多樣性。因此LIMIT數值選擇尤為重要,本文通過大量的實驗驗證,當LIMIT=0.37時,能夠有效地平衡在算法初期未收斂與算法中期已收斂2種狀態下的多級蟻群的身份,此時算法效果最優。

2.1.3 動態多級的概念

在蟻群執行完每次迭代操作以后都會對其身份進行重新分配。王蟻身份特殊,數量唯一,且用于保存最優解,在每次迭代操作中都會有固定數量的王蟻,所以適應度算子主要用來分配被雇傭蟻與非雇傭蟻身份。在算法初期路徑規劃當中,要盡可能地探索新的路徑即食物源,此時算法處于萌初狀態,所以要分配較多的被雇傭蟻用來探索新的食物源作為參考,以被雇傭蟻為主,非雇傭蟻為輔。在算法逐漸成熟即逐漸收斂時,被雇傭蟻們尋找的路徑逐漸趨于相同,被雇傭蟻尋找的路徑將再無意義,因為此時已經獲取到當前能夠獲取到的假最優解,要盡量分配較多的非雇傭蟻用于對現有食物源進行局部優化,以非雇傭蟻為主,被雇傭蟻為輔,使得本算法在信息素濃度成熟的狀態下能夠快速地尋找更優解并且使算法更快地跳出假收斂狀態。要始終動態維持多級蟻態的蟻群是本文進行尋找最優解策略的關鍵,以下動態分級具體步驟:

①當iteration=1時,采用ACO算法的路徑規劃策略作用于整體蟻群構建路徑,計算相應適應度,對蟻群進行分級,并進行信息素更新;

②當iteration>1時,王蟻與被雇傭蟻仍然會沿用ACO算法的路徑規劃策略進行構建路徑行為,通過輪盤賭算法產生食物源。非雇傭蟻會隨機選擇王蟻與被雇傭蟻生成的食物源,進行局部優化生成產生一些新的食物源,采用貪婪思想選擇最優解作為該非雇傭蟻的食物源。在所有非雇傭蟻執行完尋找新食物源的操作后,蟻群中所有螞蟻全部獲取了新的食物源, 重新計算相應的適應度,重新為其賦予相應的身份,再進行信息素更新,執行下一次迭代,直到迭代結束得到最優解。

2.2 改進信息素更新模型

為了特化多級蟻態蟻群對算法的導向作用,本文借鑒了精英蟻群的信息素加權更新策略[19],并引入了適應度算子,提出了一種改進的信息素更新模型,如式(10)所示:

由式(10)可知,本文算法的信息素更新策略采用全局更新模式,基于加權因子與適應度算子用以區分最優解與優質解,僅更新王蟻與被雇傭蟻偵查路徑上的信息素濃度用以擴大優質解與非優質解的信息素濃度差距,拋棄非優質解僅保留優質解能夠加快尋找最優解的速度。雖然可能會因此導致算法更快地陷入局部最優,但是非雇傭蟻的存在正是為了能夠使算法快速跳出這種狀態而設計,這也是人工蜂群的思想。非雇傭蟻并不增加信息素而僅僅進行局部優化,同時王蟻與被雇傭蟻的路徑規劃并沒有因為非雇傭蟻偵查的非優質解導致的信息素濃度差異而受到影響,從而維持了算法的多樣性。

雖然在初期進行信息素更新時能夠迅速拉開差距,但是隨著信息素揮發,信息素濃度趨于平整,在節點數量多的區域內尤為嚴重,會使得此領域內無法進入收斂狀態,因此額外加入加權因子μ1、μ2,還需要合理配置μ1、μ2的比例。如果比例過大,會使得當前最優解上的信息素濃度較其他路徑上的信息素濃度過于夸張,算法快速進入到收斂階段,影響算法的最優解精度。如果比例過小,會使得加權改進不明顯反而會減緩算法收斂速度。因此,本文經過大量實驗驗證,當μ1=1.5、μ2=1時算法效果最好,故作為本文改進信息素更新策略的加權因子。

2.3 引入固定鄰域優化算法

本文在針對局部優化操作提出了一種融合2-opt、3-opt和插入算子的固定鄰域優化算法。

2.3.1 變異算子

① 2-opt算子

在一條長度為n的節點序列中隨機找到2個不同的節點x1與x2,逆轉x1與x2之間的節點序列并保持其他段節點序列順序保持不變,得到一條新節點序列即為所求,2-opt路徑重組過程如圖1所示。

圖1 2-opt路徑重組過程Fig.1 2-optimization path reorganization process

② 3-opt算子

在一條長度為n的節點序列中隨機找到3個不同的節點x1、x2、x3切開重組,產生8種新的節點序列, 再采用貪用貪婪思想選擇最優解即為所求,3-opt路徑重組過程如圖2所示。

圖2 3-opt路徑重組過程Fig.2 3-optimization path reorganization process

③ 插入算子

在長度為n的節點序列中隨機找到2個不同的節點x1、x2,其中規定x1序列小于x2的序列,將x2插入到原有的序列后的新節點序列即為所求,插入算子路徑重組過程如圖3所示。

圖3 插入算子路徑重組過程Fig.3 Insertion operator path reorganization process

2.3.2 固定鄰域概念

本文提出的算法規定被雇傭蟻會隨機選擇王蟻與被雇傭蟻尋找的食物物源進行局部優化偵查出更加優質的食物源。傳統的變異算子作用域是整個區域,如果區域很大,雖然在一定程度上增加了被選擇節點的組合方式,增加了變異幾率,但是因為范圍太廣而導致變異的有效率很低。為了進一步提高產生較為優質的解,本文提出一種固定鄰域優化算法。

非雇傭蟻在隨機偵查的食物源中隨機找到一個節點作為鄰域中心點,以固定半徑范圍,尋找相對鄰域中心點的有效偵查點,將其作為固定鄰域優化算法的搜索解空間,并采用基于3種變異算子的算法對其進行優化,在通過貪婪思想選擇最優解作為該非雇傭蟻的食物源。

基于此,本文提出了一種鄰域因子ε為固定鄰域半徑,采用測試旅行商問題庫(TSP Libarary, TSPLIB)中的公開數據集bayg29、oliver30、att48、eil51、eil76,eil101和ch130用以驗證,本文算法測試數據集相應的ε值如表1所示。

表1 實驗中使用的TSPLIB數據集及其ε值Tab.1 The TSPLIB datasets and ε values used inthe experiment

2.3.3 局部優化功能組成

本文提出的固定鄰域優化算法由兩部分功能組成:

① 鄰域搜索。隨機確定某個節點作為鄰域搜索中心點,基于表1對應ε為半徑尋找有效點。

② 組合變異算子優化。根據有效點數量采取不同的變異算子,若數量為1即有效半徑內除中心點外沒有其他的有效點,則直接返回不進行局部優化,若數量大于或等于2,則進行插入算子變異優化,且數量等于2時,額外進行2-opt算子變異優化,其他情況下,進行3-opt算子變異優化。

2.4 MSACO算法流程

以下為本文MSACO算法的執行步驟:

步驟1:初始化相應參數:α、β、τ、η、ρ、Qm、iteration、iterationmax、LIMIT、μ1、μ2、ε;

步驟2:執行第一次迭代,將m只螞蟻隨機放置在m個節點;

步驟3:按照式(2)構建原始食物源;

步驟4:按照適應度分級算子式(8)、式(9)計算相應的適應度,對螞蟻進行分級,按照式(10)進行信息素更新操作;

步驟5:執行第一次迭代,將王蟻和被雇傭蟻隨機放置在m個節點;

步驟6:王蟻和被雇傭蟻按照式(2)構建食物源;

步驟7:非雇傭蟻隨機選擇一條王蟻或被雇傭蟻偵查的食物源;

步驟8:非雇傭蟻采用本文提出的固定鄰域優化算法對該食物源進行局部優化,得到最優解將其做為該非雇傭蟻的食物源;

步驟9:按照式(8)～式(9)計算所有等級螞蟻偵查食物源的適應度;

步驟10:按照適應度分級算子對螞蟻進行動態重新分級,按照式(10)進行信息素更新操作;

步驟11:本次迭代操作結束,iteration自增1。若iteration

3 實驗測試分析

3.1 實驗環境與參數設定

本實驗的硬件環境:CPU為Intel(R) Core(TM) i7-9750H CPU @ 2.60 GHz 12線程;軟件環境:Windows 10平臺PyCharm 2021.3.3本文算法基于以上配置進行實驗,對公開TSPLIB庫中的bayg29、oliver30、att48、eil51、eil76、eil101和ch130共計7個不同規模的數據集進行仿真求解。與傳統ACO算法、ABC算法以及文獻[4]提出的一種結合貪婪算法思想的蟻群改進(Greedy Algorithm-Ant Colony Optimization,GA-ACO)算法進行對比,在公共參數設定方面與文獻[4]保持一致,即α=1.0、β=3.0、ρ=0.5、m=城市數量。由于本文對信息素更新策略進行優化,所以在Q取值上與ACO和文獻[4]不同,本文算法中Q=2,其他算法中Q=106。以下是本文提出一些特殊因子的參數設定:適應度加權因子μ1=1.5、μ2=1.0,鄰域因子ε如表1所示。文獻[4]中的特殊因子的參數設定與文獻[4]所提出的數值保持一致:間接期望啟發式因子γ=3。ABC算法設定蜜源nPop=城市數量。采用以上參數設定方式將取20次連續實驗,且規定迭代上限iterationmax=500,作為研究結果進行分析驗證。

3.2 實驗結果分析

實驗數據如表2所示,其中各種數據集理論最優非整數解均來源于文獻[20]。可以看出在小規模的數據集bayg29、oliver30和att48中,MSACO與GA-ACO處理能力相差不大,但從平均誤差來看MSACO略優于GA-ACO,二者都能夠獲取到理論最優解,均優于傳統ACO算法和ABC算法。在處理eil51數據集中,GA-ACO平均誤差較MSACO少0.11%,可以證明貪婪思想更適用于這種節點比較擁擠的小型數據集。但隨著數據集的節點數量增加,GA-ACO處理這種中型規模數據集TSP能力不足,eil76、eil101和ch130均未到達最優解且距離較大。而本文提出的MSACO在這3類數據集均能達到理論最優解,且所有比較指標均優于GA-ACO。在eil101數據集能夠收斂到640.211 6,較理論最優解減少0.33%,ch130數據集能夠收斂到6 110.722 2,較理論最優解減少了0.002%。相應的平均誤差均小于1%,比其他對比算法更加穩定。由此可以看出本文提出的MSACO在處理中小型TSP時,明顯優于傳統ACO算法與GA-ACO算法,充分證明了該算法的有效性。傳統ABC算法在處理小數據bayg29、oliver30時可以獲取理論最優解,但隨著數據集規模增大,節點數量增多,獲取最優路線的效率也在同步下降,誤差均高于2%,偵查蜂無法獲取有效突變蜜源,導致算法無法跳出局部最優。而GA-ACO算法采用本文提出的固定鄰域優化算法,可以有效地避免上述問題,與ABC算法相比最優解提升約3%,平均值減少約3%。

表2 ACO、ABC、GA-ACO、MSACO在不同數據集下的最優解與平均值數據對比Tab.2 Comparison of optimal solutions and average values of ACO, ABC,GA-ACO and MSACO under different datasets

本文MSACO算法在各種數據集得到的最優路線如圖4所示,所有路線均達到理論最優路線標準,其中eil101、ch130均超越了理論最優路線的最短非整數距離。MSACO、GA-ACO、ACO以及ABC在各種數據集下獲取最優解的對比收斂曲線圖如圖5所示。總體來看,傳統ACO算法在本次對比試驗的參數設定下并沒有達到收斂狀態,因此并不作為對比試驗分析的重點,僅取其遍歷中獲取過的最優解作為全局最優解。迭代次數最大值為500,ABC算法依據分級更新蜜源機制平均300代內收斂,而MSACO算法平均100代以內就趨近于收斂狀態,收斂曲線趨于平滑曲線,其初始構建路徑距離普遍較GA-ACO算法過大,這是因為GA-ACO算法采用貪婪思想改進路徑規劃算子,較MSACO采用的是傳統ACO規劃路徑算子能夠有效地在初始階段獲取更為優質的路線。雖然初始路徑更優,但也在一定程度上降低了路徑的變異性。在100代以內,MSACO算法能夠快速地搜索更為優質的路徑,在100～200代,MSACO與GA-ACO均趨于成熟,如何快速地跳出局部最優則是通過各自的局部優化算法實現。GA-ACO的收斂曲線變化跨度大且更新迭代間隔次數較長,而MSACO收斂曲線趨于平滑,路徑更新的迭代周期更短,這是因為引入固定鄰域思想所以才能更快跳出局部最優的假收斂狀態,借此驗證了本文提出的固定鄰域優化算法的有效性。在200～500代,GA-ACO普遍沒有變化,而MSACO則可以進一步優化路徑。在數據集eil76、eil101和ch130中,此時算法以非雇傭蜂為主,雖然減少了算法的多樣型,但針對已經成熟的算法,采用不考慮信息素濃度與路徑的影響的固定鄰域優化算法能夠進一步優化局部信息。

圖4 MSACO在各種數據集下的最優路徑展示圖Fig.4 Optimal path of MSACO under various datasets

(g)ch130

ACO、ABC、GA-ACO和MSACO在所有測試集中的最優解的算法收斂運行時間與收斂迭代次數如表3所示。由于傳統ACO算法基于本文對比實驗參數設定下并沒有進入收斂狀態,所以以默認迭代次數為最高迭代次數、運行時間為迭代500代的總體時間。

表3 ACO、ABC、GA-ACO和MSACO在不同數據下達到收斂最優解時的迭代次數與運行時間 Tab.3 Iteration times and running time when ACO,ABC,GA-ACO and MSACO reach the convergentoptimal solution under different data

從總體來看,MSACO算法在各個參數指標均優于ACO算法和ABC算法,以下對比以GA-ACO、MSACO為主。在應用于小型數據集bayg29、oliver30和att48,MSACO較GA-ACO相比運行時間降低約50%、迭代收斂次數減少約43%。應用與中小型數據集eil51、eil76,MSACO較GA-ACO相比運行時間降低約60%、迭代收斂次數減少約50%。應用于中大型數據集eil101、ch130,雖然MSACO的收斂迭代次數明顯高于GA-ACO的收斂迭代次數,但從表3可知MSACO獲得的最優解均優于GA-ACO的最優解,而且迭代收斂時間與GA-ACO相比約減少超過50%,這是因為在算法進入成熟后期,非雇傭蟻數量比重最大,采用本文提出的固定鄰域優化算法對王蟻的最優路徑進行局部優化,因此在算法后期依然能保持算法的變異性。而GA-ACO隨著數據集規模的增大,運行時間也隨之快速增大,這是因為在該算法中每一只螞蟻均要執行路徑規劃與局部路徑優化操作,雖然采用了結合貪婪思想的改進路徑規劃模式,在算法前期能夠快速構建更為優質的初始路徑所以在小規模數據集中可以快速有效獲取全局最優路徑,但是在中大型數據集中,會嚴重增加運行時間,而本文提出的MSACO算法則是引入適應度算子動態分配蟻群的身份與數量,各種螞蟻各司其職,因此能夠大大減少運行時間。基于此,數據集規模越大,運行時間的優化效率越趨于明顯。

4 結束語

本文基于ABC分級思想將蟻群劃分為三蟻態蟻群。為平衡各級螞蟻身份,維持算法的多樣性,引入了適應度算子進行動態分級。為加強各級螞蟻對算法的導向作用,對信息素更新模型進行改進。在快速引導算法趨于收斂狀態期間,為避免算法陷入局部最優,引入了融合2-opt、3-opt和插入算子的固定鄰域優化算法。經過仿真TSP數據集,成功驗證了分級思想在蟻群算法中的實用性,加權改進信息素更新模型的適用性,局部尋優的有效性。下一步的研究方向包括:

①對路徑規劃算子進行改進,使其能夠在初期便能獲取到更為優質的路徑,進一步優化收斂曲線;

②在維持原有求解能力的情況下,進一步減少算法的運行時間、獲取最優解的迭代次數。