基于改進粒子群算法的露天礦運輸調度優化

李 勇,胡乃聯,李國清

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

基于改進粒子群算法的露天礦運輸調度優化

李 勇1,2,胡乃聯1,李國清1

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

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

粒子群算法；露天礦；運輸調度；優化

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

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

1 露天礦運輸調度數學模型

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

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

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

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

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

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

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

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

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

2 用PSO算法求解露天礦運輸調度問題的方法

2.1 粒子群算法及其參數計算

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

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

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

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

由于PSO算法在尋優搜索過程中容易出現早熟并陷入局部最優，從而使PSO算法的應用得到了巨大限制。而當慣性權重ω以不變或線性方式遞減時，搜索粒子會出現進入局部極值點鄰域而難以跳出的情況，致使算法無法找到全局最優解[7]。另外，學習因子對粒子的算法的尋優速度具有重要的影響。因此，為了改善粒子的尋優能力，采用用如下方式計算粒子的搜索參數。

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

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

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

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

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

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

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

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

經式(11)對露天礦運輸調度模型的約束條件處理后，式(5)可被轉化成如下多目標優化問題形式：

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

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

2.3 算法應用實現

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

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

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

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

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

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

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

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

8) 解算結束，輸出最優結果。

3 實例驗證

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

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

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

表2 各路徑運輸礦量計算結果

圖2 求解運算迭代分布圖

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

4 結論

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

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

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

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

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

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

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

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

[8]王建國，陽建宏，云海濱,等.改進粒子群優化神經網絡及其在產品質量建模中的應用[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]劉衍民,牛奔,趙慶禎.求解約束優化問題的多目標粒子群算法[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

中央高校基本科研業務費專項資金資助(編號：FRF-SD-12-001A)；國家自然科學基金項目資助(編號：51104010)

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