基于人工魚群算法的園林導覽路徑規劃方法研究

楊琳藝

摘? 要： 導覽路徑規劃作為園林智能輔助導覽系統中的重要一環，能夠為游客提供實時的目的地地圖路徑指導，直接影響著用戶的使用體驗。為了提高其準確性和實時性，提出一種基于人工魚群算法的園林導覽路徑規劃方法。對導覽環境模型及相關問題進行描述，并通過總長度和平滑度兩個方面設計了路徑規劃的目標函數。對采用的人工魚群優化算法進行分析，并針對人工魚群算法存在的缺點，在步長更新方式上進行了改進，有利于提高尋優精度和運行速度。仿真環境下的測試結果表明，提出的改進算法具有更好的最優解和快速收斂性能。實際案例應用結果驗證了提出路徑規劃方法的可行性和有效性。

關鍵詞： 園林導覽; 路徑規劃; 人工魚群算法; 自適應步長; 目標函數; 迭代曲線

中圖分類號： TN911.1?34; TP393? ? ? ? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）03?0169?04

Research on garden guiding path planning method

based on artificial fish swarm algorithm

YANG Linyi

（Sichuan Tourism University， Chengdu 610000， China）

Abstract： Guiding path planning， as an important part of the garden intelligent assistant guiding system， can provide visitors with real?time destination map path guidance， which directly affects the user experience. In order to improve its accuracy and real?time performance， a garden guiding path planning method based on artificial fish swarm is proposed. The guiding environmental model and related problems are described， and the objective function of path planning is designed by total length and smoothness. In addition， the artificial fish swarm algorithm is analyzed. In consideration of the shortcomings of the artificial fish swarm algorithm， the step size update method is improved， which is beneficial to the improvement of the optimizing precision and running speed. The test results in the simulation environment show that the improved algorithm has better optimal solution and fast convergence performance. The actual application results verify the feasibility and effectiveness of the proposed path planning method.

Keywords： garden guiding; path planning; artificial fish swarm algorithm; adaptive step size; objective function; iterative curve

0? 引? 言

隨著各種高性能電子設備的成本不斷下降，物聯網技術應用也開始得到了社會的認可和推廣。智能交通、智慧醫療和智能安防等新型市場均采用了物聯網的理論和框架。隨著國內旅游事業的不斷增長，各大景區對硬件和軟件服務的投入不斷增加，基于物聯網技術的景區、園林導覽系統正逐漸得到普及，以便為游客提供更加人性化和便捷化的服務[1?3]，例如依托移動設備的園林智能輔助導覽系統等，能夠以APP的形式為游客提供各種在線服務，承載了實現用戶人機交互的關鍵功能。其中，導覽路徑規劃作為園林智能輔助導覽系統中的重要一環，能夠為游客提供實時的目的地地圖路徑指導，改變了傳統的人工導覽方式，節省了人工成本，更提高了便捷性。

通過調查發現，目前應用于園林導覽方面的路徑規劃研究仍處于空白階段，因此，本文提出將群體智能優化算法中較為先進的人工魚群算法應用于園林導覽路徑規劃，并對標準的人工魚群算法進行了自適應步長改進，有效提高了收斂速度和尋優精度。在仿真測試和實際案例應用中均得到了較為理想的運行效果。

1? 問題描述及其環境模型

1.1? 研究思路介紹

導覽路徑規劃功能中導航的精確度和運行速度是兩個關鍵的技術指標，也成為各種相關領域研究的重點和難點。例如，文獻[4]建立了車輛的運動學模型并提出了一種基于滑模控制的自動泊車系統路徑跟蹤方法，實現了智能泊車入庫導航。文獻[5]提出了一種基于概率地圖的工業機器人路徑搜索優化算法，能夠自動搜索出一條無碰撞的全局優化路徑。相比于其他類似方法，文獻[6]將及時性與安全性作為最主要的約束目標，提出了一種應用于地震救援路徑優化問題的混合遺傳算法，得到了較高的求解精度和收斂速度。但是，目前應用于園林導覽方面的路徑規劃研究仍處于空白階段，因此，本文提出將群體智能優化算法中較為先進的人工魚群算法應用于園林導覽路徑規劃。因為相比遺傳算法，人工魚群算法具有較好的全局尋優能力和較快的收斂速度，并針對人工魚群算法存在的缺點，在步長更新方式上進行改進，有利于提高尋優精度和運行速度。此外，在目標函數的確定方面本文引入了文獻[5?6]的理念，從總長度和平滑度兩個方面來建立路徑的總目標函數。

1.2? 環境模型

假設園林導覽的場景在直角坐標系[XOY]中，起始點表示為[S（xs，ys）]，目標點表示為[T（xt，yt）]，經過坐標變換，起始點和目標點之間的直線線段[ST]設為[x]軸，得到新環境坐標系[xOy]，其中的任一點表示為[P（X，Y）]，坐標變換的公式如下：

式中：[（x，y）]表示[P]在新坐標系[xOy]中的坐標;[θ]表示初始軸與[ST]之間的夾角。

規劃路徑與障礙物的碰撞檢測分為兩種情況：

1） 多邊形障礙物。如果路徑線段和多邊形某條邊的線段滿足如下條件，則表示兩者相交，存在碰撞。

式中：[P1P2]和[Q1Q2]分別為兩條線段的兩個端點;[×]和[?]分別表示向量的叉乘和點乘。

2） 圓形障礙物。路徑線段和圓形邊相交的條件為：

式中：[x1，y1]和[x2，y2]分別表示某一路徑段的兩個端點坐標;[xo，yo]表示圓形障礙物;[R]表示圓形障礙物的半徑。

2? 基于改進人工魚群算法的園林導覽路徑規劃

2.1? 人工魚群算法

人工魚群算法[7?8]作為一種優化算法，是一種模擬自然界中動物群體智能行為的方法。利用模擬的人工魚模擬魚群的覓食行為、聚群行為和追尾行為，以便達到尋優目的。假設AF是真實魚的一個虛擬實體，稱為人工魚，其視覺概念示意圖如圖1所示。

圖1中，[X]表示AF的當前狀態;Visual為其視野范圍;[Xv]為其某時刻視點的位置，若此位置的狀態優于當前狀態，則AF移動到[Xnext]，否則，AF尋找其他位置。人工魚群的四種基本行為包括[9]：覓食行為、聚群行為、追尾行為、隨機行為。具體流程如下：

1） 覓食行為：設該人工魚此刻的狀態為[Pi]，在其感知范圍內隨機挑選一個狀態[Pj]。判斷是否移動的數學表達式為[10]：

式中：[Rand]表示一個取值范圍為（0，1）的隨機數;[step]表示步長;[dij]表示人工魚的當前鄰域;[Yi]和[Yj]分別為兩個不同狀態下的適應值。

2） 聚群行為：設人工魚群中人工魚的[dij]內感知到的伙伴數目為[nf]且中心位置狀態為[Pc]，數學表達式為：

式中[δ]表示擁擠度因子。

3） 追尾行為;設人工魚當前的[dij]內感知到食物濃度的最大狀態是[Pmax]，其數學表達式為：

4） 隨機行為：設人工魚此刻的狀態是[Pi]，在感知范圍[Visual]內隨機挑選另外一個狀態[Pj]并朝著此方向前進一步[11?12]。

2.2? 參數編碼

初始化的過程中，設人工魚的位置是[n×s]維變量，[n]表示聚類中心的數量，[s]為樣本向量的維數，則起始的位置編碼如下所示[13]：

式中：[cij，j=1，2，…，s]表示種群中每個個體代表的聚類中心。

2.3? 參數的改進

研究結果顯示：人工魚的步長越大，收斂速度較快，但會導致尋優精度降低;步長越小，尋優精度提高了，但是收斂速度會較低。因此，動態的步長變化成為了解決該問題的有效方法，本文定義的自適應步長為：

式中：[numbermax]和[numbercur]分別表示最大迭代次數和當前迭代次數;[stepmax]和[stepmin]分別表示設置的最大步長和最小步長。

2.4? 目標函數

園林導覽方面的路徑規劃不是一個單目標的優化問題，而應該是一個多目標優化求解問題，因此，本文結合權重系數法，引入總長度和平滑度兩個指標系數，來設計路徑[P]的總目標函數：

式中：[ω1]為路徑長度的權值因子;[ω2]為路徑平滑度的權值因子;[f1（P）]和[f2（P）]分別為路徑總長度和平滑度，其中平滑度的計算方式與文獻[5?6]一致。

3? 實驗結果與分析

3.1? 實驗參數

為了驗證提出園林導覽路徑規劃方法的有效性，在Matlab仿真環境下進行了模擬實驗。本文所有實驗的運行環境均為Windows 7系統下的Matlab 2015b，處理器為Intel[?] CoreTM i5?3210M CPU @ 2.50 GHz，內存為8 GB。在本文實驗過程中，設置最大迭代次數為2 000，人工魚群數目為60，[Visual]=6，[step]=0.4， [stepmin]=0.002，[stepmax]=0.6，[ω1=0.5]，[ω2=0.5]，[λ]=0.3，try_number=50。

3.2? 仿真結果分析

將文獻[6]中基于混合遺傳算法的路徑規劃方法和本文方法，在100[×]100的仿真環境地圖中分別執行10次，得到的規劃結果對比如圖2所示，兩者的迭代曲線如圖3所示。從圖2可以看出，本文提出方法規劃出的路徑明顯優于混合遺傳算法，也就是說，路徑導航的精確性更高。從圖3可以看出，相比于混合遺傳算法，本文方法能夠較快地找到全局最優解，反映出改進的人工魚群算法的快速收斂性能。

3.3? 實例應用結果分析

為了驗證提出的路徑規劃方法解決實際園林場景案例的能力，在某大型植物園林場景中進行了具體測試。該植物園林的設計總平面圖如圖4所示。

圖5為兩種方法完成路徑規劃的運行過程對比結果。表1為兩種方法的路徑規劃數據統計結果，本文方法在運行時間上減少了24.7%，說明改進算法減少了所需迭代次數，大大提高了路徑規劃效率。由最優解、路徑長度和平滑度的對比結果能夠看出，本文方法在收斂精度上表現更好，能夠有效解決多目標優化的路徑規劃問題。

4? 結? 語

本文提出將人工魚群算法應用于園林導覽路徑規劃，并針對人工魚群算法存在的缺點，在步長更新方式上進行了改進，有利于提高尋優精度和運行速度。此外，結合了權重系數法，引入總長度和平滑度兩個指標系數設計路徑的總目標函數。仿真環境下的測試和實際案例應用結果驗證了提出路徑規劃方法的可行性和有效性。但是，在實際的尋優過程中，處在障礙物類型不明確的區域時，路徑規劃算法極易陷入局部最優解，因此效果不夠穩定，魯棒性不高，后續將結合傳感器或者GIS系統進行進一步改進。

參考文獻

[1] BLETSAS A， ALEVIZOS P N， VOUGIOUKAS G. The art of signal processing in backscatter radio for μW （or less） Internet of Things： intelligent signal processing and backscatter radio enabling batteryless connectivity [J]. IEEE signal processing magazine， 2018， 35（5）： 28?40.

[2] BELLO O， ZEADALLY S. Intelligent device?to?device communication in the Internet of Things [J]. IEEE systems journal， 2016， 10（3）：1172?1182.

[3] GIL D， FERR?NDEZ A， MORAMORA H， et al. Internet of Things： A review of surveys based on context aware intelligent services [J]. Sensors， 2016， 16（7）：1069.

[4] 姜立標，楊杰.基于滑模控制的自動泊車系統路徑跟蹤研究[J].農業機械學報，2019，50（2）：363?371.

[5] 陳琳，韋志琪，戴駿，等.基于概率地圖的工業機器人路徑搜索優化算法[J].武漢理工大學學報，2016，38（4）：90?95.

[6] 張濤，曹振剛，吳坤，等.一種混合遺傳算法在地震救援路徑優化問題中的應用[J].科學技術與工程，2018，18（1）：266?272.

[7] NA F， ZHOU J， RUI Z， et al. A hybrid of real coded genetic algorithm and artificial fish swarm algorithm for short?term optimal hydrothermal scheduling [J]. International journal of electrical power & energy systems， 2014， 62（11）： 617?629.

[8] AZAD M A K， ROCHA A M A C， FERNANDES E M G P. A simplified binary artificial fish swarm algorithm for 0–1 quadratic knapsack problems [J]. Journal of computational & applied mathematics， 2014， 259（4）： 897?904.

[9] ROCHA A M A C， COSTA M F P， FERNANDES E M G P. A filter?based artificial fish swarm algorithm for constrained global optimization： theoretical and practical issues [J]. Journal of global optimization， 2014， 60（2）： 239?263.

[10] YANG Weihong. An improved artificial fish swarm algorithm and its application in multiple sequence alignment [J]. Journal of computational & theoretical nanoscience， 2014， 11（3）： 888?892.

[11] HAN Wei， WANG Honghua， CHEN Ling. Parameters identification for photovoltaic module based on an improved artificial fish swarm algorithm [EB/OL]. [2014?8?27]. https：//www.ncbi.nlm.nih.gov/pmc/articles/PMC4163354/.

[12] LIU Mingzhou， MA Jing， LIN Ling， et al. Intelligent assembly system for mechanical products and key technology based on internet of things [J]. Journal of intelligent manufacturing， 2017， 28（2）： 271?299.

[13] DUAN Qichang， MAO Mingxuan， DUAN Pan， et al. An improved artificial fish swarm algorithm optimized by particle swarm optimization algorithm with extended memory [J]. Kybernetes， 2016， 45（2）： 210?222.

[14] NESHAT M， SEPIDNAM G， SARGOLZAEi M， et al. Artificial fish swarm algorithm： a survey of the state?of?the?art， hybridization， combinatorial and indicative applications [J]. Artificial intelligence review， 2014， 42（4）：965?997.