門飛，蔣欣

(平頂山工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件工程學(xué)院， 河南 平頂山 467000)

0 引言

在露天礦生產(chǎn)中，運(yùn)輸過程會(huì)排放大量的碳，運(yùn)輸能耗約占露天礦總能耗的60%[1]，運(yùn)輸費(fèi)用約占總生產(chǎn)費(fèi)用的50%[2]。露天礦低碳運(yùn)輸調(diào)度優(yōu)化成為促進(jìn)露天礦高效生產(chǎn)、減少碳排放量和運(yùn)輸費(fèi)用的關(guān)鍵環(huán)節(jié)。

露天礦低碳運(yùn)輸調(diào)度問題可看作是在滿足露天礦生產(chǎn)的約束條件下，求解露天礦碳排費(fèi)用和運(yùn)輸費(fèi)用之和最小的多目標(biāo)優(yōu)化問題。近年來，許多學(xué)者采用仿生算法求解露天礦運(yùn)輸調(diào)度問題，如自適應(yīng)果蠅優(yōu)化算法(Adaptive Fruit Fly Optimization Algorithm，AFOA)[2]、基于差分的生物地理學(xué)算法[3]、粒子群算法[4]、模擬退火算法[5]、差分進(jìn)化算法[6]、遺傳算法(Genetic Algorithm，GA)[7]、蟻群算法[1，8]等。然而，上述算法存在全局尋優(yōu)能力較差、需調(diào)節(jié)參數(shù)較多的問題。

灰狼優(yōu)化(Grey Wolf Optimization，GWO)算法是一種通過模仿灰狼種群社會(huì)階層和獵食過程而提出的仿生算法，該算法需要調(diào)節(jié)的參數(shù)較少、較易編程實(shí)現(xiàn)、全局尋優(yōu)能力較強(qiáng)[9-10]，已被應(yīng)用于求解流水線車間調(diào)度[11]、函數(shù)優(yōu)化[12-13]、多層傳感器訓(xùn)練[14]和電力系統(tǒng)優(yōu)化[15]等問題。然而，隨著GWO算法的迭代進(jìn)化，灰狼種群的多樣性逐步減少，算法陷入局部最優(yōu)的概率增加，導(dǎo)致局部尋優(yōu)能力減弱，難以均衡全局尋優(yōu)能力和局部尋優(yōu)能力。本文在GWO算法中引入遷移操作，并且根據(jù)不同的灰狼自適應(yīng)調(diào)整其遷移概率，提出了一種改進(jìn)的GWO(An Improved Grey Wolf Optimization，AGWO)算法，并將其應(yīng)用于求解露天礦低碳運(yùn)輸調(diào)度問題。

1 露天礦低碳運(yùn)輸調(diào)度問題數(shù)學(xué)模型

在實(shí)際的露天礦生產(chǎn)過程中，多個(gè)采礦場往往同時(shí)開展采礦工作，然后將礦石分別運(yùn)輸至不同的破碎場進(jìn)行破碎工作。各個(gè)采礦場到破碎場的運(yùn)輸距離不同，因此，運(yùn)輸過程產(chǎn)生的碳排費(fèi)用和運(yùn)輸費(fèi)用也會(huì)不同。露天礦低碳運(yùn)輸調(diào)度問題的本質(zhì)是尋找碳排費(fèi)用和運(yùn)輸費(fèi)用之和的最小值。

(1) 碳排費(fèi)用。卡車在第i(i=1，2，…，I，I為采礦場個(gè)數(shù))個(gè)采礦場Mi和第j(j=1，2，…，J，J為破碎場個(gè)數(shù))個(gè)破碎場Dj之間的運(yùn)輸過程中，需要從采礦場Mi滿載至破碎場Dj，然后空載返回采礦場Mi。因此，碳排費(fèi)用為

(1)

(2)

露天礦低碳運(yùn)輸調(diào)度問題的數(shù)學(xué)模型為

(3)

式(3)為目標(biāo)函數(shù)，式(4)—式(9)為約束條件。式(4)和式(5)表示卡車裝載量不應(yīng)超過開采量和破碎量；式(6)表示每輛卡車最終必須返回至出發(fā)時(shí)的采礦場；式(7)表示運(yùn)載卡車的數(shù)量應(yīng)該在卡車總數(shù)之內(nèi)；式(8)表示卡車不能從一個(gè)采礦場到另一個(gè)采礦場；式(9)表示變量約束。

2 算法原理

2.1 GWO算法

灰狼是以群居為主的食肉動(dòng)物，種群內(nèi)具有不同的社會(huì)階層，從上至下依次分為α，β，δ，ω層。每個(gè)階層的灰狼負(fù)責(zé)相應(yīng)的獵食工作：α層為灰狼領(lǐng)導(dǎo)層，統(tǒng)管種群內(nèi)各種事務(wù)；β層為灰狼管理層，輔佐α層規(guī)劃獵食事務(wù)；δ層為灰狼普通層，負(fù)責(zé)遵守α，β層的指示；ω層為灰狼底層，負(fù)責(zé)聽從α，β，δ層的命令[16-17]。

GWO算法的基本思想：灰狼種群在追捕獵物過程中，灰狼首先根據(jù)獵物的味道等信息逐步地接近獵物，構(gòu)建包圍圈；然后，其他灰狼在α，β，δ層灰狼的帶領(lǐng)下，逐漸縮小包圍圈；最后，灰狼種群有組織地對(duì)獵物發(fā)動(dòng)攻擊，直至捕獲到獵物[18-19]。GWO算法求解問題的一般步驟：① 初始化算法參數(shù)和種群方位；② 計(jì)算適應(yīng)度函數(shù)值；③ 灰狼種群進(jìn)行包圍操作；④ 灰狼種群進(jìn)行狩獵操作；⑤ 灰狼種群進(jìn)行攻擊操作；⑥ 當(dāng)滿足終止準(zhǔn)則，輸出結(jié)果。

2.2 AGWO算法

在GWO算法中，灰狼種群根據(jù)當(dāng)前最優(yōu)灰狼的方位更新方位。然而，隨著迭代次數(shù)的增加，大部分灰狼種群逐步聚集在當(dāng)前最優(yōu)灰狼附近，若當(dāng)前最優(yōu)灰狼的方位不是全局最優(yōu)，則易陷入局部最優(yōu)，無法快速尋找到全局最優(yōu)。因此引入遷移操作構(gòu)成AGWO算法，賦予灰狼自適應(yīng)的遷移概率，由遷移操作重新生成的灰狼能更靠近全局最優(yōu)，改善種群的多樣性，降低陷入局部最優(yōu)的概率，促使快速收斂至全局最優(yōu)。AGWO算法求解問題的步驟如下。

(1) 初始化算法參數(shù)和種群方位。假定Xh=(Xh1,Xh2,…,XhL)為第h(h=1，2，…，N，N為灰狼種群大小)個(gè)灰狼的方位。初始化方位信息時(shí)，第h個(gè)灰狼的第d(d=1，2，…，L，L為搜索空間維度)維方位為

Xhd=Xmind+(Xmaxd-Xmind)rand()

(10)

式中：Xmind，Xmaxd分別為第h個(gè)灰狼的第d維方位的最小值、最大值；rand()為區(qū)間[0，1]的隨機(jī)數(shù)。

(2) 計(jì)算適應(yīng)度函數(shù)值。適應(yīng)度函數(shù)值反映了灰狼尋找最優(yōu)的能力，通常由目標(biāo)函數(shù)轉(zhuǎn)換而來。適應(yīng)度函數(shù)值較低則說明該灰狼所在方位較好。AGWO算法在迭代進(jìn)化時(shí)，適應(yīng)度函數(shù)值較低的灰狼方位被保留，同時(shí)帶領(lǐng)適應(yīng)度函數(shù)值較高的灰狼逐步地靠近獵物。

(3) 包圍操作。獵食開始時(shí)，灰狼種群先構(gòu)建包圍圈，接著逐步包圍獵物。包圍操作如下：

D=|CXp(t)-X(t)|

(11)

X(t+1)=Xp(t)-AD

(12)

A=2arand()-a

(13)

C=2rand()

(14)

式中：D為灰狼與獵物的距離向量；C為擺動(dòng)因子向量；Xp(t)為第t代獵物的方位向量；X(t)，X(t+1)分別為第t，t+1代灰狼的方位向量；A為參數(shù)向量；a為收斂因子，a從2線性遞減至0，表示灰狼種群逐漸縮小包圍圈。

(4) 狩獵操作?；讦粒?，δ層灰狼的適應(yīng)度函數(shù)值，灰狼種群更新方位：

Dα=|C1Xα-Xp|

(15)

Dβ=|C2Xβ-Xp|

(16)

Dδ=|C3Xδ-Xp|

(17)

X1=Xα-A1Dα

(18)

X2=Xβ-A2Dβ

(19)

X3=Xδ-A3Dδ

(20)

X(t+1)=(X1+X2+X3)/3

(21)

式中：Dα，Dβ，Dδ分別為α，β，δ層灰狼與獵物的距離向量；C1，C2，C3分別為α，β，δ層灰狼的擺動(dòng)因子向量；Xα，Xβ，Xδ分別為α，β，δ層灰狼的方位向量；Xp為獵物的方位向量；X1，X2，X3分別為α，β，δ層灰狼更新后的方位向量；A1，A2，A3分別為α，β，δ層灰狼的參數(shù)向量。

(5) 攻擊操作。攻擊操作主要通過收斂因子a逐漸遞減完成。根據(jù)式(13)可知，隨著算法的迭代進(jìn)化，a線性遞減為0，A逐漸遞減為0，灰狼種群方位逐漸接近獵物方位。當(dāng)灰狼種群與獵物方位相同時(shí)，表示灰狼成功捕獲獵物，完成攻擊操作。

(6) 遷移操作。每個(gè)灰狼生成一個(gè) [0，1]的隨機(jī)數(shù)，若該隨機(jī)數(shù)小于遷移概率，則對(duì)該灰狼進(jìn)行遷移操作；否則轉(zhuǎn)至步驟(7)。

Pmh=Pm1(fmin+fh)/(fmax-fmin)

(22)

式中：Pmh為第h個(gè)灰狼的遷移概率；Pm1為標(biāo)準(zhǔn)遷移概率；fmin，fmax分別為適應(yīng)度函數(shù)的最小值、最大值；fh為第h個(gè)灰狼的適應(yīng)度函數(shù)值。

將遷移操作融入GWO算法，并且根據(jù)灰狼的適應(yīng)度函數(shù)值動(dòng)態(tài)地修正其遷移概率。一方面，對(duì)于較優(yōu)灰狼(適應(yīng)度函數(shù)值較低)，較小的Pmj可以保留較優(yōu)灰狼的方位，避免算法錯(cuò)過全局最優(yōu)，提升了全局尋優(yōu)能力。另一方面，對(duì)于較差灰狼(適應(yīng)度函數(shù)值較高)，較大的Pmj確保了較差灰狼可以被重新分配，分配后的灰狼可位于全局最優(yōu)的周圍，豐富了灰狼種群的多樣性，加強(qiáng)了算法局部尋優(yōu)能力，能快速地尋找到全局最優(yōu)。

(7) 終止準(zhǔn)則。當(dāng)AGWO算法迭代至指定的進(jìn)化代數(shù)，輸出結(jié)果；否則轉(zhuǎn)至步驟(2)。

3 仿真分析

為驗(yàn)證AGWO的有效性，以某露天礦實(shí)際運(yùn)輸調(diào)度數(shù)據(jù)為例，將AGWO應(yīng)用于求解露天礦低碳運(yùn)輸調(diào)度問題，與AFOA，GWO，GA進(jìn)行比較分析。

該露天礦包含10個(gè)采礦場和5個(gè)破碎場，采礦場至破碎場的距離見表1?？ㄜ嚁?shù)量K=40輛；每輛卡車的裝載量lk=40 t；卡車空載時(shí)單位距離油耗量yij1=0.08 L/(km·t)；卡車滿載時(shí)單位距離油耗量yij2=0.22 L/(km·t)；燃油轉(zhuǎn)化為CO2的單位轉(zhuǎn)化率γ=2.65 kg/L；CO2的單位排放成本B3=0.25元/kg；每輛卡車的固定啟用成本B1=20元/輛；每輛卡車的單位燃油成本B2=7.99元/L。

表1 采礦場至破碎場的距離Table 1 Distances between mining area and crushing station km

AGWO和GWO相關(guān)參數(shù)：搜索空間維度L=20，灰狼種群大小N=100，進(jìn)化代數(shù)G=100。AGWO中的標(biāo)準(zhǔn)遷移概率Pm1=0.25。AFOA和GA參數(shù)設(shè)置分別與文獻(xiàn)[2]和文獻(xiàn)[7]中相同。為減少算法的時(shí)間復(fù)雜度，本文將露天礦運(yùn)輸調(diào)度的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。采用Matlab仿真露天礦低碳運(yùn)輸調(diào)度問題的求解。

AGWO，AFOA，GWO，GA的進(jìn)化曲線如圖1所示，可看出AGWO的尋優(yōu)精度和尋優(yōu)速度均優(yōu)于其他算法。這是由于AGWO在初期繼承了GWO較強(qiáng)的全局尋優(yōu)能力，可以較快地聚集到全局最優(yōu)附近；在后期灰狼種群逐漸集中在最優(yōu)灰狼周圍，此時(shí)遷移操作和自適應(yīng)的遷移概率能夠保留較優(yōu)灰狼方位，重新分配較差的灰狼到新方位，從而降低了AGWO陷入局部最優(yōu)的概率。

圖1 不同算法的進(jìn)化曲線Fig.1 Iterative curves of different algorithms

露天礦在實(shí)際運(yùn)輸中需要36輛卡車。根據(jù)式(1)—式(3)，結(jié)合表1和露天礦運(yùn)輸相關(guān)參數(shù)可知，露天礦的實(shí)際運(yùn)輸距離為1 882.227 km，運(yùn)輸費(fèi)用為5 271.698元，碳排費(fèi)用為374.093元，綜合費(fèi)用為5 645.791元。分別基于AGWO，AFOA，GWO，GA的露天礦低碳運(yùn)輸調(diào)度的碳排費(fèi)用和運(yùn)輸費(fèi)用見表2。可看出與實(shí)際運(yùn)輸數(shù)據(jù)相比，采用AGWO求解的運(yùn)輸距離減少了492.086 km，卡車數(shù)量減少了10輛，運(yùn)輸費(fèi)用節(jié)省了1 419.531元，碳排費(fèi)用節(jié)省了97.802元，綜合費(fèi)用節(jié)省了1 517.333元，采用AFOA，GWO，GA求解的綜合費(fèi)用分別節(jié)省了967.972，598.695，427.970元。由此可見，采用AGWO優(yōu)化露天礦運(yùn)輸調(diào)度可有效提高運(yùn)輸效率，減少碳排費(fèi)用和運(yùn)輸費(fèi)用。

表2 不同算法下露天礦低碳運(yùn)輸調(diào)度結(jié)果對(duì)比Table 2 Comparison of open-pit mine low-carbon transportation scheduling results under different algorithms

4 結(jié)語

AGWO算法在GWO算法的基礎(chǔ)上引入遷移操作，并且根據(jù)灰狼的適應(yīng)度函數(shù)值自適應(yīng)調(diào)整灰狼的遷移概率，提升了算法局部尋優(yōu)能力，促使算法能夠較快尋找到全局最優(yōu)，均衡了全局尋優(yōu)能力和局部尋優(yōu)能力；將AGWO算法用于求解露天礦低碳運(yùn)輸調(diào)度問題，提高了尋優(yōu)精度與尋優(yōu)速度，有效提高了運(yùn)輸效率，減少了碳排費(fèi)用和運(yùn)輸費(fèi)用。