基于改進蟻群算法的放牧路徑優(yōu)化研究

劉建國,谷曉燕,陳 亮,陳夢彤

(北京信息科技大學(xué)信息管理學(xué)院,北京 100192)

1 引 言

現(xiàn)階段國內(nèi)很多牧區(qū)在進行放牧?xí)r還是采用連續(xù)放牧[1]等“竭澤而漁”式的傳統(tǒng)飼養(yǎng)方式[2],放牧路徑也是按照以往經(jīng)驗進行粗略估計[3],從而導(dǎo)致放牧路徑規(guī)劃的潛在價值沒有得到完善體現(xiàn)[4]。因此,設(shè)計具有科學(xué)指導(dǎo)性的放牧路徑具有重要的研究意義。

目前,針對放牧行為的研究,Gu[5]等將分配模型和載畜量約束相結(jié)合,建立了動態(tài)輪牧分配模型,使得資源在時間和空間上得到有效利用;李鳳霞[6]等通過遙感衛(wèi)星對青海省海晏縣的牧場牧草質(zhì)量,建成輪牧動態(tài)監(jiān)測預(yù)測管理模型及業(yè)務(wù)服務(wù)平臺,為科學(xué)放牧建立了技術(shù)支撐;張智起[7]等人針對中國北方干旱半干旱草地過度放牧和連續(xù)放牧等問題強調(diào)了科學(xué)放牧的重要性。但是沒有從牧場條件多變的視角考慮如何科學(xué)的規(guī)劃放牧路徑。

針對路徑規(guī)劃問題,常用的算法主要有遺傳算法[8]、人工勢場法[9]、粒子群算法[10]、神經(jīng)網(wǎng)絡(luò)算法[11]和蟻群算法等。蟻群算法具有強魯棒性和良好的搜索能力,在二維圖上搜索效果好,適合在柵格化牧場環(huán)境模型圖上進行路徑搜索。部分學(xué)者把蟻群算法用于規(guī)劃機器人的路徑。胡春陽[12]和孫功武[13]通過對蟻群算法進行平滑改進為水面無人艇進行路徑規(guī)劃。李開榮[14]通過添加轉(zhuǎn)角約束的算法為移動機器人進行路徑規(guī)劃。以上學(xué)者在為機器人設(shè)計路徑時,著重于在規(guī)避障礙物的同時約束機器人的轉(zhuǎn)彎角度,而放牧領(lǐng)域則不同,牲畜在規(guī)避障礙物時擁有良好的機動性,因此考慮的因素會有區(qū)別,如轉(zhuǎn)彎角度并不是最優(yōu)先考慮的。蔣強[15]和HUANG[16]使用蟻群算法在通過大量螞蟻個體尋找最優(yōu)路徑上有比較好的表現(xiàn),但收斂速度慢,不適合在條件多變的放牧場景下進行動態(tài)的路徑規(guī)劃。

在進行放牧路徑規(guī)劃時,通過對牧場進行二維柵格化環(huán)境建模后,在生成的二維柵格化地圖中生成較優(yōu)的無碰撞路徑,因此本文針對放牧路徑規(guī)劃場景下蟻群算法存在的一些不足進行適應(yīng)性改進,使之更加適合牲畜的運動習(xí)慣。在基本的蟻群算法中,每次迭代更新信息素時,可能出現(xiàn)信息素濃度差別不大的情況,從而出現(xiàn)收斂速度慢和規(guī)劃的線路并不是較優(yōu)線路的缺點,因此本文將對蟻群算法控制信息素變化方面加以改進。

本文首先對牧區(qū)進行柵格化環(huán)境建模。然后,針對蟻群算法在放牧路徑規(guī)劃場景下存在的不足進行適應(yīng)性改進。接著根據(jù)實驗?zāi)羺^(qū)的詳細條件[17]和實驗數(shù)據(jù)集來源,劃分小牧區(qū)。最后通過仿真為牲畜規(guī)劃放牧路徑,并與改進前的算法和其它算法進行對比驗證模型的可行性和合理性。

2 環(huán)境建模

在進行蟻群算法規(guī)劃路徑前,要使用柵格圖法[18]對所選取牧場進行二維環(huán)境建模,查找選定區(qū)域內(nèi)不會生長牧草的裸露地,坡度過陡的地形,牧場退化牧草生長期不匹配、牧場過度放牧等地區(qū),為了牧場可持續(xù)發(fā)展以及提高牲畜采食的有效性,把不適宜放牧的區(qū)域抽象為障礙物并做好障礙物標(biāo)記,之后對整個區(qū)域進行柵格化建模,通過二進制的格式對整個區(qū)域進行編碼處理,有障礙物為1,無障礙物為0,設(shè)各柵格的邊長為1,白色柵格為可自由放牧區(qū)域,而黑色柵格為障礙物區(qū)域,讓建立的模型盡可能地貼近實際牧場地形條件。

接下來對圖像分別進行腐蝕和膨脹處理[19],其中腐蝕處理是對圖像里不會對路徑規(guī)劃產(chǎn)生影響的細小障礙物進行消除;而膨脹處理則是對不規(guī)則的較大障礙物添加像素,使得所在柵格得以擴充。腐蝕和膨脹處理并不為不可逆運算,因此可以結(jié)合使用。

圖1 二維柵格環(huán)境建模示意圖

3 基于改進蟻群算法的放牧路徑規(guī)劃方法

使用蟻群算法規(guī)劃放牧路徑時還需要考慮到諸多實際問題,例如起點和終點的選擇,牲畜的行動特點等。另外,考慮多變的牧場條件,因此設(shè)計路徑的算法要有能快速應(yīng)對牧場條件變化的能力,通過優(yōu)化放牧路徑來減少牲畜在放牧過程中的額外能量損耗。

3.1 問題描述

在放牧場景下,因牧草條件、河流改道和惡劣天氣等不可抗因素較多,放牧路徑規(guī)劃方式要具有柔性,傳統(tǒng)蟻群算法在進行路徑規(guī)劃運算時因收斂速度慢導(dǎo)致時間成本較高,若直接用于放牧場景下存在未根據(jù)牧場情況及時做好應(yīng)對措施的風(fēng)險,從而不滿足牧場的實際需求,所以本文將針對蟻群算法在放牧場景下的即時性做適應(yīng)性改進,使之在尋得較優(yōu)路徑的情況下降低時間成本。

在傳統(tǒng)的蟻群算法中,信息素濃度和啟發(fā)式信息是影響整個螞蟻族群尋找最優(yōu)路徑時重要的兩個因素,節(jié)點i和目標(biāo)節(jié)點j之間的歐幾里得距離dij是傳統(tǒng)蟻群算法中啟發(fā)式信息的重要影響因素,但是傳統(tǒng)蟻群算法忽視了障礙物對于算法的影響,這是算法出現(xiàn)局部最優(yōu)的非常關(guān)鍵的原因,設(shè)置更多初始的螞蟻數(shù)量和改進信息素的更新方法雖然增強了尋找最優(yōu)路徑的能力,但是會較大程度的影響整個算法的收斂速度,所以本文會對以上重要因素進行一定程度的改進,改進后算法的快速尋路能力將有較大提升。

3.2 蟻群算法參數(shù)設(shè)定

在放牧路徑規(guī)劃過程中,可以將牧場環(huán)境建模后的每一個牧區(qū)柵格抽象為蟻群算法螞蟻尋路的每一個節(jié)點,而每次迭代每只螞蟻個體所尋得的路線也可以抽象為放牧路徑。

針對放牧路徑規(guī)劃,基于蟻群算法的尋路方法:

當(dāng)螞蟻從起點出發(fā),螞蟻選擇的下一節(jié)點和移動方向是隨機的,并使用輪轉(zhuǎn)賭法對下一節(jié)點的走向進行選擇,具體公式如下

(1)

(2)

(3)

式(1)中

τij為牧區(qū)i到牧區(qū)j的信息素濃度;

ηij為牧區(qū)i到牧區(qū)j的啟發(fā)因子;

α為信息素激勵因子;

β為啟發(fā)式因子期望;

dij為牧區(qū)i到牧區(qū)j的歐幾里得距離。

在一段時間過后,環(huán)境里的信息素濃度會根據(jù)每一輪螞蟻選擇完路徑后的信息素而稀釋,產(chǎn)生揮發(fā)現(xiàn)象,具體揮發(fā)公式如下

τij=(1-ρ)τij

(4)

式(4)中,ρ為信息素揮發(fā)系數(shù)

在環(huán)境中,更新信息素的公式為

τij(t+1)=τij(t)*(1-ρ)+Δτij,0<ρ<1

(5)

螞蟻在環(huán)境中釋放的信息素計算公式為

(6)

(7)

式(7)中,A1為設(shè)置的信息素強度系數(shù)。

3.3 改進信息素更新機制

因為傳統(tǒng)蟻群算法是一種自組織、并行且正反饋的算法,每只螞蟻作為一個個獨立個體,在行動時不會受其它個體影響,每只螞蟻都采用同一種原則進行單獨行動,且如果初始信息素常量如果過大,會影響整個螞蟻族群的搜索范圍,范圍變小會使得過早收斂,陷入局部最優(yōu);而過小的話,算法運行后環(huán)境內(nèi)各條路徑的信息素濃度差別也會過小,會使得算法出現(xiàn)混沌現(xiàn)象。同時,螞蟻在尋找路徑過程中碰到死路或者繞路的情況時,同樣會釋放信息素,這些信息素?zé)o疑是干擾性的,只有找尋到合理路徑的螞蟻釋放的信息素才是對整個路徑規(guī)劃有幫助的?；谝陨蠁栴},本文提出改進的蟻群算法,目的是減少錯誤路徑上的螞蟻信息素的影響,提升收斂速度,解決局部最優(yōu)的問題。

算法的改進方式為:在蟻群算法中,添加一種可以將處在較優(yōu)放牧路徑上的螞蟻和處在較差放牧路徑上的螞蟻進行區(qū)分的機制,也就是在經(jīng)過每一次迭代后,收集每只螞蟻個體的行動路徑及長度,將找尋到最近路徑的螞蟻的路徑上的信息素增強,同時,將找尋到最遠路徑的螞蟻的路徑上的信息素減弱。之后,經(jīng)過一次次的反復(fù)迭代,最優(yōu)路徑上的信息素濃度越來越高,逐漸和其它非最優(yōu)路徑的信息素濃度產(chǎn)生差別,從而加快了算法的收斂速度,提出一種隨迭代時間改變的信息素濃度更新機制,因此,下面要對信息素更新機制的公式進行進一步的改進:

τij(t+1)=τij(t)*(1-ρ)

(8)

(9)

式(9)中,

x為每次迭代找尋到的最近放牧路徑的螞蟻個體只數(shù);

A2為下一次迭代增強的信息素因子指數(shù);

L*為每次迭代的最近距離。

(10)

式(10)中,y為每次迭代找尋到的最遠放牧路徑的螞蟻個體只數(shù);B為下一次迭代增強的信息素因子指數(shù);L**為每次迭代的最遠距離。

3.4 改進算法步驟

本文提出的改進蟻群算法的步驟如圖2所示。

圖2 改進算法流程圖

下面針對相應(yīng)步驟進行說明:

Step1:初始化算法的各項參數(shù),設(shè)置螞蟻只數(shù)、初始啟發(fā)因子、初始信息素因子和放牧路徑的起點和終點等參數(shù)。

Step2:使用柵格圖法,利用0-1編碼構(gòu)建柵格化障礙物牧場地圖模型。

Step3:螞蟻開始搜索路徑,使用輪轉(zhuǎn)賭法計算螞蟻選擇下一牧場節(jié)點的概率。

Step4:統(tǒng)計每一只螞蟻個體經(jīng)過的放牧路徑及長度,更新禁忌表,判斷螞蟻是否成功到達設(shè)定終點牧場節(jié)點,若到達,進入Step5;若未到達,返回Step3。

Step5:改進更新信息素的方法,使得信息素濃度差異化,繼續(xù)迭代,判斷是否到達最大迭代次數(shù),若到達,進入Step6,若未到達,返回Step3。

Step6:判斷是否到達目標(biāo)位置,若到達,結(jié)束算法,輸出仿真結(jié)果;若未到達,宣告算法失敗,結(jié)束算法。

4 仿真分析

4.1 實驗數(shù)據(jù)

本文選取了位于青藏高原面積約為400公頃的牧場,該牧場所在地區(qū)氣候類型為高原大陸性氣候,主要的草場植被類型為高寒草甸類和高寒草原類等[20,21],如圖3所示。經(jīng)過環(huán)境建模后,可用面積約為330公頃,如圖4所示。實驗中放牧牲畜數(shù)量為300羊單位。

圖3 目標(biāo)牧區(qū)地圖

圖4 二維柵格環(huán)境建模

4.2 參數(shù)設(shè)計

為了驗證本文改進后的蟻群算法的可靠性和合理性,本文使用Matlab R2016a軟件進行改進前后的算法仿真對比實驗,本次實驗采用的計算機配置為11th Gen Intel? Core(TM) i5-1135G7 @ 2.40GHz 四核CPU,內(nèi)存為16GB LPDDR4,GPU為Intel? Iris? Xe Graphics,構(gòu)建的仿真環(huán)境為20×20經(jīng)過腐蝕和膨脹處理過的平面柵格模擬環(huán)境,為了保障實驗結(jié)果的嚴謹性和準(zhǔn)確性,分別進行了若干次獨立重復(fù)實驗。

為了貼合實驗?zāi)翀龅膶嶋H放牧情況和測試不同路徑上算法的表現(xiàn),本文為牲畜的放牧路徑設(shè)計了6種不同的路徑,各條路徑的起始點和終止點的設(shè)置情況分別為:

1)起始點:地圖左上角柵格;終止點:地圖右上角柵格。

2)起始點:地圖左上角柵格;終止點:地圖右下角柵格。

3)起始點:地圖左上角柵格;終止點:地圖左下角柵格。

4)起始點:地圖右上角柵格;終止點:地圖右下角柵格。

5)起始點:地圖右上角柵格;終止點:地圖左下角柵格。

6)起始點:地圖右下角柵格;終止點:地圖左下角柵格。

參數(shù)設(shè)置:因為信息素因子α過大會使螞蟻的隨機搜索性減弱,信息素因子α過小會使算法搜索范圍減小,容易過早收斂,使得螞蟻族群陷入局部最優(yōu),所以本文設(shè)置α=1;啟發(fā)函數(shù)因子β過大,雖然會使收斂速度加快,但是反而容易陷入局部最優(yōu),相反,啟發(fā)函數(shù)因子β過小會使螞蟻族群陷入純粹的隨機搜索,增加尋找最優(yōu)解的難度,所以本文中的β=7;信息素揮發(fā)因子ρ過大,會使信息素揮發(fā)速度加快,容易錯失最優(yōu)路徑,使得最優(yōu)路徑被較先排除,ρ過小,又會使各條路徑上的信息素濃度差別過小,導(dǎo)致影響收斂速度,因此本文設(shè)置ρ=0.3;螞蟻數(shù)量m統(tǒng)一設(shè)置為100;最大迭代次數(shù)K統(tǒng)一設(shè)置為100。遺傳算法迭代次數(shù)也為100,交叉概率為0.8,變異概率為0.2,種群數(shù)量為200。

4.3 仿真結(jié)果與算法對比

在所構(gòu)建的20×20的環(huán)境模型中,改進前后的傳統(tǒng)蟻群算法六種不同路徑的仿真結(jié)果如圖5所示。

圖5 蟻群算法六條放牧路徑規(guī)劃結(jié)果圖

圖6 遺傳算法六條放牧路徑規(guī)劃結(jié)果圖

如上圖5、6、7所示:左上右下路徑、右上左下路徑和右下左下路徑改進之后效果較明顯,本文用藍色將該路徑標(biāo)注出來,圖7的上述三條路徑在應(yīng)對相對復(fù)雜的障礙物環(huán)境條件時,選擇的路徑較蟻群算法和遺傳算法選擇的路徑更為平滑,收斂后的路徑距離也較改進前更優(yōu),對于改進前中出現(xiàn)的路徑陷入局部最優(yōu)情況也有較大的改善,避免出現(xiàn)較為嚴重繞路情況。至于左上右上路徑、左上右下路徑和右上右下路徑,改進后的區(qū)別較小,主要原因是這三條路徑上沒有較為復(fù)雜的障礙物,所以“螞蟻族群”在搜索的過程中不容易出現(xiàn)盲目搜索的情況。

圖7 本文算法六條放牧路徑規(guī)劃結(jié)果圖注:改進前后路徑區(qū)別明顯的由藍色標(biāo)注

對比圖8改進前后的路徑收斂曲線,本文提出的改進后的算法相對于同路徑改進前的蟻群算法和遺傳算法,收斂速度和運行明顯加快。根據(jù)表1中改進前后的最短路徑對比結(jié)果,可以看出六條路徑中有五條改進后的路徑的最小距離相較于改進前更短,另外的一條與改進前持平。綜上所述,改進后的算法在路徑優(yōu)化和收斂性上要優(yōu)于傳統(tǒng)蟻群算法。

表1 算法運行結(jié)果比較

圖8 蟻群算法、遺傳算法和本文算法前后六條放牧路徑收斂曲線

5 結(jié)束語

本文針對現(xiàn)階段放牧存在的實際可操作性較復(fù)雜的問題,通過與適應(yīng)性改進蟻群算法相結(jié)合,在一定程度上有效的解決該牧場的過度放牧和草場閑置問題;通過設(shè)計多條路徑來應(yīng)對多變的牧場條件和測試改進算法在不同路徑下表現(xiàn),來檢測改進算法應(yīng)對不同條件的適應(yīng)能力,本文針對傳統(tǒng)蟻群算法容易陷入局部最優(yōu)和在迭代過程中信息素濃度差別不明顯等問題進行相應(yīng)的改進,在每次迭代后增加最短路徑上的信息素濃度并減少最長路徑上的信息素濃度來優(yōu)化算法的收斂速度和尋找最優(yōu)路徑的能力。

本文設(shè)計的輪牧和路徑規(guī)劃相結(jié)合的方法不僅適用于實驗?zāi)翀?通過修改相關(guān)參數(shù),可以根據(jù)不同地區(qū)的放牧習(xí)慣和牧草特點進行個性化的輪牧劃分設(shè)計;同時,通過設(shè)計不同的起點和終點,規(guī)劃的路徑可以更好的應(yīng)對當(dāng)?shù)啬翀鰲l件的變化,選擇合適的線路進行放牧作業(yè),實驗證明本文提出的改進方法具有一定的理論參考意義和實際應(yīng)用意義。