基于遺傳算法的鈷結殼采礦車行走路徑規劃研究

陳 波(長沙航空職業技術學院,湖南 長沙 410124)

基于遺傳算法的鈷結殼采礦車行走路徑規劃研究

陳 波
(長沙航空職業技術學院,湖南 長沙 410124)

海洋富鈷結殼是海洋礦產資源中經濟價值高又極具戰略意義的礦產之一。富鈷結殼主要位于海洋的海山表面，因所處地形地貌復雜多樣，所以開采難度非常大。基于遺傳算法對鈷結殼采礦系統中關鍵的采礦車行走路徑問題進行了研究。

鈷結殼采礦車；路徑規劃；遺傳算法

礦產資源是人類社會進步和經濟發展的物質基礎。從長遠來看，礦業在國民經濟和社會發展中基礎地位不可替代。在世界經濟和科學技術高速發展的今天，各國政府已逐漸將目光從內陸投向資源豐富的海洋，而富含多種稀缺礦物的海底多金屬結殼開發也成為各國大力發展的戰略目標。海洋富鈷結殼(鐵錳結殼、錳結殼)是現今所探索到的最具戰略發展意義和潛在經濟價值的海洋礦產資源之一，礦體富含鈷、鈦、鈰、鉑和鎳等多種稀貴金屬，其中鈷的含量相比于陸地原生鈷礦中鈷含量凈高幾十倍，平均含量達到1%以上[1，2]。而據科學考察，僅太平洋某火山隆起地帶就蘊含約為10億噸的富鈷結殼礦床[3，4]。但是，因富鈷結殼多位于海洋山體斜坡表面處，開采環境惡劣復雜，結殼開采難度大。而研制一種能夠在深海水域自主作業的移動車輛是深海采礦作業最關鍵的問題。鈷結殼采礦車是深海采礦作業的主體，能夠實現在水下自主作業功能，對其研究涉及眾多學科領域[5]，其中采礦車路徑規劃是其研究的基礎和重點[6]。

路徑規劃是鈷結殼采礦車行走的關鍵步驟。鈷結殼采礦車的行走是指采礦車在既定的海底采礦區域根據預先設定的路徑進行安全行駛，并在行駛過程中高效地完成采礦作業。采礦車在海底的行走主要包括路徑規劃和路徑跟蹤兩個部分。采礦車路徑規劃包括兩個方面：1)高效地獲得作業環境信息；2)在此基礎上，規劃采礦車的最優行走路徑[7]。由于采礦車深海作業環境的極端復雜，作業要求具有多樣性，因此采礦車的行走具有多約束性和多目標性[8]。

遺傳算法(Genetic Algorithm)屬于進化算法(Evolutionary Algorithms) 的一種，最初由美國Michigan大學J.Holland教授于1975年首先提出來，通過模仿自然選擇和遺傳機理獲得最優解[9]。遺傳算法主要包括三個算子：選擇、交叉和變異[10]。本文以鉸接式深海鈷結殼采礦車為研究對象，在分析總體方案和主要控制執行元件的基礎上，運用遺傳算法研究其海底采礦作業行走路徑。

1 采礦車路徑規劃總體方案設計

采礦車通過聲納傳感器檢測前方障礙物的信息。在行進過程中聲納傳感器只能檢測到障礙物面向采礦車這一側的信息，而障礙物的完整信息卻無法有效獲取。為獲取障礙物更多的有效信息，可以采用多次局部規劃過程代替一次性規劃，并在每次局部規劃中充分利用該時刻最新的局部環境信息的方案。但是這種方案會導致控制系統實效性伴隨頻繁的局部路徑規劃操作而降低[11]。

本文采用障礙物膨脹處理的方法，提高控制系統算法效率，解決頻繁局部路徑規劃的弊病，如圖1所示，L1，L2是兩條聲納線，點A，B分別是聲納探測線與障礙物的切點。假設障礙物的位置、尺寸正好位于以A，B兩點為軸線的A、B劣弧后方之內。那么采礦車則可以直接沿著以劣弧A、B的鏡像曲線為依據規劃的路徑行走，并逐步獲取障礙物的完整信息。 如果A、B劣弧后方障礙物的位置、尺寸并不完全在A、B劣弧鏡像曲線的范圍內，則以當前障礙物的實際范圍為依據，重新規劃路徑。

圖1 采礦車聲納探測示意圖

以上路徑規劃步驟如圖2所示。

圖2 路徑規劃流程圖

2 基于遺傳算法的采礦車路徑規劃

2.1 遺傳算法的運算過程和設計

遺傳算法屬于進化算法的一種，其具體步驟如圖3所示。

圖3 遺傳算法流程圖

2.2 路徑編碼方式

遺傳算法是在編碼空間和解碼空間中交替工作。所以解決路徑編碼問題[12]是基于遺傳算法的路徑規劃研究的首要問題。

實際路徑點都是二維的，為了提高算法的運算速度，需將二維路徑坐標點進行降維處理。設當前坐標系為x0y，x軸為起始點與目標點的連線，起始點即為原點。將終點和起點間的線段等分為n段，取等分點xj(j=1，2，…，n-2)，設過xj點與x軸垂直的直線為Lj，在Lj上隨機選取一點Pj，共得到n-2個點，P0，P(n-1)分別為起點、終點，如圖4所示。

圖4 路徑編碼示意圖

路徑規劃等分點的間距應該保持在適當的范圍內。根據采礦車的具體情況，把等分點間距定為1米。此外，局部規劃路徑的長度很大程度上由聲納探測器的作用距離決定。國產高端聲納探測器最大的作用距離為200米[13]，可以將路徑規劃最優檢測長度設定為100米。在100米的路徑區域里選取101個等分點(含首尾兩點)，然后用隨機數在每一個等分點生成相對應的縱坐標，依次連接所有的隨機生成的點，得到一條隨機路徑。

等分點的縱坐標設為yi,j，隨機路徑為Ri，二維的實際路徑通過以上步驟轉化為一維的y坐標編碼，采用浮點數方式編碼，具體編碼如下：

yi,0yi,1yi,2…yi,n-2yi,n-1

當采礦車的當前位置縱坐標為yi,0，目標點縱坐標為yi,n-1，路徑則為：

Ri=((xi,0，yi,0)，(xi,1，yi,1)，…，(xi,n-1，yi,n-1))

(1)

對應的染色體為：

vi=(yi,0，yi,1，…，yi,n-1)

(2)

2.3 路徑基因初始種群設定

由遺傳算法獲取的采礦車最佳行走路徑是必須位于障礙物區域之外。但是從遺傳學的角度來說，障礙物區域內靠近設定路徑的點顯然比平坦區域遙遠的點更具有基因遺傳的優越性。為了提高遺傳基因的優勢性，采用懲罰策略把具有遺傳優勢的點包含在初始群體的設定范圍內，并對不可行解給予一定程度的罰分，使其適應值相應降低。

根據采礦車的具體作業情況，可將作業區域區分為兩種：即障礙物區域和平坦區域。如圖5所示，最優路徑點出現在平坦區與障礙物區的交界處a點附近。在障礙物區的路徑點c與最優路徑點a的距離比平坦區中的路徑點b近得多，雖然點c為不可行解，但是c點顯然比b點更具有優勢遺傳基因信息。為了最大限度利用c點的優勢遺傳基因信息，允許它繼續參與遺傳運算，同時給予適當的懲罰，作為其違反路徑安全性的一個判值。這樣基于遺傳算法的路徑種群具備了從平坦區和障礙物區同時逼近最優解的優勢。

圖5 平坦區域和障礙物區域示意圖

采用懲罰策略可使初始種群隨機點的搜索范圍擴大到整個搜索空間。本文采用10條染色體，對應的初始隨機路徑布滿整個采礦區域，如圖6所示。

圖6 初始路徑

2.4 懲罰策略的實現

為了有效地減少種群中違反約束的非可行解的個數，懲罰策略必須采用合適的遺傳因子和設計合理懲罰函數[14，15]。設Pi,j為隨機路徑點，P'i,j為該點對應的障礙物邊緣點，如圖7所示。

圖7 懲罰策略的實現示意圖

懲罰函數φ(vi)為

(3)

則

(4)

其中：yi，j為Pi，j點縱坐標值，y'i，j為P'i，j點縱坐標，兩點縱坐標通過聲納設備測定；ξ為函數的懲罰因子，取值為2。函數子項φi，j是被懲罰點與障礙物區與平坦區的交界處的函數距離。該點離邊界越遠，懲罰力度就越大。

2.5 路徑適應度函數的確定

適應度函數是搜索進化過程評估群體成員優劣程度的標準，直接影響遺傳算法的收斂速度和成敗[16，17]。為了滿足路徑規劃的特征，本文選取適應度函數時，需著重研究路徑的長度和光滑度等參數。

(1)路徑的長度

路徑長度指標函數如式(5)所示：

(5)

式中，D(vi)為路徑長度，yi,j為pi,j點的縱坐標，xi,j為pi,j點的橫坐標。

(2)路徑的光滑度

路徑光滑度指標函數如式(6)所示：

(6)

式中，φ(vi)為路徑光滑度，yi,j為pi,j點的縱坐標，xi,j為pi,j點的橫坐標。

采礦車轉彎時，角度應盡可能的小，生成的路徑越光滑越有助于采礦車運行。故路徑轉角差累積值φ(vi)越小的成員越優先級越高。

路徑長度指標函數和路徑光滑度指標函數均取最小值時，路徑長度指標函數和路徑光滑度指標函數通過線形相加得初始目標函數。

fit'(vi)=αD(vi)+βφ(vi)

(7)

將懲罰函數代入初始目標函數中得終點函數。

fit(vi)=αD(vi)+βφ(vi)+γφ(vi)

(8)

其中，fit( )為路徑最優函數 ，α、β、γ分別為長度指標函數、光滑度指標函數和懲罰函數的加權系數。

理想的路徑需滿足：1)位于可行域內，2)路徑光滑，3)路程短，所以終點函數的最優解為全局最小值。

適應度函數采用改進的界限構造法算出終點函數的全局最小值

(9)

其中，c為終點函數界限的保守預測值。

在路徑規劃中f(x)恒>0，故式(9)可改寫為：

(10)

當路徑規劃的初始階段，f(x)值較大，Fit(f(x))的改變需要f(x)巨大的變量才能實現。當路徑規劃處于終了階段時，f(x)值很小，f(x)的細小變量將導致Fit(f(x))顯著改變。

因此適應度為：

(11)

將求取全局最小值的終點目標函數映射為適應度函數。

2.6 選擇方式

選擇是從群體中優勝劣汰的操作過程。輪盤法是遺傳算法中應用最廣泛的選擇方法，即輪盤上的每個扇形分區與群體中的每個成員一一對應，且分區面積與對應成員的適應度成正比。輪盤旋轉一次即可從群體中選擇一個成員。

pi=fi/∑fi

(12)

式中，第i成員被選中的概率為pi；第i成員的適應度為fi；群體的累加適應度為∑fi。由式(12)推算可知，適應度值越高的成員，被選中的概率越大。

本文采用輪盤選擇法研究路徑規劃問題的步驟如下：

設第i個染色體為vi，按出現的次序累計群體內所有染色體的適應度函數值Fit(vi)，得到累計值sum：

(13)

染色體的選擇概率p(vi)如式(14)：

(14)

累積選擇概率q(vi) 如式(15)：

(15)

r為[0，1]內均勻分布的偽隨機數；若r≤q(vi)，則選擇染色體vi，否則，選擇第k個染色體vk，，滿足q(vk-1)

2.7 新個體產生方式

遺傳算法中新個體的產生模擬子代染色體產生的方式，即通過交叉和變異的方法產生子代。具體算法如下：

(1)交叉

交叉是遺傳算法中產生子代的主要方法。群中染色體配對后，染色體對中各元件按照式(16)進行交叉，從而產生子代染色體的相應元件。

y'i,k=λ1,kyi,k+(1-λ1,k)yj,ky'j,k=λ2,kyj,k+(1-λ2,k)yi,k

(16)

生成的子代染色體如式(17)所示。

vi=(y'i,0,y'i,1,…,y'i,n-1)vj=(y'j,0,y'j,1,…,y'j,n-1)

(17)

其中，yi,k，yj,k為親代染色體元件，y'i,k，y'j,k為子代染色體元件，λ1,k，λ2,k為隨機獲取的交叉系數，且0<λ1，λ2<1[18，19]。

(2)變異

變異是指將染色體的基因被等位基因替換得到子代染色體的過程[19]。變異算法能夠維持路徑規劃的多樣性。但路徑規劃又具有特殊性：在初始階段，需采用較大的變異量以增大遺傳搜索范圍；而在后期，需縮小變異幅度，僅對接近最優解的基因進行微調。因此本文設計了一種隨著搜索推進而變異逐漸減小的遺傳算法。

設染色體為vi，基因yi,j以某種概率變異，則生成的子代為：

v'i=(yi,0,yi,1,…y'i,j,yi,n-1)

(18)

其中，y'i,j以下列兩種方式變異：

y'i,j=yi,j+Δ(t,y"i,j-yi,j)y'i,j=yi,j-Δ(t,yi,j-y'i,j)

(19)

式中，y"i,j，y'i,j分別是yi,j的最大和最小值。設函數Δ(t,y"i,j-yi,j)和Δ(t,yi,j-y'i,j)的統一形式為Δ(t,y)(式18)，則Δ(t,y)隨著t的增加而趨近于0。

Δ(t,y)=y*r*(1-t/T)b

(20)

其中，r是[0，1]中的任何數，T是最長搜索時間，t為當前搜索時間，b是非均勻度參數。

由式(20)可知，在初始階段，t/T趨近于0，變異值Δ(t,y)趨近最大值，路徑搜索范圍最大；在結尾階段，t/T趨近于1，Δ(t,y)則逐漸趨于0，相當于僅在已有搜索結果上增加細小的校正。該變異算法既在前期促進了遺傳搜索的進行，又在后期保護了現有的搜索結果。

2.8 仿真試驗與結果分析

本文采用遺傳算法規劃了采礦車避障路徑，并通過仿真實驗驗證其效率和準度。

如圖8所示，驗證仿真程序由VC++ 6.0語言編寫，部分參數設為：種群規模為10，交叉概率為0.7，變異概率0.2。圖9中兩個橢圓體代表障礙物，A，B和C圖分別表示第10次，第20次和第40次迭代運算的結果。結果表明，隨著迭代次數的增加，路徑性能得到改善，規劃的路徑也更為精確。由此可見，獲得比較。

優越的可行駛路徑僅需通過40代的迭代運算，從而說明遺傳算法在路徑規劃研究中的適用和高效。

3 結論

采礦車路徑規劃問題是開采鈷結殼礦產資源的關鍵問題之一。本文在完善的總體方案框架內，通過系統研究遺傳算法各要素，設計并采用仿真程序驗證了采礦車最優化路徑規劃方案，從而證明了遺傳算法在鈷結殼采礦車路徑規劃研究中的可行性和高效性。

圖8 基于遺傳算法的避障路徑規劃仿真程序流程圖

圖9 遺傳算法仿真路徑規劃圖

[1] 沈裕軍，鐘祥，賀澤全．大洋鉆結殼資源鈷究開發現狀[J]．礦冶工程，1999， (2)．

[2] Yamazaki T.&T.Sharma. Distribution characteristics of CO-rich manganese deposition sea-mountain the central Pacific Ocean [J]．MarineGeoresources&Geotechnology，1998， (4)．

[3] Manheim F. T.Marine Cobalt Resources [J]．Science，1986，(4750)．

[4] James Hein. Cobalt rich ferro manganese crusts：global distribution composition，origin and Research activities．Poly metallic massive sulphides and cobalt-rich ferromanganese crusts：status and prospects[R]．ISATechnicalstudy，2000，(2)．

[5] 張捍東，鄭睿，岑豫皖．機器人路徑規劃技術的現狀與展望[J]．系統仿真學報，2005，(17).

[6] Nilsson N.A mobile automation：An application of artificial intelligence techniques[A]．Proceedingsofthe1stInternationalJointConferenceonArtificialIntelligence[C]，Washington，USA，1969.

[7] 王隨平，朱燕春．基于GAAA算法的深海集礦車的最優路徑規劃[J]．計算機測量與控制, 2008，(1)．

[8] 陳峰．深海底采礦機器車運動建模與控制研究[D]．長沙：中南大學，2005．

[9] 張文修，梁怡．遺傳算法的數學基礎[M]．西安：西安交通大學出版社，2000．

[10] 劉勇，康立山，陳毓屏．非數值并行算法(第二冊遺傳算法)[M]．北京：科學出版社，2000．

[11] 吳衛國，陳輝堂．非完整輪式移動機器人控制研究[A]．1997中國控制與決策年會[C]，1997．

[12] 鄭月鋒．遺傳算法在求解時間表問題中的應用研究[D]．杭州：浙江工業大學, 2005．

[13] 盧迎春，桑恩方．基于主動聲納的水下目標特征提取技術綜述[J]．哈爾濱工程大學學報，1997，(6)．

[14] Deb K. & S.Agrawal. A niched～penalty approach for constraint handling in genetic algorithms[A]．ProceedingsoftheICANNGA[C], Portoroz, Slovenia, 1999．

[15] Kazarlis S. A., S.E.Papadakis & J. B.Theocharis. Microgenetic algorithms as generalized hill-climbing operators for GA optimization[J]．EvolutionaryComputation, 2001，(3)．

[16] Krishnakumar k.,&D. E.Goldberg Control system optimization using genetic algorithms[J]．JournalofGuidance．ControlandDynamics，1992, (3)．

[17] Michalewicz Z．GeneticAlgorithms+DataStructures=EvolutionProgram[M]． New York: Springer-Verlag, 1996．

[18] Richard J.B.GeneticAlgorithmsandInvestmentStrategies[M]． New York: John Wiley & Sons, 1994．

[19] Allbrecht R., C.Reeves & N.Steele.ArtificialNeuralNetsandGeneticAlgorithms[M]．New York:Springer-Verlag, 1993．

[編校：楊 琴]

Path Planning Research Based on Genetic Algorithm for Cobalt-rich Crust Mining Vehicles

CHEN Bo

(ChangshaAeronauticalVocationalandTechnicalCollege，ChangshaHunan410124)

The cobalt-rich crust, a marine resource with an economic value and a strategic importance, is blocked to be mined by the complicated landform. The current paper focused on the path planning based on genetic algorithm which was a critical question of the cobalt-rich crust mining system.

cobalt-rich crust mining vehicle；path planning；genetic algorithm

2014-10-21

陳波(1979- )，女，湖南衡陽人，講師，工學碩士，研究方向為機械電子工程。

U442.4

A

1671-9654(2014)04-046-07