基于粒子群算法的拉薩市最短旅游路線規(guī)劃

胡冉 西藏大學 工學院

1.引言

拉薩市的旅游業(yè)發(fā)展雖一直穩(wěn)中求進，但由于拉薩市地理位置的特殊，導致了拉薩市產(chǎn)業(yè)結(jié)構(gòu)單一的現(xiàn)象，目前旅游業(yè)所帶來的經(jīng)濟收入難以滿足城市經(jīng)濟的發(fā)展要求。受到地形地質(zhì)等自然條件的影響，現(xiàn)階段想通過改變交通運輸方式來提高拉薩市的整體旅游效率和收入仍存在著較大的技術(shù)空缺，因此縮短旅游路線，為旅客提供高效旅游服務(wù)是解決當務(wù)之急的有效方法。

粒子群算法是近年來較為科學有效的全局尋優(yōu)算法，它模擬鳥群飛行覓食的行為，通過鳥之間的集體協(xié)作使群體達到最優(yōu)。盡管每個個體的行為準則是很簡單的，但組合成整個群體的行為將會是非常復雜的。此算法是在解空間中利用種群迭代的方法對最優(yōu)粒子進行搜索。它具有模型簡單且易實現(xiàn)的優(yōu)點，目前在科學研究以及工程應(yīng)用都發(fā)揮了一定的作用。

2.模型簡介

2.1 旅行商問題

旅行商問題，即TSP問題是數(shù)學領(lǐng)域中著名問題之一。即要求商人在每個城市只能拜訪一次的前提下走完所有選定的城市并返回出發(fā)點通過旅行商問題的啟發(fā)，本文利用基于交叉變異的混合粒子群算法，尋找出各旅游景點的之間的最短路徑。

2.2 粒子群優(yōu)化算法

其中：K是迭代次數(shù)，r1和r2為之間的隨機數(shù)，用來保持群體的多樣性。c1和c2為學習因子，也稱為加速因子，其使粒子具有自我總結(jié)和向群體中最優(yōu)秀個體學習的能力，從而向自己的歷史最優(yōu)點以及群體內(nèi)歷史最優(yōu)點靠近。

2.3 模型求解

PSO算法是依靠群體之間的相互合作和競爭在問題空間中搜索最優(yōu)值，本文為了彌補粒子自身缺乏選擇、交叉和變異的特性，在基本粒子群算法中引入了交叉和變異的機制，既加快了算法的收斂速度，又保證了粒子群的尋優(yōu)精度。

本文通過對拉薩市四個著名景點做出了景點之間的分布圖1。

圖1 景點分布圖

為了更直觀的展現(xiàn)各景點之間的距離，本文將路徑均以直線代替且取整。其中①代表羅布林卡；②代表布達拉宮；③代表小昭寺；④代表大昭寺。

2.4.1 仿真參數(shù)設(shè)置

種群數(shù)量N=1000，迭代次數(shù)k=50。表1為各景點的具體坐標。

表1 景點坐標圖

2.4.2 仿真結(jié)果與分析

在MATLAB2018b版本中的運行結(jié)果如下圖2所示。通過交叉變異的混合粒子群算法，可較為精確的確定各個景點之間路徑最短的旅行方式，以①號羅布林卡為起點，可先選擇②號布達拉宮游玩，再經(jīng)過③號小昭寺，最后選擇大昭寺回到起點布達拉宮。由于旅行路線為無向圖，因此還可以選擇反方向的旅游路線。

圖2 最短旅行路線

3.結(jié)論

本文利用基于交叉變異的混合粒子群算法本文粗略地介紹了基于交叉變異的混合粒子群算法在PSO問題上的簡單應(yīng)用，并能有效解決拉薩市旅游規(guī)劃上帶來效率低下等問題。但由于本文景點個數(shù)較少，因此難以體現(xiàn)此算法在收斂速度上的優(yōu)勢。但此算法在生活和工業(yè)應(yīng)用中具有極大的探究潛能，可延申至有向圖等非對稱問題上的研究。將本算法應(yīng)用至西藏自治區(qū)中將有更大的實踐價值和意義，西藏自治區(qū)地域廣袤、旅游景點眾多，距離因素是影響當?shù)芈糜螛I(yè)發(fā)展的主要因素，可利用此算法有效地將旅游資源整合，更好地推動西藏自治區(qū)旅游業(yè)的發(fā)展。