面向農(nóng)業(yè)旅游的人工智能路線規(guī)劃算法應用研究

王 潤

（無錫城市職業(yè)技術(shù)學院旅游學院，江蘇 無錫 214000）

旅游是大多數(shù)人在工作之余會選擇的放松方式之一；旅游業(yè)為各個地區(qū)的經(jīng)濟發(fā)展提供了重要支撐［1］。近年來，各縣、村積極響應國家鄉(xiāng)村振興戰(zhàn)略要求，農(nóng)業(yè)旅游是被重點關(guān)注的方面［2］。人們在旅游時通常會選擇陌生城市，因此需要根據(jù)該區(qū)域?qū)τ诰包c的介紹自行制定旅游方案，也可在當?shù)馗鷪F旅行。但這兩種方式普遍存在耗時長、路線規(guī)劃不合理的現(xiàn)象，無法給予人們較好的旅游體驗。因此，人們開始關(guān)注路線規(guī)劃算法方面的研究，目前在旅游路徑規(guī)劃研究中應用較為廣泛的是蟻群算法和遺傳算法。

李磊等［3］提出了一種蟻群優(yōu)化算法，并將其應用于旅游線路規(guī)劃。試驗結(jié)果表明，經(jīng)過優(yōu)化的蟻群算法能夠有效提高路徑的搜索速度，且緩解了景點的擁堵情況。陳雄等［4］提出一種改進的最大最小蟻群算法來進行旅游線路規(guī)劃。試驗結(jié)果表明，該算法與其他算法相比較擁有更好的性能，可有效規(guī)劃出較好的旅游線路。Damos 等［5］將遺傳算法和層次分析法應用于多個沖突目標下的城市旅游線路規(guī)劃評價，結(jié)果表明該方法比其他選擇路徑的方法更準確、更直觀。

傳統(tǒng)的遺傳算法無法利用系統(tǒng)的反饋信息，求解到一定程度時會造成過多的無用迭代，無法得到較好的解［6］；而蟻群算法在路徑搜索初期會由于信息素不存在或過少導致算法收斂速度慢和易陷入局部解［7］。基于此，本研究首先對蟻群算法和遺傳算法的基礎(chǔ)理論進行詳細闡述；其次，將兩種算法進行融合，提出了一種蟻群-遺傳（Ant colony-genetic algorithm，AC-GA）融合算法。兩種算法互補可有效彌補各自的缺陷，在旅游路線尋優(yōu)中發(fā)揮其最大優(yōu)勢，對于提高鄉(xiāng)村農(nóng)業(yè)旅游線路規(guī)劃的效率和質(zhì)量、促進區(qū)域經(jīng)濟發(fā)展具有重要意義。

1 材料與方法

1.1 試驗材料

本試驗以鄉(xiāng)村農(nóng)業(yè)旅游特色較為突出的江蘇省某縣為例，開展相關(guān)旅游線路規(guī)劃算法研究。該縣共有15 個較為熱門的景點，通過導航軟件定位得到每個景點的經(jīng)緯度坐標。

設景點r的經(jīng)緯度坐標為(xr,yr)，景點s的經(jīng)緯度坐標為(xs,ys)，則2 個景點之間的實際距離可由如下公式進行計算。

式中，R=6 371 km，代表地球半徑。

1.2 試驗方法

1.2.1 遺傳算法概述 遺傳算法是模仿生物進化過程中的優(yōu)勝劣汰遺傳機制而產(chǎn)生的隨機進化搜索方法，是通過搜索最優(yōu)解來解決問題的啟發(fā)式算法［8］。其基本思想是將生物界的繁殖、雜交、變異以及競爭的概念引入算法；在初始種群生成后，對其中的個體進行優(yōu)勝劣汰的選擇，通過交叉以及變異產(chǎn)生下一代種群等操作，以此從有限個問題解中找出最優(yōu)的一個［9］。生物遺傳術(shù)語在遺傳算法中的對應關(guān)系如圖1 所示。

圖1 遺傳術(shù)語在算法中的對應關(guān)系

解決一個特定問題可以有很多種方法，而初始種群就是由這些問題解隨機排列組成的，種群中的所有個體被視為染色體，個體的優(yōu)劣采用適應度函數(shù)評判，適應度值越大則代表個體越優(yōu)秀。按照適應度值的大小對父代進行篩選，淘汰較差的個體，將優(yōu)秀個體經(jīng)過交叉和變異來產(chǎn)生下一代種群，通過不斷循環(huán)迭代，解的質(zhì)量越來越好，最終算法收斂于最合適的解，當前種群所對應的問題結(jié)果即為最優(yōu)解［10］。遺傳算法的基本流程如圖2 所示。

圖2 遺傳算法的基本流程

常用的遺傳操作算子有選擇算子、交叉算子以及變異算子3 種，其中，選擇算子是遺傳算法，具備以下幾個優(yōu)點：算法可將問題的參數(shù)編碼成基因片段并進行循環(huán)迭代優(yōu)化，由于直接作用于參數(shù)本身，因此不受函數(shù)約束條件的限制；算法尋優(yōu)過程從任意一個種群開始，并非由某一個個體開始，過程中伴隨隱含并行搜索，能夠在一定程度上降低算法陷入局部最優(yōu)解的概率。綜上所述，遺傳算法適用于處理與旅游路線規(guī)劃類似的非線性組合優(yōu)化問題。

1.2.2 蟻群算法概述 螞蟻群在尋找食物時有其特定的配合方式，而蟻群算法是模擬這一過程而產(chǎn)生的一種算法［11］。螞蟻會在其經(jīng)過的路徑上釋放信息素，以此來進行標記和向同伴傳遞信息；蟻群會自發(fā)地選擇信息素濃度更高的路徑移動［12］。隨著時間的推移，當某一條路上的螞蟻數(shù)量越多，其路徑上的信息素濃度就越高，進而選擇此路徑的螞蟻就會越來越多，因而逐漸表現(xiàn)出一種正反饋現(xiàn)象，這就能夠很快找到最優(yōu)路徑［13］。其原理如圖3 所示。

圖3 蟻群算法原理

螞蟻主要是根據(jù)路徑上的信息素濃度與啟發(fā)式函數(shù)對下一步的節(jié)點進行選擇的［14］。設一個蟻群共有m只螞蟻，假定其中的第k只螞蟻目前在節(jié)點r處，則可按照如下公式對下一節(jié)點s進行選取。

式中，τ(r,s)為節(jié)點r與s之間的信息素強度；α為啟發(fā)因子；β為期望啟發(fā)因子；η(r,s)為能見度的啟發(fā)式信息，即啟發(fā)函數(shù)；其為r與s之間距離的倒數(shù)，即：

q為[0,1]區(qū)間上的隨機數(shù)，q0為[0,1]區(qū)間上的給定數(shù)。若q＞q0，根據(jù)如下公式對可行節(jié)點s進行選擇。

式中，Pk(r,s)為螞蟻k從r轉(zhuǎn)移到s的概率。螞蟻k經(jīng)過的全部節(jié)點均被記錄在禁忌表Tabuk之中，則有：

式中，arrowed(r)為螞蟻k在節(jié)點r處的可行節(jié)點集合；N(r)為螞蟻k在節(jié)點r處周圍所有可行節(jié)點的集合；NT(r)為節(jié)點r周圍禁忌節(jié)點的集合。

各個路徑上的信息素濃度不會一直保持不變，而是會隨時間逐步揮發(fā)。將信息素揮發(fā)因子表示為ρ，用1-ρ表示殘留的信息素濃度，每只螞蟻通過1個節(jié)點后可用如下公式進行局部信息素的更新。

式中，Q1為常數(shù)；ds為螞蟻k已經(jīng)走過的路徑總長。每只螞蟻在完成1 次循環(huán)后，需要對全局信息進行更新。通過以下公式對全局信息素進行更新。

式中，Q2為常數(shù)；Lkmin為本次搜索中的最短路徑長度；(r,s) ∈GlobalBestTour為螞蟻k所經(jīng)過的路徑(r,s)的最短路徑；Δτkr,s為螞 蟻k在 搜索后留在r與s之間路徑上的信息素增量。

蟻群算法的實現(xiàn)流程見圖4。

圖4 蟻群算法的實現(xiàn)流程

1.2.3 蟻群-遺傳融合算法 傳統(tǒng)的遺傳算法無法利用系統(tǒng)的反饋信息，求解到一定程度時會造成過多的無用迭代，無法得到較好的解。傳統(tǒng)的蟻群算法在路徑搜索初期會由于信息素不存在或過少而出現(xiàn)尋優(yōu)無頭緒的情況，使得算法極易出現(xiàn)收斂速度緩慢以及陷入局部最優(yōu)解的問題。為解決上述問題，提出了AC-GA 融合算法。融合算法路徑尋優(yōu)步驟如圖5 所示。

圖5 融合算法流程

第1 步，將目標問題中的景點采用1～N的實數(shù)進行編碼，并隨即排列。

第2 步，編碼后對種群以及算法的參數(shù)進行初始化。

第3 步，將2 個景點之間的路徑長度作為本試驗的適應度函數(shù)。

第4 步，根據(jù)種群中個體的適應度值進行篩選。

第5 步，根據(jù)交叉概率將要交叉的種群在對應的片段處進行交叉。

第6 步，根據(jù)變異概率選取個體，將其2 個不同位置的片段進行交換，完成變異。

第7 步，不斷循環(huán)以上步驟，直至滿足設定的最大迭代次數(shù)，輸出目標問題的若干初始解。

第8 步，蟻群算法參數(shù)初始化；將由遺傳算法輸出的初始解轉(zhuǎn)換為信息素，并按照其分布將螞蟻置于N個節(jié)點上。

第9 步，螞蟻根據(jù)計算所得概率移動至下一節(jié)點。

第10 步，螞蟻對所有節(jié)點進行一次完整的循環(huán)后，增加較短路徑上的信息素濃度，并清空途徑路徑記錄表。

第11 步，若已滿足前期設置的循環(huán)次數(shù)，則終止操作，輸出最優(yōu)解；若否，則返回步驟9。

1.2.4 仿真試驗方法

1）蟻群算法參數(shù)尋優(yōu)。合適的參數(shù)設置對于提高算法的性能有關(guān)鍵作用，起決定性的參數(shù)主要有啟發(fā)因子α、期望啟發(fā)因子β以及信息素揮發(fā)因子ρ。本試驗選取Tsplib 國際數(shù)據(jù)集中的Ei151 子數(shù)據(jù)集進行算法參數(shù)尋優(yōu)試驗。Tsplib 國際數(shù)據(jù)集是一個包含從十幾個節(jié)點的小規(guī)模問題集至數(shù)百個節(jié)點的大規(guī)模問題集的測試集合［15］；其中，Ei151 數(shù)據(jù)集的城市規(guī)模為50，最短路徑長度為426。試驗的其他參數(shù)設置如表1 所示。

表1 融合算法其他參數(shù)設置

每組試驗取10 次結(jié)果的平均值，并將融合算法的試驗結(jié)果與單一的蟻群算法進行比較。如，在α尋優(yōu)過程中，暫設置信息素強度Q= 100，β= 4，ρ=0.5，α在合理范圍內(nèi)取值進行仿真；同理，在確定了α的最佳取值范圍后，將其應用于β的尋優(yōu)過程，Q、ρ取值不變，確定β的最佳取值范圍；以此類推，最后對ρ的取值范圍進行確定。在對上述結(jié)果進行綜合考慮后，最后確定α、β和ρ的最佳組合。

2）旅游路徑尋優(yōu)方案。試驗以江蘇省某縣的15個景點作為算法尋優(yōu)過程中的15個節(jié)點，將該縣域視作1個坐標軸，各個節(jié)點在其中的位置如圖6所示。

圖6 15 個節(jié)點的位置示意圖

本試驗主要采用Matlab 軟件對算法的路徑尋優(yōu)過程進行仿真模擬；將路徑長度作為算法的適用度函數(shù)，并使用AC-GA 融合算法進行路徑尋優(yōu)。

2 結(jié)果與分析

2.1 算法參數(shù)尋優(yōu)結(jié)果

1）啟發(fā)因子α。本研究提出的AC-GA 融合算法與傳統(tǒng)蟻群算法的α尋優(yōu)結(jié)果如圖7所示。由圖7可以看出，當α較小時，傳統(tǒng)算法在搜索初期具有盲目性，迷失螞蟻數(shù)量以及算法的迭代次數(shù)較多；而采用融合算法后迷失螞蟻的數(shù)量有明顯減少，相較于傳統(tǒng)算法更易搜尋到最優(yōu)路徑?？紤]到算法是在α= 1時尋到了最優(yōu)路徑，并且迭代次數(shù)以及迷失螞蟻數(shù)量也趨于穩(wěn)定，因此將算法的啟發(fā)因子α設置為1。

圖7 啟發(fā)因子α 參數(shù)尋優(yōu)結(jié)果

2）期望啟發(fā)因子β。本研究提出的AC-GA 融合算法與傳統(tǒng)蟻群算法的β尋優(yōu)結(jié)果如圖8 所示。由圖8 可知，采用融合算法在β較小時，明顯地減少了迷失螞蟻的數(shù)量以及算法迭代次數(shù)，使算法的收斂速度得以提升。在β較大時，傳統(tǒng)的蟻群算法易陷入局部最優(yōu)，但融合算法降低了模型陷入局部最優(yōu)的幾率。算法在β= 7 時，迷失螞蟻數(shù)量以及迭代次數(shù)最少并且趨于穩(wěn)定，因此將β設置為7。

圖8 期望啟發(fā)因子β 參數(shù)尋優(yōu)結(jié)果

3）信息素揮發(fā)因子ρ。本研究提出的AC-GA 融合算法與傳統(tǒng)蟻群算法的ρ尋優(yōu)結(jié)果如圖9 所示。由圖9 可以看出，傳統(tǒng)算法在ρ∈[0.1,0.5]區(qū)間內(nèi)時，雖能夠?qū)さ米顑?yōu)路徑，但其收斂速度較慢；而融合算法在ρ∈[0.1,0.7]區(qū)間內(nèi)迷失螞蟻數(shù)量遠遠低于傳統(tǒng)算法，并且收斂速度快，曲線穩(wěn)定，ρ的選取空間更大，表現(xiàn)出更好的性能。當ρ較大時，算法極易陷入局部最優(yōu)。綜合考慮，將算法的信息素揮發(fā)因子ρ設置為0.7。綜上所述，融合算法的最優(yōu)參數(shù)組合為α= 1、β= 7、ρ= 0.7。

圖9 信息素揮發(fā)因子ρ參數(shù)尋優(yōu)結(jié)果

2.2 算法仿真結(jié)果

AC-GA融合算法與傳統(tǒng)蟻群算法的仿真結(jié)果如圖10 所示。由圖10 可以看出，采用AC-GA 融合算法與傳統(tǒng)蟻群算法輸出的路線圖有區(qū)別。由傳統(tǒng)蟻群算法輸出的最優(yōu)路線長度為4 705.486 9 km，ACGA融合算法輸出的最優(yōu)路線長度為2 247.731 6 km，比傳統(tǒng)算法短2 457.755 3 km。傳統(tǒng)算法在10 次試驗過程中的迭代次數(shù)平均為164，搜索時間平均為44.40 s；融合算法的迭代次數(shù)平均為51，比傳統(tǒng)算法少68.9%；搜索時間平均為9.01 s，比傳統(tǒng)算法少79.7%。綜上所述，AC-GA 算法表現(xiàn)出更優(yōu)秀的性能，適用于農(nóng)業(yè)旅游路線規(guī)劃研究。

圖10 算法仿真結(jié)果

3 結(jié)論與討論

智能算法已在旅游線路規(guī)劃研究中被廣泛使用，其中應用最多的是遺傳算法和蟻群算法。但傳統(tǒng)的遺傳算法和蟻群算法都存在一定的缺陷?；诖藛栴}，首先對蟻群算法和遺傳算法的基礎(chǔ)理論進行了詳細的闡述；其次，提出了AC-GA 融合算法；最后，以江蘇省某縣的15個景點為例，對算法的性能進行了驗證。結(jié)果表明，在同一參數(shù)設置條件下，采用本研究提出的AC-GA融合算法尋到最優(yōu)路徑時的迭代次數(shù)遠低于傳統(tǒng)的蟻群算法，收斂速度更快。ACGA融合算法輸出的最優(yōu)路線長度為2 247.731 6 km，比傳統(tǒng)蟻群算法短2 457.755 3 km。融合算法在10次試驗過程中的迭代次數(shù)平均為51，比傳統(tǒng)算法少68.9%；搜索時間平均為9.01 s，比傳統(tǒng)算法少79.7%。綜上所述，AC-GA 融合算法的性能優(yōu)于傳統(tǒng)算法，適用于農(nóng)業(yè)旅游路線規(guī)劃研究。由于文章的篇幅問題，只考慮了路線長度問題，未來還需將景點的熱度、開放時間以及費用等問題考慮進算法中，以提供更優(yōu)的路線規(guī)劃方案。本研究的開展對于提高鄉(xiāng)村農(nóng)業(yè)旅游線路規(guī)劃的效率和質(zhì)量，提升游客滿意度，進而帶動區(qū)域發(fā)展有重要意義。