陽光學(xué)院基礎(chǔ)教研部 俞超群

針對粒子群算法在求解時容易早熟收斂，搜索得到最優(yōu)解的能力差，引入遺傳算法中的雜交思想，采用改進(jìn)后的粒子群算法，應(yīng)用對福州市10個景點(diǎn)的旅游線路的規(guī)劃，結(jié)合不同旅游價值取向的游客，將雜交粒子群算法應(yīng)用到含模糊價值評判的旅游線路的優(yōu)化研究中去。通過仿真實(shí)驗(yàn)，驗(yàn)證了該算法理論運(yùn)用于旅游線路能有效提高尋優(yōu)的效率，給游客及旅行社一個比較合理的意見和建議。

隨著社會經(jīng)濟(jì)的發(fā)展，近年來，周邊游逐漸成為福州人的旅游線路的首選，旅游線路的設(shè)計(jì)和優(yōu)化，是各個旅行社以及游客關(guān)注的問題所在，節(jié)約時間成本，優(yōu)化旅行距離，是旅行線路選擇的一個關(guān)注點(diǎn)?？紤]到游客的旅行價值偏好[1]，文獻(xiàn)[1]將模糊評價引入遺傳算法理論，建立基于遺傳算法的旅行線路優(yōu)化算法，設(shè)計(jì)出既滿足追求最少的路程時間消耗和又滿足游客最大的旅游價值的旅行線路。但遺傳算法編碼復(fù)雜，收斂速度慢，導(dǎo)致尋優(yōu)過程耗時較長。粒子群算法[2]（PSO）是對鳥類覓食行為這樣一個簡單的社會系統(tǒng)進(jìn)行模擬,通過迭代的形式進(jìn)行全局優(yōu)化的一種群體智能算法，目前已經(jīng)開始應(yīng)用于諸多領(lǐng)域[3-5]，其在優(yōu)化問題上的研究已經(jīng)逐漸被人們重視，但是如果優(yōu)化問題的搜索空間大，粒子群算法在求解時容易早熟收斂，不容易得到最優(yōu)解。雜交粒子群算法[6]由Angeline提出，將遺傳算法中雜交的概念引入到粒子群算法中，是對粒子群算法的一種改進(jìn)，把個體粒子的交叉、變異操作引入到粒子群的結(jié)構(gòu)當(dāng)中，該算法保留了粒子間的差異，同時其在收斂性和魯棒性都優(yōu)于標(biāo)準(zhǔn)粒子群算法。本文采用雜交粒子群算法，結(jié)合模糊評價理論[7]，建立基于雜交粒子群算法的旅游線路的優(yōu)化算法，充分發(fā)揮遺傳算法和粒子群算法的優(yōu)勢，以期選擇的線路既滿足實(shí)現(xiàn)最少的路程時間消耗，又能給予游客最大的旅游價值體驗(yàn)。

1 旅游線路優(yōu)化問題描述

旅游線路選擇問題是指具有一定價值偏好的游客從追求最小的路程時間消耗和滿足最大旅游價值感出發(fā)，在選定的一組景點(diǎn)中選擇合適的起點(diǎn)進(jìn)行遍歷。為了便于進(jìn)行比較，采集的景點(diǎn)坐標(biāo)和價值偏好均采用文獻(xiàn)[1]的數(shù)據(jù)，在百度地圖上選定10個景點(diǎn)，采集景區(qū)坐標(biāo)，針對景點(diǎn)的景觀屬性和游客的主觀感受構(gòu)造綜合評判矩陣，得到各個景點(diǎn)的模糊綜合評價[1]。每個景區(qū)的坐標(biāo)、對應(yīng)序號以及旅游價值如表1所示。

表1 10個景區(qū)位置的數(shù)字序號、位置和旅游價值Tab.1 Number, location and tourism value of 10 scenic spots

文獻(xiàn)[1]中單獨(dú)利用遺傳算法進(jìn)行求解可以實(shí)現(xiàn)旅游價值的優(yōu)化，但收斂速度慢，尋優(yōu)過程耗時較長。

2 粒子群算法和雜交粒子群算法簡介

粒子群優(yōu)化算法[2]是于1995年首次提出來的一種在全局范圍內(nèi)搜索最優(yōu)解的群體智能算法，根據(jù)目前廣泛使用的標(biāo)準(zhǔn)粒子群算法的流程，該算法的數(shù)學(xué)思想是：設(shè)m維空間中有popsiz個粒子，第i個粒子在時刻t的位置為

群體最優(yōu)位置（全局極值）為gbestt=[g1,g2,…,gm]T，

所有的粒子都通過追尋個體極值和全局極值在這個群體空間中飛行以找到最優(yōu)解。其速度和位置的更新的數(shù)學(xué)表達(dá)式如下所示：

其中，ω為慣性權(quán)重系數(shù)，c1，c2為學(xué)習(xí)因子。

算法通過maxiter次迭代得到最優(yōu)解，也就是將最大迭代次數(shù)作為算法的終止條件。

作為粒子群算法中最重要參數(shù)的慣性權(quán)重系數(shù)，其數(shù)值的大小決定了算法的全局和局部搜索能力的強(qiáng)弱，分別提出了自適應(yīng)權(quán)重法、隨機(jī)權(quán)重法、線性遞減權(quán)重法。戴文智,楊新樂于2015年提出了慣性權(quán)重對數(shù)遞減的粒子群優(yōu)化算法[8]。為了提高算法的收斂速度，王玉燕,李幫義,申亮將算法迭代公式中個體粒子的速度項(xiàng)去掉，保留位置更新公式，并將慣性權(quán)重系數(shù)放在位置矢量上，這樣算法迭代公式由二階降為一階微分方程，能有效提高算法收斂速度[9]。文獻(xiàn)[10]中，譚皓和王金巖等將粒子群算法和蟻群算法這兩種不同設(shè)計(jì)的雜交算子，通過模擬自然界中的物種在不同種群間的協(xié)作和交流，將雜交粒子選擇機(jī)制引入到粒子群結(jié)構(gòu)中，提高算法的尋優(yōu)能力，這也為粒子群算法改進(jìn)給予啟發(fā)。

傳統(tǒng)PSO算法容易出現(xiàn)粒子收斂于一個非最優(yōu)解后，無法跳出來導(dǎo)致搜索停止。為了解決這個問題，本文在進(jìn)行旅游線路尋優(yōu)，采取了基于雜交機(jī)制的粒子群算法[4]，該算法是借鑒遺傳算法中雜交的概念，選擇一定數(shù)量的粒子放入雜交池內(nèi)，將個體和最優(yōu)個體或個體和群體最優(yōu)的粒子進(jìn)行雜交，完成粒子間的信息交換，提高尋優(yōu)能力。子代位置由父代位置以一定的概率交叉得到c(x)=kp1(x)+(1-k)p2(x)，其中c(x)為子代個體的位置，p1(x),p2(x)父代個體的位置，k在[0,1]上服從均勻分布，子代個體的速度

其中p1(v),p2(v)父代個體的速度。

3 雜交PSO算法對于旅行線路優(yōu)化求解設(shè)計(jì)

雜交PSO算法對旅行線路優(yōu)化求解設(shè)計(jì)的算法流程如圖1所示，根據(jù)圖1中雜交PSO算法對旅行線路優(yōu)化求解設(shè)計(jì)的算法的流程圖所示，具體步驟如下：

圖1 雜交PSO算法對旅行線路優(yōu)化求解設(shè)計(jì)的算法流程Fig.1 The algorithm flow of the hybrid PSO algorithm for the optimal solution design of the travel route

(1)對粒子群進(jìn)行初始化，設(shè)置各個粒子的位置，群體規(guī)模和迭代次數(shù)。粒子的編碼采用整數(shù)編碼的形式，每個粒子表示遍歷的10個景區(qū)的路線，比如粒子編碼為[1,2,3,4,5,6,7,8,9,10],表示從西湖公園開始，三坊七巷，閩江公園南園，船政文化景區(qū)，中國鼓山風(fēng)景區(qū)，福州國家森林公園，于山風(fēng)景區(qū)，福州花海公園，飛鳳山奧體主體公園這樣的一條路線。

(3)將每個粒子的適應(yīng)度和個體極值進(jìn)行比較，更新個體極值pbesti。

(4)比較當(dāng)前所有的pbesti，更新gbest。

(5)將粒子和個體極值、群體極值進(jìn)行交叉，按一定的概率選擇兩個位置，然后把粒子和個體極值或者粒子和群體極值進(jìn)行交叉，產(chǎn)生新的個體粒子，如果新的個體粒子中存在重復(fù)位置，則將個體粒子中未包括的景區(qū)序號代替重復(fù)的景區(qū)序號。

(6)對自身進(jìn)行變異，隨機(jī)選擇個體粒子中的兩個位置，進(jìn)行互換，如果變異后的個體粒子優(yōu)于原來的粒子，才保留，否則放棄。

(7)判斷是否滿足算法終止條件，滿足則停止搜索，如果不滿足，則返回步驟（3）。

(8)輸出最終結(jié)果。

4 仿真結(jié)果

在程序中，種群規(guī)模我們?nèi)?0，總共進(jìn)行100次迭代。適應(yīng)度值變化情況如圖2所示，可以看出，雜交PSO算法具有較強(qiáng)的收斂能力，較快得到全局最優(yōu)解。

圖2 適應(yīng)度值變化Fig.2 Changes in fitness value

綜合考慮游客的價值偏好和最大效率的路線規(guī)劃，如圖3所示，游客可以選擇烏龍江濕地公園—于山風(fēng)景區(qū)—中國船政文化景區(qū)—福州國家森林公園—閩江公園南園—西湖公園—三坊七巷—鼓山風(fēng)景區(qū)—飛鳳山奧體公園—福州花海公園。

圖3 種群中10個景點(diǎn)的路線優(yōu)化方案Fig.3 Route optimization scheme for 10 scenic spots in the population

5 結(jié)論

在旅游線路選擇問題上，既要考慮優(yōu)化旅行距離和時間，使得效率最大，又要考慮游客的旅行價值偏好，在智能算法中遺傳算法編碼復(fù)雜，尋優(yōu)過程耗時長，在求解最優(yōu)解時，存在收斂速度慢，局部搜索能力差等缺點(diǎn)，本文提出了基于雜交機(jī)制的粒子群算法，并結(jié)合游客對于景點(diǎn)的模糊評價，設(shè)計(jì)出完善可行的旅游線路。經(jīng)過實(shí)驗(yàn)仿真，驗(yàn)證了該算法理論運(yùn)用于旅游線路能有效提高尋優(yōu)的效率，給游客及旅行社一個比較合理的意見和建議。但是，對于景點(diǎn)的評價方式，還是比較標(biāo)準(zhǔn)化，評價手段比較單一，在應(yīng)用中還要尋求更靈活的評價方式，以期能廣泛應(yīng)用于旅游線路的規(guī)劃和設(shè)計(jì)。

引用

[1] 俞超群.基于模糊綜合評判和遺傳算法的旅游線路的優(yōu)化[J].寧德師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2018,30(2):171-175+181.

[2] 楊明軒.粒子群算法的改進(jìn)及應(yīng)用研究[D].岳陽:湖南理工學(xué)院,2020.

[3] 張津源.基于改進(jìn)粒子群算法的物流路徑規(guī)劃研究[D].哈爾濱:哈爾濱師范大學(xué),2021.

[4] 邢曉溪.粒子群算法研究進(jìn)展[J].數(shù)據(jù)通信,2015(3):19-21+30.

[5] 趙先章,常紅星,曾雋芳,等.一種基于粒子群算法的移動機(jī)器人路徑規(guī)劃方法[J].計(jì)算機(jī)應(yīng)用研究,2007(3):181-183+186.

[6] 黃煒霖,劉建軍,張明,等.帶有退火和雜交變異思想的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(19):43-49.

[7] 徐永琳,王斐然.基于多因素模糊綜合評價的最優(yōu)旅游線路分析[J].湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版),2014(1):81-84.

[8] 戴文智,楊新樂.基于慣性權(quán)重對數(shù)遞減的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(17):14-19+52.

[9] 王玉燕,李幫義,申亮.TPT-CLSC的協(xié)調(diào)研究[J].中國管理科學(xué),2007(05):101-106.

[10] 譚皓,王金巖,何亦征,等.一種基于子群雜交機(jī)制的粒子群算法求解旅行商問題[J].系統(tǒng)工程,2005(04):83-87.