基于遺傳算法的農(nóng)業(yè)機(jī)械調(diào)配研究

劉 麗，劉 野，王新利

(黑龍江八一農(nóng)墾大學(xué) 工程學(xué)院，黑龍江 大慶 163319)

0 引言

農(nóng)業(yè)機(jī)械化程度是衡量現(xiàn)代農(nóng)業(yè)發(fā)展水平的重要標(biāo)志。近年來，現(xiàn)代科技對農(nóng)業(yè)的引領(lǐng)作用加速，我國農(nóng)機(jī)裝備水平和農(nóng)業(yè)機(jī)械化水平均明顯提升。與發(fā)達(dá)國家相比，我國農(nóng)業(yè)械機(jī)化總體水平仍然偏低，地區(qū)間發(fā)展不平衡、部分地區(qū)農(nóng)機(jī)閑置問題非常突出。2016年，黑龍江省農(nóng)業(yè)機(jī)械化水平達(dá)95%，黑龍江墾區(qū)農(nóng)業(yè)機(jī)械化率已近100%，且農(nóng)業(yè)裝備先進(jìn)，但由于氣候條件限制，這里每年11月至來年的4月近半年的時(shí)間大型進(jìn)口農(nóng)業(yè)機(jī)械處于閑置狀態(tài)。由于農(nóng)業(yè)生產(chǎn)具有較強(qiáng)的時(shí)效性和連貫性，對于大范圍的農(nóng)業(yè)生產(chǎn)作業(yè)，需要對農(nóng)機(jī)資源進(jìn)行合理配置和有效調(diào)度，以按時(shí)完成農(nóng)業(yè)生產(chǎn)任務(wù)，提高農(nóng)機(jī)利用率，避免農(nóng)作物損失和農(nóng)機(jī)資源浪費(fèi)，最終提高農(nóng)戶、機(jī)手和農(nóng)機(jī)組織的收益[1]。近年來，黑龍江墾區(qū)充分利用農(nóng)機(jī)資源實(shí)行跨區(qū)作業(yè)，大大提高了農(nóng)機(jī)利用率，但如何調(diào)配農(nóng)機(jī)以縮短作業(yè)時(shí)間并降低作業(yè)成本，發(fā)揮現(xiàn)代大型農(nóng)機(jī)對提高農(nóng)業(yè)生產(chǎn)效率的作用，推進(jìn)現(xiàn)代農(nóng)業(yè)發(fā)展，越來越成為重要的研究課題。

從本質(zhì)上講，農(nóng)業(yè)機(jī)械調(diào)配是一種排列組合的問題，在問題確定時(shí)，必定會存在問題的最優(yōu)解。然而，實(shí)際生產(chǎn)中的問題規(guī)模往往都比較大，排列組合的可能性呈指數(shù)化增長，在人類現(xiàn)有的計(jì)算能力下，只能精確求解很小規(guī)模的問題，遠(yuǎn)遠(yuǎn)不能滿足實(shí)際的生產(chǎn)需求。退而求其次，學(xué)術(shù)界提出了啟發(fā)式算法，這類算法基于直觀或經(jīng)驗(yàn)構(gòu)造，在可接受的計(jì)算資源消耗下，給出待解決組合優(yōu)化問題實(shí)例的一個(gè)可行解。雖然該可行解與最優(yōu)解的偏離程度難以預(yù)計(jì)，卻往往可以在實(shí)際的問題中證明可行解的有效性。

作為現(xiàn)代啟發(fā)式算法的代表之一，遺傳算法(Genetic Algorithm，簡稱GA)是基于適者生存的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法，通過模擬“染色體”的進(jìn)化，最終得到最適應(yīng)環(huán)境的個(gè)體，即問題的滿意解。

1 遺傳算法概述

遺傳算法[2]是由美國Michigan大學(xué)的Holland教授于1975年首先提出的，源于達(dá)爾文的進(jìn)化論、孟德爾的群體遺傳學(xué)說和魏茨曼的物種選擇學(xué)說，是一種基于自然選擇和基因遺傳學(xué)原理的隨機(jī)并行搜索算法和尋求全局最優(yōu)解而不需要任何初始化信息的高效優(yōu)化方法[3]。遺傳算法將目標(biāo)問題看作進(jìn)化環(huán)境，將目標(biāo)問題的解集當(dāng)作環(huán)境中的生物個(gè)體，通過適當(dāng)?shù)木幋a組合用解來表達(dá)個(gè)體，解答優(yōu)劣度代表著個(gè)體對生存環(huán)境的適應(yīng)程度，適應(yīng)度越高，個(gè)體存活率越高。算法借此將自然界中的優(yōu)勝劣汰引入到具體的問題中，采取適當(dāng)?shù)牟呗詠砟M生物進(jìn)化中的競爭、繁殖、變異和選擇，以引導(dǎo)問題的解逐步逼近最優(yōu)解。傳統(tǒng)優(yōu)化算法通常以梯度信息接近最優(yōu)點(diǎn)，容易陷入局部最優(yōu)而停止搜索；遺傳算法則通過全局尋優(yōu)的方式，提高了找到最優(yōu)解的可能性。本質(zhì)上，遺傳算法是一種計(jì)算機(jī)模擬方法，具有適用面廣、多點(diǎn)搜索、魯棒性好、自適應(yīng)強(qiáng)及并行性高的特點(diǎn)，是一種有著自適應(yīng)能力的搜索優(yōu)化方法，在函數(shù)優(yōu)化、圖像處理、系統(tǒng)辨識、自動控制、經(jīng)濟(jì)預(yù)測和工程優(yōu)化等領(lǐng)域得到了廣泛的應(yīng)用[4]。

2 建立農(nóng)業(yè)機(jī)械調(diào)配優(yōu)化問題模型

2.1 農(nóng)業(yè)機(jī)械調(diào)配優(yōu)化問題的描述

在確定數(shù)目及位置的農(nóng)機(jī)調(diào)配站中，派出確定數(shù)目的某項(xiàng)單一功能農(nóng)業(yè)機(jī)械，完成指定作業(yè)區(qū)域內(nèi)的單一目標(biāo)作業(yè)。農(nóng)機(jī)站適合指定作業(yè)需求的機(jī)型僅有一種；每塊農(nóng)田的待作業(yè)面積確定且已知，每輛農(nóng)機(jī)可以依次對多塊農(nóng)田實(shí)施作業(yè)，且對每塊農(nóng)田都通過一次作業(yè)即可完成；農(nóng)機(jī)隸屬于特定的調(diào)配站，作業(yè)完成后必須回到出發(fā)站。解答問題需要規(guī)劃所有農(nóng)機(jī)的作業(yè)路線，使得農(nóng)機(jī)在整個(gè)作業(yè)過程中滿足以下優(yōu)化目標(biāo)：每塊農(nóng)田都得以被實(shí)施作業(yè)；整個(gè)作業(yè)的農(nóng)機(jī)運(yùn)行路線最短；整個(gè)作業(yè)過程的時(shí)間最短。簡而言之，農(nóng)機(jī)調(diào)度即是要為所有參與作業(yè)的農(nóng)機(jī)選擇適當(dāng)?shù)淖鳂I(yè)路徑，從而生成從各農(nóng)機(jī)站到各農(nóng)田作業(yè)點(diǎn)之間的調(diào)度方案，以達(dá)到使用最少的農(nóng)機(jī)、最短的作業(yè)路徑及最短的作業(yè)時(shí)間來為所有農(nóng)田實(shí)施作業(yè)的目標(biāo)。

2.2 模型假設(shè)

1)農(nóng)機(jī)調(diào)配站的位置、各農(nóng)田的位置和面積及農(nóng)機(jī)單日作業(yè)能力均確定且已知；

2)一塊農(nóng)田僅由一臺農(nóng)機(jī)來實(shí)施作業(yè)；

3)單臺農(nóng)機(jī)的作業(yè)能力恰好可以滿足單塊農(nóng)田要求；

4)有多個(gè)農(nóng)機(jī)調(diào)配站，各農(nóng)機(jī)調(diào)配站中針對特定農(nóng)機(jī)作業(yè)需求只配有一種車型；

5)在一個(gè)調(diào)度方案中，每輛農(nóng)機(jī)僅僅被分配一次作業(yè)路線，該農(nóng)機(jī)從其隸屬的農(nóng)機(jī)調(diào)配站出發(fā)，按指定順序?qū)β窂缴系霓r(nóng)田依次實(shí)施作業(yè)之后，返回到其出發(fā)的農(nóng)機(jī)調(diào)配站；

6)在一個(gè)調(diào)度方案中，每輛農(nóng)機(jī)至少可以分配到一塊農(nóng)田實(shí)施作業(yè)任務(wù)，即保證所有農(nóng)機(jī)的有效利用；

7)不考慮天氣，農(nóng)村道路阻塞等特殊情況。

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

針對農(nóng)業(yè)機(jī)械的作業(yè)問題(見圖1)，按照如下步驟建立數(shù)學(xué)模型。

圖1 農(nóng)業(yè)機(jī)械調(diào)配優(yōu)化路徑Fig.1 The mathematical model of path optimization of wheat harvest

1)問題的要素。農(nóng)機(jī)調(diào)配站：DP1，DP2，…，DPn，共計(jì)n座?？墒褂玫霓r(nóng)機(jī)：Veh1，Veh2，…，Vehm，共計(jì)m輛。

每臺農(nóng)機(jī)與調(diào)配站的隸屬關(guān)系：Sub1，Sub2，…， Subm(任一農(nóng)機(jī)必屬于某調(diào)配站，即Subi∈ DP)。

農(nóng)田：Frm1，F(xiàn)rm2，…，F(xiàn)rmq，共計(jì)q塊。為建模及計(jì)算方便，農(nóng)田的劃分按農(nóng)機(jī)單日作業(yè)量劃分，即某塊農(nóng)田Frmi在模型中可由某臺機(jī)械Vehj單日作業(yè)完成。

調(diào)配站DPi與農(nóng)田Frmj之間的路途長度Disij。

農(nóng)田Frmi與農(nóng)田Frmj之間的路途長度Dsij。

農(nóng)機(jī)Vehi的作業(yè)序列Frma，F(xiàn)rmb，…，F(xiàn)rmp，共計(jì)p個(gè)(作業(yè)序列中的元素為農(nóng)田，p≤q)。

農(nóng)田Frmi在作業(yè)序列中的順序[Vehj，Ordk]，其中Vehj意為農(nóng)田Frmi由車輛Vehj作業(yè)，Ordk意為農(nóng)田Frmi在車輛Vehj路徑上的序號(任一序列必屬于該車輛的作業(yè)序列，即Ordk≤p)

2)問題的目標(biāo)1為所有車輛路徑總和最小，由下式表示，即

其中，DS為DS(Sj)(Sj+1)，即農(nóng)機(jī)作業(yè)序列中相連的兩塊農(nóng)田之間的距離；Dis1為Dis(Ci)(S1)，即農(nóng)機(jī)所屬調(diào)配站與農(nóng)機(jī)作業(yè)序列中第一塊農(nóng)田之間的距離；Dis2為Dis(Ci)(Sp)，即農(nóng)機(jī)所屬調(diào)配站與農(nóng)機(jī)作業(yè)序列中最后一塊農(nóng)田之間的距離。

3)問題的目標(biāo)2為完成整個(gè)作業(yè)所用的時(shí)間最少，由下式表示，即

min(Ordk)

其中，Ordk即為任一農(nóng)田在農(nóng)機(jī)作業(yè)路徑中的序號，所有農(nóng)田的Ord值最大的一個(gè)即為作業(yè)全部完成的時(shí)間。

4)問題的約束條件1為所有農(nóng)田都被農(nóng)機(jī)作業(yè)，且只由一臺農(nóng)機(jī)作業(yè)，即

上式表示農(nóng)田的作業(yè)序列中，Vehj為車輛集合V中的任一元素，且該農(nóng)田在車輛Vehj的作業(yè)順序合法。

5)問題的約束條件2為農(nóng)機(jī)某個(gè)作業(yè)順序上，只允許對一塊農(nóng)田作業(yè)。

3 農(nóng)業(yè)機(jī)械調(diào)度遺傳算法流程

遺傳算法流程如圖2所示。

本文所使用遺傳算法的計(jì)算流程如下：

1)隨機(jī)產(chǎn)生一組初始個(gè)體，形成起始種群；

2)對種群內(nèi)的每個(gè)個(gè)體執(zhí)行適應(yīng)度判斷，保留適應(yīng)度高的個(gè)體，形成新的種群；

3)判斷整個(gè)算法是否達(dá)到了終止條件，如是結(jié)束算法，否則進(jìn)入下一個(gè)步驟；

4)對種群執(zhí)行交叉操作，產(chǎn)生子種群；

5)對子種群進(jìn)行變異操作，并跳入步驟2)。

4 調(diào)度遺傳算法設(shè)計(jì)

使用遺傳算法首先要選擇合適的染色體編碼方式。在問題的建模中，本文使用[Vehj，Ordk]來表示農(nóng)田Frmi在整個(gè)作業(yè)序列中由農(nóng)機(jī)Vehj的第Ordk個(gè)順序進(jìn)行作業(yè)。按照這個(gè)方式，將所有的農(nóng)田的作業(yè)序列依照農(nóng)田的順序依次列出，即形成了一種可能的整體作業(yè)方案，如圖3所示。

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

圖3 農(nóng)機(jī)作業(yè)方案示意Fig.3 The deployment program sketch

圖3中，每塊農(nóng)田的作業(yè)為一個(gè)染色體，所有農(nóng)田的作業(yè)串接成整個(gè)方案，形成一個(gè)個(gè)體。

在構(gòu)建整個(gè)方案的時(shí)候，需要滿足問題建模時(shí)的兩個(gè)約束條件。

滿足約束條件1的方式為：依次為所有農(nóng)田隨機(jī)抽取某一臺農(nóng)機(jī)作業(yè)。

滿足約束條件2的方式為：每當(dāng)抽取到某臺農(nóng)機(jī)時(shí)，將該農(nóng)機(jī)的作業(yè)順序加1。

1)形成起始種群。為每塊農(nóng)田Frmi隨機(jī)抽取一臺農(nóng)機(jī)Vehj，并將Frmi附加到Vehj現(xiàn)有的作業(yè)序列之后。記錄Frmi[Vehj，Ordk]為一個(gè)染色體。為所有農(nóng)田抽取農(nóng)機(jī)，形成一個(gè)方案，即個(gè)體；同時(shí)，記錄這個(gè)個(gè)體每臺農(nóng)機(jī)的作業(yè)順序。重復(fù)這個(gè)過程Par1次(Par1值可由問題的規(guī)模決定，此處設(shè)定初始值為10 000)，即形成了個(gè)體數(shù)量為Par1的起始種群。

2)適應(yīng)度判斷。適應(yīng)度(Fit)直白地表達(dá)了個(gè)體的好壞。在問題建模時(shí)有兩個(gè)目標(biāo)：總路徑最短(Fitdis)及作業(yè)時(shí)間最短(Fittim)。將兩個(gè)目標(biāo)按照Par2及1-Par2的比例加權(quán)作為適應(yīng)度來判斷個(gè)體的好壞，即

Fit=Par2·Fitdis+(1-Par2)·Fittim

Par2的值初始假定為50%，即認(rèn)為總路徑最短和作業(yè)時(shí)間最短的重要性相當(dāng)?？梢哉{(diào)節(jié)Par2的值來加強(qiáng)某一目標(biāo)的權(quán)重，如天氣狀況不良，搶收時(shí)的作業(yè)方案計(jì)算，就應(yīng)當(dāng)將作業(yè)時(shí)間最短這個(gè)目標(biāo)的權(quán)重加強(qiáng)(如Par2=10%)。

計(jì)算總路徑最短的適應(yīng)度Fitdis，首先要計(jì)算每個(gè)個(gè)體各自的總路徑TtlDs，計(jì)算方式為累加每臺農(nóng)機(jī)的行駛總路程，即

因?yàn)槁窂蕉痰膫€(gè)體適應(yīng)度應(yīng)該更高，將每個(gè)個(gè)體的總路徑TtlDs取倒數(shù)，然后按照個(gè)體與總體的比例計(jì)算路徑適應(yīng)度，即

計(jì)算作業(yè)時(shí)間最短的適應(yīng)度Fittim，首先要計(jì)算每個(gè)個(gè)體各自的作業(yè)時(shí)間，計(jì)算方式為選取作業(yè)序列最長的農(nóng)機(jī)的最后一個(gè)序列號為該個(gè)體的作業(yè)時(shí)間，用Ordmax表示。

因?yàn)樽鳂I(yè)時(shí)間段的個(gè)體適應(yīng)度應(yīng)更高，將每個(gè)個(gè)體的作業(yè)時(shí)間Ordmax取倒數(shù)，然后按照個(gè)體與總體的比例計(jì)算作業(yè)時(shí)間適應(yīng)度，即

將整個(gè)群體中的每個(gè)個(gè)體的適應(yīng)度都計(jì)算出來后，按照適應(yīng)度由高到低排序，保留前10%的個(gè)體作為新的種群，種群規(guī)模變?yōu)榱?.1Par1。

3)算法終止判斷。算法以固定的迭代次數(shù)Par3作為終止條件，迭代次數(shù)達(dá)到Par3則終止計(jì)算，將適應(yīng)度最高的個(gè)體作為解決方案輸出。

4)交叉形成子種群。由2)中形成的0.1Par1規(guī)模的種群為父種群，按照輪盤賭的方式執(zhí)行交叉策略，生成子種群，子種群的規(guī)?；謴?fù)為Par1大小，如圖4所示。具體的策略如下：首先從父種群中隨機(jī)選擇兩個(gè)個(gè)體，方式為在區(qū)間(0, 1]上隨機(jī)兩次，得到兩個(gè)隨機(jī)數(shù)；父種群是按照適應(yīng)度從高到低依次排列的，且所有個(gè)體的適應(yīng)度和為1，兩個(gè)隨機(jī)數(shù)落到哪個(gè)個(gè)體的區(qū)間，則這兩個(gè)個(gè)體成為雙親。

圖4 雙親選擇示意圖Fig.4 The parents choice sketch

選中雙親以后，由雙親交換多個(gè)染色體生成兩個(gè)子代，如圖5所示。策略為：隨機(jī)選擇多個(gè)染色體Frmrdm，進(jìn)行互換。

圖5 染色體交換示意圖Fig.5 The chromosome exchange sketch

圖5中，雙親交換了染色體2，形成了2個(gè)新的子代，交叉完成后，需要對每個(gè)子代的新的染色體執(zhí)行合法化。將原來的染色體[Vehold，Ordold]刪除，將農(nóng)機(jī)Vehold的第Ordold作業(yè)序列刪除，并將后續(xù)作業(yè)序列前提；然后添加新的交換來的染色體[Vehnew，Ordnew]，將農(nóng)機(jī)Vehnew的第Ordnew作業(yè)序列之后插入農(nóng)田Frmrdm，并將后續(xù)作業(yè)順序后延。在合法化的過程中，非Frmrdm的染色體也會隨之發(fā)生更新。

重復(fù)選擇雙親生成子代的過程0.5Par1次，子代種群達(dá)到Par1規(guī)模。

5)子種群的變異。以一個(gè)較低的概率Par4(初始設(shè)定為0.1%)隨機(jī)選擇子種群中的個(gè)體，對選中的個(gè)體隨機(jī)挑選多個(gè)染色體Frmrdm，隨機(jī)更改該染色體的農(nóng)機(jī)，作業(yè)順序則保持不變。個(gè)體變異以后也需要執(zhí)行合法化。方式與4)中相同，不再贅述。

5 農(nóng)業(yè)機(jī)械調(diào)度遺傳算法的應(yīng)用與分析

使用MatLab編程本文設(shè)計(jì)的算法，并以隨機(jī)生成的數(shù)據(jù)(4個(gè)站點(diǎn)，40臺農(nóng)機(jī)，400塊農(nóng)田)為例進(jìn)行計(jì)算，如圖6所示。

圖6 遺傳算法算例Fig.6 The genetic algorithm example

初始種群Par1設(shè)定為2 000；兩個(gè)目標(biāo)的比例加權(quán)Par2設(shè)定為50%；迭代次數(shù)Par3設(shè)定為10 000次；變異比例Par4設(shè)定為0.1%。

計(jì)算完成后，可看到各臺機(jī)械被分配到的農(nóng)田數(shù)量均勻，作業(yè)路徑合理，路徑交叉路線較少。證明算法的設(shè)計(jì)是合理有效的，結(jié)果如圖7所示。

圖7 算法結(jié)果Fig.7 The genetic algorithm result

作為對比，假設(shè)一種由人工指定作業(yè)的方式：所有車輛負(fù)責(zé)等面積的作業(yè)區(qū)域，作業(yè)路徑按維度依次排列，這種方式與現(xiàn)實(shí)世界中的人工調(diào)配比較相似。最后的作業(yè)結(jié)果如圖8所示。

對比使用遺傳算法的結(jié)算，路程由2 698.5km增加到3 592.2km，作業(yè)天數(shù)由10天增加到12天。遺傳算法的運(yùn)算結(jié)果明顯優(yōu)于簡單的按區(qū)域劃分分配作業(yè)車輛的方式。

遺傳算法本質(zhì)上是一種規(guī)則約束下的全局搜索，隨著問題的復(fù)雜化，解空間的大小對比算法計(jì)算量趨向于無窮大。所以，算法難以保證最終解與最優(yōu)解的接近程度。遺傳算法解的演進(jìn)方式為：先探索，再驗(yàn)證，接受或否定本次探索，算法特性決定了它的搜索方向是隨機(jī)跳動的。這樣做的益處在于保證了搜索的全局性，但對特定解的局部優(yōu)化則不是算法的優(yōu)先考慮項(xiàng)。反映到實(shí)際的運(yùn)算結(jié)果中，往往發(fā)現(xiàn)可以對結(jié)果進(jìn)行局部微調(diào)優(yōu)化，這種微調(diào)既可以人工進(jìn)行，也可以另設(shè)計(jì)算法處理。圖9為對遺傳算法運(yùn)行結(jié)果進(jìn)行人工微調(diào)后的示例。

圖8 人工調(diào)配結(jié)果Fig.8 The manual deployment result

圖9 人工微調(diào)結(jié)果Fig.9 The manual trimming result

由圖9可以看出：手動微調(diào)以后，總路程稍微下降至2 666.6km，作業(yè)天數(shù)增加到11天。人工微調(diào)的作用比較有限，而如果設(shè)計(jì)算法進(jìn)行局部微調(diào)的話，則可能會有更明顯的優(yōu)化效果，從而形成遺傳算法搜索全局、微調(diào)算法局部優(yōu)化的結(jié)構(gòu)。因本文重點(diǎn)不在于此，故不展開研究。

為測試遺傳算法計(jì)算結(jié)果的穩(wěn)定性，重復(fù)執(zhí)行算法，計(jì)算20次，各次結(jié)果分布如圖10所示。

由圖10可見：各次結(jié)果離散性較小，算法求解效果穩(wěn)定，具有較高的實(shí)用性。

6 結(jié)論

對農(nóng)機(jī)調(diào)配問題進(jìn)行建模，使用遺傳算法進(jìn)行編程及算例運(yùn)行，證明遺傳算法適用于解答較大規(guī)模的農(nóng)機(jī)調(diào)配問題。本文所構(gòu)建的遺傳算法使用比較簡單，運(yùn)行結(jié)果穩(wěn)定，輸出的調(diào)配方案整體優(yōu)于人工調(diào)配方案，可明顯縮短農(nóng)機(jī)調(diào)配的作業(yè)里程及工期，具有較高的實(shí)用性。同時(shí)，也應(yīng)看到因?yàn)橹悄芩惴ü逃械奶匦?，算法運(yùn)行結(jié)果并不能保證為問題最優(yōu)解，對結(jié)果進(jìn)行特定方向的人工再調(diào)整在實(shí)踐中仍有其必要性。

圖10 結(jié)果穩(wěn)定性Fig.10 The results stability