基于改進(jìn)蟻群算法的羊群放牧規(guī)劃方案研究 *

楊顏博，孫一鳳，杜永興，胡偉建，史湘楠

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

因受改革開放和市場經(jīng)濟(jì)的影響，農(nóng)村牧區(qū)人口紛紛流向城鎮(zhèn)[1]，導(dǎo)致牧區(qū)勞動力嚴(yán)重減少；牧區(qū)放牧采用無目標(biāo)式放牧方式，導(dǎo)致牧區(qū)草場出現(xiàn)嚴(yán)重過度放牧區(qū)域，過度放牧導(dǎo)致的草地資源嚴(yán)重退化已經(jīng)成為畜牧業(yè)經(jīng)濟(jì)發(fā)展和草地生態(tài)平衡的主要障礙[2]；草原牧區(qū)自然條件不理想，放牧及牲畜管理難度很大[3].因此科學(xué)指導(dǎo)放牧對于減少牧民工作量和維持草畜平衡有著重要的意義.

近年來不少學(xué)者對放牧?xí)r空軌跡數(shù)據(jù)進(jìn)行了研究，利用時空軌跡數(shù)據(jù)提出放牧強(qiáng)度估算方法[4]；發(fā)現(xiàn)牲畜區(qū)域?qū)傩訹5]；測算牲畜的采食行走速度[6]，但很少人將軌跡數(shù)據(jù)運(yùn)用到牲畜放牧路線規(guī)劃研究中.在路線規(guī)劃領(lǐng)域，陳呈利用算法對無人艇進(jìn)行路徑規(guī)劃[7]，王晨旸對復(fù)雜室內(nèi)環(huán)境進(jìn)行了路徑規(guī)劃[8]，但利用軌跡數(shù)據(jù)對牲畜放牧路線規(guī)劃的文獻(xiàn)較少.路徑規(guī)劃算法有模擬退火、人工勢場法、遺傳算法、蟻群算法等，因蟻群算法具有良好的尋找最短路徑能力和搜索特征，且強(qiáng)魯棒性等優(yōu)點(diǎn)，所以路徑規(guī)劃采用蟻群算法.關(guān)于蟻群算法的研究，學(xué)者們都進(jìn)行了一系列的研究工作[9-12].JIAO Z等[13]采用自適應(yīng)狀態(tài)轉(zhuǎn)移策略和自適應(yīng)信息更新策略；CHEN X等[14]介紹了一個2階段的螞蟻算法，但少有文獻(xiàn)將改進(jìn)點(diǎn)與實(shí)際放牧相結(jié)合.

基于上述原因，利用放牧?xí)r空軌跡數(shù)據(jù)，提出基于改進(jìn)蟻群算法進(jìn)行放牧規(guī)劃的方案.文章的其余部分安排如下.第一節(jié)介紹試驗(yàn)區(qū)概況和數(shù)據(jù)來源；第二節(jié)介紹輪牧區(qū)域劃分，起點(diǎn)和終點(diǎn)判定，環(huán)境建模和改進(jìn)的蟻群算法；第三節(jié)對實(shí)驗(yàn)結(jié)果進(jìn)行分析；第四、五節(jié)進(jìn)行討論總結(jié).

1 實(shí)驗(yàn)數(shù)據(jù)

1.1 試驗(yàn)區(qū)概況

試驗(yàn)區(qū)位于錫林郭勒大草原西北部的蘇尼特左旗巴彥淖爾鎮(zhèn)呼和淖爾嘎查，該地區(qū)屬于干早大陸性氣候，植被類型以荒漠草原和干草原植被為主[15].

1.2 數(shù)據(jù)來源

實(shí)驗(yàn)數(shù)據(jù)來源蘇尼特左旗巴彥淖爾鎮(zhèn)呼和淖爾嘎查某一牧區(qū)2019年羊群軌跡數(shù)據(jù)記錄，由羊群放牧過程中頭羊所佩戴的定位項(xiàng)圈按照每10 min左右產(chǎn)生的連續(xù)定位數(shù)據(jù)，其中對原始數(shù)據(jù)進(jìn)行清洗和預(yù)處理并對其數(shù)據(jù)進(jìn)行分布式放牧強(qiáng)度估算，得到牧區(qū)過度放牧軌跡數(shù)據(jù)，使用的方法是基于杜永

興等[4]人提出的放牧強(qiáng)度估算方法.這些數(shù)據(jù)將在環(huán)境建模中被填充為障礙物.其中數(shù)據(jù)包括過度放牧區(qū)域中心經(jīng)緯度坐標(biāo)、區(qū)域大小、過度比率、采集更新時間、養(yǎng)殖戶等.

2 研究方法

2.1 劃分輪牧區(qū)域

將牧區(qū)劃分區(qū)域，進(jìn)行輪牧，輪牧區(qū)域的劃分根據(jù)載畜能力來計(jì)算.載畜能力是指草場在中等程度利用下全年放牧期內(nèi)可能容載的牲畜最大定額.《錫林郭勒盟牧區(qū)牧業(yè)人口承載量研究》這一文獻(xiàn)中提出錫林郭勒盟北部牧區(qū)載畜能力為0.5羊/公頃/年[16]，即1羊/0.006 hm2/d.某牧民有m頭羊，S公頃，可劃分輪牧區(qū)塊數(shù)n按下式計(jì)算：

(1)

假設(shè)m=300頭，S=441公頃，所分塊數(shù)n=245，下圖為劃分輪牧區(qū)域示意圖，如圖1所示.

當(dāng)前區(qū)域中所含草場資源與載畜量相等，然而區(qū)域中可能包含已放牧區(qū)域，因此區(qū)域不足以承擔(dān)羊群進(jìn)行采食，所以在此基礎(chǔ)上需進(jìn)行進(jìn)一步劃分，流程如下：

(1)找出區(qū)域含有最大過度放牧區(qū)域fi的區(qū)域Si，則Si區(qū)域中可利用面積Δi=Si-fi.

(2)計(jì)算與Si相鄰的2個區(qū)域可利用面積Δi+1，Δi-1.

(3)若{(Δi+1+Δi+Δi-1)/2}-S≥0即表明Δi區(qū)域平分到相鄰的2個區(qū)域可滿足載畜量需求，并將Δi平分到相鄰2個區(qū)域進(jìn)行第四步操作.若不滿足上述條件則進(jìn)行第三步.

(4)當(dāng)fi+fi+1≥S/n，fi+fi-1≥S/n2個條件都滿足則將Δi分給相鄰2個區(qū)域中過度區(qū)域小的區(qū)域進(jìn)行第四步操作；若2個條件滿足其中一個，則選擇將Δi分給對應(yīng)滿足條件中的區(qū)域進(jìn)行第四步操作；若上述條件都不滿足則將這3個區(qū)域合并為1個區(qū)域，在與相鄰2個區(qū)域進(jìn)行第一步操作.

(5)找出除Si區(qū)域其余區(qū)域中過度放牧最大的區(qū)域Si′，再重復(fù)2,3兩步.直到每個區(qū)域的可利用面積都滿足載畜量要求，劃分結(jié)束.

這樣的劃分可以讓每一個輪牧區(qū)域的可采食面積都可以滿足載畜量的要求.

2.2 環(huán)境建模

在建模過程中對牧區(qū)進(jìn)行區(qū)域范圍的設(shè)定，將羊群在放牧過程中產(chǎn)生的過度放牧區(qū)域設(shè)置為障礙物.

在障礙物填充過程中發(fā)現(xiàn)，障礙物縮放比例會影響到算法效果和放牧效果.針對這種情況，對過度放牧區(qū)面積進(jìn)行統(tǒng)計(jì)，多次建模試驗(yàn)和實(shí)際羊群數(shù)量比對，一柵格的面積應(yīng)該在一定誤差的情況下，容納所有采食的羊群.本實(shí)驗(yàn)中一柵格面積為0.09 hm2.

2.3 路線中起點(diǎn)與終點(diǎn)判定

在利用算法進(jìn)行路徑規(guī)劃時，路徑的起點(diǎn)和終點(diǎn)是根據(jù)真實(shí)情況進(jìn)行設(shè)定，設(shè)定了一種準(zhǔn)則.起點(diǎn)為軌跡數(shù)據(jù)中每天開始進(jìn)行放牧活動的經(jīng)緯度點(diǎn)；終點(diǎn)為利用載畜量劃分區(qū)域后，該區(qū)域離起點(diǎn)較遠(yuǎn)的點(diǎn).

2.4 改進(jìn)蟻群算法

蟻群算法是進(jìn)行路徑規(guī)劃時常用的一種啟發(fā)式算法.信息素在蟻群算法中發(fā)揮重要的指引作用.算法中信息素更新分2部分，一是螞蟻分泌的信息素;二是隨著時間推移揮發(fā)的信息素.如果螞蟻陷入死角沒有找到目標(biāo)點(diǎn)，螞蟻仍會釋放信息素，這些信息素會給其它的螞蟻帶來錯誤訊息.選擇錯誤路徑的數(shù)量越多，錯誤路徑上信息素也越多，算法收斂速度變慢.并且在傳統(tǒng)蟻群算法中，螞蟻選擇下一節(jié)點(diǎn)是通過輪轉(zhuǎn)賭法決定，所以螞蟻的走向并不是確定性的.通過之前螞蟻無方向性的行走，才可確定最優(yōu)路徑，雖然在此過程中會出現(xiàn)小部分螞蟻選擇錯誤方向路徑，但在全局搜索最優(yōu)路徑時仍會影響到蟻群算法的收斂速度.針對這2個問題，對傳統(tǒng)蟻群算法進(jìn)行了2方面的改進(jìn)工作.

(1)信息回溯機(jī)制.當(dāng)檢測到螞蟻陷入死角時，信息素回溯到上一只螞蟻狀態(tài).這樣即使螞蟻行走錯誤路徑而遺留下來信息素也會回溯到上一步的狀態(tài)，不會讓錯誤的信息素影響后面螞蟻的選擇，減少蟻群對錯誤路徑的選擇.回溯機(jī)制公式如下所示：

(2)

式中：t為時刻；ρ為信息素?fù)]發(fā)系數(shù)；Δτ為殘留信息素.

(2)動態(tài)檢測機(jī)制.因?yàn)槟羺^(qū)進(jìn)行了輪牧區(qū)域劃分，所以目標(biāo)點(diǎn)和起點(diǎn)的相對位置已知，每次判斷螞蟻行走方向是否在正確方向區(qū)域，指引螞蟻在正確方向上進(jìn)行尋路，即規(guī)定區(qū)域方向?qū)ぢ?算法中的起始點(diǎn)和目標(biāo)點(diǎn)位置不產(chǎn)生變化，但每次尋找下一步可走節(jié)點(diǎn)時它和終點(diǎn)的相對位置都會發(fā)生變化，所以在每一次進(jìn)行節(jié)點(diǎn)選擇時都要對節(jié)點(diǎn)和目標(biāo)點(diǎn)進(jìn)行位置檢測.檢測算法流程是將目標(biāo)點(diǎn)設(shè)置為固定位置，判斷相對位置所在區(qū)域.

通過信息素回溯和劃分過牧區(qū)域設(shè)置動態(tài)檢測機(jī)制提高算法收斂速度，并將其運(yùn)用到羊群放牧軌跡規(guī)劃中.改進(jìn)算法流程圖如圖2所示.

3 結(jié)果與分析

3.1 環(huán)境建模結(jié)果

對于障礙物填充采用膨脹化處理，膨脹化處理的原則為：不滿一柵格的按照一柵格計(jì)算.膨脹化處理也防止羊群進(jìn)入不足以進(jìn)行采食活動的區(qū)域活動.

進(jìn)行環(huán)境建模的牧區(qū)如圖3所示.

3.2 軌跡路線算法分析

牧民牧場面積441 hm2，經(jīng)過劃分輪牧區(qū)進(jìn)行計(jì)算，其劃分為175個區(qū)域，并且每個區(qū)域的放牧周期為1 d進(jìn)行輪流放牧活動.在模擬建模圖中每個輪牧區(qū)域占20個柵格.進(jìn)行算法計(jì)算，得到規(guī)劃路線如圖4所示，圖中實(shí)線為規(guī)劃路徑.

并且在相同柵格環(huán)境下傳統(tǒng)算法和改進(jìn)算法進(jìn)行了收斂性的對比，算法各項(xiàng)參數(shù)相同，對比如圖5所示.

對軌跡路線和算法進(jìn)行分析，結(jié)果表明該方法可以有效避開過度放牧區(qū)域，將改進(jìn)后的算法與未改進(jìn)的進(jìn)行比對驗(yàn)證，改進(jìn)后的效率有著明顯的提高，收斂速度提高了28%.可以為之后的科學(xué)化放牧提供可靠的技術(shù)支持.

4 討論

4.1 輪牧區(qū)劃分

在利用蟻群算法進(jìn)行路徑規(guī)劃前，輪牧區(qū)域的劃分是關(guān)鍵部分，如果輪牧區(qū)域劃分不合理，將會導(dǎo)致影響后面算法的尋路部分.當(dāng)劃分區(qū)域不滿足牧民放牧天數(shù)時應(yīng)進(jìn)行短暫休牧，防止過度放牧.所以之后的研究可以結(jié)合氣候影響草勢生長情況，更好的劃分輪牧區(qū)域和規(guī)定輪牧區(qū)的輪牧天數(shù).

4.2 軌跡路線

軌跡路線可以很好地躲避障礙物即過度放牧區(qū)域，找到較短路徑，并可以轉(zhuǎn)化為實(shí)際牧場的經(jīng)緯度，供無人機(jī)或無人小車進(jìn)行放牧活動.

5 結(jié)論

為了更好地解決牧區(qū)過度放牧的問題，需要對放牧活動進(jìn)行規(guī)劃，并結(jié)合羊群軌跡數(shù)據(jù)盡量減少對過牧區(qū)域進(jìn)行采食活動.本研究以蘇尼特左旗巴彥淖爾鎮(zhèn)呼和淖爾嘎查某一牧民牧區(qū)為例，利用蟻群算法對羊群放牧軌跡路線進(jìn)行了規(guī)劃，結(jié)果顯示：該方案可以運(yùn)用在羊群放牧中，并且可以為之后的無人機(jī)放牧提供技術(shù)支持.