梁 肖，周湘貞

(1.河北政法職業(yè)學院 計算機系，石家莊 050000；2.鄭州升達經貿管理學院 信息工程系，鄭州 451191)

基于遺傳算法的小麥收割機路徑智能優(yōu)化控制研究

梁 肖1，周湘貞2

(1.河北政法職業(yè)學院 計算機系，石家莊 050000；2.鄭州升達經貿管理學院 信息工程系，鄭州 451191)

基于遺傳算法，以小麥收割機全局路徑優(yōu)化為研究目標，對小麥收割機從起始點到終點的收割作業(yè)問題進行了數(shù)學建模，并利用MatLab軟件進行了仿真計算。結果表明：采用遺傳算法得到的優(yōu)化路徑比駕駛員主觀的隨機路徑縮短路線19km，節(jié)省費用和時間各為10.8%和7.8%。這說明，該算法可以對小麥收割機全局路徑進行有效優(yōu)化，能夠大大提高小麥收割機的工作效率，實際應用前景廣闊。

小麥收割機；路徑優(yōu)化；遺傳算法；MatLab

0 引言

人工智能技術和互聯(lián)網技術的發(fā)展和應用，加快了我國從傳統(tǒng)農業(yè)向現(xiàn)代農業(yè)轉型的步伐，提高了農業(yè)生產的自動化水平和作業(yè)效率。在聯(lián)合收割機作業(yè)效率的研究中，全局路徑優(yōu)化是研究的重點問題。目前，往往采用蟻群、遺傳、免疫、聚類分割、BP網絡神經及多目標粒子群等人工智能算法進行路徑的優(yōu)化。本文引入遺傳算法，對小麥收割機作業(yè)過程進行全局路徑優(yōu)化，可以大大節(jié)省作業(yè)時間和成本，提高小麥收割機的工作效率。

1 遺傳算法概述

遺傳算法是以達爾文進化論為基礎提出的一種優(yōu)勝劣汰算法，其模擬自然選擇和遺傳生物進化過程中的計算模型，可以進行全局區(qū)域搜索最優(yōu)解。遺傳算法采用一串編碼組合，將需要解決問題的假設解集看作單個個體，然后將待解決問題看成是一個大環(huán)境，每個個體在這個大環(huán)境中的適應能力稱為適配度，適配度越高存活率越高。因此，將生物進化中的繁殖、雜交、變異、競爭和選擇引入算法中，將適配度表達式與優(yōu)化問題相結合，建立目標函數(shù)對應關系。

傳統(tǒng)優(yōu)化算法往往以梯度信息尋找最優(yōu)點，其缺點是可能因陷入局部最優(yōu)而無法得到最優(yōu)解。遺傳算法則是一種全局尋優(yōu)方法，更易找到全局最優(yōu)解。遺傳算法其實是一種計算機模擬方法，具有適用面廣、多點搜索、魯棒性好、自適應強、并行性高的特點，本質來講是一種有著自適應能力的搜索優(yōu)化方法。

對于使用遺傳算法解決小麥收割機路徑智能優(yōu)化控制問題，首先需要構建待解決問題的假設解集的編碼形式，然后通過選擇、交叉、變異操作來尋找最優(yōu)解。遺傳算法解決路徑智能優(yōu)化控制問題的流程如圖1所示。

圖1 遺傳算法流程Fig.1 The genetic algorithm flow

遺傳算法流程主要包括以下幾個步驟：

1)準備。

2)初始化，設定變量和可行解等參數(shù)值。

3)產生一個個體數(shù)為100的初始種群。

4)輸入第一個樣本值P1。

5)進行遺傳操作。

6)若P≥300，則不滿足要求，退出遺傳算法；若P<300，則繼續(xù)執(zhí)行下一步。

7)將P進行加1操作，并指向下一個樣本，且q值也加1。

8)轉入步驟5)。

2 建立小麥收割機路徑智能優(yōu)化問題模型

小麥收割機路徑優(yōu)化問題是跨區(qū)收割最為重要的問題，緊密聯(lián)系生產效率。如果不將收割路線進行系統(tǒng)規(guī)劃，容易造成盲目跨區(qū)作業(yè)及收割機行走路徑過長，增加作業(yè)成本。在尋求小麥收割機路徑最優(yōu)化中過程，合理進行數(shù)學建模是進行路徑優(yōu)化算法的重要途徑。

2.1 車輛路徑優(yōu)化問題的一般描述

本文研究的小麥收割機路徑優(yōu)化是以有限個具體的作業(yè)點為服務對象的路徑優(yōu)化VRP問題。對于具體問題，VRP路徑優(yōu)化的數(shù)學描述形式較多，但一般可以將此類問題描述為：用作業(yè)起點向多個作業(yè)區(qū)域依次收割，在跨區(qū)域作業(yè)過程中計算或者規(guī)劃出一條最優(yōu)路徑的作業(yè)路線，使得收割機在整個作業(yè)過程中找出一種或者多種優(yōu)化目標，從而使總的路線長度最短。

VRP路徑優(yōu)化問題中一般需要事先知道收割機起始和各個作業(yè)區(qū)域的地理位置，實現(xiàn)優(yōu)化目標需要了解如下3點：

1)使小麥收割機在作業(yè)過程中行走路徑最短；

2)使作業(yè)過程的總成本最小，包括燃油費、人工費和其它費用；

3)使整個作業(yè)過程時間最少。

一般在小麥收割機路徑優(yōu)化中，起始點A0與各個作業(yè)區(qū)域點A1到An的位置均已知，各點之間的距離也已經知道，小麥收割機從A0至A1、An開始收割作業(yè)。該路徑優(yōu)化問題是指小麥收割機在行駛路徑最短的情況下到達每個作業(yè)區(qū)域進行作業(yè)，其路徑優(yōu)化模型如圖2所示。

2.2 建立數(shù)學建模

針對小麥收割機從A0至A1—An收割作業(yè)問題，建立數(shù)學模型，如圖3所示。

圖2 小麥收割機路徑VRP模型Fig.2 The VRP model of wheat harvester path

圖3 小麥收割機路徑優(yōu)化數(shù)學模型Fig.3 The mathematical model of path optimization of wheat harvester

圖3中，A0到Ai的運動路徑全部給出，只需確定一條最優(yōu)路徑，使得所有區(qū)域小麥收割完畢即可。因此，該問題優(yōu)化目標是成本最低、所需時間最少或行駛路線最短。本文將行駛路線最短作為優(yōu)化目標，對小麥收割機作業(yè)路徑進行優(yōu)化。首先假設：

1)假設小麥收割機在換區(qū)作業(yè)中的行走速度為定值；

2)假設小麥收割機在各路線通行狀態(tài)一致；

3)假設行駛費用、所需時間與路程成正比；

4)假設小麥收割機全程無故障，所有費用均來自行駛費用。

小麥收割機路徑優(yōu)化問題的目標是在滿足以下約束條件下，使收割機總行駛成本最小，具體如下：

1)路徑的起點和終點都是作業(yè)區(qū)域點；

2)每個作業(yè)區(qū)域點收割任務一次完成，不能重復路過兩次；

3)所有作業(yè)區(qū)域點收割任務不能超過收割機預算時間。

小麥收割機路徑優(yōu)化模型可以描述為

(1)

其中，i=0,1,2,…,n；k=0,1,2,…,n。

(2)

根據收割機總行駛成本最小為目標，建立小麥收割機路徑優(yōu)化模型，即

(3)

(4)

(5)

(6)

(7)

(8)

xij∈{0,1} (i,j=0,1,,…,n;k=1,2,…,K)

(9)

yki∈{0,1} (i=0,1,,…,n;k=1,2,…,K)

(10)

其中，作業(yè)區(qū)域點編號為0,1,2,…，n。式(3)是小麥收割機行駛成本最低的目標函數(shù)；式(4)是每個作業(yè)區(qū)域工作時間的約束條件；式(5)是保證每個作業(yè)區(qū)域都會到達的約束條件；式(6)是保證收割機從出發(fā)點出發(fā)最后返回到出發(fā)點的約束條件；式(7)～式(10)是收割機行走路徑最短的約束條件。

3 小麥收割機路徑智能優(yōu)化問題求解

3.1 遺傳算法路徑優(yōu)化基本參數(shù)

在采用遺傳算法進行路徑優(yōu)化前，首先需要清楚群體規(guī)模、編碼長度、交叉概率、變異概率、迭代步長和終止條件。具體如下：

1)群體規(guī)模。群體規(guī)模較小可以提高運算速度，但會降低種群多樣性，進而破壞全局最優(yōu)化；而規(guī)模過大亦會降低運算速度，在求優(yōu)過程中很難收斂。

2)編碼長度。編碼長度若采用2進制編碼，選取時需要考慮求解問題精度；若采用浮點數(shù)編碼，則編碼長度由實際問題決定，與精度沒有太大關系。

3)交叉概率Pc。交叉概率與父代間發(fā)生交叉概率有關，常常取0.5上下。交叉概率大不利于全局路徑的優(yōu)化，而交叉概率小則會增加計算時間、降低算法效率。

4)變異概率Pm。變異算子是在全局求優(yōu)的過程中跳出局部求優(yōu)的一種辦法，取值不能太大，一般取0.1～0.3。

5)迭代步長。迭代步長是指多長時間迭代1次，該值過大會降低優(yōu)化效率，過小會加大計算時間。

6)終止條件。在初始階段設置一終止條件，使算法在達到要求后結束該操作，并得到全局最優(yōu)解。

3.2 小麥收割機路徑優(yōu)化遺傳算法的設計

針對本文提出的從起始點到8個區(qū)域依次作業(yè)小麥收割機路徑優(yōu)化問題，遺傳算法結合選擇、交叉和變異3種算子的優(yōu)化設計。對于遺傳算法而言，交叉概率越大表示種群進化程度越高，而變異可能性較小。小麥收割機路徑優(yōu)化問題中，遺傳算法各參數(shù)設定如下：種群大小M為30；最大迭代次數(shù)G為300；交叉概率Pc為0.7；變異概率Pm為0.2。

參數(shù)設定完成后，可以對可行解集進行編碼，得到初始種群，設定好配度函數(shù)與終止條件；根據數(shù)學模型的輸入條件，結合適配度計算結果進行種群選擇操作。小麥收割機路徑優(yōu)化遺傳算法的步驟如圖4所示。

圖4 小麥收割機路徑優(yōu)化遺傳算法的步驟Fig.4 The steps of optimization genetic algorithm for wheat harvester

4 實驗與結果分析

根據上述從起始點到8個區(qū)域依次作業(yè)的小麥收割機路徑優(yōu)化遺傳算法設計方案，由美國MathWorks公司的MatLab軟件進行計算，經過87次迭代后收斂。優(yōu)化結果如下：

vx_opt0= [0.14 0.27 0.19 0.43 0.68 0.44 0.63 0.91]

vx_opt1= [0.23 0.56 0.45 0.79]

vx_opt2= [0.55 0.21 0.26 0.68]

結合適配度計算結果進行種群選擇操作，將編碼解碼后得到最優(yōu)的路徑方案為A0→A1→A2→A3→A4→A5→A6→A7→A8→A0。

最優(yōu)路徑方案的有向圖如圖5所示。

圖5 最優(yōu)路徑方案的有向圖Fig.5 The directed graph of the optimal path plan

為了分析優(yōu)化結果和可信度，本文將遺傳算法得到的最優(yōu)路徑與駕駛員主觀進行的隨機路徑進行對比分析，如表1所示。

表1 優(yōu)化路徑與隨機路徑對比分析

從圖5和表1可以看出：遺傳算法得到的優(yōu)化路徑長度為66km，駕駛員主觀的隨機路徑為85 km，優(yōu)化路徑縮短路線19km，節(jié)省費用和時間各為10.8%和7.8%。從路徑長度和耗費時間而言，遺傳算法路徑較短并且大大節(jié)省了時間和成本，具有良好的優(yōu)化效果，其優(yōu)勢較為明顯。

5 結論

1)為了實現(xiàn)小麥收割機全局路徑規(guī)劃功能，利用遺傳算法對路徑規(guī)劃進行有效優(yōu)化。對小麥收割機從A0至A1—An收割作業(yè)問題，進行數(shù)學建模，并設定好配度函數(shù)與終止條件進行種群選擇操作，簡化了計算的復雜性，大大提高了全局優(yōu)化效率。

2)利用MatLab軟件對小麥收割機全局路徑規(guī)劃進行了仿真計算，結果表明：采用遺傳算法得到的優(yōu)化路徑長度為66km，駕駛員主觀的隨機路徑為85 km，遺傳算法得到優(yōu)化路徑縮短路線19km，節(jié)省費用和時間各為10.8%和7.8%。因此，遺傳算法路徑較短并且大大節(jié)省了時間和成本，具有良好的優(yōu)化效果，大大提高了小麥收割機的工作效率，實際應用前景廣闊。

[1] 趙辰.基于遺傳算法的車輛路徑優(yōu)化問題研究[D].天津：天津大學,2012.

[2] 晏剛,王力,周俊,等.基于改進型遺傳算法的AUV路徑規(guī)劃[J].重慶理工大學學報：自然科學版,2010(5):81-85.

[3] 朱大奇,顏明重.移動機器人路徑規(guī)劃技術綜述[J]. 控制與決策,2010(7):961-967.

[4] 朱霞,陳仁文,徐棟霞,等.基于改進粒子群的焊點檢測路徑規(guī)劃方法[J].儀器儀表學報,2014(11):2484-2493.

[5] 張培彥,李丹丹.物聯(lián)網技術在聯(lián)合收割機跨區(qū)作業(yè)中的應用研究[J].南方農機,2015(3):58-59,62.

[6] 饒喆,唐雙喜,劉國平.基于蟻群粒子群混合算法的K均值聚類優(yōu)化算法研究[J].數(shù)字技術與應用,2015(4):122-123.

[7] 李天旭,陳廣大.基于改進遺傳算法的室內移動機器人路徑規(guī)劃[J].制造業(yè)自動化,2015(20):31-35.

[8] 王銀年.遺傳算法的研究與應用[D].無錫：江南大學,2009.

[9] 王麗.移動機器人路徑規(guī)劃方法研究[D].西安：西北工業(yè)大學,2007.

[10] 蔣卓強.基于遺傳模擬退火算法的靜態(tài)路徑規(guī)劃研究[D].重慶：重慶大學,2007.

[11] 張燕濤.基于遺傳算法的泊位調度問題優(yōu)化研究及仿真[D].武漢：武漢理工大學,2005.

[12] 李麗.基于遺傳算法的艦船航行路徑規(guī)劃技術研究[D].哈爾濱：哈爾濱工程大學,2006.

[13] 張敏輝,賴麟,孫連海.基于遺傳算法的研究與Matlab代碼的實現(xiàn)[J].四川教育學院學報,2012(1):115- 117.

[14] 徐曉晴,朱慶保.動態(tài)環(huán)境下基于多人工魚群算法和避碰規(guī)則庫的機器人路徑規(guī)劃[J].電子學報,2012(8):1694-1700.

[15] 林愛蘭.淺談如何提高聯(lián)合收割機的作業(yè)效率[J]. 機電技術,2005(1):21-22,28.

[16] 陳華華,杜歆,顧偉康. 基于遺傳算法的靜態(tài)環(huán)境全局路徑規(guī)劃[J].浙江大學學報:理學版,2005(1): 49-53,61.

[17] 趙金輝,碩良勛,曲文斌. 基于遺傳L-system植物繁殖與模擬的研究[J].邢臺職業(yè)技術學院學報,2006(3):30-32.

[18] 崔建軍.基于遺傳算法的移動機器人路徑規(guī)劃研究[D].西安：西安科技大學,2010.

[19] 陳衛(wèi)東,朱奇光.基于模糊算法的移動機器人路徑規(guī)劃[J].電子學報,2011(4):971-974,980.

[20] 張銀玲,牛小梅.蟻群算法在移動機器人路徑規(guī)劃中的仿真研究[J].計算機仿真,2011(6):231-234.

[21] 朱磊,樊繼壯,趙杰,等.基于柵格法的礦難搜索機器人全局路徑規(guī)劃與局部避障[J].中南大學學報：自然科學版,2011(11):3421-3428.

[22] 趙榮齊.基于人工勢場法的機器人路徑規(guī)劃研究[D].濟南：山東大學,2008.

[23] 于海璁,陸鋒.一種基于遺傳算法的多模式多標準路徑規(guī)劃方法[J].測繪學報,2014(1):89-96.

[24] 史恩秀,陳敏敏,李俊,等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農業(yè)機械學報,2014(6):53-57.

[25] 劉傳領.基于勢場法和遺傳算法的機器人路徑規(guī)劃技術研究[D].南京：南京理工大學,2012.

[26] 張宏烈.移動機器人全局路徑規(guī)劃的研究[D].哈爾濱：哈爾濱工程大學,2002.

[27] 黃鋁文.蘋果采摘機器人視覺識別與路徑規(guī)劃方法研究[D].楊凌：西北農林科技大學,2013.

[28] 趙慶波.果樹采摘機器人控制與避障技術研究[D].鎮(zhèn)江：江蘇大學,2008.

Research on Intelligent Optimization Control of Wheat Harvester Path Based on Genetic Algorithm

Liang Xiao1, Zhou Xiangzhen2

(1.Department of Computer Science，Hebei Professional College of Political Science and Low,Shijiazhuang 050000, China; 2.Department of Information Engineering, Shengda Economics Trade & Management College of Zhengzhou, Zhengzhou 451191, China)

Based on genetic algorithm, it studied the path optimization of wheat harvester global through harvesting wheat harvester from the starting point to the end, the mathematical modeling and simulation by using MATLAB software. The simulation results showed that the random path optimization path obtained by genetic algorithm than the subjective saving route 19km, save cost and time is 10.8% and 7.8%, indicating that the algorithm can effectively optimize the wheat harvester global path, which can greatly improve the wheat harvesting efficiency, application prospect.

wheat harvester; path optimization; genetic algorithm; MatLab

2016-12-11

河南省科技攻關計劃項目(142102310362)

梁 肖(1984-),女，河北保定人，講師，碩士，(E-mail)liangxiaolx123@sina.com。

S225.3

A

1003-188X(2018)02-0056-05