基于Clifford代數的露天礦山路徑優化算法

柴森霖，劉光偉，趙景昌，白潤才，李浩然，張 靖

(1.鹽城工學院 經濟管理學院，江蘇 鹽城 224051; 2.遼寧工程技術大學 礦業學院，遼寧 阜新 123000; 3.遼寧工程技術大學 遼寧省高等學校礦產資源開發利用技術及裝備研究院,遼寧 阜新 123000)

露天礦山路徑優化問題是滿足特定物理和經濟約束之下搜索最佳運輸線路的組合優化問題，長期以來一直都是卡車調度、物料流規劃等相關領域的重點研究課題之一，對于降低礦山運營成本具有重要意義[1-2]。

目前，針對于露天礦山路徑優化算法大致可分為兩類，第一種方法是使用等效運距作為權重或優化指標，采用靜態網絡分析方法來搜索最佳路線。如，WHITE和OLSON[3]以全局等效運距的總和最小化為優化目標，建立露天礦山運輸路徑優化模型;CHANG等[4]在綜合考慮等效距離和運輸系統收益的情況下，針對卡車調度需求，提出一種尋徑算法;ADENSO-DIAZ[5]指出煤礦的運輸路線存在波動變化，并結合這種動態特點，提出了一種用于自動更新靜態網絡的新方法;LI J Q等[6]提出了一種同時考慮設備作業和時效性成本最小化的露天礦山灑水車線路優化策略;HU[7]采用和聲搜索算法設計了露天礦山路徑優化算法;陳應顯[8]、孫臣良[9]、李勇[10]等分別將群智能算法引入靜態運輸網絡圖中，提出適用于露天礦路徑優化問題的解決方案;另一類方法則是在多種約束條件下，結合圖論中網絡分析方法，通過求解數學規劃模型來實現礦山運輸路徑優化，頗有代表性的研究如CHOI,PARK和 SUNWOO[11]指出“目前很少有關于卡車最佳運輸路線的研究，這主要是因為在以前的研究中，人們總是假設路面狀況在其生命周期內總是相同的，這種假設對露天礦山進行優化分析往往是不現實的”，基于此種考慮將多指標評價方法與最小成本路徑分析方法相結合，提出適用于大型露天礦山線路優化的新方法;CHOI和NLETO[12]通過對最小成本路徑分析算法的改進，提出一種適用于不同路面類型的優化方法，并對地形和曲線設計變化對交通效率的影響進行了分析。

事實上，路徑優化算法在物流、交通運輸和路由器尋址[13-14]等相關領域有著極為廣泛的應用，近年來也形成了一系列極為成熟的動態網絡尋徑算法，但這些算法很難被直接應用于露天礦山路線優化問題中，其主要原因在于:在露天礦山實際作業場景中,運輸系統常受到多種綜合因素限制,運輸成本常表現出周期性的隨機波動效應，如直接采用傳統的物理距離或單一靜態常量來表征，則存在明顯的局限性。特別是當路面受到頻繁碾壓破壞和周期性維護后，這種成本波動效應的周期性特征則更為明顯。筆者在充分考慮上述問題的基礎上，將Clifford代數引入到露天礦山路徑優化問題中，利用其拓撲連通性計算與標量表達的無關性，構建了線路拓撲邏輯計算方法，并建立了標量場動態表達模型;考慮道路運輸網絡具有動態隨機特性，提出基于時變運輸功最小化的優化目標，并定義了時變運輸功公式，提出了一種有效估計時變滾動阻力系數的新方法，給出了計算此類時變指標的優化計算策略;最終結合遺傳算法構建了路徑優化算法。經多組仿真對比實驗驗證，文中算法對于求解礦山路徑優化問題可行且有效。

1 基于Clifford代數的運輸網絡建模

1.1 有向圖的幾何代數編碼

在Clifford代數空間內進行基于有向圖的路徑分析，實質上是對歐式空間內的網絡分析法的一種多維推廣，是有效降低網絡分析復雜度的重要手段之一。在Clifford代數空間內，任意歐式空間中的一條帶有n個節點的路徑方案，均可以被抽象表達為一個n階片積對象(n-blade)，并總是可以通過blade對象的幾何代數運算來實現路徑拓撲關系的生成、遍歷和篩選[15]。因此，對于一個包含n個路徑節點的運輸系統有向圖G=(V,E)，則可進行如下的幾何代數描述:對于有向圖G，存在一簇向量{e1,e2,…,en}為幾何代數空間Cln,0的向量集合，其中每一個元素ei均對應有向圖網絡中的惟一節點;同理，空間中的另一簇向量{e13,e24,…,eij};for1

1.2 Cln,0空間內拓撲關系計算

Cln,0空間中對象的維度擴張和形體的構建與表達均是通過外積運算來實現，這種內蘊的外積拓撲延拓特性能建立網絡圖中節點、有向邊以及路徑間的統一表達。因此，對于網絡圖中節點與有向邊間的二目幾何運算關系則可形式化表達為

(1)

式(1)描述了有向圖節點到有向邊的拓撲延拓方法，對于路徑中有向邊之間的進一步延拓也可以采用類似的外積運算來實現。故對于圖中具備連通性的n個節點v1,v2,…,vn，其有序排列所組成的有效路徑則可描述為具有n個基向量ei的連續外積形式，即L=e1∧e2…∧en=e1,2,…,n，e1,2,…,n為空間中的n階片積對象，它所對應的路徑即為可行解。

上述運算介紹了路徑拓撲延拓的具體方法，但并不能判斷出路徑間的拓撲連通性。為此，文中引入片積維度的概念，并通過片積的維度運算實現延拓路徑的連通性判斷。由路徑Cln,0可以看出，對具備連通性的路徑進行連續的外積運算，其本質上是將一維向量ei擴展拉伸為n維片積對象e1,2,…,n的過程。因此，可以廣義的認為基的每一次外積運算，其維度均向上延拓一階，也就是說片積的重復外積運算將滿足維度的可加性條件。根據這種可加性，就可以通過外積的維度變化來判別路徑的連通性。因此，文中采用判據:grade(ei∧ej)=grade(ei)+grade(ej)來判斷拓撲延拓的連通性。相反，當路徑間不具備連通性時，由于有向邊運算結果為變量0，可加性判別則將不再成立，即grade(0)≠grade(ei)+grade(ej)。綜合上述兩組判據，即可實現路徑延拓與連通性拓撲的快速識別。

按照上述的幾何拓撲關系，將有向圖中的有向邊的幾何拓撲關系抽象為幾何鄰接矩陣描述為A，矩陣A中的任意一個元素皆描述了圖中任意兩點之間的幾何拓撲關系和連通性。

(2)

觀察式(2)不難發現，其本質上就是2-blade有向邊的矩陣表達，因此外積運算仍適用于其所對應的矩陣表達?；诖朔N考慮，根據鄰接矩陣的運算特性，將外積運算進一步推廣，按照矩陣“叉乘”運算定義鄰接矩陣的外積運算規則:A2=A∧A，按照此種運算規則，幾何鄰接矩陣A每參與外積運算(A∧A)就等同于片積維度延拓一次，也就是向外擴展一層節點的路徑，其路徑延拓原理如圖1所示，對于圖1中包含有9個節點的有向圖，帶有2-blade有向邊的幾何鄰接矩陣A，經過一次外積運算即可計算出所有3-blade的路徑，即包含3個任意節點的有效路徑(其中A2矩陣中“+”并不指代數學運算，僅表示可能路徑的組合)。故通過多次迭代上述外積運算即可得到任意節點間的拓撲連通性關系。

1.3 Cln,0空間內標量計算

權重信息是尋徑問題的求解基礎，在露天礦山的路徑優化問題中，這種權重信息多表現為數值型變量，且變量常以節點或有向邊的關聯函數形式存在。但在之前定義的幾何代數空間中，空間對象間所有二目運算均基于外積的形式參與代數運算，這使得標量場數據均以積的形式表達，導致部分標量場數據喪失了可加性關系。為保證計算模型的合理性，需要對標量場內的關聯函數進行如下可加性變換:考慮網絡自身與權重間的無關性，將如式(3)所示的帶有標量權重的外積拓撲運算的標量部分嵌入可加性映射Φ。

aei∧bej=(a*b)ei∧ej

(3)

eaei∧ebej=(ea*eb)ei∧ej=ea+beij

(4)

圖1 幾何鄰接矩陣外積運算原理Fig.1 Operation principle of geometric adjacency matrix exterior product

2 數值約束標量場建模

2.1 定義模型變量

為定義模型方便，文中首先對約束模型中的參數變量做以下說明，其中:

(2)待估計參數:Fei,j為相鄰有向邊之間的阻力集合,kN。

(3)規劃模型的決策變量:xi為各弧段上決策變量。

2.2 數值型約束模型

數值型約束是描述路徑屬性特征的依據，也是建立路徑優化問題的數值計算基礎。對于文中所述的優化問題與傳統的混合整數規劃模型建模過程相同，只是無需在考慮模型中的決策變量和相關約束。因此，對于有向邊約束的標量場建模，仍可采用規劃建模的思路，按照全局時變運輸功最小化進行建模，其優化問題的目標函數如式(5)所示。

(5)

式中,Fei,j阻力為時變函數，其主要由3部分組成:滾動阻力Ffeij、坡度阻力Freij以及空氣阻力Fweij，其關聯函數的形式化表達如式(6)所示。

考慮所選路徑差異以及因路面頻繁碾壓而造成的路面阻力系數變化，定義相鄰節點路徑間的阻力公式:

(6)

不等約束以及等式約束條件如下:

(1)對于各個路徑弧段的車流密度約束:

(7)

(8)

(2)所選路徑的總體車流密度約束:

(9)

式中,KE應滿足計算條件如下式:

(10)

(3)道路通過能力約束:

(11)

式中,N應滿足計算條件如下:

(12)

2.3 時變阻力系數估計

由權重指標的關聯函數式(5),(6)不難看出，模型中最難計算的參數即為對模型中時變阻力系數的估計，這主要是因為該參數在不同路段以及相同路段的不同養護周期內均存在波動變化，進而導致阻力系數存在時變效應。因此，為了更好地模擬卡車在運輸道路上因滾動阻力系數變化而造成的這種阻力時變效應，筆者采用多標簽模式識別(分類)和趨勢面技術來構建阻力系數的時變參數估計。其估計算法的基本思路是:首先利用統計所得路面屬性指標和特定的人為路面分級，建立多標記的模式分類模型;利用模式分組后所得的指標參數進一步構建其阻力系數趨勢面模型;最終按照給定路徑的指標參數，實現阻力系數的時變估計，其算法實現過程如下:

第1步，道路表面類型的分類。根據露天礦山的運輸道路狀況及文獻[16]中匯總的各類路面特征和阻力系數分布范圍，對扎哈淖爾露天煤礦不同養護周期內的路面特征進行分類，并將各類路面特征及阻力系數分布范圍進行統計，其分類統計結果見表1。

表1 不同路面條件下的滾動阻力系數分類
Table 1 Classification of rolling resistance coefficient under different road conditions

路面類型分類阻力系數范圍1.非常堅硬,光滑的路面或污垢表面,沒有滲透或彎曲0.010～0.0182.堅硬、光滑、穩定的路面,不滲透、澆灌、定期養護0.018～0.0203.堅固、光滑、滾動的道路,有泥土或彎曲的表面,微微彎曲,保持輕微,保持相當的規律性澆水0.020～0.0304.泥路,在負荷作用下彎曲,很少維護,沒有水,25 mm的輪胎滲透或彎曲0.030～0.0455.泥路,在負荷作用下彎曲,很少維護,沒有水,50 mm的輪胎滲透或彎曲0.045～0.0606.坑坑洼洼的土路,在負荷作用下變柔軟,沒有維護,不穩定,100 mm的輪胎滲透或彎曲0.060～0.0757.坑坑洼洼的土路,在負荷作用下變柔軟,沒有維護,不穩定,200 mm的輪胎滲透和彎曲0.075～0.1008.非常柔軟,泥濘,坑坑洼洼的道路,300 mm的輪胎滲透,沒有彎曲0.100～0.140

第2步，多標簽模式分類訓練數據處理。根據滾動阻力系數的測試表明[16-17]，車輛的滾動阻力系數易受多種因素綜合影響，如路面條件、行駛速度、輪胎結構、輪胎材料和輪胎壓力等，但考慮問題自身、數學模型抽象及問題求解的復雜性，本文僅討論因路面頻繁碾壓和因周期性路面養護，而引起的滾動阻力系數波動變化。為此，筆者將對路面碾壓破壞的三大主要因素作為多標簽分類模型的屬性指標，即路段上平均行駛速度、養護周期內的累積運輸物料量以及距上一個路面養護周期的時間間隔。按照上述屬性和對應路面類型，統計扎礦2017年指標數據作為模式分組的訓練數據，數據統計結果如圖2所示。

圖2 訓練數據樣本Fig.2 Training data sample

圖3 四分類邏輯流程Fig.3 Four-classification logic flow

(13)

式中,K(x·xi)為核函數，筆者選用高斯徑向基核函數。

(14)

并進一步采用最小二乘估計，建立規劃模型如式(15)所示，8組路面的二次多項式趨勢面擬合結果如圖4所示。

圖4 不同路面類型的趨勢面估計Fig.4 Trend surface estimates for different road types

(15)

3 基于Clifford代數的路徑優化算法

傳統的路徑優化算法都是建立在求解整數規劃模型的基礎上，并結合群智能算法提高求解效率。這類規劃模型計算常采用決策變量控制路徑的拓撲連通性，求解過程需要同時考慮拓撲連通性計算和數值約束指標的目標尋優。當大型網絡中數值約束存在動態特性時，求解這類問題的復雜度就會明顯增加，易導致優化算法陷入局部最優，而無法獲得全局最優解。在充分考慮這些因素的基礎上，筆者將幾何代數引入動態運輸網絡中，將傳統歐式空間的有向圖推廣到Clifford代數空間，實現網絡中的節點、有向邊和路徑的統一表達，利用迭代外積運算來表達出路徑的拓撲連通性，從而實現拓撲計算和數值約束優化計算的分離，并且拓撲連通性計算結果可直接為群智能優化算法提供啟發式拓撲關系。因此，文中路徑優化算法設計的重點即為考慮如何將數值型約束嵌入有向圖中，實現在幾何代數空間內處理拓撲解析計算和動態有向邊權重的標量計算，并利用外積的幾何鄰接矩陣計算結果為群智能算法提供啟發式編碼方案，最終實現復雜大型動態網絡的快速尋徑。

3.1 權重關聯函數優化策略

第2節定義了關于路面養護時間間隔(t)的卡車時變行駛阻力的表達方式和計算方法，它標定了網絡中各有向邊之間的數值約束關系，但對于這樣一個動態網絡，特別是當網絡節點規模較大時，這類數值計算仍極為復雜。出于簡化計算提高算法收斂性考慮，文中基于隨機理論和數理統計知識，引入兩組推論和一組數值計算優化策略。

推論1:對于任意兩個隨機變量X,Y，如果其期望E(·)滿足E(X)≤E(Y)，則事件所對應的概率P(X≤Y)>0.5也成立。

為進一步說明該推論的正確性，筆者結合數理統計知識推導出此推論的證明過程如下:

假設:

E(X)≤E(Y)

(16)

可推知:

E(X)-E(Y)≤0?E(X-Y)≤0

(17)

引入相關變量Z:

Z=X-Y

(18)

可推得:

E(Z)≤0

(19)

根據期望定義可推知:

(20)

將公式分為A,B兩部分討論:

考慮公式A,B所在區間，可推知:

因為

(22)

又

E[Z]≤0

(23)

所以，式A絕對值一定大于式B絕對值:

(24)

故可推得如下P之間的關系:

P(Z≤0)≥P(Z≥0)

(25)

又因為整個概率空間和恒等于1:

P(Z≤0)+P(Z≥0)=1

(26)

進而推得:

P(Z≤0)≥1-P(Z≤0)?2P(Z≤0)≥1

(27)

整理即可證明出推論結果正確，即

P(Z≤0)≥0.5?P(X≤Y)≥0.5

(28)

推論2:對于路徑優化問題中具備聯通性且參與對比的兩條路徑L和K，可采用P(L≤K)和P(L>K)分別描述L和K成為最優路徑的概率。因此，根據推論1結論，文中廣義的認為min{E(L),E(K)}為最優路徑的判據，判據所對應的路徑即為最優路徑。

結合上述2組推論，采用隨機理論進行優化建模，其數值計算優化策略可表述為:假設道路運輸網絡中存在有效的可行路徑r邊的全路徑運輸功能耗可以表示為一個l維的隨機變量Ω={W1(t),W2(t),…,Wl(t)}，其聯合概率密度分布函數可以表示為

fr=f[w1(t),…,wl(t)]=

(29)

因此，對于表征全路徑中最優路徑為r的事件γ，且該事件滿足如下路徑間的能耗條件:

wγ(t)≤w1(t),…,wγ(t)≤wl(t)，該路徑成為全局最優路徑的概率即可表示為:

Pγ[wγ(t)≤w1(t),…,wγ(t)≤wl(t)]=

(30)

再進一步結合推論1，將路徑事件的概率估計轉化為求全局能耗期望值問題，即可實現數值約束的優化計算。

3.2 路徑優化算法流程

為進一步提高算法的收斂特性，筆者將幾何代數空間外積計算所得的幾何鄰接矩陣結果嵌入遺傳算法，利用拓撲計算結果啟發式的枚舉路徑基因編碼，并將3.1節所介紹的優化策略嵌入到遺傳算法的適應度函數(M/U(t),其中M為一個較大的常數，防止適應度值過小)中，用于簡化時變動態網絡中的標量場計算，算法具體處理流程將如圖5所示。

圖5 算法邏輯流程Fig 5 Algorithm logic flow

4 仿真實驗對比分析

為了直觀地表達算法的優化效果，文中以扎哈淖爾露天礦為研究對象，選擇了5組測試路徑，對文中算法各代最優解的運輸功能耗進行統計，如圖6所示。

圖6 路徑優化結果Fig.6 Route optimization results

對比分析圖6可知，N1和N4兩組路徑節點數分別為74和77，在早期路徑優化過程中運輸功值較大，并在第30～40代左右算法開始快速收斂，最終收斂于全局最優解。

考慮現階段對于遺傳算法的精度、可信度和計算復雜程度尚沒有有效的定量分析方法，為進一步論證文中算法的魯棒特性，筆者采用上述5組測試路徑進行20次重復測試，其20次重復實驗的統計數據見表2。對比表2數據可知，20組重復實驗除N1存在錯誤估計外，均收斂于最優解。通過平均相對誤差水平和計算用時對比，說明算法具有較強的穩定性和較高執行效率。

表2 重復實驗對比數據(20組)
Table 2 Repeated test comparison data(20 groups)

實例實驗值最優解最差解平均誤差/%平均用時/sN1746 932.9746 937.8746 952.10.000 835.09N2677 493.7677 493.7677 507.40.000 392.07N3898 642.1898 642.1898 646.80.000 303.91N4959 358.6959 358.6959 365.60.000 314.87N5955 632.7955 632.7955 632.701.61

筆者曾在文獻[18]中論證過基于時變運輸功最小化的路徑優化方法，并采用改進的遺傳算法對路徑優化模型進行求解。為進一步說明引入Clifford代數計算后對于提高尋徑算法效率的改善作用，筆者將此5組測試路徑代入文獻[18]算法模型進行仿真，其各代最優解的運輸功能耗統計如圖7所示。

圖7 基于改進遺傳算法的路徑優化結果Fig.7 Route optimization results based on IGA

對比圖6和7可發現，圖7中N1和N4兩組模型迭代前期收斂速度緩慢，并且伴有過早熟現象。而圖6中引入幾何代數方法后算法的收斂速度更快，而且能消除圖7中的過早熟現象，能夠快速的優化出全局最優解。對比N2,N3和N5節點相對較少的路徑，圖6中3組曲線收斂方向上的梯度明顯大于圖7中曲線。因此，可以說明文中算法具有更快的收斂速度和過早熟控制能力。

最后為論證采用時變運輸功作為尋徑問題目標函數的優勢，筆者進一步利用經典靜態網絡路徑優化算法對5組測試路徑進行仿真實驗，其仿真計算結果見表3。通過對比表格中數據可看出，較之經典算法，文中算法能快速的找出路徑中的能耗最優解，對于求解路徑優化問題具有更強的現實意義。

表3 對比算法的優化效果
Table 3 Comparison of the effect of algorithmic optimization

CaseLoad StatusAlgorithmsNodeAverage speed/(km·h-1)Haul dist-ance/kmTransport energy/kJExecution time/sN11Clifford-GA74341.39746 932.95.16Dijkstra/PSO321.27776 826.421.17/7.79N21Clifford-GA31311.17677 493.72.02Dijkstra /PSO291.08704 826.58.77/3.04N31Clifford-GA39341.68898 642.13.97Dijkstra /PSO331.59914 732.311.87/3.73N41Clifford-GA77351.93959 358.65.07Dijkstra /PSO321.87967 439.525.02/9.35N51Clifford-GA36271.94955 632.71.59Dijkstra /PSO221.67979 261.87.07/4.72

5 結 論

(1)從有向圖網絡分析法出發，將經典歐式空間內網絡分析方法推廣至幾何代數空間，建立了一套路徑的幾何拓撲連通性和約束指標計算的方法，實現了幾何拓撲和數值最優化問題的分離，降低了傳統露天礦多約束條件路徑優化問題的復雜度。

(2)將路徑分析中的數值型約束嵌入到幾何代數空間，并根據露天礦山工程實際，建立了基于時變運輸功的路徑優化模型，并結合數理統計和隨機理論，提出兩組推論和一組優化策略，顯著提高了算法的收斂效率。

(3)針對傳統遺傳算法的隨機路徑編碼易存在冗余編碼問題，通過引入外積拓撲運算結果進行啟發式遺傳編碼，能有效提高遺傳算法的收斂速度。

(4)通過對比多組尋徑算法，證明采用Clifford代數與遺傳算法進行組合來構建路徑優化算法是現實可行的，對于降低礦山能耗、指導礦山生產具有極為重要的現實意義。