迷宮問題的路徑優化

摘要:迷宮問題是圖形學、圖論和數據結構等領域中的一個經典問題。目前解決迷宮問題的算法主要包括傳統算法以及智能算法兩大類。如何更好的解決迷宮問題獲得最優路徑一直是有待解決的問題。首先基于蟻群算法獲得導航路徑，然后利用粒子群算法優化導航路徑獲得近似最優化路徑。實驗仿真表明，利用粒子群算法優化后的路徑效果十分令人滿意。

關鍵詞:迷宮問題;路徑;粒子群算法

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)32-9045-02

Path Optimization of Maze Problem

XU Shou-jiang

(Jiangsu Food Science College， Huai'an 223003， China)

Abstract: The maze is a classic problem in the area of graphics， data structures and graph theory. At present the algorithm to solve maze problem include the traditional algorithms and intelligent algorithms two categories. How to better solve the problem of access to optimal path of maze problem is an outstanding issue. First of all a navigation path is obtained using any general algorithm， and then a more optimization path based on the navigation path is gotten using particle swarm algorithm. Simulation shows that the path optimized by particle swarm algorithm is very satisfying.

Key words: maze problem; path; particle swarm algorithm

迷宮問題是圖形學、圖論和數據結構等領域中廣為人知的一個經典問題。戰略決策、機器人路徑規劃等許多智能問題都可以轉化為尋找迷宮最優路徑問題[1-3] 。迷宮最優路徑是指從迷宮的入口到達迷宮出口的最短通路。傳統解迷宮路徑問題的算法大多采用廣度優先搜索或深度優先搜索[4]。隨著迷宮規模的增大和復雜性的增加，傳統搜索算法的空間和時間復雜性呈指數增加，且求解最優路徑是通過全部路徑求出后進行比較得到的，這些算法非常費時。隨后出現了基于八方向跟蹤算法的、利用人工智能算法的搜索原理等方法[5-6]解決迷宮問題，這些方法搜索效率較低。隨著近幾年智能算法研究的深入，涌現了不少求解迷宮最優路徑問題的仿生智能算法如遺傳算法[7]、蟻群算法[8-9]等。仿生智能算法通過并行程序設計來解決大規模事例，但其結果大多只是近似最優解，解的收斂性是需要重點解決的問題。

迷宮問題目前研究主要在離散空間下基于柵格環境利用某種算法求得最優路徑(導航路徑)，所求得的路徑并非實際問題中的真正最優路徑。本文基于粒子群算法對蟻群算法獲得的導航路徑進行優化，從而獲得連續空間中的近似最優化路徑。

1 迷宮算法

1.1 迷宮問題描述

圖1為長m(此處m=10)，寬n(此處n=10)的方形區域。在其上任意一點P(i，j)(0≤i≤m-1;0≤j≤n-1)上涂有黑色或白色，其中黑色表示人可以經過，白色表示不能經過，且對位于P(i，j)點的行人，每次只能向其周圍的白色柵格移動一步。則迷宮最優路徑問題即為:從方形區域上的某一點P(is，js)出發，沿可行路徑到達某一終點P(it，jt )，使其經過的路徑長度最短。

1.2 蟻群算法獲得導航路徑

根據蟻群覓食過程中能夠發現蟻巢和食物源之間最短路徑的啟發，意大利學者Colorni A 和Dorigo M 等人提出了一種新型的智能優化算法——蟻群算法，這種算法對旅行商問題(TSP)的求解結果顯示，其具有較強的魯棒性和發現較好解的能力。

像螞蟻這類社會性動物。雖然個體的行為極其簡單，但由這些個體組成的蟻群卻表現出極其復雜的行為特征，能完成復雜的任務;不僅如此，螞蟻還能適應環境的變化，如在蟻群運動路線上突然出現障礙物時，螞蟻能夠很快地重新找到最優路徑。蟻群是如何完成這些復雜任務的呢?人們經過大量研究發現，螞蟻個體之間是通過一種稱之為外激素(pheromone)的物質進行信息傳遞，從而能相互協作，完成復雜的任務。螞蟻在運動過程中，能夠在它所經過的路徑上留下這種物質，而且能夠感知這種物質的存在及其強度，并以此指導自己的運動方向。螞蟻傾向于朝著該物質強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象:某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。蟻群正是通過這種信息的交流最終找到食物源與蟻巢之間的最短路徑。

蟻群算法應用于解決迷宮問題，步驟大致如下:

Step 1:數據初始化:初始化迷宮矩陣，算法最大迭代次數計數器lt，不能改善優化解的最大迭代次數計數器vt ，設定螞蟻數量2m ，正、反向螞蟻各m只，設定常系數。

Step 2:m只螞蟻以信息素為依據按概率分布于距離迷宮的入口路徑長度為k的位置上，另m只螞蟻以信息素為依據概率分布于距離迷宮的出口路徑長度為k的位置上。

Step 3:蟻群按移動規則前行，同時更新迷宮矩陣的路徑信息，直到所有螞蟻停止活動。

Step 4:查找本次移動搜索到的最優路徑，更新最優路徑上信息素。

Step 5:計數。

Step 6:如果lt， vt均不超過設定初值，轉Step2，否則下一步。

Step 7:輸出最優路徑長度和最優路徑。

Step 8:算法結束。

2 迷宮問題的路徑優化

2.1 優化思想與步驟

上述算法得到的迷宮路徑基于柵格模型獲得的路徑并非真正意義上的最優路徑。為了解決此缺陷本文算法首先用一般常用迷宮算法找到一條無碰較優導航路徑，得到初始的路徑點;再用粒子群算法調整每一個初始路徑與柵格邊界的交點，每一個粒子的每一維代表一個交點，每個粒子從低維到高維的逐一連線就構成了新的路徑，通過若干次迭代從而得到全局近似最優路徑。調節過程如圖2所示。讓導航路徑上的每一個與柵格邊界相交的xd 點在xdmin、xdmax兩點間的線段上滑動，用粒子群算法來搜索最佳xd，使得尋找的路徑最短。xd只在無障礙的豎直方向滑動，保證了xd在線段xdmin、xdmax上滑動時形成的新路徑上點與點之間是相通的從后最終優化出的路徑不會與障礙物相交。對每個路徑點都這樣調節后， 這些新的路徑點就組成了一條新的移動路徑。

根據以上思想，優化步驟描述如下:

Step1: 計算出導航路徑與豎直方向柵格邊界的交點的個數Pnum，即每個粒子有Pnum維，并計算出粒子第d維的滑動范圍[xdmin，xdmax]。

Step2: 初始化粒子數Pn，在允許的范圍內隨機初始化粒子c的位置xc(0)和速度vc(0)，把粒子c的初始化位置視為其初始最優位置pc，設定ωmax、ωmin、c1、c2和最大迭代次數pmax，并令n=0。

Step3:依據式(1)計算每個粒子c的適應度Fc，適應度最小的粒子位置記為Pg。

(1)

其中S為入口點，G為出口點。

Step4: 依據式(2)更新粒子c的各維速度，依據式(3)更新粒子c的位置。其中r1，r2是[0，1]之間的隨機數，若 vc，d<-vdmax則令vc，d=-vdmax;若vc，d>-vdmax則令vc，d=vdmax;若xc，dxdmax，則令xc，d>xdmax。

(2)

(3)

Step5:依據(1)式計算每個粒子的適應度Fc(x(t+1))，更新pc、pg。n自動增1，ω=ωmax-(ωmax-ωmin)×n/pmax。

Step6:若n< pmax則轉Step11，否則繼續。

Step7:輸出最優路徑。

3.2仿真實驗

為了體現該算法的有效性及其特點，作者對分別在10維、20維環境下進行了大量測試，效果都十分令人滿意。

圖3、4分別給出了10維、20維環境下的一個特例。其中紅色細線是蟻群算法獲得的優化導航路徑。黑色粗線給出用微粒群思想優化導航路徑后得到的更優路徑。從圖3、4可以很明顯看出經過微粒群優化后的路徑比蟻群算法獲得的導航路徑要優化的多。

3 結論

本文采用柵格法對環境進行建模，使算法簡單容易實現。在此基礎上，用螞蟻算法快速全局搜索出一條導航路徑，然后對該路徑上的點用微粒群思想進行調節，得到近似最優路徑。微粒群算法具有簡單，容易實現、耗時短等特點，比遺傳算法、魚群算法等在優化導航路徑上更有優勢。仿真實驗表明本文利用微粒群算法優化后的迷宮路徑比一般算法獲得的路徑獲得得路徑要優化的多，可以有效地解決迷宮問題柵格建模的缺陷，快速搜索出一條近似最優化路徑。

參考文獻:

[I] 盧開澄.圖論及其應用[M].北京:清華大學出版社，1980.

[2] 戴一奇.圖論及其應用[M].北京:水利電力出版社，1988.

[3] Bondy J A， Murty U S R.Graph Theory With Applications[M].London:Macmillan Press，1976.

[4] 嚴蔚敏，陳文博.數據結構及應用算法教程[M].北京:清華大學出版社，2001.

[5] 孫東秋.基于八方向跟蹤算法的迷宮問題新解[J].計算機應用于研究，2005，22(8):103-105.

[6] 陳春梅，楊世恩.用人工智能中的搜索原理解決迷宮問題[J].微計算機信息.2004，22(4-2):267-269.

[7] 王斌，李元香.用遺傳算法解迷宮問題[J].微型機與應用，2002(10):58-60.

[8] 胡曉兵，黃席樾.蟻群算法在迷宮最優路徑問題中的應用[J].計算機仿真，2005，22(4):114-116.

[9] 張公敬，徐熙君.蟻群算法求解迷宮問題[J].青島大學學報:自然科學版，2008，22(1):61-65.