蔣浩辰，查正清，段 云

(1.北京礦冶研究總院，北京 100160；2.礦冶科技集團(tuán)有限公司，北京 100160)

目前地下礦山開采存在自動化及智能化程度較低、工人的作業(yè)環(huán)境較差、開采效率較低等問題。為保障作業(yè)人員安全，將工業(yè)機(jī)器人用于地下礦山掘進(jìn)面的對孔裝藥作業(yè)中，而地下礦山掘進(jìn)面對孔裝藥效率在一定程度上影響開采效率。裝藥路徑規(guī)劃問題可簡化為TSP問題，常被用于TSP問題求解的智能優(yōu)化算法包括遺傳算法、粒子群算法、蟻群算法等。

20世紀(jì)90年代，意大利學(xué)者M(jìn)ARCO DORIGO[1]首次提出蟻群算法(Ant Colony Optimization，ACO)的基本模型，并將其用于TSP求解。1996年，MARCO DORIGO等[2]發(fā)表文章詳述蟻群優(yōu)化算法的理論基礎(chǔ)及數(shù)學(xué)模型。

經(jīng)過近三十年的研究，蟻群優(yōu)化算法已被廣泛用于TSP問題求解、機(jī)器人路徑規(guī)劃、控制系統(tǒng)參數(shù)優(yōu)化等領(lǐng)域。蟻群優(yōu)化算法應(yīng)用范圍廣泛，但存在參數(shù)多且不易確定、求解效率低、易收斂到局部最優(yōu)解等缺點(diǎn)。國內(nèi)外學(xué)者針對基本蟻群優(yōu)化算法存在的缺點(diǎn)提出大量改進(jìn)策略，并取得豐碩研究成果。

文獻(xiàn)[3-6]對信息素濃度的更新策略進(jìn)行改進(jìn)，算法的收斂速度與精度得到提升；文獻(xiàn)[7-8]通過對蟻群算法中的三個參數(shù)α、β和ρ優(yōu)化求解，提升蟻群算法求解性能；文獻(xiàn)[9]在ACS基礎(chǔ)上加入一個偽隨機(jī)因子，通過調(diào)節(jié)該因子平衡算法前期及后期的搜索能力與收斂速度，并引入精英螞蟻，算法收斂速度與多樣性得到提高。文獻(xiàn)[10]將蟻群算法與禁忌搜索算法相結(jié)合作為局部搜索解決TSP問題，利用一個存儲結(jié)構(gòu)來記錄已搜索局部路徑，防止搜索到的局部路徑在解集空間中再次被搜索，改進(jìn)算法具有較好的全局搜索能力。

為避免因參數(shù)選取不當(dāng)導(dǎo)致算法性能較差的情況，提高蟻群優(yōu)化算法收斂速度的同時避免算法過早收斂于局部最優(yōu)解的現(xiàn)象，對基本蟻群算法做如下改進(jìn)：將粒子群算法用于蟻群算法的參數(shù)求解，通過改進(jìn)粒子群算法的慣性權(quán)重、蟻群算法中引入自適應(yīng)信息素?fù)]發(fā)因子ρ、改進(jìn)信息素濃度更新策略，使算法具有更強(qiáng)的全局搜索能力，提升算法求解性能。最后以TSPLIB測試庫中部分問題為測試對象，將本文改進(jìn)算法、基本蟻群算法以及最大最小蟻群算法分別用于求解問題，并比較求解結(jié)果以證明改進(jìn)算法的求解性能。

1 基于粒子群算法求解蟻群算法參數(shù)

參數(shù)選取影響蟻群優(yōu)化算法求解性能，蟻群算法參數(shù)中，信息素啟發(fā)式因子α和期望值啟發(fā)因子β是一對關(guān)聯(lián)性很強(qiáng)的參數(shù)：蟻群算法的全局尋優(yōu)性能，要求蟻群的搜索過程具有較強(qiáng)的隨機(jī)性；蟻群算法的快速收斂性能，要求蟻群的搜索過程具有較高的確定性。兩參數(shù)對蟻群算法性能的影響和作用是相互配合、密切相關(guān)的，算法要獲得最優(yōu)解，就必須在這二者之間選取一個平衡點(diǎn)，才能避免在搜索過程中出現(xiàn)過早停滯或陷入局部最優(yōu)等情況。

1.1 粒子群算法求解蟻群算法參數(shù)過程

粒子群算法是通過模仿鳥群覓食行為而提出的，其具有模型簡單、收斂速度快、設(shè)置參數(shù)少、容易與其它算法融合使用等特點(diǎn)，可以對蟻群算法的參數(shù)進(jìn)行優(yōu)化。因此本文采用粒子群算法求解蟻群算法中的信息素啟發(fā)因子α、期望值啟發(fā)因子β。

粒子群算法求解蟻群算法參數(shù)的基本思想為：隨機(jī)生成N個粒子，每個粒子在空間中對應(yīng)一個二維坐標(biāo)，坐標(biāo)中兩個值分別對應(yīng)蟻群算法中的α、β兩個參數(shù)；將每個粒子的二維坐標(biāo)反饋給蟻群算法，并用基于這組參數(shù)的蟻群算法求解TSP，所求得的最短路徑長度作為粒子群算法的目標(biāo)函數(shù)；粒子群算法根據(jù)目標(biāo)函數(shù)求出個體最優(yōu)解Pbest和群體最優(yōu)解Gbest，并依據(jù)Pbest和Gbest更新粒子的位置與速度；為提高粒子群算法的收斂速度，需確定合適的粒子運(yùn)動范圍和最大速度；最終所有粒子飛向同一個點(diǎn)，該點(diǎn)的坐標(biāo)即為蟻群算法參數(shù)。粒子群算法求解蟻群算法參數(shù)流程圖如圖1所示。

圖1 粒子群算法求解蟻群算法參數(shù)流程圖Fig.1 Particle swarm optimization algorithm to solve ant colony algorithm parameter flow chart

粒子群算法求解蟻群算法參數(shù)的具體步驟如下。

步驟1：設(shè)計粒子群參數(shù)，國內(nèi)外學(xué)者通過反復(fù)實(shí)驗(yàn)發(fā)現(xiàn)蟻群算法參數(shù)α的最佳取值范圍為[1，2]，β的最佳取值范圍為[4，9]，兩個參數(shù)取值范圍對應(yīng)粒子位置坐標(biāo)的取值范圍，粒子速度的取值范圍設(shè)為位置范圍的十分之一。隨機(jī)生成N個二維粒子X1，X2，…，Xn。

步驟2：將每個粒子的坐標(biāo)作為蟻群算法一組參數(shù)，用基于這組參數(shù)的蟻群算法求解TSP問題。

步驟3：將所得路徑長度作為目標(biāo)函數(shù)，根據(jù)目標(biāo)函數(shù)更新個體最優(yōu)解Pbest和群體最優(yōu)解Gbest。

步驟4：根據(jù)式(1)和式(2)更新粒子的速度和位置[12]。

Vi(t+1)=ωVi(t)+C1r1(Pbesti(t)-Xi(t))+C2r2(Gbesti(t)-Xi(t))

(1)

Xi(t+1)=Xi(t)+Vi(t+1)

(2)

式中：ω為粒子運(yùn)動慣性權(quán)重；r1、r2為[0，1]區(qū)間的隨機(jī)數(shù)；t為當(dāng)前迭代次數(shù)；Pbesti(t)為當(dāng)前迭代中粒子個體的最優(yōu)位置；Gbesti(t)為當(dāng)前迭代中粒子全局的最優(yōu)位置；Vi(t)為當(dāng)前迭代中粒子運(yùn)動速度；Xi(t)為當(dāng)前迭代中粒子位置；C1、C2為常數(shù)。

1.2 粒子群算法改進(jìn)

粒子群速度更新公式中，ω為非負(fù)數(shù)，其表示前一時刻粒子運(yùn)動速度對后一時刻運(yùn)動速度的影響程度。當(dāng)ω取較大值時，后一時刻運(yùn)動速度受前一時刻運(yùn)動速度影響較大，算法具有較強(qiáng)的全局搜索能力；ω取值較小時，后一時刻運(yùn)動速度受前一時刻運(yùn)動速度影響較小，算法具有較強(qiáng)的局部搜索能力。通過調(diào)整ω值大小可使算法跳出局部最優(yōu)解。

史峰等[11]對具有自適應(yīng)變化ω的粒子群算法性能進(jìn)行分析，提出4種不同ω取值方法并對多組函數(shù)求解，比較所得解的平均值、陷入次優(yōu)解次數(shù)及求得最優(yōu)解的次數(shù)。分析可知，慣性權(quán)重ω取為常數(shù)時，粒子群算法具有較快的收斂速度，但算法后期易因收斂到局部最優(yōu)解而停滯；采用ω自適應(yīng)變化時，算法前期收斂速度較慢，但全局搜索能力較強(qiáng)，求解精度較高。

本文采用式(3)計算動態(tài)變化ω慣性權(quán)重。

(3)

式中：i為當(dāng)前迭代次數(shù)；ωstart為初始慣性權(quán)重；ωend為最終慣性權(quán)重，一般取ωstart=0.9，ωend=0.4；Itermax為最大迭代次數(shù)；Lmax為本次迭代最長路徑長度；Lmin為本次迭代最短路徑長度。

本文中給出的動態(tài)變化ω慣性權(quán)重具有以下特點(diǎn)：

1)將權(quán)重值的取值范圍設(shè)定在[0.4，0.9]，使上一時刻速度對當(dāng)前速度影響適中。

2)算法在循環(huán)迭代初期，粒子以較高的速度運(yùn)動，算法更容易搜索到全局最優(yōu)解所在區(qū)域；隨著算法循環(huán)迭代次數(shù)增加，逐漸降低粒子運(yùn)動速度，算法的局部搜索能力逐漸增強(qiáng)，易于搜索到全局最優(yōu)解。

3)將蟻群算法本次循環(huán)搜索到的最短路徑長度及最長路徑長度與ω慣性權(quán)重關(guān)聯(lián)，當(dāng)最短路徑長度越小于最長路徑長度時，表示粒子越接近最優(yōu)解，此時降低粒子運(yùn)動速度，提高算法局部搜索能力。

1.3 蟻群算法改進(jìn)

1.3.1 信息素?fù)]發(fā)因子ρ

信息素?fù)]發(fā)因子ρ可以影響蟻群算法的隨機(jī)搜索能力，在傳統(tǒng)蟻群算法中，ρ一般取為固定常數(shù)[12]。針對TSP求解，應(yīng)使算法在循環(huán)迭代初期具有更強(qiáng)的全局搜索能力，以獲得更多不同的可能解；隨著循環(huán)迭代次數(shù)增加，算法的局部搜索能力應(yīng)逐漸增強(qiáng)，以尋得最優(yōu)解。

本文采用自適應(yīng)變化信息素?fù)]發(fā)因子ρ，當(dāng)蟻群算法的迭代次數(shù)小于指定值，ρ的更新方式如式(4)所示。

ρ(NC+1)=

(4)

式中：NC為當(dāng)前迭代次數(shù)；NCset為設(shè)置的迭代次數(shù)；Iterbest為最優(yōu)解從初次求得至當(dāng)前未更新次數(shù)；Iterset為設(shè)置的最優(yōu)解未更新次數(shù)；ρmax為最大信息素?fù)]發(fā)因子；ρmin為最小信息素?fù)]發(fā)因子。

本文的信息素?fù)]發(fā)因子具有以下特點(diǎn)：

1)取值存在上下限，使信息素?fù)]發(fā)速度適中。

2)在算法迭代初期，信息素?fù)]發(fā)較快，蟻群隨機(jī)搜索能力較強(qiáng)，算法全局搜索能力得到提高；在算法迭代后期，信息素?fù)]發(fā)較慢，蟻群隨機(jī)搜索能力較弱，算法局部搜索能力得到提高。

3)算法長時間內(nèi)未發(fā)現(xiàn)更優(yōu)解時，適當(dāng)增加信息素?fù)]發(fā)速度，提高算法全局搜索能力。

1.3.2 信息素濃度更新策略

信息素濃度更新策略包括定值變化與自適應(yīng)變化，大部分學(xué)者在對信息素濃度自適應(yīng)變化時，只考慮每次迭代后求得數(shù)值解是否更優(yōu)，而未對問題的幾何特性加以約束[13-15]。本文以TSP為背景，搜索路徑長度最短的軌跡。以圖2中的A、B、C、D四個城市為例，由三角形兩邊之和大于第三邊定理可知：

DC+AB

(5)

AD+BC

(6)

圖2 四座城市間所有可能路徑Fig.2 All possible routes between the four cities

本文信息素濃度更新策略如下：

1)當(dāng)NCNCset且Iterbest

τij(NC+1)=(1-ρ)τij(NC)+Δτij(NC,

NC+1)

(7)

式中：τij為路徑ij上的信息素濃度。

2)當(dāng)NC>NCset，Iterbest≥Iterset且局部路徑不相交時：

(8)

式中：τmax為最大信息素濃度；k為常數(shù)，通過實(shí)驗(yàn)，本文取k=5。

3)NC>NCset，Iterbest≥Iterset且局部路徑相交時：

τij(NC+1)=τmin

(9)

式中：τmin為最小信息素濃度。

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

2.1 粒子群算法慣性權(quán)重改進(jìn)性能分析

本文用于測試算法的非線性函數(shù)為式(10)，目標(biāo)為求取函數(shù)在自變量[-2，2]間的極大值，函數(shù)圖形如圖3所示。

(10)

圖3 函數(shù)圖形Fig.3 Function graph

公式(11)至(13)為常用的慣性權(quán)重。

ω(k)=ωstart-k(ωstart-ωend)/Tmax

(11)

(12)

(13)

利用公式(11)至(13)及本文提出的公式(3)表示的慣性權(quán)重粒子群算法對非線性函數(shù)公式(10)求解，算法適應(yīng)度變化曲線如圖4所示，ω動態(tài)變化曲線如圖5所示。

圖4 適應(yīng)度變化曲線Fig.4 Fitness change curve

圖5 ω動態(tài)變化曲線Fig.5 ω dynamic curve

粒子群算法參數(shù)設(shè)置：粒子個數(shù)m=20，迭代次數(shù)N=300。每種不同ω取值方法運(yùn)行100次，并比較所得解的平均值、陷入次優(yōu)解次數(shù)和接近最優(yōu)解次數(shù)，分析其收斂精度和收斂速度等性能。已知函數(shù)最優(yōu)解為1.005 4，將大于0.847 7小于等于1.005 4的解視為接近最優(yōu)解，將0.847 7及更小的解視為陷入局部最優(yōu)的解。實(shí)驗(yàn)結(jié)果如表1所示。

表 1 4種慣性權(quán)重下的算法性能比較

分析圖4及表1可知，本文提出的慣性權(quán)重動態(tài)變化方法在前期變化較慢，取值較大，算法具有較強(qiáng)的全局搜索能力；后期慣性權(quán)重動態(tài)變化較快，算法具有較強(qiáng)的局部搜索能力，且算法收斂速度更快，獲得較好的求解結(jié)果。

2.2 本文改進(jìn)粒子蟻群算法求解性能分析

本文對蟻群算法的信息素?fù)]發(fā)因子和信息素濃度更新策略進(jìn)行改進(jìn)，為驗(yàn)證參數(shù)改進(jìn)對粒子蟻群算法性能的影響，基于MATLAB平臺，選取TSPLIB測試庫中的Oliver30、Eil51、Att48、Eil76作為測試數(shù)據(jù)，分別用基本蟻群算法、粒子蟻群算法、最大最小蟻群算法、信息素?fù)]發(fā)因子動態(tài)變化粒子蟻群算法、改進(jìn)信息素濃度更新粒子蟻群算法以及本文所提的改進(jìn)粒子蟻群算法求解50次，最大迭代次數(shù)均為1 000次，并分析求解結(jié)果，求解結(jié)果如表2至表5所示。

表2 Oliver30問題求解結(jié)果

表3 Eil51問題求解結(jié)果

表4 Att48問題求解結(jié)果

表5 Eil76問題求解結(jié)果

已知Oliver30整數(shù)最優(yōu)解為420，Eil51整數(shù)最優(yōu)解為426，Att48整數(shù)最優(yōu)解為33 522，Eil76整數(shù)最優(yōu)解為538。

由求解結(jié)果可知基本蟻群算法及粒子蟻群算法在對4種問題的50次求解中均未求得最優(yōu)解，最大最小蟻群算法僅在一種問題的50次求解中求得最優(yōu)解，而本文提出的改進(jìn)粒子蟻群算法在4種問題求解中均至少求得一次最優(yōu)解，最差解優(yōu)于其他幾種算法，平均求解精度較其他幾種算法高5%～9%。本文提出的基于動態(tài)變化信息素?fù)]發(fā)因子和信息素濃度更新策略蟻群算法在TSP問題求解上具有較好性能。

以Eil51問題為例，三種算法求解的平均距離和最短距離變化曲線如圖6至圖11所示。

圖6 基本蟻群算法求得路徑Fig.6 Path planning by ACO

圖7 基本蟻群算法求得平均距離與最短距離Fig.7 The average distance and minimum distance of path planning based on ACO

圖8 最大最小蟻群算法求得路徑Fig.8 Path planning by MMAS

圖9 最大最小蟻群算法求得平均距離與最短距離Fig.9 The average distance and minimum distance of path planning based on MMAS

圖10 改進(jìn)粒子蟻群算法求得路徑Fig.10 Path planning by improved PSO-ACO

圖11 改進(jìn)粒子蟻群算法求得平均距離與最短距離Fig.11 The average distance and minimum distance of path planning based on improved PSO-ACO

通過分析可知，基本蟻群算法與最大最小蟻群算法求得的最優(yōu)路徑中，均出現(xiàn)局部路徑交叉情況，沒能搜索到全局最優(yōu)解，且算法在200次迭代內(nèi)迅速收斂于局部最優(yōu)解；改進(jìn)粒子蟻群算法求得的最優(yōu)解路徑中，沒出現(xiàn)局部路徑交叉情況，信息素濃度自適應(yīng)調(diào)整，算法在后期能跳出局部最優(yōu)解，搜索到全局最優(yōu)解，缺點(diǎn)是收斂速度較慢。

2.3 模擬對孔實(shí)驗(yàn)

為驗(yàn)證本文設(shè)計裝藥路徑規(guī)劃算法對機(jī)器人掘進(jìn)面對孔裝藥效率的影響，在實(shí)驗(yàn)室中搭建模擬掘進(jìn)面對孔環(huán)境，實(shí)驗(yàn)環(huán)境如圖12所示。

圖12 實(shí)驗(yàn)環(huán)境Fig.12 Experimental environment

模擬掘進(jìn)面模型如圖13所示，模擬炮眼分布如圖14所示。分別利用基本蟻群算法與改進(jìn)粒子—蟻群算法對模擬掘進(jìn)面炮眼裝藥路徑進(jìn)行規(guī)劃，路徑規(guī)劃結(jié)果分別如圖15、16所示。對孔路徑總長及對孔耗時如表6所示。

圖13 模擬掘進(jìn)面建模Fig.13 Modeling of simulated driving face

圖14 模擬炮眼分布圖Fig.14 Simulated borehole distribution map

圖15 基于基本蟻群算法規(guī)劃裝藥路徑Fig.15 Charge path planning based on basic ant colony algorithm

圖16 基于自適應(yīng)粒子—蟻群算法規(guī)劃裝藥路徑Fig.16 Charging path planning based on adaptive particle ant colony algorithm

表6 對孔實(shí)驗(yàn)結(jié)果

由實(shí)驗(yàn)結(jié)果可知，針對實(shí)驗(yàn)中模擬掘進(jìn)面炮眼對孔路徑規(guī)劃，機(jī)器人根據(jù)蟻群算法規(guī)劃的裝藥路徑裝藥總時長79.1 s，根據(jù)本文提出算法規(guī)劃裝藥路徑裝藥總時長72.6 s，采用本文改進(jìn)算法所規(guī)劃的裝藥路徑較基本蟻群算法縮短約8%。利用本文改進(jìn)粒子—蟻群算法規(guī)劃所得裝藥路徑總長更短，機(jī)器人對孔效率得到提升。

3 結(jié)論

本文針對地下礦山掘進(jìn)面對孔裝藥路徑規(guī)劃問題，利用粒子群算法優(yōu)化蟻群算法中的部分參數(shù)，提出一種基于參數(shù)自適應(yīng)調(diào)整慣性權(quán)重及一種基于判斷局部路徑是否交叉自適應(yīng)更新信息素策略。仿真結(jié)果證明改進(jìn)算法具有較強(qiáng)的全局搜索能力與局部搜索能力，求解精度高于基本蟻群算法、最大最小蟻群算法及粒子蟻群算法等算法，規(guī)劃的對孔裝藥路徑更優(yōu)，提升了地下礦山開采效率。