面向農業旅游的人工智能路線規劃算法應用研究

王 潤

（無錫城市職業技術學院旅游學院，江蘇 無錫 214000）

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

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

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

1 材料與方法

1.1 試驗材料

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

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

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

1.2 試驗方法

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

圖1 遺傳術語在算法中的對應關系

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

圖2 遺傳算法的基本流程

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

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

圖3 蟻群算法原理

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

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

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

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

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

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

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

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

蟻群算法的實現流程見圖4。

圖4 蟻群算法的實現流程

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

圖5 融合算法流程

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

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

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

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

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

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

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

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

第9 步，螞蟻根據計算所得概率移動至下一節點。

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

第11 步，若已滿足前期設置的循環次數，則終止操作，輸出最優解；若否，則返回步驟9。

1.2.4 仿真試驗方法

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

表1 融合算法其他參數設置

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

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

圖6 15 個節點的位置示意圖

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

2 結果與分析

2.1 算法參數尋優結果

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

圖7 啟發因子α 參數尋優結果

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

圖8 期望啟發因子β 參數尋優結果

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

圖9 信息素揮發因子ρ參數尋優結果

2.2 算法仿真結果

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

圖10 算法仿真結果

3 結論與討論

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