規(guī)劃高速公路路線的變異蟻群算法

尚艷艷，李應，董晨

(福州大學數(shù)學與計算機科學學院網(wǎng)絡系統(tǒng)信息安全福建省高校重點實驗室，福建福州 350116)

1 路徑規(guī)劃問題

路徑規(guī)劃是指在數(shù)據(jù)或物理網(wǎng)絡中選擇路徑的過程.機器人路徑規(guī)劃［1－4］和物流配送路徑優(yōu)化［5－6］是常見的路徑規(guī)劃的問題，也是采用蟻群算法研究的兩個熱點.蟻群算法是信息正反饋原理和啟發(fā)式算法的有機結(jié)合，在求解組合優(yōu)化等問題方面具有其它群智能算法所不具有的優(yōu)點［7］.正反饋原理雖然可以強化較優(yōu)的解，卻容易陷入停滯現(xiàn)象，所以在采用蟻群算法規(guī)劃路徑時往往對蟻群算法做一些改進.規(guī)劃高速公路修建路線和機器人尋徑相同的是給出起點和終點，搜索一條最優(yōu)路徑.但不同的是，機器人遇到障礙物時選擇繞開［1－4］，而修建高速公路時可以通過架設高架橋、開鑿隧道等手段通過河流、高山等障礙物.

1.1 地理信息表示

修建高速公路的區(qū)域可能有高山、山谷、河流和城鎮(zhèn)等地理情況，為了更好地研究路徑規(guī)劃問題，需要較準確地表示該路徑規(guī)劃區(qū)域的地理信息.

地圖和路徑有坐標、網(wǎng)格和位圖三種地圖表示方法.坐標地圖最貼近實際，但其坐標值是浮點數(shù)，螞蟻的行動方向沒有限制，導致對路徑的保存、操作、計算和表示有一定的困難;網(wǎng)格地圖對實際地圖進行了一定程度的抽象，坐標值是整型，螞蟻的行動限制在上、下、左、右四個方向上，使得路徑的保存、操作和計算方便簡單，網(wǎng)格表示路徑直觀易懂，但是對于障礙物，特別是障礙物范圍的表示不夠明確清晰，這對判斷螞蟻是否遇到障礙物造成了較大的困難;位圖地圖類似于網(wǎng)格地圖，坐標值也是整型，螞蟻的行動也有四個方向上的限制，但是位圖能明確表示障礙物及其范圍，而且位圖的每個像素相互獨立.基于以上三種地圖的特點，本研究選擇位圖地圖來表示區(qū)域地圖上的地理信息和路徑.

雖然位圖地圖只是實際地圖的抽象，但在實際應用中，只要像素細化到一定程度，就可以無限近似于實際地圖.對位圖地圖上像素點的屬性進行設置:

1)坐標.用于定位.

2)類型.0表示可行地區(qū)，1表示高山或者山脈，2表示山谷，3表示河流，4表示城鎮(zhèn).

3)權值.類型為0、1、2、3的像素點權值設為0.類型為4的城鎮(zhèn)像素點權值取值為1～10之間的一個整數(shù)值，權值越高表示城鎮(zhèn)越發(fā)達越重要.在遇到城鎮(zhèn)時由權值的大小來判斷是繞開城鎮(zhèn)、架設高架橋通過城鎮(zhèn)還是進行征地直接修建高速公路.

4)信息素值.保存每個像素點上的信息素值.該值會隨著經(jīng)過的螞蟻和時間的變化而變化.終點的像素值被賦予一個極大值，不會改變.

5)經(jīng)過標志.為每只螞蟻設置像素點經(jīng)過標志.0表示某只螞蟻未走過該像素點，1表示螞蟻已走過該像素點.為實現(xiàn)螞蟻行走路線不形成回路，任意螞蟻下一步只能選擇標志為0的像素點.

對于以上地圖像素點的屬性，除了信息素濃度和經(jīng)過標志在系統(tǒng)運行時會發(fā)生改變之外，其他屬性初始化之后一般不會再改變.

1.2 建立數(shù)學模型

修建高速公路的造價可轉(zhuǎn)換為修建高速公路所需的時間.假定普通情況下修建每公里需要時間為t1，架設高架橋、開鑿隧道、征用居民用地等的造價分別轉(zhuǎn)換為普通情況下造價的X、Y、Z倍，相應的修建時間可轉(zhuǎn)化為普通情況修建時間的X、Y、Z倍.假設建設一條高速公路的總長度為L，其中普通路段長度為L1、高架橋路段長度為L2、開鑿隧道路段長度為L3、征用居民用地路段長度為L4，則修建這條高速公路需要的時間為:

因此，修建造價最小的高速公路轉(zhuǎn)化為式(1)取得最小值.

在位圖地圖上，螞蟻從當前位置出發(fā)可以有上、下、左、右4個行進方向，到達相鄰像素點需要一步.假設從起點到終點的規(guī)劃路徑上依次經(jīng)過位圖上的m個像素點，xi，i+1為從i點到i+1點的行進距離，位圖方式下設為一個距離單位，i=1，2，…，m－1.從i像素點到i+1像素點的行進時間為ci，i+1，普通路段行進時間需要一個時間單位，修建高架橋、開鑿隧道、征用居民用地路段的行進時間設為普通路段的相應倍數(shù).設螞蟻從起點到終點的行進時間為w，則數(shù)學模型為:

約束條件:

xij=0表示螞蟻沒有走i和j之間的路徑，xij=1表示螞蟻走了i和j之間的路徑.在位圖方式下，螞蟻只能走相鄰的像素點.式(3)表示只從i點走出來一次;式(4)表示只走入j點1次;式(5)表示在任意點之間不形成回路.

1.3 遇到障礙物的處理

螞蟻從像素點i行走到達像素點i+1，如果像素點i+1的類型值為1或者2或者3，表示螞蟻遇到了高山或者山谷或者河流，則該螞蟻有一定的較小概率ζ因為遇到障礙物走入死角死亡，借鑒蟻群算法引入偵查子群［8］和生物可變異的思想，讓螞蟻以1－ζ的概率變異成一種特殊螞蟻，可通過相應的方法(架設高架橋或者開鑿隧道)穿過障礙物.

如果像素點i+1的類型值為4，表示螞蟻遇到了城鎮(zhèn).此時判斷像素點i+1的權值，如果權值大于等于5，表示遇到的是主要城市，不適合架設高架橋，螞蟻就因為遇到障礙物走入死角死亡;如果權值小于2，表示是偏遠小村落，可以進行征地直接修建高速公路;如果權值小于5并且大于等于2，表示可以對這個城市架設高架橋，則螞蟻有一定的較小概率ζ因為遇到障礙物走入死角死亡，以1－ζ的概率變異成特殊螞蟻，能通過架設高架橋穿過該城鎮(zhèn).對于這些能夠通過障礙物的特殊螞蟻，螞蟻的行進時間為:

2 算法

2.1 設置每只螞蟻屬性

1)螞蟻的坐標.用于表示每只螞蟻的當前位置.初始化為起點坐標.

2)螞蟻的生存時間.用于保存每只螞蟻從起點出發(fā)行進到當前位置花費的時間，當超過最大值T時表示螞蟻死亡.初始化為0.到達終點且生存時間最小即為最優(yōu)解.

3)螞蟻的障礙物標志.用來記錄螞蟻遇到的障礙物的長度.與障礙物類型有關，并且遇到的障礙物越長，延時越長.初始化為0.

4)螞蟻到達終點標志.用來標記每只螞蟻是否到達終點.初始化為0，到達終點為1.

5)路徑.用于保存每只螞蟻走過的路徑.

2.2 更新信息素

在基本蟻群算法中，每只螞蟻都可以到達終點并在它經(jīng)過的路徑上留下信息素.在本文中，螞蟻在尋徑過程中會由于超時或遇到障礙物而死亡，因此，可把能夠到達終點并且沒有超時的螞蟻看做精英螞蟻，只有精英螞蟻k到達終點后才按照式(7)更新其經(jīng)過路徑上的信息素:

其中:timek表示精英螞蟻k搜尋路徑的時間;ρ為局部信息素揮發(fā)系數(shù)，ρ值越大表示信息素的影響越小.

為進一步增強最優(yōu)螞蟻的作用，迭代一次后，按照式(9)更新目前搜索到的最優(yōu)路徑上的信息素，加強蟻群算法的正反饋作用［9］.

其中:besttime表示當前最短搜尋路徑時間;γ是全局信息素揮發(fā)系數(shù)，γ值越大表示信息素的影響越小.

如果一次迭代中有多只螞蟻搜尋到了最優(yōu)路徑，那么這幾條最優(yōu)路徑都按式(9)進行信息素更新.

2.3 設置延時系數(shù)

在改進的蟻群算法中，需將架設高架橋、開鑿隧道和征用土地等轉(zhuǎn)換為修建普通路段時間的相應倍數(shù)，設置相應的延時系數(shù).這三個系數(shù)與螞蟻穿過障礙物的長度直接影響螞蟻對最優(yōu)路徑的選取，因此它們的取值非常重要.

一般障礙物分為狹長形和寬廣型.實際障礙物在位圖中抽象成規(guī)則形狀，如圖1中的陰影部分所示，但障礙物的范圍和走向不同.圖1中的“⊕”字符表示起點和終點，實線箭頭表示螞蟻繞障礙物行走路線，虛線箭頭表示螞蟻穿過障礙物行走路線(參照實際穿過障礙物時一般采用直線路線).

圖1 障礙物和起點、終點走向關系圖Fig.1 Diagrams of obstacles and start，and point

表1 穿過和繞開障礙物步數(shù)對比表Tab.1 Comparison of passing or bypassing obstacles

圖1四種情況下螞蟻穿過障礙物和繞開障礙物步數(shù)對比如表1所示.從表1可以看出，隨著障礙物和起點、終點走向由平行變?yōu)榇怪?，螞蟻穿過障礙物需要行走步數(shù)不變，但是繞開障礙物需要行走的步數(shù)在不斷增加.在二者走向是平行時，繞開與穿過步數(shù)比值小于2;而二者走向是垂直時，繞開與穿過步數(shù)比值大于2，小于3.如果圖1(d)中障礙物沿走向再繼續(xù)延長，螞蟻繞開障礙物需要行走更多步，繞開與穿過障礙物的步數(shù)比值將會更大.因此延時系數(shù)的范圍可選擇在2～3之間.

結(jié)合在實際工程中，開鑿隧道工程難度最高、花費也最大，架設高架橋最常用且工程難度中等，征用土地工程難度較小，因此開鑿隧道延時系數(shù)relaytime1最大，架設高架橋延時系數(shù)relaytime2次之，征用土地延時系數(shù)relaytime3最小.程序選擇relaytime1=2.8、relaytime2=2.6、relaytime3=2.2這一組數(shù)據(jù)做了測試，測試結(jié)果說明，這樣的系數(shù)設置較合適.

2.4 定義每只螞蟻的行動規(guī)則

螞蟻在前進時會受到信息素的吸引，根據(jù)信息素濃度決定轉(zhuǎn)移方向.在位圖方式下，每只螞蟻只有上、下、左、右4個方向可走.螞蟻k在t時刻從i像素點出發(fā)選擇j像素點的轉(zhuǎn)移概率如式(11)所示.

其中:allowedk表示螞蟻k可選擇方向的集合;α是信息素啟發(fā)因子，表示信息素濃度在螞蟻選擇路徑中作用的大小.

為增加探索新路徑的機會，螞蟻有一定的概率隨機選擇前進方向.定義螞蟻的行動規(guī)則如下:

①判斷螞蟻是否能走下一步.對于生存時間小于最大值T且沒有到達終點的螞蟻，進行步驟②;否則這只螞蟻已經(jīng)死亡.

②螞蟻選擇下一步的坐標.如果一只螞蟻當前處在起點處，則比較起點坐標和終點坐標，讓螞蟻有較大概率走某個方向;否則排除螞蟻上、下、左、右已經(jīng)走過的方向，螞蟻有一定的概率不被信息素的濃度吸引，而是隨機選擇向可走的方向走一步，螞蟻進入步驟④;或者螞蟻被信息素濃度吸引，螞蟻進入步驟③.

③按式(11)計算可走方向的轉(zhuǎn)移概率，選擇轉(zhuǎn)移概率最大的方向.

④判斷步驟②或步驟③計算的螞蟻的下一步坐標:

如果坐標為終點坐標，表示這一只螞蟻完成了尋徑過程，更新該螞蟻當前坐標，記錄螞蟻行進方向，計算生存時間，到達終點的標志記為1.

如果坐標對應的像素點類型為0，表示下一步螞蟻沒有遇到障礙物，則更新螞蟻的當前坐標，記錄螞蟻行進方向，該像素點的經(jīng)過標志置1，計算其生存時間;否則螞蟻遇到了障礙物，按遇到障礙物處理，如果螞蟻可通過障礙物變?yōu)樘厥馕浵仯系K物長度+1，更新其坐標，記錄螞蟻行進方向，該像素點的經(jīng)過標志置1，為其計算生存時間.

⑤重復上述步驟①直至螞蟻死亡或到達終點.

2.5 保存螞蟻行進路徑

考慮到螞蟻的行進方向只有上、下、左、右4種可能，上、下、左、右4個方向分別用1、2、3、4數(shù)值表示，所以在保存螞蟻的路徑時，只保存1～4之間的某一個整數(shù)值來表示螞蟻每一步行進的方向，而未保存每一步的坐標.只有當一只螞蟻到達終點后的生存時間最短時再將其路徑轉(zhuǎn)換成坐標值.這樣路徑保存的數(shù)據(jù)量減少了一半.

2.6 算法偽代碼

1)read要修建高速公路的起點坐標、終點坐標;

2)初始化地圖信息;

3)位圖上所有像素點的經(jīng)過標識初始化為0;

4)初始化迭代次數(shù)N，每代螞蟻數(shù)量m;

5)set最小尋經(jīng)時間besttime=T;

9)計算最小搜尋時間besttime對應的最優(yōu)路徑，保存路徑;

10)輸出最優(yōu)路徑.

3 實驗

3.1 初始化區(qū)域地圖

初始化一個如圖2所示的位圖地圖，圖中的“－”字符表示平地，“1”字符部分表示山谷，“～”字符部分表示河流，“#”字符部分表示高山或者山脈，“4”字符部分表示城鎮(zhèn).地圖橫坐標為［0，99］，縱坐標為［0，99］，坐標原點在左上角.

3.2 搜尋最優(yōu)路徑

在實驗中，螞蟻的迭代次數(shù)和種群數(shù)均設定為100.以地圖中的起點坐標［43，17］和終點坐標［72，85］為例，測試變異蟻群算法的α、ρ、γ 3個參數(shù).實驗中為每一個參數(shù)設定一組值，ρ∈{0.1，0.2，0.3，0.5，0.7，0.9}，γ∈{0.1，0.2，0.3，0.5，0.7，0.9}，α∈{0 ，0.5，1，2，5}.每次實驗只改變其中一個參數(shù)的值，其他參數(shù)保持不變.為降低偶然因素的影響，每組參數(shù)仿真10次，取10次實驗的平均值、最優(yōu)值、最差值作比較，以此來分析參數(shù)取值對算法性能的影響.設α=1，ρ=0.3，γ=0.4為默認參數(shù)值.實驗結(jié)果如表2所示.

在表2中，當設定α=1，γ=0.4時，ρ∈［0.2，0.3］得到的解是較優(yōu)的;當α=1，ρ=0.3時，γ=0.2得到的解是較優(yōu)的;當設定ρ=0.3，γ=0.4時，α∈［0.5，1，2］得到的解是較優(yōu)的.所以可以得出，設定α=1、ρ=0.2、γ=0.2較為合適.

同樣以圖2所示的地圖中的起點坐標［43，17］和終點坐標［72，85］為例，設定參數(shù)α=1、ρ=0.2、γ=0.2對變異蟻群算法仿真10次，得到最優(yōu)時間 besttime為104.0，最長時間為127.6，平均時間為113.8.通過對比仿真結(jié)果與表2中的數(shù)據(jù)說明，參數(shù)的取值是有效的.當參數(shù)α=1、ρ=0.2、γ=0.2時對可變異和不變異蟻群算法分別進行測試，測試搜索到的最優(yōu)路徑分別如圖3的(a)和(b)中起點至終點的連線所示.在圖3(a)中螞蟻遇到障礙物可變異成一種特殊螞蟻穿越山脈和河流，最優(yōu)時間besttime為104.0.而在圖3(b)中，螞蟻沒有變異，不可穿越障礙物，只能繞著障礙物行走，最優(yōu)時間besttime為120.0.仿真10次得到的最優(yōu)時間besttime為120.0，最長時間為149.0，平均時間為136.8.通過數(shù)據(jù)對比說明，挖隧道經(jīng)過山脈、架設高架橋通過河流、繞過中等權值城市的路徑是造價最小的.

圖2 擬修建高速公路的區(qū)域地圖Fig.2 Regional map of the highway to be constructed

表2 變異蟻群算法各參數(shù)測試結(jié)果Tab.2 Test results of the parameters of the mutated ant colony algorithm

圖3 最優(yōu)路徑Fig.3 Optimal path

4 結(jié)語

蟻群算法是一種啟發(fā)式的隨機搜索技術，具有魯棒性、正反饋等特點.考慮到高速公路路線規(guī)劃問題的特殊性，利用生物進化過程中可能出現(xiàn)的變異特性，對蟻群算法做了一些改進，使得螞蟻種群中的部分螞蟻可以變異成一種特殊螞蟻，通過架設高架橋、穿鑿隧道等方式穿越障礙物，可搜尋出一條造價最小的修建路線.

由于采用位圖地圖來表示地理信息，螞蟻的行進路線只有上、下、左、右4個方向，所以不可避免的在搜尋高速公路路徑時出現(xiàn)了垂直角度的路線，這不符合高速公路不能出現(xiàn)直角路線的要求，所以本文的高速公路選徑研究離真正的選徑路線還有一定的差距，但在實際應用時有一定的指導意義.本文的研究是規(guī)劃高速公路路線的一種新理論方法的探索，也為其他道路設施如高速鐵路的規(guī)劃建設，提供了一些參考依據(jù).智能算法應用于高速公路建設對未來合理、智能地規(guī)劃道路具有一定的參考意義.

［1］Porta Garcia M A，Oscar M，Oscar C，et al.Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation［J］.Applied Soft Computing，2009，9(3):1 102 －1 110.

［2］Mei Hao，Tian Yan－tao，Zu Li－nan.A hybrid ant colony optimization algorithm for path planning of robot in dynamic environment［J］.International Journal of Information Technology，2006，12(3):78 －88.

［3］Zhu Qing－bao，Hu Jun，Cai Wen －bin，et al.A new robot navigation algorithm for dynamic unknown environments based on dynamic path re－computation and an improved scout ant algorithm［J］.Applied Soft Computing，2011，11(8):4667－4 676.

［4］溫如春，許櫻，王祖麟.改進蟻群算法在迷宮路徑規(guī)劃問題中的研究和應用［J］.江西理工大學學報，2010，31(2):26－28.

［5］張維澤，林劍波，吳洪森，等.基于改進蟻群算法的物流配送路徑優(yōu)化［J］.浙江大學學報:工學版，2008，42(4):574－578;597.

［6］吳建軍，劉軍.物流配送路徑安排問題的混合蟻群算法［J］.土木工程學報，2004，37(8):98－101.

［7］Duran T M.Ant colony optimization for finding the global minimum［J］.Applied Mathematics and Computation，2006，176(1):308－316.

［8］胡中華，趙敏，姚敏.引入偵查子群的二進制蟻群算法求解函數(shù)優(yōu)化問題［J］.小型微型計算機系統(tǒng)，2010，31(6):1 175－1 179.

［9］朱慶保，楊志軍.基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法［J］.軟件學報，2004，15(2):185－192.