基于量子粒子群優化的最優障礙路徑分析

劉亞威，張雪萍，楊騰飛

（河南工業大學 信息科學與工程學院，河南 鄭州 450001）

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

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

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

1 柵格空間建模

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

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

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

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

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

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

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

2 量子粒子群優化最優障礙路徑分析

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

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

利用QPSO算法解決優化問題的兩個重要步驟是：問題解的編碼和適應度函數的選擇。

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

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

粒子編碼可以表示為：

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

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

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

量子行為粒子群優化算法的主要計算步驟如下：

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

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

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

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

Step5：比較粒子的適應值和種群最優值gbest，如果當前值比gbest更優，則置gbest為當前粒子的適應值，即：

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

Step7：刷新位置：

Step8：檢查結束條件（通常設為足夠好的適應值或達到一個預設最大迭代數），若滿足，則尋優結束；否則轉至Step2。

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

3 實驗結果及分析

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

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

圖2中所示曲線即為搜索到的工作空間中的全局最優路徑，從起點柵格序號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所示環境下運行所得的平均最短路徑長度為30.1，平均運行時間為26.4 s。在文獻[12]中，用粒子群算法進行了30次仿真實驗，粒子群的參數分別為：粒子數目Np=30，最大迭代次數Mp=50，c1=c2=2，初始慣性權重w由0.9隨迭代次數線性遞減到0.4，最大速度VMax=10。仿真結果如下圖3所示。

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

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

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

4 結 論

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

[1]劉學鋒，孟令奎，李少華，等.基于柵格GIS的最優路徑分析及其應用[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]劉靜，須文波.粒子群優化算法研究及其在優化理論中的應用[D].無錫：江南大學，2007.

[3]譚冠政，劉關俊.基于粒子群算法的移動機器人全局最優路徑規劃[J].計算機應用研究， 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]高尚，楊靜宇.群智能算法及其應用[M].北京:中國水利水電出版社，2006.

[6]高偉，張劍波.基于柵格數據模型的最優路徑分析算法及實現[J].黑龍江工程學院報:自然科學版，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]鄧高峰，張雪萍，劉彥萍.一種障礙環境下機器人路徑規劃的蟻群粒子群算法[J].控制理論與應用，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]唐槐璐，須文波.基于量子行為微粒群優化算法的數據聚類[D].無錫：江南大學，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]鄧高峰，張雪萍.基于粒子群優化的帶障礙約束空間聚類分析研究[D].鄭州：河南工業大學，2008.