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

楊琳藝

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

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

中圖分類號(hào)： TN911.1?34; TP393? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? 文章編號(hào)： 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)用也開(kāi)始得到了社會(huì)的認(rèn)可和推廣。智能交通、智慧醫(yī)療和智能安防等新型市場(chǎng)均采用了物聯(lián)網(wǎng)的理論和框架。隨著國(guó)內(nèi)旅游事業(yè)的不斷增長(zhǎng)，各大景區(qū)對(duì)硬件和軟件服務(wù)的投入不斷增加，基于物聯(lián)網(wǎng)技術(shù)的景區(qū)、園林導(dǎo)覽系統(tǒng)正逐漸得到普及，以便為游客提供更加人性化和便捷化的服務(wù)[1?3]，例如依托移動(dòng)設(shè)備的園林智能輔助導(dǎo)覽系統(tǒng)等，能夠以APP的形式為游客提供各種在線服務(wù)，承載了實(shí)現(xiàn)用戶人機(jī)交互的關(guān)鍵功能。其中，導(dǎo)覽路徑規(guī)劃作為園林智能輔助導(dǎo)覽系統(tǒng)中的重要一環(huán)，能夠?yàn)橛慰吞峁?shí)時(shí)的目的地地圖路徑指導(dǎo)，改變了傳統(tǒng)的人工導(dǎo)覽方式，節(jié)省了人工成本，更提高了便捷性。

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

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

1.1? 研究思路介紹

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

1.2? 環(huán)境模型

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

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

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

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

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

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

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

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

2.1? 人工魚(yú)群算法

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

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

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

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

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

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

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

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

2.2? 參數(shù)編碼

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

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

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

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

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

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

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

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

3? 實(shí)驗(yàn)結(jié)果與分析

3.1? 實(shí)驗(yàn)參數(shù)

為了驗(yàn)證提出園林導(dǎo)覽路徑規(guī)劃方法的有效性，在Matlab仿真環(huán)境下進(jìn)行了模擬實(shí)驗(yàn)。本文所有實(shí)驗(yàn)的運(yùn)行環(huán)境均為Windows 7系統(tǒng)下的Matlab 2015b，處理器為Intel[?] CoreTM i5?3210M CPU @ 2.50 GHz，內(nèi)存為8 GB。在本文實(shí)驗(yàn)過(guò)程中，設(shè)置最大迭代次數(shù)為2 000，人工魚(yú)群數(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é)果對(duì)比如圖2所示，兩者的迭代曲線如圖3所示。從圖2可以看出，本文提出方法規(guī)劃出的路徑明顯優(yōu)于混合遺傳算法，也就是說(shuō)，路徑導(dǎo)航的精確性更高。從圖3可以看出，相比于混合遺傳算法，本文方法能夠較快地找到全局最優(yōu)解，反映出改進(jìn)的人工魚(yú)群算法的快速收斂性能。

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

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

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

4? 結(jié)? 語(yǔ)

本文提出將人工魚(yú)群算法應(yīng)用于園林導(dǎo)覽路徑規(guī)劃，并針對(duì)人工魚(yú)群算法存在的缺點(diǎn)，在步長(zhǎng)更新方式上進(jìn)行了改進(jìn)，有利于提高尋優(yōu)精度和運(yùn)行速度。此外，結(jié)合了權(quán)重系數(shù)法，引入總長(zhǎng)度和平滑度兩個(gè)指標(biāo)系數(shù)設(shè)計(jì)路徑的總目標(biāo)函數(shù)。仿真環(huán)境下的測(cè)試和實(shí)際案例應(yīng)用結(jié)果驗(yàn)證了提出路徑規(guī)劃方法的可行性和有效性。但是，在實(shí)際的尋優(yōu)過(guò)程中，處在障礙物類型不明確的區(qū)域時(shí)，路徑規(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)，楊杰.基于滑模控制的自動(dòng)泊車系統(tǒng)路徑跟蹤研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2019，50（2）：363?371.

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

[6] 張濤，曹振剛，吳坤，等.一種混合遺傳算法在地震救援路徑優(yōu)化問(wèn)題中的應(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.