基于人工魚群算法的園林導(dǎo)覽路徑規(guī)劃方法研究

楊琳藝

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

關(guān)鍵詞： 園林導(dǎo)覽; 路徑規(guī)劃; 人工魚群算法; 自適應(yīng)步長; 目標(biāo)函數(shù); 迭代曲線

中圖分類號： TN911.1?34; TP393? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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? 引? 言

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

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

1? 問題描述及其環(huán)境模型

1.1? 研究思路介紹

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

1.2? 環(huán)境模型

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

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

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

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

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

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

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

2? 基于改進(jìn)人工魚群算法的園林導(dǎo)覽路徑規(guī)劃

2.1? 人工魚群算法

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

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

1） 覓食行為：設(shè)該人工魚此刻的狀態(tài)為[Pi]，在其感知范圍內(nèi)隨機(jī)挑選一個狀態(tài)[Pj]。判斷是否移動的數(shù)學(xué)表達(dá)式為[10]：

式中：[Rand]表示一個取值范圍為（0，1）的隨機(jī)數(shù);[step]表示步長;[dij]表示人工魚的當(dāng)前鄰域;[Yi]和[Yj]分別為兩個不同狀態(tài)下的適應(yīng)值。

2） 聚群行為：設(shè)人工魚群中人工魚的[dij]內(nèi)感知到的伙伴數(shù)目為[nf]且中心位置狀態(tài)為[Pc]，數(shù)學(xué)表達(dá)式為：

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

3） 追尾行為;設(shè)人工魚當(dāng)前的[dij]內(nèi)感知到食物濃度的最大狀態(tài)是[Pmax]，其數(shù)學(xué)表達(dá)式為：

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

2.2? 參數(shù)編碼

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

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

2.3? 參數(shù)的改進(jìn)

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

式中：[numbermax]和[numbercur]分別表示最大迭代次數(shù)和當(dāng)前迭代次數(shù);[stepmax]和[stepmin]分別表示設(shè)置的最大步長和最小步長。

2.4? 目標(biāo)函數(shù)

園林導(dǎo)覽方面的路徑規(guī)劃不是一個單目標(biāo)的優(yōu)化問題，而應(yīng)該是一個多目標(biāo)優(yōu)化求解問題，因此，本文結(jié)合權(quán)重系數(shù)法，引入總長度和平滑度兩個指標(biāo)系數(shù)，來設(shè)計路徑[P]的總目標(biāo)函數(shù)：

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

3? 實驗結(jié)果與分析

3.1? 實驗參數(shù)

為了驗證提出園林導(dǎo)覽路徑規(guī)劃方法的有效性，在Matlab仿真環(huán)境下進(jìn)行了模擬實驗。本文所有實驗的運行環(huán)境均為Windows 7系統(tǒng)下的Matlab 2015b，處理器為Intel[?] CoreTM i5?3210M CPU @ 2.50 GHz，內(nèi)存為8 GB。在本文實驗過程中，設(shè)置最大迭代次數(shù)為2 000，人工魚群數(shù)目為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? 仿真結(jié)果分析

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

3.3? 實例應(yīng)用結(jié)果分析

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

圖5為兩種方法完成路徑規(guī)劃的運行過程對比結(jié)果。表1為兩種方法的路徑規(guī)劃數(shù)據(jù)統(tǒng)計結(jié)果，本文方法在運行時間上減少了24.7%，說明改進(jìn)算法減少了所需迭代次數(shù)，大大提高了路徑規(guī)劃效率。由最優(yōu)解、路徑長度和平滑度的對比結(jié)果能夠看出，本文方法在收斂精度上表現(xiàn)更好，能夠有效解決多目標(biāo)優(yōu)化的路徑規(guī)劃問題。

4? 結(jié)? 語

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

參考文獻(xiàn)

[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] 姜立標(biāo)，楊杰.基于滑?？刂频淖詣硬窜囅到y(tǒng)路徑跟蹤研究[J].農(nóng)業(yè)機(jī)械學(xué)報，2019，50（2）：363?371.

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

[6] 張濤，曹振剛，吳坤，等.一種混合遺傳算法在地震救援路徑優(yōu)化問題中的應(yīng)用[J].科學(xué)技術(shù)與工程，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.