張 毅 高永琪 牛興江

（海軍工程大學兵器工程系 武漢 430033）

0 引 言

路徑規(guī)劃［1－2］是指在特定的約束條件下，如在綜合考慮機器人（航行器）的到達時間、燃料消耗、威脅，以及飛行區(qū)域的選擇等因素的前提下，為機器人（航行器）規(guī)劃出一條最優(yōu)的，或者滿足特定需要的行走路徑，從而保證圓滿完成任務．

傳統(tǒng)的路徑規(guī)劃算法主要有最速下降法［3］、A＊算法［4］、圖搜索算法［5］等，由于路徑規(guī)劃問題屬于組合優(yōu)化問題，基本都是 NP－Hard問題［6］，因此傳統(tǒng)路徑規(guī)劃方法都存在不同程度上的不足．而研究表明，一些生物啟發(fā)式算法在解決NPHard問題時，往往能夠取得更好的結果，比如，粒子群算法、遺傳算法、魚群算法，以及蟻群優(yōu)化算法等．其中蟻群優(yōu)化算法在解決旅行商問題（traveling salesman problem，TSP）、機器人路徑規(guī)劃等組合優(yōu)化問題中取得了較其他方法更優(yōu)的結果．但是蟻群優(yōu)化算法也存在容易陷入局部最優(yōu)、收斂速度慢、參數(shù)設置麻煩等不足［7］．本文針對蟻群優(yōu)化算法的上述缺點進行了改進研究，并對TSP問題和機器人路徑規(guī)劃問題進行了仿真研究和比較．

1 蟻群算法

蟻群優(yōu)化算法（ant colony optimization，ACO）［8－9］針對離散的組合優(yōu)化問題，采用概率性選擇機制并正向移動地構建解，信息素的更新是在逆向移動中做出，信息素的釋放量和之前構建解的質(zhì)量有關．為了更好地探索最優(yōu)解，算法加入了信息素揮發(fā)機制．

下面以求解平面上N個城市的TSP問題為例來說明蟻群算法的狀態(tài)轉移規(guī)則［10－11］．設m為螞蟻數(shù)量，dij（i，j＝1，2，…，n）表示城市i和城市j之間的距離，τij（t）表示t時刻在ij連線上殘留的信息素．螞蟻k（k＝1，2，…，m）在運動過程中根據(jù)各路徑上的信息量決定轉移方向．螞蟻系統(tǒng)所使用的狀態(tài)轉移規(guī)則被稱為隨機比例規(guī)則，其給出了位于城市i的螞蟻k選擇移動到城市j的概率．在t時刻，螞蟻k在城市i選擇城市j的轉移概率（t）為

式中：allowedk為螞蟻k下一步允許選擇的城市集合；ηij為啟發(fā)式函數(shù)；α和β為2個參數(shù)，分別反映了螞蟻在運動過程中所積累的信息和啟發(fā)式信息在螞蟻選擇路徑中的相對重要性．

螞蟻根據(jù)式（2）所給出的偽隨機比例規(guī)則移動到下一城市

式中：q為［0，1］區(qū)間均勻分布的隨機數(shù)；q0（0≤q0≤1）為參數(shù)；S為根據(jù)式（1）給出的概率分布所選出的為隨機變量．

當螞蟻完成一次循環(huán)，各路徑上信息素根據(jù)下式調(diào)整．

式中：Δτkij（t，t＋1）為第k只螞蟻在時刻（t，t＋1）留在路徑ij上的信息素；Δτij（t，t＋1）為本次循環(huán)中路徑ij上信息素的增量；ρ（0＜ρ＜1）為信息素的揮發(fā)系數(shù)．

2 算法改進

由于蟻群優(yōu)化算法存在容易陷入局部最優(yōu)、計算量大、沒有明確的參數(shù)設置方式等缺點，本文對蟻群優(yōu)化算法做如下改進．

1）蟻群算法在構造解的過程中，利用了概率隨機選擇的策略，這使得算法的收斂速度慢．式（2）中的參數(shù)q0對于算法的選擇策略起著關鍵性的作用，因此本文對q0的取值進行了改進．隨著搜索的進行，動態(tài)地調(diào)整q0的值

式中：k為當前搜索的次數(shù)；K1為一具體的搜索次數(shù)；q10（q0min≤q10≤1）為q0的一個較大的初始值；q0min為q0的下限．

初始時刻定義較大的q0能夠加快算法的收斂速度，當搜索到一定代數(shù)K1后，搜索方向已經(jīng)基本確定，這時減小q0的值，能夠適當加大隨機選擇的概率，即是在前K1次迭代所搜索的最好解周圍加強了局部搜索的能力．這一改進減小了路徑選擇的計算量，不僅能夠加快收斂速度，節(jié)省搜索時間，而且能夠克服算法過早的停滯，有利于發(fā)現(xiàn)更好的解．

2）為了避免搜索的過早停滯，借鑒最大－最小螞蟻系統(tǒng)的方法，將信息素的值域范圍限制在［τmin，τmax］區(qū)間內(nèi)，并且將信息素軌跡初始化為

又算法的信息素更新規(guī)則為

式中：Δτbestij ＝1／f（sbest），f（sbest）為當前迭代最優(yōu)解sib或者全局最優(yōu)解sgb．為了兼顧收斂速度和解搜索范圍，螞蟻在搜索過程中默認使用sib進行信息素更新，只在第10n（n＝1，2，…）次循環(huán)中使用sgb．

3）當所有螞蟻完成一次循環(huán)，只有本次迭代構造出最優(yōu)解和最差解的螞蟻才被允許釋放信息素．其中最優(yōu)解路徑上的信息素更新公式如式（6）所示，對于最差解所經(jīng)過的路徑ij，并且ij不屬于最優(yōu)解，則ij上的信息素更新公式如下．

式中：?為一個固定的參數(shù)；Lbest為本次迭代中最優(yōu)路徑長度；Lworst為本次迭代中最差路徑長度．

這樣的改進能夠?qū)ψ顑?yōu)解進行更大限度的增強，并且對最差解進行消弱，使得最優(yōu)路徑與最差路徑之間的信息素差異進一步增大，從而使螞蟻的搜索行為能夠更加集中于最優(yōu)解附近．

3 仿真研究

3．1 TSP問題

以中國大陸31個省會、自治區(qū)和直轄市城市的相對坐標為基礎的TSP問題為例，利用Matlab 7．0對改進算法和基本蟻群優(yōu)化算法進行20次仿真實驗．算法的各參數(shù)設置見表1．

表1 系數(shù)取值

以緯度方向為X軸，經(jīng)度方向為Y軸建立31個城市的相對位置坐標系，仿真結果分別見表2和圖1．

表2 仿真結果對比

由以上仿真結果可知，改進的算法在解決TSP問題時，不僅能夠得到更好的解，更能顯著地提高算法的收斂速度．

圖1 改進算法所得到的最好解

3．2 機器人路徑規(guī)劃問題

首先對環(huán)境進行網(wǎng)格化處理，網(wǎng)格長度為1，障礙物（威脅）用圓形區(qū)域表示（如圖2）．不同于TSP問題中的信息素表示方式，這里將信息素存儲在環(huán)境模型的離散點上，每個點上信息素的大小代表該離散點對螞蟻的吸引程度．

算法的參數(shù)設置見表3．仿真結果見圖3．

表3 系數(shù)取值

圖2 規(guī)劃路徑

圖3 收斂曲線

圖3 分別為改進算法和基本蟻群優(yōu)化算法的歷次迭代最小路徑長度，即收斂曲線，通過對比可知，改進算法能夠顯著提高算法的收斂速度．

4 結束語

蟻群優(yōu)化算法是模擬自然界中的螞蟻覓食過程可以找到最短路徑的行為過程而設計的一種仿生算法，作為通用型隨機優(yōu)化方法，它吸收了螞蟻的行為特性，通過其內(nèi)在的搜索機制，利用一群人工螞蟻的協(xié)作來尋找問題的解，成為求解組合優(yōu)化等NP－Hard問題的一種有效的智能優(yōu)化算法．然而蟻群算法存在容易陷入局部最優(yōu)、收斂速度慢、參數(shù)設置麻煩等不足．本文對蟻群算法的上述問題進行了改進，并對TSP問題和路徑規(guī)劃問題進行了仿真研究．仿真結果表明：改進之后的算法不僅能夠得到更好的解，更能顯著地提高算法的

收斂速度．

［1］謝曉方，孫 濤，歐陽中輝．反艦導彈航路規(guī)劃技術［M］．北京：國防工業(yè)出版社，2010．

［2］樊曉平，羅 熊，易 晟，等．復雜環(huán)境下基于蟻群優(yōu)化算法的機器人路徑規(guī)劃［J］．控制與決策，2004，19（2）：166－170．

［3］韓志剛，林爭輝，李林森，等．低空突防路徑規(guī)劃方法綜述［J］．飛行力學，2002，20（3）：1－4．

［4］顧新艷，金世俊．基于A＊算法的移動機器人路徑規(guī)劃［J］．科技信息：科學教研，2007，34：36－38．

［5］仝秋紅，趙忠杰．汽車駕駛智能化中路線規(guī)劃及導航的最佳路徑求解法［J］．西安公路交通大學學報，1999，19（3）：88－90．

［6］溫一慧．組合·算法·理論與應用［M］．蘭州：蘭州大學出版社，2006．

［7］DORIGO M，GAMBARDELLA L M．Ant colony system：a cooperative learning approach to the traveling salesman problem［J］．IEEE Transactions on Evolutionary Computation（S1089－778X），1997，1（1）：53－66．

［8］COLORNI A．Ant system for Job－shop scheduling［J］．JORBEL，1994，34（1）：39－54．

［9］DORIGO M，STUTZLE T．Ant colony optimization［M］．Brussels：MIT，2004．

［10］李士勇．蟻群算法及其應用［M］．哈爾濱：哈爾濱工業(yè)大學出版社，2004．

［11］彭斯俊，黃樟燦，劉道海，等．基于螞蟻系統(tǒng)的TSP問題的新算法［J］．武漢汽車工業(yè)大學學報，1998，20（5）：88－92．