摘  要： 將遺傳算法與蟻群算法進(jìn)行有機結(jié)合，并將其應(yīng)用到智能機器人全局路徑規(guī)劃中，其目的是探索一種基于柵格劃分的環(huán)境中新的路徑尋優(yōu)算法，研究機器人路徑規(guī)劃問題。首先利用遺傳算法全局搜索能力強的特點，生成初始信息素分布，再利用蟻群算法正反饋機制的特點求精確解，通過兩種算法的優(yōu)勢互補，提高系統(tǒng)的路徑尋優(yōu)能力。
關(guān)鍵詞： 遺傳算法；蟻群算法；路徑尋優(yōu)算法；路徑規(guī)劃

    移動機器人的全局路徑規(guī)劃可歸為有約束條件下的多目標(biāo)優(yōu)化問題，在已知環(huán)境信息的情況下，利用有限條件規(guī)劃出一條由起始點到目標(biāo)點、且能避開障礙物的最優(yōu)或次最優(yōu)路徑[1]。目前，國內(nèi)外學(xué)者針對機器人全局路徑規(guī)劃問題做了大量研究，提出了許多算法，主要有可視圖法、柵格法、人工勢場法、A*搜索方法以及隨機搜索法等，這些算法都存在搜索速度慢、易陷入局部最小等缺點。
    隨著蟻群算法(ACO)[2]、微粒群算法(PSO)[3]、遺傳算法(GA)[4]等智能算法的提出，機器人路徑規(guī)劃算法得到了很大的發(fā)展。通過這些方法在路徑規(guī)劃中的應(yīng)用使得機器人更加智能，其運行路徑也更加逼近理想的優(yōu)化要求，但在搜索效率以及最優(yōu)能力等方面仍然存在各自的缺陷。本文主要針對遺傳算法進(jìn)行路徑規(guī)劃時運算速度慢、占據(jù)存儲空間大、容易陷入早熟等缺點，結(jié)合蟻群算法和遺傳算法兩種算法的優(yōu)點提出一種新的復(fù)合型路徑規(guī)劃算法。
1 遺傳算法的應(yīng)用
    遺傳算法是一種概率搜索算法，它利用某種編碼技術(shù)作用于稱為染色體的數(shù)串。其基本思想是模擬由這些串組成的個體的進(jìn)化過程[5]。遺傳算法實現(xiàn)主要涉及編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計以及遺傳算子操作。
1.1 編碼
    遺傳編碼對于算法的性能如搜索能力和計算效率等影響很大，本文采用路徑編碼方法，從起點到目標(biāo)點的路徑節(jié)點序列作為染色體，該染色體是不定長的。編碼如下所示：



    綜上所述，改進(jìn)的組合優(yōu)化算法主要步驟如下：
    (1)進(jìn)行編碼，產(chǎn)生初始種群；對個體適應(yīng)度進(jìn)行檢測評估；
    (2)根據(jù)適配值大小進(jìn)行選擇、交叉和變異操作；
    (3)根據(jù)結(jié)果判斷子代群體的進(jìn)化率是否都小于設(shè)置的子代群體最小進(jìn)化率，若滿足則根據(jù)結(jié)果生成若干組優(yōu)化解，否則重新進(jìn)行個體適應(yīng)度的檢測評估，執(zhí)行步驟(3)、步驟(4)；
    (4)根據(jù)遺傳算法生成的若干組優(yōu)化解，初始化蟻群算法參數(shù)，生成信息素初始分布，并將螞蟻置于初始節(jié)點；
    (5)根據(jù)蟻群算法的狀態(tài)轉(zhuǎn)移概率進(jìn)行下一個節(jié)點的選擇；
    (6)更新蟻群算法禁忌表，并對信息素進(jìn)行更新；
    (7)判斷是否滿足結(jié)束條件，若滿足則輸出結(jié)果，否則轉(zhuǎn)到步驟(3)，繼續(xù)執(zhí)行步驟(3)~步驟(7)。
3 仿真驗證
    為了驗證本文所提出的靜態(tài)環(huán)境下改進(jìn)組合算法在機器人路徑規(guī)劃中的正確性和有效性，在Matlab環(huán)境下進(jìn)行了仿真驗證。運用概率地圖方法在規(guī)劃環(huán)境中得到路線圖，分別采用基本蟻群算法和改進(jìn)后的組合優(yōu)化算法進(jìn)行路線圖搜索，假設(shè)機器人的規(guī)劃區(qū)域為400 m×400 m的空間，其遺傳操作取值為：交叉率為0.7，變異概率為0.06，種群規(guī)模為35，進(jìn)化代數(shù)為5%，n為3；蟻群算法取值為：ι0=0.01，ρ=0.3，β=4，NC_max=10Q=100，m=60。仿真曲線結(jié)果如圖1～圖4所示，其中，圖4為收斂曲線。

    仿真結(jié)果表明，蟻群算法路徑長度為490.077 663 m；搜索用時9.941 37 s；路徑上節(jié)點數(shù)為15；混合算法路徑長度為448.825 552 m；搜索用時4.614 29 s；路徑上節(jié)點數(shù)為14。經(jīng)計算，混合算法路徑長度比蟻群算法路徑長度縮短了8.4%，用時縮短了53.5%。
    本文對復(fù)雜環(huán)境下全局路徑規(guī)劃搜索速度較慢的問題進(jìn)行了改進(jìn)。首先利用遺傳算法的全局尋優(yōu)特性進(jìn)行大范圍尋優(yōu)，構(gòu)成蟻群算法的初始信息素分布，再利用蟻群算法正反饋機制尋找精確解，通過信息素的不斷更新最終收斂于最優(yōu)路徑。該組合優(yōu)化算法根據(jù)遺傳算法與蟻群算法各自的特點，將兩者進(jìn)行有機結(jié)合構(gòu)成GA-ACO(Genetic Algorithm- Ant Colony Optimization)算法，并將其應(yīng)用在規(guī)劃路徑尋優(yōu)中。通過仿真驗證，組合后的優(yōu)化算法在路徑的搜索過程中更具有方向性，顯著地減少了冗余迭代的次數(shù)，在收斂速度和求解精度上均優(yōu)于基本蟻群算法。
參考文獻(xiàn)
[1] TSAI C C，HUANG H C，CHAN C K.Parallel elite genetic  algorithm and its application to global path planning for autonomous robot navigation[C].In Proceedings of IEEE international Conference on Computer Applications，Shipbuilding，2011：4813-4821.
[2] LIM K K，Yew-Soon Ong，LIM M H，et al.Hybrid ant colony algorithms for path planning in sparse graphs[J].Soft Computing，2008，12(10)：981-994.
[3] 孫波，陳衛(wèi)東，席裕庚.基于粒子群優(yōu)化算法的移動機器人全局路徑規(guī)劃[J].控制與決策，2005，20(9)：1052-1060.
[4] CASTILLO O，TRUJILLO L，MELIN P.Multiple objective genetic algorithms for path-planning optimization in  autonomous mobile robots[J].Soft Computer，2007，11(3)：69-279.
[5] 李劍鋒，段文軍，方斌，等.基于改進(jìn)遺傳算法立體車庫存取調(diào)度優(yōu)化[J].控制工程，2010，17(5)：658-661.
[6] 鄧見光，袁華強，趙躍龍.一種基于遺傳—蟻群算法的網(wǎng)格任務(wù)調(diào)度策略[J].計算機應(yīng)用研究，2011，28(12)：4485-4488.
[7] Tan Guanzheng，He Huan，SLOMAN A.Global optimal path  planning for mobile robot based on improved Dijkstra  algorithm and ant system algorithm[J].Journal of Central   South University of Technology，2006，13(1)：80-86.
[8] BRANKE J，GUNTSCH M.Solving the probabilistic TSP with ant colony optimization[J].Journal of Mathematical  Modelling and Algorithms，2004，3(4)：403-425.