闕晨曦　鄧雙　蘭思仁

摘 ?要： 針對園林景觀路徑規(guī)劃對于個性化服務與智能規(guī)劃的需求，文中提出一種基于改進魚群算法的園林景觀路徑設計優(yōu)化方法。該算法通過構建二維導覽模型來確定優(yōu)化路徑平滑度與總長度目標函數(shù)，實現(xiàn)無障礙路徑規(guī)劃。針對傳統(tǒng)人工魚群算法局部搜索能力較差、前期容易出現(xiàn)盲目搜索的問題，將和聲搜索算法引入人工魚群算法，對魚群信息進行微調擾動從而得到更優(yōu)的全局最優(yōu)路徑。仿真與實驗測試結果表明，所提出的方法能夠有效優(yōu)化園林路徑規(guī)劃問題，進而得到更平滑、更合理的園林導覽路徑，且所提出的改進算法相對于傳統(tǒng)算法具有更快的收斂速度。

關鍵詞： 園林景觀; 路徑規(guī)劃; 改進魚群算法; 和聲搜索; 最優(yōu)路徑; 仿真測試

中圖分類號： TN915.02?34; TP391 ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）24?0113?04

Research on garden path design optimization method based on

improved fish swarm algorithm

QUE Chenxi1， DENG Shuang2， LAN Siren1

（1. Fujian agriculture and Forestry University， Fuzhou 350007， China;

2. Shanghai Tongji Urban Planning and Design Institute Co.， Ltd.， Shanghai 200092， China）

Abstract： In allusion to the demand for personalized services and intelligent planning for landscape path planning， a garden landscape path design optimization method based on improved fish school algorithm is proposed. The algorithm is used to build the two?dimensional guiding model to determine the objective functions of optimization path smoothness and total length， so as to achieve the barrier?free path planning. Aiming at the problem of poor local search ability and blind search in the early stage of traditional artificial fish swarm algorithm， the harmony search algorithm is introduced into the artificial fish swarm algorithm， and the fish swarm information is fine?tuned and disturbed to obtain a better global optimal path. The simulation and experimental testing results show that the proposed method can effectively optimize the garden path planning and obtain a smoother and more reasonable garden guiding path， and the proposed improved algorithm has faster convergence rate than that of the traditional algorithm.

Keywords： garden landscape; path planning; improved fish swarm algorithm; harmony search; optimal path; simulation testing

0 ?引 ?言

隨著物聯(lián)網技術和高性能電子設備的迅速發(fā)展與推廣，智慧安防、智慧醫(yī)療及智能交通等應用均采用了物聯(lián)網的技術框架與思路為用戶提供更加便捷化、人性化的服務[1]。同時為了加快旅游事業(yè)的發(fā)展，推進物聯(lián)網技術在智慧園林中的應用，國內各大景區(qū)不斷增加軟件與硬件設施來構建園林智能導覽系統(tǒng)[2?4]。該系統(tǒng)以APP的形式為旅客提供各類景點信息，實現(xiàn)用戶與園林的智能交互[5?7]。其中，園林路徑導覽規(guī)劃是智慧園林建設的重要一環(huán)，其通過引入智能路徑規(guī)劃應用為游客提供實時目的地圖引導[8?10]。

目前，為了提升路徑規(guī)劃的運行速度與精確度，在各應用領域提出了多種智能優(yōu)化和處理算法。文獻[11]為了實現(xiàn)智能泊車入庫，提出一種基于車輛運動模型的自動泊車路徑跟蹤算法。文獻[12]提出使用遺傳優(yōu)化算法來提升工業(yè)機器人路徑搜索的精度。文獻[13]中，為了保證冷鏈物流運輸?shù)募皶r配送，通過分析車輛運行成本、貨物變質成本和冷藏成本來構建車輛取貨配送優(yōu)化模型。文獻[14]將低碳經濟的思路引入冷鏈物流路徑規(guī)劃問題中，采用蟻群算法求解最優(yōu)運輸路徑。

然而，目前針對園林導覽路徑規(guī)劃的研究仍較少。為了提供個性化與智能化的路徑規(guī)劃流程，本文提出一種基于改進魚群算法的園林路徑規(guī)劃算法。該算法通過構建園林導覽二維模型來確定路徑規(guī)劃目標，并基于人工魚群算法的迅速收斂與全局優(yōu)化能力求解該多目標優(yōu)化問題，實現(xiàn)了園林路徑的快速規(guī)劃。仿真與實驗結果表明，所提出的方法能夠有效解決園林路徑規(guī)劃問題，相對于傳統(tǒng)算法具有更快的收斂速度。

1 ?園林路徑規(guī)劃模型

園林路徑規(guī)劃即根據(jù)用戶的當前位置與目的位置，構建一條最優(yōu)的游覽路徑。本文將該問題表示成在給定的直角坐標系xOy中，求解從起始點[S（xS，yS）]到目標點[T（xT，yT）]的最優(yōu)路徑問題。為了簡化計算，本文將該直角坐標系進行仿射變換，將起始點到目標點間的路徑表示為直線段ST，則xOy坐標系上的任意一點[P（X，Y）]可以表示為：

[xy=cos θ ? -sin θsin θ ? ? cos θ-1?XY-xSyS] （1）

[θ=arcsinyT-ySST] （2）

式中：[θ]為直線段ST與x軸間的距離;[（x，y）]為[P（X，Y）]映射后的坐標點。

由于在路徑規(guī)劃中存在各種障礙物，文中將其分為多邊形障礙物與圓形障礙物。為了避免導覽路徑和障礙物發(fā)生碰撞，本文定義了以下防碰撞條件。

1） 防多邊形碰撞。為了防止規(guī)劃處的路徑與多邊形障礙物發(fā)生碰撞，本文設定的條件為：

[[（P1-Q1）（Q2-Q1）]?[（Q2-Q1）（P2-P1）]>0[（Q1-P1）（P2-P1）]?[（Q2-P1）（P2-P1）]>0] （3）

式中，兩條線段的端點由[P2P1，Q2Q1]表示。

2） 防圓形碰撞。為了防止規(guī)劃處的路徑與圓形障礙物發(fā)生碰撞，本文設定的條件為：

[（y2-y1）x0-（x2-x1）y0+（y1x2-x1y2）（y2-y1）2+（x2-x1）2>R] （4）

式中：[x2x1，y2y1]為兩條線段端點; [（x0，y0）]為圓形障礙物的圓心;R為半徑。

2 ?基于改進人工魚群算法的路徑規(guī)劃

為了獲得距離更短、更平滑的目標線路，本文結合權重系數(shù)法來定義園林導覽路徑。該目標函數(shù)包括總長度[f1（P）]與平滑度[f2（P）]目標，具體表示如下：

[f（P）=w1f1（P）+w2f2（P）] （5）

式中，[w1，w2]為權重系數(shù)。

文中使用魚群算法求解上述多目標優(yōu)化問題，其是一種源于仿生學的智能優(yōu)化算法。通過采用計算機程序來計算模擬魚群的覓食、聚群、追尾及隨機行為，從而求解目標函數(shù)并得到其最優(yōu)解。然而，該算法在前期容易出現(xiàn)盲目搜索的問題。本文為了提升算法的全局搜索能力，將和聲搜索算法引入其中。通過在迭代過程中產生大量的局部最優(yōu)解，來提升魚群隨機行為的搜索效率。

文中假設搜索空間中存在N條人工魚，并用[X=（x1，x2，…，xD）]表示人工魚的狀態(tài)信息，[f（x）]表示食物濃度，Y為式（5）所示的適應度函數(shù)值，[Xi-Xj]為人工魚i與j間的距離。文中將和聲搜索微調后的人工魚狀態(tài)賦值給人工魚群，公式如下：

[X=（x1，x2，…，xD）=Xi=（xi1，xi2，…，xiD）] （6）

從人工魚[Xi]的視野[Visual]內隨機抽取一個狀態(tài)[Xj]來更新[Xi]，公式如下：

[Xj=Xi+Visual·Rand（）] （7）

當更新后的狀態(tài)[Xi]優(yōu)于[Xj]時，則向狀態(tài)[Xj]移動一定步長，公式如下：

[Xt+1i=Xti+Xi-XtiXi-Xti·step·Rand（）] （8）

當狀態(tài)[Xi]不優(yōu)于[Xj]時，繼續(xù)更新[Xj]，直至達到最大覓食次數(shù)，公式如下：

[Xt+1i=xti+Visual·Rand（）] （9）

假設某人工魚所處的狀態(tài)為[Xi]，在其視野范圍[dijYi]時，該位置人工魚密度低于食物密度，則[Xi]根據(jù)式（10）向狀態(tài)[XC]前進一步;否則，繼續(xù)進行覓食。

[Xt+1i=Xti+XC-XtiXC-Xti·step·Rand（）] （10）

對處于狀態(tài)[Xi]的人工魚，通過搜索其周圍的同伴數(shù)量[nf]，計算[Xj]的最大適應度值[Yj]。當[Yjnf

[Xt+1i=Xti+Xj-XtiXj-Xti·step·Rand（）] （11）

基于上述步驟與尋優(yōu)操作，文中結合魚群密度與追尾行為形成人工魚庫，并通過尋優(yōu)操作生成新種群。然后使用和聲搜索算法進行微調擾動，及時跳出局部最優(yōu)解，從而得到全局最優(yōu)解。其中，和聲搜索的擾動因子為[δj（t）]，則人工魚的狀態(tài)演變公式為：

[x′i（j）=xi（j）+δj（t）] ? ? ?（12）

本文提出的改進人工魚群搜索算法的整體流程如圖1所示。

1） 算法初始化。設置魚群數(shù)量為N，每條魚的視野為Visual，更新步長為Step。

2） 魚群行為選擇。根據(jù)每條魚的追尾行為、覓食行為得到相應的[Xj]，并根據(jù)[Xnew=Xi+2·Visual]對[Xj]的每個分量進行混沌搜索。當狀態(tài)[Xi]優(yōu)于[Xj]時，使用式（8）更新[Xi];否則，使用式（9）更新[Xi]。