基于遺傳算法的小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化控制研究

梁 肖，周湘貞

(1.河北政法職業(yè)學(xué)院 計(jì)算機(jī)系，石家莊 050000；2.鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院 信息工程系，鄭州 451191)

基于遺傳算法的小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化控制研究

梁 肖1，周湘貞2

(1.河北政法職業(yè)學(xué)院 計(jì)算機(jī)系，石家莊 050000；2.鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院 信息工程系，鄭州 451191)

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

小麥?zhǔn)崭顧C(jī)；路徑優(yōu)化；遺傳算法；MatLab

0 引言

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

1 遺傳算法概述

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

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

對(duì)于使用遺傳算法解決小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化控制問(wèn)題，首先需要構(gòu)建待解決問(wèn)題的假設(shè)解集的編碼形式，然后通過(guò)選擇、交叉、變異操作來(lái)尋找最優(yōu)解。遺傳算法解決路徑智能優(yōu)化控制問(wèn)題的流程如圖1所示。

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

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

1)準(zhǔn)備。

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

3)產(chǎn)生一個(gè)個(gè)體數(shù)為100的初始種群。

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

5)進(jìn)行遺傳操作。

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

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

8)轉(zhuǎn)入步驟5)。

2 建立小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化問(wèn)題模型

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

2.1 車(chē)輛路徑優(yōu)化問(wèn)題的一般描述

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

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

1)使小麥?zhǔn)崭顧C(jī)在作業(yè)過(guò)程中行走路徑最短；

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

3)使整個(gè)作業(yè)過(guò)程時(shí)間最少。

一般在小麥?zhǔn)崭顧C(jī)路徑優(yōu)化中，起始點(diǎn)A0與各個(gè)作業(yè)區(qū)域點(diǎn)A1到An的位置均已知，各點(diǎn)之間的距離也已經(jīng)知道，小麥?zhǔn)崭顧C(jī)從A0至A1、An開(kāi)始收割作業(yè)。該路徑優(yōu)化問(wèn)題是指小麥?zhǔn)崭顧C(jī)在行駛路徑最短的情況下到達(dá)每個(gè)作業(yè)區(qū)域進(jìn)行作業(yè)，其路徑優(yōu)化模型如圖2所示。

2.2 建立數(shù)學(xué)建模

針對(duì)小麥?zhǔn)崭顧C(jī)從A0至A1—An收割作業(yè)問(wèn)題，建立數(shù)學(xué)模型，如圖3所示。

圖2 小麥?zhǔn)崭顧C(jī)路徑VRP模型Fig.2 The VRP model of wheat harvester path

圖3 小麥?zhǔn)崭顧C(jī)路徑優(yōu)化數(shù)學(xué)模型Fig.3 The mathematical model of path optimization of wheat harvester

圖3中，A0到Ai的運(yùn)動(dòng)路徑全部給出，只需確定一條最優(yōu)路徑，使得所有區(qū)域小麥?zhǔn)崭钔戤吋纯伞Ｒ虼?，該?wèn)題優(yōu)化目標(biāo)是成本最低、所需時(shí)間最少或行駛路線最短。本文將行駛路線最短作為優(yōu)化目標(biāo)，對(duì)小麥?zhǔn)崭顧C(jī)作業(yè)路徑進(jìn)行優(yōu)化。首先假設(shè)：

1)假設(shè)小麥?zhǔn)崭顧C(jī)在換區(qū)作業(yè)中的行走速度為定值；

2)假設(shè)小麥?zhǔn)崭顧C(jī)在各路線通行狀態(tài)一致；

3)假設(shè)行駛費(fèi)用、所需時(shí)間與路程成正比；

4)假設(shè)小麥?zhǔn)崭顧C(jī)全程無(wú)故障，所有費(fèi)用均來(lái)自行駛費(fèi)用。

小麥?zhǔn)崭顧C(jī)路徑優(yōu)化問(wèn)題的目標(biāo)是在滿(mǎn)足以下約束條件下，使收割機(jī)總行駛成本最小，具體如下：

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

2)每個(gè)作業(yè)區(qū)域點(diǎn)收割任務(wù)一次完成，不能重復(fù)路過(guò)兩次；

3)所有作業(yè)區(qū)域點(diǎn)收割任務(wù)不能超過(guò)收割機(jī)預(yù)算時(shí)間。

小麥?zhǔn)崭顧C(jī)路徑優(yōu)化模型可以描述為

(1)

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

(2)

根據(jù)收割機(jī)總行駛成本最小為目標(biāo)，建立小麥?zhǔn)崭顧C(jī)路徑優(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ū)域點(diǎn)編號(hào)為0,1,2,…，n。式(3)是小麥?zhǔn)崭顧C(jī)行駛成本最低的目標(biāo)函數(shù)；式(4)是每個(gè)作業(yè)區(qū)域工作時(shí)間的約束條件；式(5)是保證每個(gè)作業(yè)區(qū)域都會(huì)到達(dá)的約束條件；式(6)是保證收割機(jī)從出發(fā)點(diǎn)出發(fā)最后返回到出發(fā)點(diǎn)的約束條件；式(7)～式(10)是收割機(jī)行走路徑最短的約束條件。

3 小麥?zhǔn)崭顧C(jī)路徑智能優(yōu)化問(wèn)題求解

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

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

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

2)編碼長(zhǎng)度。編碼長(zhǎng)度若采用2進(jìn)制編碼，選取時(shí)需要考慮求解問(wèn)題精度；若采用浮點(diǎn)數(shù)編碼，則編碼長(zhǎng)度由實(shí)際問(wèn)題決定，與精度沒(méi)有太大關(guān)系。

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

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

5)迭代步長(zhǎng)。迭代步長(zhǎng)是指多長(zhǎng)時(shí)間迭代1次，該值過(guò)大會(huì)降低優(yōu)化效率，過(guò)小會(huì)加大計(jì)算時(shí)間。

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

3.2 小麥?zhǔn)崭顧C(jī)路徑優(yōu)化遺傳算法的設(shè)計(jì)

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

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

圖4 小麥?zhǔn)崭顧C(jī)路徑優(yōu)化遺傳算法的步驟Fig.4 The steps of optimization genetic algorithm for wheat harvester

4 實(shí)驗(yàn)與結(jié)果分析

根據(jù)上述從起始點(diǎn)到8個(gè)區(qū)域依次作業(yè)的小麥?zhǔn)崭顧C(jī)路徑優(yōu)化遺傳算法設(shè)計(jì)方案，由美國(guó)MathWorks公司的MatLab軟件進(jìn)行計(jì)算，經(jīng)過(guò)87次迭代后收斂。優(yōu)化結(jié)果如下：

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]

結(jié)合適配度計(jì)算結(jié)果進(jìn)行種群選擇操作，將編碼解碼后得到最優(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)化結(jié)果和可信度，本文將遺傳算法得到的最優(yōu)路徑與駕駛員主觀進(jìn)行的隨機(jī)路徑進(jìn)行對(duì)比分析，如表1所示。

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

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

5 結(jié)論

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

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

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

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

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

[4] 朱霞,陳仁文,徐棟霞,等.基于改進(jìn)粒子群的焊點(diǎn)檢測(cè)路徑規(guī)劃方法[J].儀器儀表學(xué)報(bào),2014(11):2484-2493.

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

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

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

[8] 王銀年.遺傳算法的研究與應(yīng)用[D].無(wú)錫：江南大學(xué),2009.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[23] 于海璁,陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測(cè)繪學(xué)報(bào),2014(1):89-96.

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

[25] 劉傳領(lǐng).基于勢(shì)場(chǎng)法和遺傳算法的機(jī)器人路徑規(guī)劃技術(shù)研究[D].南京：南京理工大學(xué),2012.

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

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

[28] 趙慶波.果樹(shù)采摘機(jī)器人控制與避障技術(shù)研究[D].鎮(zhèn)江：江蘇大學(xué),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

河南省科技攻關(guān)計(jì)劃項(xiàng)目(142102310362)

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

S225.3

A

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