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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) 受礦能力約束。每個卸料點的受礦能力時一定的，因此各采區(qū)運往同一卸料點的總礦石量應當滿足卸料點的受礦能力。

式中，Rj表示第j個卸料點的容量，m3。

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

基于上述目標函數(shù)和約束條件描述，構建露天礦運輸調(diào)度數(shù)學模型：

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

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

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

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

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

式中:t表示粒子更新次數(shù)；vid(t)表示當前粒子的每一維速度信息，xid(t)表示當前粒子的每一維位置信息；rand()在[0,1]之間的隨機產(chǎn)生；ω為粒子搜索的慣性系數(shù)。c1和c2為學習因子，用于控制粒子搜索的步長。需要說明的是為了引導粒子能夠進入搜索空間，粒子的搜索速度不能太大，也不能太小，通常會被限制在給定的搜索區(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算法的應用得到了巨大限制。而當慣性權重ω以不變或線性方式遞減時，搜索粒子會出現(xiàn)進入局部極值點鄰域而難以跳出的情況，致使算法無法找到全局最優(yōu)解[7]。另外，學習因子對粒子的算法的尋優(yōu)速度具有重要的影響。因此，為了改善粒子的尋優(yōu)能力，采用用如下方式計算粒子的搜索參數(shù)。

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

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

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

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

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

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

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

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

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

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

圖1 雙吸引子作用下的粒子移動搜索原理

2.3 算法應用實現(xiàn)

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

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

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

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

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

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

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

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

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

3 實例驗證

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

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

表1 各采區(qū)至每個卸料點的運輸費用

表2 各路徑運輸?shù)V量計算結果

圖2 求解運算迭代分布圖

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

4 結論

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

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

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

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

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

[5]紀震，廖慧連，吳青華.粒子群算法及應用[M].北京：科學出版社，2009.

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

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

[8]王建國，陽建宏，云海濱,等.改進粒子群優(yōu)化神經(jīng)網(wǎng)絡及其在產(chǎn)品質(zhì)量建模中的應用[J].北京科技大學學報，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)化問題的多目標粒子群算法[J].計算機應用研究,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è)務費專項資金資助(編號：FRF-SD-12-001A)；國家自然科學基金項目資助(編號：51104010)

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