劉亞威，張雪萍，楊騰飛

（河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，河南 鄭州 450001）

最優(yōu)路徑分析是遙感和地理信息系統(tǒng)空間分析的重要技術(shù)之一，也是當(dāng)前計算機科學(xué)領(lǐng)域中具有較高研究價值的一類問題。最優(yōu)路徑分析[1]問題源于計算機幾何學(xué)的傳統(tǒng)研究課題，此類問題可以描述為已知起始點、目標點以及環(huán)境信息，確定一條從起始點到目標點的與障礙物無碰撞的線路。目前考慮實際障礙物的最優(yōu)路徑分析方法有：可視圖法、Dijkstra算法、A算法、柵格法、存在障礙物約束的最優(yōu)控制法等。其中基于柵格法的最優(yōu)路徑分析具有數(shù)據(jù)結(jié)構(gòu)簡單、無需建立復(fù)雜的拓撲關(guān)系和進行復(fù)雜的拓撲運算以及處理速度快等特點，已成為目前研究最廣泛的最優(yōu)路徑分析方法之一。

粒子群優(yōu)化算法[2-4]最早是由Kenney博士與Eberhart博士于1995年提出的，源于對鳥群覓食的行為研究的PSO同遺傳算法類似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)值函數(shù)來評價解的品質(zhì)。由于粒子群算法具有全局搜索能力不強，容易陷入局部最優(yōu)的缺點，而量子粒子群優(yōu)化[5]算法具有參數(shù)少，收斂速度快，魯棒性好，能夠較好地收斂于全局最優(yōu)點等優(yōu)點，能夠很容易解決經(jīng)典PSO算法中的不足，所以就用量子粒子群優(yōu)化算法來取代經(jīng)典的粒子群算法。

本文用柵格法建立環(huán)境模型，以量子粒子群優(yōu)化算法作為基本的演化算法，將量子粒子群優(yōu)化算法運用到柵格中，搜索出一條全局的最優(yōu)路徑，最后進行仿真實驗，證明取得了很好的效果。

1 柵格空間建模

本文使用柵格法進行空間建模。柵格法[6-7]是把自由空間劃分成一個由簡單單元所構(gòu)成的N×M的柵格陣，每一個單元就稱為一個柵格，并且空間環(huán)境中障礙物的位置和大小都不發(fā)生變化。單元的劃分可以是依賴于障礙物，也可以是獨立于障礙物。對于獨立于障礙物的單元分解，自由空間被劃分成一些有規(guī)則形狀的單元，同時測試每個單元是否屬于自由位姿空間。由于單元的形狀和位置獨立于障礙物的形狀和位置，所以這種方法并不一定能精確地表示障礙物。不過這種表示的誤差可以通過增加單元的數(shù)量，即提高劃分精度的辦法來解決。

假設(shè)該空間為一個二維平面上的凸多邊形有限區(qū)域，該區(qū)域內(nèi)分布著有限個大小不同的靜態(tài)障礙物，用尺寸相同的柵格對空間環(huán)境進行劃分，并在該區(qū)域內(nèi)建立直角坐標系。如果障礙區(qū)域為不規(guī)則形狀，可以將其補為規(guī)則的正方形或者長方形或者其他形狀，即讓每個障礙物占一個或多個柵格，若障礙物不滿一個柵格，則把此柵格補滿，使其按一個柵格計算。在該區(qū)域建立的坐標系中，每個柵格都有對應(yīng)的坐標和序列號，而且序列號和坐標一一對應(yīng)。坐標（xp，yp）與序列號p之間的映射關(guān)系可以由公式（1）確定：

其中：int為取整運算，mod為求余運算，m為每一行的柵格數(shù)。

柵格法把工作空間分割成規(guī)則而均勻的含二值信息的柵格，用0和1分別表示自由柵格和障礙柵格。若某一柵格內(nèi)不含任何障礙物，則稱其為自由柵格；反之，則稱其為障礙柵格。以20×20為例，劃分后的數(shù)據(jù)空間如圖1所示，其中圖中陰影區(qū)表示障礙柵格，柵格中的數(shù)字表示序列號。

圖1 直角坐標法建立的柵格Fig.1 Establishing grid by method of direct coordinate

我們的任務(wù)就是搜索一條由起點S到終點E的路徑長度最短的避障路徑。其目標函數(shù)可表示為：

其中：（xi，yi）為路徑點的坐標信息，np為路徑點的個數(shù)。

2 量子粒子群優(yōu)化最優(yōu)障礙路徑分析

在粒子群優(yōu)化算法中，粒子的運動狀態(tài)由位置和速度描述，隨著時間的演化，粒子的運動軌跡是既定的，同時粒子的速度受到一定限制，使得粒子的搜索空間是一個有限的區(qū)域，不能覆蓋整個可行空間，從而PSO算法不能保證全局收斂，這個結(jié)論已經(jīng)被Van de Bergh所證明。針對PSO算法的這個主要缺陷，根據(jù)粒子群的基本收斂性質(zhì)，受到量子物理基本理論的啟發(fā)，提出了量子行為粒子群優(yōu)化[8-11]（Quantumbehaved Particle Swarm Optimization，QPSO）算法。

QPSO的量子系統(tǒng)是態(tài)疊加原理作用的一個復(fù)雜的非線性系統(tǒng)，所以一個量子系統(tǒng)比一個線性系統(tǒng)能描述更多的狀態(tài)。量子系統(tǒng)與經(jīng)典隨機系統(tǒng)不同，是一個不確定性系統(tǒng)。在測量之前，由于沒有既定的軌道，粒子在這樣一個系統(tǒng)中會以一定的概率出現(xiàn)在任何位置。在傳統(tǒng)PSO算法中，粒子必須在束縛狀態(tài)以保證粒子群的聚集性，使PSO算法收斂到最優(yōu)解或次優(yōu)解。所以在傳統(tǒng)PSO算法中，束縛狀態(tài)限制了粒子在一個有限的區(qū)域中，而在QPSO優(yōu)化算法中，有概率密度函數(shù)描述的束縛狀態(tài)的一個粒子可以以一定的概率出現(xiàn)在整個可行搜索空間的任何位置，因此，其全局搜索性能遠遠好于一般PSO算法。

利用QPSO算法解決優(yōu)化問題的兩個重要步驟是：問題解的編碼和適應(yīng)度函數(shù)的選擇。

在QPSO系統(tǒng)中，每個粒子個體代表一條從起點到終點的路徑，如 xi=（xi1，xi2，…xiD），其中 D 表示粒子的維數(shù)大小，粒子的每一維都代表一個柵格序號，粒子的第一維表示起點柵格序號，最后一維表示終點柵格序號，將序號按照由小到大的順序連接起來可構(gòu)成一條路徑。例如，從起點柵格序號1到終點柵格序號400的一條路徑可以表示為：

1→21→147 →148→295→315→377→378→400

粒子編碼可以表示為：

xi=（1，21，147，295，315，377，378，400）

適應(yīng)值函數(shù)是量子粒子群算法中的一個很重要的因素，適當(dāng)?shù)倪x擇適應(yīng)值函數(shù)可以保證獲得最小距離。以路徑長度最短作為評價標準，選擇適應(yīng)值函數(shù)為：

其中：n表示路徑通過的柵格的數(shù)目，L為代表該路徑的個體中相鄰序號間直線距離之和，即式（1）。

量子行為粒子群優(yōu)化算法的主要計算步驟如下：

Step1：初始化，設(shè)定最大進化代數(shù)maxT，將當(dāng)前進化代數(shù)置t=1，在問題空間隨機產(chǎn)生 M個粒子x1，x2，…，xm組成初始種群 X（t）；

Step2：計算所有粒子的平均最好位置：

Step3：評價種群X（t），計算每個粒子在每一維空間的適應(yīng)值；

Step4：比較粒子的適應(yīng)值和自身最優(yōu)值pbest，如果當(dāng)前值比 pbest更優(yōu)，則置 pbest為當(dāng)前值，即 if f（xi）＜f（pi），then xi=pi；

Step5：比較粒子的適應(yīng)值和種群最優(yōu)值gbest，如果當(dāng)前值比gbest更優(yōu)，則置gbest為當(dāng)前粒子的適應(yīng)值，即：

Step6：計算學(xué)習(xí)傾向點pd，對粒子的每一維，在 pid和 pgd之間得到一個隨機點：

Step7：刷新位置：

Step8：檢查結(jié)束條件（通常設(shè)為足夠好的適應(yīng)值或達到一個預(yù)設(shè)最大迭代數(shù)），若滿足，則尋優(yōu)結(jié)束；否則轉(zhuǎn)至Step2。

在上述算法的公式（4）、（5）、（6）、（7）中：M 為種群中粒子的數(shù)目，D為粒子的維數(shù)，u和φ是在[0，1]上均勻分布的隨機數(shù)，mbest是種群中所有粒子的平均最好位置點。和標準PSO一樣，pid和pgd分別表示粒子所經(jīng)歷的最好位置和種群中所有粒子所經(jīng)歷的最好位置。β稱為收縮擴張系數(shù)，是QPSO優(yōu)化算法中惟一的參數(shù)，一般 β=（1-0.5）×（MaxT-T）/MaxT+0.5。

3 實驗結(jié)果及分析

為了驗證算法的正確性和可行性，對本文提出的算法進行了30次仿真實驗，其中量子粒子群優(yōu)化算法的參數(shù)設(shè)置如下：粒子個數(shù)M=30，最大迭代次數(shù)T=50，β從搜索開始的1.0線性遞減到搜索結(jié)束的0.5。以圖1所示環(huán)境為仿真實驗的工作空間，假定工作空間在20×20的柵格環(huán)境中進行，柵格序號1為最優(yōu)路徑分析的起點，柵格序號400為最優(yōu)路徑分析的終點，實驗結(jié)果如圖2所示。

圖2 QPSO算法計算機仿真結(jié)果Fig.2 The computer simulation result based on QPSO algorithm

圖2中所示曲線即為搜索到的工作空間中的全局最優(yōu)路徑，從起點柵格序號1到終點柵格序號400的路徑為：

1→22→62→167→168→210→211→316→336→399→400

粒子編碼可以表示為：

xi=（1，22，62，167，168，210，211，316，336，399，400）

在圖2所示環(huán)境下運行所得的平均最短路徑長度為30.1，平均運行時間為26.4 s。在文獻[12]中，用粒子群算法進行了30次仿真實驗，粒子群的參數(shù)分別為：粒子數(shù)目Np=30，最大迭代次數(shù)Mp=50，c1=c2=2，初始慣性權(quán)重w由0.9隨迭代次數(shù)線性遞減到0.4，最大速度VMax=10。仿真結(jié)果如下圖3所示。

在該仿真實驗中，粒子群算法的空間障礙距離分析算法能以很快的速度收斂，但得到的障礙路徑并不是全局最優(yōu)路徑，該方法不能有效的避免跨障礙問題。起始節(jié)點S點到目標節(jié)點E之間的路徑是無效的，計算得到的障礙距離也是不具有實際意義的。

圖2、圖3仿真結(jié)果表明，量子粒子群算法能夠解決粒子群算法中跨障礙的問題，并且能夠以比粒子群算法更快的速度收斂，得到障礙環(huán)境下的全局最優(yōu)路徑。從以上結(jié)論可知在靜態(tài)環(huán)境下，本文所提出的算法是有效且可行的。

圖3 PSO算法計算機仿真結(jié)果Fig.3 The computer simulation result based on PSO algorithm

4 結(jié) 論

本文針對障礙環(huán)境下空間最優(yōu)路徑分析問題，提出了一種基于量子粒子群優(yōu)化的空間最優(yōu)路徑分析方法。該方法以柵格法為空間環(huán)境建模，然后運用量子粒子群優(yōu)化算法在環(huán)境中搜索全局最優(yōu)路徑。最后仿真實驗證明該方法不僅可以找到最優(yōu)路徑，而且該方法具有建模容易，算法過程簡單，易于實現(xiàn)，收斂速度快，參數(shù)少，能夠較好地收斂于全局最優(yōu)點等優(yōu)點，完全可以用于空間全局最優(yōu)路徑分析問題，為帶障礙空間路徑分析問題的研究提出了一種新的思路。

[1]劉學(xué)鋒，孟令奎，李少華，等.基于柵格GIS的最優(yōu)路徑分析及其應(yīng)用[J].測繪通報，2004（6）:43-45.LIU Xue-feng， MENG Ling-kui， LI Shao-hua， et al.The optimal path analysis and it’s application based on grid GIS[J].Bulletin of Surveying and Mapping， 2004（6）:43-45.

[2]劉靜，須文波.粒子群優(yōu)化算法研究及其在優(yōu)化理論中的應(yīng)用[D].無錫：江南大學(xué)，2007.

[3]譚冠政，劉關(guān)俊.基于粒子群算法的移動機器人全局最優(yōu)路徑規(guī)劃[J].計算機應(yīng)用研究， 2007，24（11）:210-212.TAN Guan-zheng，LIU Guan-jun.The mobile robot global optimal path planning based on particle swarm optimization algorithm[J].Application Research of Computer， 2007，24（11）:210-212.

[4]Kennedy J，Eberhart R.Particle swarm optimization[C]//In：Proc of IEEE Int.Conf.on Neutral Networks， Perth，Australian，1995:1942-1948.

[5]高尚，楊靜宇.群智能算法及其應(yīng)用[M].北京:中國水利水電出版社，2006.

[6]高偉，張劍波.基于柵格數(shù)據(jù)模型的最優(yōu)路徑分析算法及實現(xiàn)[J].黑龍江工程學(xué)院報:自然科學(xué)版，2004，18（1）:22-24.GAOWei，ZHANG Jian-bo.Theoptimalpathanalysisalgorithm and implementation based on grid data model[J].Journal of Heilongjiang Institute of Technology:Natural Science，2004，18（1）:22-24.

[7]鄧高峰，張雪萍，劉彥萍.一種障礙環(huán)境下機器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用，2009，26（8）：879-883.DENG Gao-feng， ZHANG Xue-ping， LIU Yan-ping.Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J].Control Theory and Applications， 2009，26（8）：879-883.

[8]唐槐璐，須文波.基于量子行為微粒群優(yōu)化算法的數(shù)據(jù)聚類[D].無錫：江南大學(xué)，2008.

[9]Sun J， Feng B， Xu W B.Particle swam optimization with particles having quantum behavior[C]//IEEE Congress on Evolutionary Computation，2004：325-331.

[10]Sun J， Xu W B， Feng B.A global search strategy of quantum-behaved particle swam optimization [C]//IEEE Conference on Cybernetics and Intelligent Systems，2004：111-116.

[11]Sun J， Lai C H， XU Wen-bo.Quantum-behaved particle swarm optimization and its application [J].Journal of Computer and Mathematics with Applications，U.K.2005（49）：1669-1678.

[12]鄧高峰，張雪萍.基于粒子群優(yōu)化的帶障礙約束空間聚類分析研究[D].鄭州：河南工業(yè)大學(xué)，2008.