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

1、 基于改進(jìn)魚群算法的園林路徑設(shè)計(jì)優(yōu)化方法研究 闕晨曦鄧雙蘭思仁摘 要： 針對(duì)園林景觀路徑規(guī)劃對(duì)于個(gè)性化服務(wù)與智能規(guī)劃的需求，文中提出一種基于改進(jìn)魚群算法的園林景觀路徑設(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)人工魚群算法局部搜索能力較差、前期容易出現(xiàn)盲目搜索的問(wèn)題，將和聲搜索算法引入人工魚群算法，對(duì)魚群信息進(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)算法具有更快的收斂速度。Key： 園林景觀; 路徑規(guī)劃;

2、 改進(jìn)魚群算法; 和聲搜索; 最優(yōu)路徑; 仿真測(cè)試： TN915.02?34; TP391 ： A ： 1004?373X（2020）24?0113?04Research on garden path design optimization method based onimproved fish swarm algorithmQUE Chenxi1， DENG Shuang2， LAN Siren1（1. Fujian agriculture and Forestry University， Fuzhou 350007， China;2. Shanghai Tongji Urban Plan

3、ning 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 use

4、d 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 s

5、warm 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 optimi

6、ze 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; si

7、mulation testing0 引 言隨著物聯(lián)網(wǎng)技術(shù)和高性能電子設(shè)備的迅速發(fā)展與推廣，智慧安防、智慧醫(yī)療及智能交通等應(yīng)用均采用了物聯(lián)網(wǎng)的技術(shù)框架與思路為用戶提供更加便捷化、人性化的服務(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的形式為旅客提供各類景點(diǎn)信息，實(shí)現(xiàn)用戶與園林的智能交互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為了

8、實(shí)現(xiàn)智能泊車入庫(kù)，提出一種基于車輛運(yùn)動(dòng)模型的自動(dòng)泊車路徑跟蹤算法。文獻(xiàn)12提出使用遺傳優(yōu)化算法來(lái)提升工業(yè)機(jī)器人路徑搜索的精度。文獻(xiàn)13中，為了保證冷鏈物流運(yùn)輸?shù)募皶r(shí)配送，通過(guò)分析車輛運(yùn)行成本、貨物變質(zhì)成本和冷藏成本來(lái)構(gòu)建車輛取貨配送優(yōu)化模型。文獻(xiàn)14將低碳經(jīng)濟(jì)的思路引入冷鏈物流路徑規(guī)劃問(wèn)題中，采用蟻群算法求解最優(yōu)運(yùn)輸路徑。然而，目前針對(duì)園林導(dǎo)覽路徑規(guī)劃的研究仍較少。為了提供個(gè)性化與智能化的路徑規(guī)劃流程，本文提出一種基于改進(jìn)魚群算法的園林路徑規(guī)劃算法。該算法通過(guò)構(gòu)建園林導(dǎo)覽二維模型來(lái)確定路徑規(guī)劃目標(biāo)，并基于人工魚群算法的迅速收斂與全局優(yōu)化能力求解該多目標(biāo)優(yōu)化問(wèn)題，實(shí)現(xiàn)了園林路徑的快速規(guī)劃。仿真與

9、實(shí)驗(yàn)結(jié)果表明，所提出的方法能夠有效解決園林路徑規(guī)劃問(wèn)題，相對(duì)于傳統(tǒng)算法具有更快的收斂速度。1 園林路徑規(guī)劃模型園林路徑規(guī)劃即根據(jù)用戶的當(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)間的路徑表示為直線段ST，則xOy坐標(biāo)系上的任意一點(diǎn)P（X，Y）可以表示為：xy=cos -sin sin cos -1?XY-xSyS （1）=arcsinyT-ySST （2）式中：為直線段ST與x軸間的距離;（x，y）為P（X，Y）映射后的

10、坐標(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）式中，兩條線段的端點(diǎn)由P2P1，Q2Q1表示。2） 防圓形碰撞。為了防止規(guī)劃處的路徑與圓形障礙物發(fā)生碰撞，本文設(shè)定的條件為：（y2-y1）x0-（x2-x1）y0+（y1x2-x1y2）（y2-y1）2+（x2-x1）2R （4）式中：x2x1，y2y

11、1為兩條線段端點(diǎn); （x0，y0）為圓形障礙物的圓心;R為半徑。2 基于改進(jìn)人工魚群算法的路徑規(guī)劃為了獲得距離更短、更平滑的目標(biāo)線路，本文結(jié)合權(quán)重系數(shù)法來(lái)定義園林導(dǎo)覽路徑。該目標(biāo)函數(shù)包括總長(zhǎng)度f(wàn)1（P）與平滑度f(wàn)2（P）目標(biāo)，具體表示如下：f（P）=w1f1（P）+w2f2（P） （5）式中，w1，w2為權(quán)重系數(shù)。文中使用魚群算法求解上述多目標(biāo)優(yōu)化問(wèn)題，其是一種源于仿生學(xué)的智能優(yōu)化算法。通過(guò)采用計(jì)算機(jī)程序來(lái)計(jì)算模擬魚群的覓食、聚群、追尾及隨機(jī)行為，從而求解目標(biāo)函數(shù)并得到其最優(yōu)解。然而，該算法在前期容易出現(xiàn)盲目搜索的問(wèn)題。本文為了提升算法的全局搜索能力，將和聲搜索算法引入其中。通過(guò)在迭代過(guò)程中產(chǎn)

12、生大量的局部最優(yōu)解，來(lái)提升魚群隨機(jī)行為的搜索效率。文中假設(shè)搜索空間中存在N條人工魚，并用X=（x1，x2，xD）表示人工魚的狀態(tài)信息，f（x）表示食物濃度，Y為式（5）所示的適應(yīng)度函數(shù)值，Xi-Xj為人工魚i與j間的距離。文中將和聲搜索微調(diào)后的人工魚狀態(tài)賦值給人工魚群，公式如下：X=（x1，x2，xD）=Xi=（xi1，xi2，xiD） （6）從人工魚Xi的視野Visual內(nèi)隨機(jī)抽取一個(gè)狀態(tài)Xj來(lái)更新Xi，公式如下：Xj=Xi+VisualRand（） （7）當(dāng)更新后的狀態(tài)Xi優(yōu)于Xj時(shí)，則向狀態(tài)Xj移動(dòng)一定步長(zhǎng)，公式如下：Xt+1i=Xti+Xi-XtiXi-XtistepRand（） （8

13、）當(dāng)狀態(tài)Xi不優(yōu)于Xj時(shí)，繼續(xù)更新Xj，直至達(dá)到最大覓食次數(shù)，公式如下：Xt+1i=xti+VisualRand（） （9）假設(shè)某人工魚所處的狀態(tài)為Xi，在其視野范圍dijYi時(shí)，該位置人工魚密度低于食物密度，則Xi根據(jù)式（10）向狀態(tài)XC前進(jìn)一步;否則，繼續(xù)進(jìn)行覓食。Xt+1i=Xti+XC-XtiXC-XtistepRand（） （10）對(duì)處于狀態(tài)Xi的人工魚，通過(guò)搜索其周圍的同伴數(shù)量nf，計(jì)算Xj的最大適應(yīng)度值Yj。當(dāng)YjnfYi時(shí)，該位置人工魚密度高于食物密度，則可根據(jù)式（11）向狀態(tài)Xj前進(jìn)一步;否則，繼續(xù)進(jìn)行覓食。Xt+1i=Xti+Xj-XtiXj-XtistepRand（） （11）基于上述步驟與尋優(yōu)操作，文中結(jié)合魚群密度與追尾行為形成人工魚庫(kù)，并通過(guò)尋優(yōu)操作生成新種群。然后使用和聲搜索算法進(jìn)行微調(diào)擾動(dòng)，及時(shí)跳出局部最優(yōu)解，從而得到全局最優(yōu)解。其中，和聲搜索的擾動(dòng)因子為j（t），