李 勇,胡乃聯(lián),李國(guó)清

(1.北京科技大學(xué)土木與環(huán)境工程學(xué)院，北京 100083；2.北京科技大學(xué)金屬礦山高效開采與安全教育部重點(diǎn)實(shí)驗(yàn)室，北京 100083)

基于改進(jìn)粒子群算法的露天礦運(yùn)輸調(diào)度優(yōu)化

李 勇1,2,胡乃聯(lián)1,李國(guó)清1

(1.北京科技大學(xué)土木與環(huán)境工程學(xué)院，北京100083；2.北京科技大學(xué)金屬礦山高效開采與安全教育部重點(diǎn)實(shí)驗(yàn)室，北京100083)

針對(duì)露天礦運(yùn)輸調(diào)度問題，以運(yùn)輸費(fèi)用達(dá)到最小為目標(biāo)，構(gòu)建露天礦運(yùn)輸調(diào)度系統(tǒng)的優(yōu)化數(shù)學(xué)模型，基于群體智能優(yōu)化理論，提出用粒子群算法對(duì)露天礦運(yùn)輸調(diào)度模型進(jìn)行解算的方法，并在求解過程中設(shè)計(jì)了帶雙引子的粒子搜索策略。以MATLAB軟件為平臺(tái)，應(yīng)用計(jì)算機(jī)編程技術(shù)，實(shí)現(xiàn)模型解算。最后，用露天礦實(shí)際生產(chǎn)數(shù)據(jù)驗(yàn)證了帶雙引子粒子群算法求解露天礦運(yùn)輸調(diào)度問題的有效性。

粒子群算法；露天礦；運(yùn)輸調(diào)度；優(yōu)化

露天礦開采是集礦巖采掘和運(yùn)輸為一體的綜合系統(tǒng)[1]。其中，礦巖運(yùn)輸?shù)挠行ЫM織和調(diào)配對(duì)露天礦采剝過程的實(shí)施和完成生產(chǎn)任務(wù)具有重要意義，因?yàn)檫\(yùn)輸調(diào)度對(duì)礦山生產(chǎn)設(shè)備的利用效率、礦石產(chǎn)量、設(shè)備的運(yùn)營(yíng)狀態(tài)檢測(cè)、故障排查、維修、不同質(zhì)量開采礦石的搭配及相關(guān)調(diào)度控制有重要作用[2]。因此，對(duì)露天礦運(yùn)輸調(diào)度問題展開優(yōu)化研究，對(duì)提升礦山生產(chǎn)設(shè)備的利用率、降低生產(chǎn)成本具有直接影響，從而決定了露天礦整個(gè)生產(chǎn)系統(tǒng)的生產(chǎn)效率和經(jīng)濟(jì)效益的好壞[3]。

露天礦運(yùn)輸調(diào)度優(yōu)化的目標(biāo)是在滿足一定生產(chǎn)條件下，尋求運(yùn)輸成本最小的運(yùn)輸調(diào)度方案，屬于函數(shù)最值優(yōu)化問題。針對(duì)函數(shù)優(yōu)化問題，近些年來，受自然界生物的群體行為啟發(fā)而產(chǎn)生的群體智能計(jì)算已成為新興的優(yōu)化算法[4]。其中Eberhart與Kennedy提出的粒子群(Particle Swarm Optimization,PSO)算法是一種模擬鳥群飛行覓食的仿生算法，具有簡(jiǎn)潔、易于實(shí)現(xiàn)、魯棒性好等特點(diǎn)，在函數(shù)優(yōu)化領(lǐng)域已被廣泛接受。PSO算法雖然在函數(shù)優(yōu)化求解過程中能夠快速收斂，但出現(xiàn)陷入局部區(qū)域而無法逃出的可能性很大，導(dǎo)致得到的最優(yōu)解是局部?jī)?yōu)化解[5]。因此，針對(duì)露天礦運(yùn)輸調(diào)度問題的復(fù)雜性，本文首先對(duì)PSO算法搜索系數(shù)進(jìn)行改進(jìn)，以增強(qiáng)其全局搜索能力，并在此基礎(chǔ)上，結(jié)合露天礦運(yùn)輸調(diào)度問題，對(duì)PSO算法的粒子搜索策略進(jìn)行改進(jìn)，并嘗試用改進(jìn)的PSO算法對(duì)露天礦運(yùn)輸調(diào)度問題進(jìn)行優(yōu)化研究。

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

設(shè)露天礦當(dāng)前各作業(yè)采區(qū)運(yùn)往各卸料點(diǎn)的礦量為xij,其中下標(biāo)字母i表示采區(qū)個(gè)數(shù)，且有i=1,2,…,I;下標(biāo)字母j表示卸料點(diǎn)個(gè)數(shù)，且有j=1,2,3…,J；在各采區(qū)開采量和各卸料點(diǎn)受礦能力已知的條件下，以完成生產(chǎn)任務(wù)前提下的運(yùn)輸費(fèi)用最小為目標(biāo)，以露天礦各采區(qū)的開采量和各卸料點(diǎn)的受礦能力為約束條件，構(gòu)建露天礦運(yùn)輸調(diào)度的數(shù)學(xué)模型。

1) 露天礦最小運(yùn)輸成本目標(biāo)。通常情況下，露天礦山一般采用多個(gè)采區(qū)同時(shí)開采，而采出的礦石要運(yùn)往不同的卸料點(diǎn)，由于各采區(qū)至每個(gè)卸料點(diǎn)的運(yùn)距不同，運(yùn)輸?shù)V石的成本隨運(yùn)距的變化也會(huì)不同，由此建立目標(biāo)函數(shù)如下：

式中，Cij表示將礦量xij從露天礦第i個(gè)采區(qū)運(yùn)往第j個(gè)卸料點(diǎn)的的運(yùn)輸成本，元/m3。

2) 開采礦量約束。露天礦每個(gè)采區(qū)的礦石采出以后被運(yùn)往各卸料點(diǎn)，而從每個(gè)采區(qū)運(yùn)出的礦石量要等于每個(gè)采區(qū)開采的礦石量。約束條件表達(dá)式如式(2)所示。

式中，Qi表示第i個(gè)采區(qū)開采礦量，m3。

3) 受礦能力約束。每個(gè)卸料點(diǎn)的受礦能力時(shí)一定的，因此各采區(qū)運(yùn)往同一卸料點(diǎn)的總礦石量應(yīng)當(dāng)滿足卸料點(diǎn)的受礦能力。

式中，Rj表示第j個(gè)卸料點(diǎn)的容量，m3。

4) 變量非負(fù)條件。每個(gè)采區(qū)運(yùn)往每個(gè)卸料點(diǎn)的礦量不能為負(fù)值，即要求每個(gè)變量不小于0。

基于上述目標(biāo)函數(shù)和約束條件描述，構(gòu)建露天礦運(yùn)輸調(diào)度數(shù)學(xué)模型：

2 用PSO算法求解露天礦運(yùn)輸調(diào)度問題的方法

2.1 粒子群算法及其參數(shù)計(jì)算

本文不對(duì)基本粒子群算法過程做詳細(xì)描述，僅列出算法相關(guān)公式，以供后文描述應(yīng)用。設(shè)在D維搜索空間，xi=(xi1,xi2,…,xiD)表示第i個(gè)粒子的位置信息，其速度vi=(vi1,vi2,…,viD)。BestPi=(Pi1,Pi2,…,PiD)為第i個(gè)粒子在D維空間的最好位置，粒子群當(dāng)前的最好位置記為BestG=(G1,G2,…,GD)。粒子的每一維屬性信息將根據(jù)式(6)和式(7)進(jìn)行更新。

vid(t+1)=ω×vid(t)+

c1rand()[Pid(t)-xid(t)]+

式中:t表示粒子更新次數(shù)；vid(t)表示當(dāng)前粒子的每一維速度信息，xid(t)表示當(dāng)前粒子的每一維位置信息；rand()在[0,1]之間的隨機(jī)產(chǎn)生；ω為粒子搜索的慣性系數(shù)。c1和c2為學(xué)習(xí)因子，用于控制粒子搜索的步長(zhǎng)。需要說明的是為了引導(dǎo)粒子能夠進(jìn)入搜索空間，粒子的搜索速度不能太大，也不能太小，通常會(huì)被限制在給定的搜索區(qū)間[-v(max),v(max)]中，一般選擇用v(max)=σx(max)，0.1≤σ≤1.0[6]，其中[-x(max),x(max)]為粒子每一維的搜索空間范圍。

由于PSO算法在尋優(yōu)搜索過程中容易出現(xiàn)早熟并陷入局部最優(yōu)，從而使PSO算法的應(yīng)用得到了巨大限制。而當(dāng)慣性權(quán)重ω以不變或線性方式遞減時(shí)，搜索粒子會(huì)出現(xiàn)進(jìn)入局部極值點(diǎn)鄰域而難以跳出的情況，致使算法無法找到全局最優(yōu)解[7]。另外，學(xué)習(xí)因子對(duì)粒子的算法的尋優(yōu)速度具有重要的影響。因此，為了改善粒子的尋優(yōu)能力，采用用如下方式計(jì)算粒子的搜索參數(shù)。

1) 慣性權(quán)重。對(duì)慣性權(quán)重ω采用以“S”形函數(shù)遞減[8]。如式(8)所示，粒子在搜索過程的初期以較高的飛行速度進(jìn)行搜索，在搜索過程的中期，粒子飛行速度快速下降，在搜索過程的后期，粒子則保持一定的搜索速度進(jìn)行最后的收斂.

式中：ωmax、ωmin為慣性系數(shù)的最大取值和最小取值，這里ωmax=0.9，ωmin=0.4；t和tmax分別為當(dāng)前粒子更新次數(shù)和最大更新次數(shù)；τ為控制系數(shù)，用于調(diào)節(jié)慣性權(quán)重變化速度的快慢，一般τ=10。

2) 學(xué)習(xí)因子調(diào)節(jié)。為加快粒子搜索速度，在搜索開始采用較大的c1和較小的c2,目的是使粒子遍歷整個(gè)搜索空間而不屈于局部極值點(diǎn)；在迭代后期則采用較小的c1和較大的c2,以便粒子趨于全局最優(yōu)解。學(xué)習(xí)因子調(diào)節(jié)公式如式(11)、式(12)所示[9].

式中，c1initial=2.5，c2initial=0.5，c1final=0.5，c2final=2.5。

通過對(duì)PSO算法的慣性權(quán)重和加速系數(shù)的調(diào)節(jié)，可保證粒子在全局范圍內(nèi)快速搜索尋優(yōu)。因此，在對(duì)PSO算法搜索參數(shù)進(jìn)行調(diào)整的基礎(chǔ)上，結(jié)合露天礦運(yùn)輸調(diào)度模型，下文將研究用PSO算法解算露天礦運(yùn)輸調(diào)度模型。

2.2 求解露天礦運(yùn)輸調(diào)度問題的帶雙引子PSO算法

本文討論的露天礦運(yùn)輸調(diào)度問題是一個(gè)帶約束的函數(shù)優(yōu)化問題，約束條件的有效處理，對(duì)于函數(shù)優(yōu)化求解至關(guān)重要.因此本文考慮用約束條件構(gòu)建目標(biāo)函數(shù)，將單目標(biāo)露天礦運(yùn)輸調(diào)度問題轉(zhuǎn)化為多目標(biāo)問題.依據(jù)上述思想，首先對(duì)式(5)中的約束條件進(jìn)行如下處理：

式中：vio(x)用于衡量計(jì)算結(jié)果違反約束條件的程度；θj(x)為不等式約束條件；φ(x)為等式約束條件；ε為等式約束容忍度，表明計(jì)算的各采區(qū)輸出礦量和開采礦量出入在[-ε,ε]之間是可接受的，ε通常取很小的正數(shù)。

經(jīng)式(11)對(duì)露天礦運(yùn)輸調(diào)度模型的約束條件處理后，式(5)可被轉(zhuǎn)化成如下多目標(biāo)優(yōu)化問題形式：

需要說明的是，當(dāng)vio(x)=0時(shí)，當(dāng)前解滿足約束；當(dāng)vio(x)≠0時(shí)，當(dāng)前解不滿足約束。這里定義vio(x)=0的區(qū)域?yàn)榭尚薪鈪^(qū)域，vio(x)≠0的區(qū)域?yàn)椴豢尚薪鈪^(qū)域。在粒子搜索過程中，在不可行解區(qū)域內(nèi)的粒子經(jīng)過迭代更新運(yùn)算以后向可行解區(qū)域運(yùn)動(dòng)，為了加速這一運(yùn)動(dòng)過程，提高粒子算法的搜索效率，本文提出帶雙引子的PSO算法，所謂雙引子是指粒子在搜索過程中采用兩個(gè)個(gè)體極值對(duì)自身的速度和位置信息進(jìn)行更新運(yùn)算。對(duì)處于可行解區(qū)域外的粒子，使用離自己最近而且在可行解區(qū)域內(nèi)的粒子(BestPS)和全局最優(yōu)粒子(BestG)更新其信息,該策略可以吸引整個(gè)種群快速進(jìn)入可行域；對(duì)處于可行解區(qū)域內(nèi)的粒子，可依據(jù)粒子自身的個(gè)體極值和粒子群的全局極值更新其位置和速度.帶雙引子的粒子移動(dòng)搜索原理如圖1所示。圖1顯示，在一般粒子群的搜索策略下，粒子被BestG和BestP吸引，從P(t)移動(dòng)到P1(t+1);在帶雙引子的搜索策略下，粒子被BestG和BestPS吸引，從P(t)移動(dòng)到P2(t+1);粒子在雙引子吸引下，以更快的進(jìn)入至閥值內(nèi)區(qū)域。

圖1 雙吸引子作用下的粒子移動(dòng)搜索原理

2.3 算法應(yīng)用實(shí)現(xiàn)

根據(jù)前文構(gòu)建的露天礦運(yùn)輸調(diào)度優(yōu)化數(shù)學(xué)模型，設(shè)計(jì)粒子群算法的粒子編碼方式。用每個(gè)粒子代表一種露天礦運(yùn)輸調(diào)度方案，粒子的每一維表示一條露天礦采區(qū)至卸料點(diǎn)的運(yùn)輸路徑(粒子的維數(shù)可用I×J表示)，粒子的每一維位置信息表示露天礦每個(gè)運(yùn)輸路徑上的運(yùn)輸?shù)V量，將露天礦運(yùn)輸?shù)木C合生產(chǎn)作業(yè)成本作為PSO算法的適應(yīng)度函數(shù)。在此基礎(chǔ)上，采用帶雙引子PSO算法對(duì)露天礦運(yùn)輸調(diào)度模型進(jìn)行解算，其解算過程描述如下。

1) 粒子群初始化。隨機(jī)給定一個(gè)初始粒子群，且保證有粒子在可行域內(nèi)。

2) 確定粒子群解算初始參數(shù)。粒子初始速度和初始位置在允許范圍內(nèi)隨機(jī)生成，根據(jù)粒子的適應(yīng)度值，計(jì)算粒子群的初始個(gè)體極值BestP和全局極值BestG.

3) 停止條件判定。在實(shí)際應(yīng)用中，一般以限定迭代次數(shù)或連續(xù)幾次迭代記錄的最優(yōu)解無法改善為限定條件。本文采用限定最大迭代次數(shù)作為終止條件，即t≤tmax。

4) 計(jì)算慣性權(quán)重ω和加速系數(shù)c1和c2。

5) 粒子更新操作。可行解區(qū)域外粒子以BestPS和BestG為雙引子，用式(6)、式(7)更新其位置和速度信息；可行解區(qū)域內(nèi)粒子用BestP和BestG直接以式(6)、式(7)更新其位置和速度信息.

6) 極值更新操作。依據(jù)粒子的適應(yīng)度函數(shù)，計(jì)算更新粒子群的個(gè)體極值和全局極值.

7) 令t=t+1,返回(3)停止條件判定。

8) 解算結(jié)束，輸出最優(yōu)結(jié)果。

3 實(shí)例驗(yàn)證

為驗(yàn)證應(yīng)用帶雙引子PSO算法優(yōu)化露天礦運(yùn)輸調(diào)度問題的有效性，以某露天礦實(shí)際生產(chǎn)數(shù)據(jù)為驗(yàn)證實(shí)例進(jìn)行實(shí)證研究。已知露天礦共有9個(gè)礦石開采采區(qū)和5個(gè)處在不同位置的礦石卸料點(diǎn)。各采區(qū)的開采礦量、各卸料點(diǎn)的受礦能力及各采區(qū)至每個(gè)卸料點(diǎn)的運(yùn)輸費(fèi)用如表1所示。

依據(jù)實(shí)例數(shù)據(jù)，確定粒子群的初始化參數(shù)為：粒子數(shù)m=50，粒子維數(shù)k=45，慣性權(quán)重由式(8)計(jì)算得到，學(xué)習(xí)因子由式(9)、式(10)計(jì)算得到，粒子的每一維搜索變化范圍為[0，xij(max)]，粒子最大搜索速度Vmax=0.1*xij(max)，取最大迭代次數(shù)tmax=1000。結(jié)合實(shí)例數(shù)據(jù)和上述參數(shù)，以MATLAB 7.1為平臺(tái)，用計(jì)算機(jī)編程技術(shù)，實(shí)現(xiàn)露天礦運(yùn)輸調(diào)度數(shù)學(xué)模型解算，通過控制最大迭代次數(shù)tmax，給出露天礦運(yùn)輸調(diào)度數(shù)學(xué)模型的PSO解算迭代過程(圖2)，求得各運(yùn)輸路徑上運(yùn)輸?shù)V量X的解如表2所示。按照優(yōu)化給出的各運(yùn)輸路徑的運(yùn)輸?shù)V量，可對(duì)每個(gè)采區(qū)和運(yùn)輸路徑的運(yùn)輸設(shè)備進(jìn)行合理分配，實(shí)現(xiàn)整個(gè)運(yùn)輸調(diào)度系統(tǒng)的優(yōu)化。

表1 各采區(qū)至每個(gè)卸料點(diǎn)的運(yùn)輸費(fèi)用

表2 各路徑運(yùn)輸?shù)V量計(jì)算結(jié)果

圖2 求解運(yùn)算迭代分布圖

依據(jù)表2給出露天礦運(yùn)輸調(diào)度優(yōu)化結(jié)果和現(xiàn)行實(shí)際結(jié)果數(shù)據(jù)，優(yōu)化解算得到的運(yùn)輸綜合成本為44090萬元，而實(shí)際現(xiàn)行運(yùn)輸方案的運(yùn)輸綜合總成本為49740萬元，通過和現(xiàn)行實(shí)際數(shù)據(jù)對(duì)比，結(jié)果顯示優(yōu)化解算得到的運(yùn)輸綜合成本比實(shí)際減少了5650萬元，另外，從表2給出的各運(yùn)輸路徑的運(yùn)輸?shù)V量?jī)?yōu)化結(jié)果可以看出，改進(jìn)PSO算法優(yōu)化結(jié)果滿足實(shí)際生產(chǎn)要求，證明帶雙引子PSO算法在露天礦運(yùn)輸調(diào)度優(yōu)化應(yīng)用中的有效性。

4 結(jié)論

通過對(duì)露天礦運(yùn)輸調(diào)度問題分析，構(gòu)建了以最小綜合運(yùn)輸成本為目標(biāo)函數(shù)的運(yùn)輸調(diào)度數(shù)學(xué)模型，針對(duì)模型提出用改進(jìn)的PSO算法對(duì)模型進(jìn)行解算的方法。經(jīng)過實(shí)例數(shù)據(jù)驗(yàn)證，顯示計(jì)算結(jié)果符合露天礦生產(chǎn)實(shí)際，并能有效減少運(yùn)輸成本。因此，本文提出的改進(jìn)PSO算法在露天礦運(yùn)輸調(diào)度優(yōu)化應(yīng)用中是有效的，可用于指導(dǎo)露天礦實(shí)際生產(chǎn)中運(yùn)輸設(shè)備的調(diào)度和分配，具有較好的應(yīng)用前景。

[1]姚再興,劉海娟.遺傳算法在大型露天礦卡車優(yōu)化調(diào)度中的應(yīng)用[J].露天采礦技術(shù),2007(5):44-47.

[2]鞠興軍,李林,劉光偉.基于遺傳算法的神經(jīng)網(wǎng)絡(luò)在露天礦卡車調(diào)度系統(tǒng)中的應(yīng)用研究[J].露天采礦技術(shù),2009(6):31-33.

[3]孫效玉,宋守志.露天礦卡車優(yōu)化調(diào)度系統(tǒng)實(shí)時(shí)調(diào)度方法[J].金屬礦山,2005(8):14-17.

[4]高尚，楊靜宇.群智能算法及其應(yīng)用[M].北京:中國(guó)水利水電出版社，2006.

[5]紀(jì)震，廖慧連，吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009.

[6]陳應(yīng)顯，韓明峰.改進(jìn)粒子群算法的露天礦路徑優(yōu)化研究[J].微電子學(xué)與計(jì)算機(jī)，2011,28(11):61-64.

[7]王洪濤,任燕.基于改進(jìn)慣性權(quán)重的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件,2011,28(10):271- 274.

[8]王建國(guó)，陽建宏，云海濱,等.改進(jìn)粒子群優(yōu)化神經(jīng)網(wǎng)絡(luò)及其在產(chǎn)品質(zhì)量建模中的應(yīng)用[J].北京科技大學(xué)學(xué)報(bào)，2008,30(10):1188-1193.

[9]Ratnaweera A,Halgamuge S K,Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficient.IEEE Trans Evol Comput,2004:240.

[10]劉衍民,牛奔,趙慶禎.求解約束優(yōu)化問題的多目標(biāo)粒子群算法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):851-853.

Open-pithaulingdispatchingoptimizationbasedonimprovedPSOalgorithm

LI Yong1,2，HU Nai-lian1，LI Guo-qing1

(1.School of Civil and Environmental Engineering,University of Science and Technology Beijing100083,China；2.State Key Laboratory of High-Efficient Mining and Safety of Metal Mines(University of Science and Technology Beijing),Ministry of Education,Beijing100083,China)

A mathematical model of open-pit hauling dispatching was constructed from the view point of minimizing open-pit transportation cost.Based on the theory of swarm intelligence optimization,a method of using particle swarm optimization algorithm to optimize open-pit mining operation plan was proposed in this paper,and the search strategy with double attractor was designed for particles in the calculation process.With MATLAB software as a computation platform,the model was calculated by using computer programming technology.With taking the actual production data of an open pit mine as an example,the effectiveness for using improved PSO(Particle Swarm Optimization) algorithm to solve open-pit hauling dispatching problem was verified.

particle swarm algorithm；open-pit mine；hauling dispatching；optimization

TD57

B

1004-4051(2013)04-0098-04

2012-12-07

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助(編號(hào)：FRF-SD-12-001A)；國(guó)家自然科學(xué)基金項(xiàng)目資助(編號(hào)：51104010)

李勇(1985-)，男，博士研究生。E-mail：yongli9898@hotmail.com。