基于改進(jìn)魚(yú)群算法的園林路徑設(shè)計(jì)優(yōu)化方法研究

闕晨曦　鄧雙　蘭思仁

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

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

中圖分類(lèi)號(hào)： TN915.02?34; TP391 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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)網(wǎng)技術(shù)和高性能電子設(shè)備的迅速發(fā)展與推廣，智慧安防、智慧醫(yī)療及智能交通等應(yīng)用均采用了物聯(lián)網(wǎng)的技術(shù)框架與思路為用戶(hù)提供更加便捷化、人性化的服務(wù)[1]。同時(shí)為了加快旅游事業(yè)的發(fā)展，推進(jìn)物聯(lián)網(wǎng)技術(shù)在智慧園林中的應(yīng)用，國(guó)內(nèi)各大景區(qū)不斷增加軟件與硬件設(shè)施來(lái)構(gòu)建園林智能導(dǎo)覽系統(tǒng)[2?4]。該系統(tǒng)以APP的形式為旅客提供各類(lèi)景點(diǎn)信息，實(shí)現(xiàn)用戶(hù)與園林的智能交互[5?7]。其中，園林路徑導(dǎo)覽規(guī)劃是智慧園林建設(shè)的重要一環(huán)，其通過(guò)引入智能路徑規(guī)劃應(yīng)用為游客提供實(shí)時(shí)目的地圖引導(dǎo)[8?10]。

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

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

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

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

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

[θ=arcsinyT-ySST] （2）

式中：[θ]為直線(xiàn)段ST與x軸間的距離;[（x，y）]為[P（X，Y）]映射后的坐標(biāo)點(diǎn)。

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

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

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

式中，兩條線(xiàn)段的端點(diǎn)由[P2P1，Q2Q1]表示。

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

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

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

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

為了獲得距離更短、更平滑的目標(biāo)線(xiàn)路，本文結(jié)合權(quán)重系數(shù)法來(lái)定義園林導(dǎo)覽路徑。該目標(biāo)函數(shù)包括總長(zhǎng)度[f1（P）]與平滑度[f2（P）]目標(biāo)，具體表示如下：

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

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

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

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

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

從人工魚(yú)[Xi]的視野[Visual]內(nèi)隨機(jī)抽取一個(gè)狀態(tài)[Xj]來(lái)更新[Xi]，公式如下：

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

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

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

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

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

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

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

對(duì)處于狀態(tài)[Xi]的人工魚(yú)，通過(guò)搜索其周?chē)耐閿?shù)量[nf]，計(jì)算[Xj]的最大適應(yīng)度值[Yj]。當(dāng)[Yjnf

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

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

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

本文提出的改進(jìn)人工魚(yú)群搜索算法的整體流程如圖1所示。

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

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