劉 麗,劉 野,王新利
(黑龍江八一農(nóng)墾大學(xué) 工程學(xué)院,黑龍江 大慶 163319)
農(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è)體,即問題的滿意解。
遺傳算法[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]。
在確定數(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)。
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)村道路阻塞等特殊情況。
針對農(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è)。
遺傳算法流程如圖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)。
使用遺傳算法首先要選擇合適的染色體編碼方式。在問題的建模中,本文使用[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)中相同,不再贅述。
使用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í)用性。
對農(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