航海上蟻群算法研究及應用范文

本站小編為你精心準備了航海上蟻群算法研究及應用參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

摘要:本文介紹了自然界中蟻群的覓食行為、基本蟻群算法的數學模型和程序結構流程、蟻群算法的改進以及蟻群算法在航海上的應用等方面，最后將蟻群算法在航海領域中的研究問題和未來研究方向進行了總結，對從事船舶路徑規劃和船舶自動避碰等問題的學者來講，具有重要參考價值．

關鍵詞:蟻群算法;路徑規劃;自動避碰

在計算機技術飛速發展的21世紀，隨著科技的成熟，人類正朝著智能化、機械化、自動化穩步邁進，無人車、無人飛機、無人船等紛紛問世．隨著海運強國戰略的實施，航運事業飛速發展，近年來涌現出一大批專家和學者，圍繞無人駕駛船舶路徑規劃和航線自動生成等問題展開研究．在此之前，機器人路徑規劃技術已經趨于成熟，鑒于機器人路徑規劃與無人駕駛船舶路徑規劃、航線自動生成的相似性，例如遺傳算法、人工勢場算法、粒子群優化算法、蟻群算法等，都可以應用于無人駕駛船舶路徑規劃或船舶航線自動生成等航海問題．蟻群算法因其強大的魯棒性，廣泛的適用性，優良的分布式計算以及與其他算法的簡單組合而得到廣泛應用．其他學者大多寫蟻群算法在非航海方面的應用，并無學者將蟻群算法在航海上的應用總結出來，本文將蟻群算法在航海方面的應用(如無人船路徑規劃、潛艇導航規劃、船舶避碰規劃等)以及研究中發現的問題和未來研究方向總結出來，對從事無人駕駛船舶路徑規劃或船舶航線自動生成等與航海相關的學者來講具有參考價值．

1蟻群算法的算法原理

蟻群算法(antcolonyoptimization，ACO)，又稱螞蟻算法或蟻群優化算法，是由意大利學者MarcoDorigo等人于1991年在法國巴黎召開的第一屆歐洲人工生命會議(EuropeanConferenceonArtificialLife，ECAL)上提出［1］．然而，截至1996年，它一直沒有引起國內外學者的廣泛關注，直到后來MarcoDorigo又發表了“Antsystem:optimizationbyacolonyofcooperationagents”這篇文章，蟻群算法這才引起了學術界的關注．

1．1蟻群行為描述仿生學家通過對螞蟻生活習性的長期觀察，發現螞蟻并不像其他動物那樣擁有視覺，且個體螞蟻的智慧并不高，然而，群體螞蟻在尋找食物的過程中尋找路徑的行為反映出了高度組織的結構化．該研究發現，在覓食的過程中，螞蟻會分泌一種特殊的化學信息素，螞蟻通過這些信息素傳遞信息，協同合作，形成集體自催化行為，然后找到從蟻巢到食物來源的最短路徑［2］．螞蟻選擇特定路徑的趨勢與發現的路徑上的信息素濃度正相關，即通過路徑的螞蟻越多，螞蟻留下的信息越多，道路上存在的信息素濃度就越大，其他螞蟻選擇這條道路的可能性就越大．在尋找食物的過程中，螞蟻尋找路徑的這種行為形成了積極的正反饋機制［2］．由于信息素的濃度隨時間逐漸降低，因此路徑越長，信息素的濃度越小．圖1是自然界螞蟻的覓食原理［3］．A為食物源，D為蟻巢，B和C為障礙物的端點．如圖(a)所示，在通往食物源的途中，如果沒有障礙物，螞蟻將始終選擇最短的路徑．如圖(b)所示，如果蟻巢和食物源之間存在障礙物，螞蟻將以相同的概率選擇DBA和DCA路徑．如圖(c)所示，因為路徑DCA的長度小于路徑DBA，所以等時通過路徑DCA的螞蟻比通過路徑DBA的螞蟻多．然后，螞蟻在DCA上分泌的信息素濃度高于螞蟻在DBA上分泌的信息素濃度．后續螞蟻就傾向于選擇路徑DCA．如圖(d)所示，最終螞蟻都會選擇路徑DCA，蟻群正是通過這種方法，才用最短的路徑尋找到了食物源．

1．2基本蟻群算法的數學模型本文借助于經典的旅行商問題(TravelingSalesmanProblem，TSP)，對基本蟻群算法的數學模型進行說明．即人工螞蟻k(k=1，2，3，…，m)從n個城市中任選一個作為起點，隨機前往下一個城市，中途不能折回，一個城市不能重復走過，最后返回起點，最終找到一條最短的路徑．為了確保螞蟻k不重復經過一個城市，這里用禁忌表tabuk(k=k=1，2，3，…，m)記錄螞蟻k當前走過的城市，則人工螞蟻t時刻從一個城市i到另外一個城市j的轉移概率為:式中，α為信息啟發式因子，表示軌跡的相對重要程度，其值越大，其他螞蟻選擇該路徑的可能性越大;β為期望啟發式因子，表示能見度的相對重要程度，其值越大，其他螞蟻選擇該路徑的可能性越大．τis(t)為t時刻城市i到城市j路徑上存在的信息量，ηis(t)為t時刻螞蟻從城市i到城市j的期望程度，且，ηis(t)越小，pkij(t)就越小，即轉移概率就越小．為了避免殘留信息素淹沒啟發信息，需要對殘留信息素進行更新處理，t+n時刻，路徑(i，j)上的信息素調整為:式中，1－ρ為信息素殘留因子，且ρ［0，1］;Δτijk(t)表示第k只螞蟻在路徑(i，j)上留下的信息量;Δτij(t)表示循環結束后路徑(i，j)上信息素的增加量;Q表示信息素強度;Lk表示第k只螞蟻在本次循環中行走的路徑長度．

1．3基本蟻群算法的程序結構流程以旅行商問題為例，基本蟻群算法的程序結構流程如圖2所示:

2蟻群算法的改進

盡管蟻群算法具有許多優點，但必須考慮其存在的缺陷．蟻群算法需要花費大量時間進行計算，搜索速度太慢，算法收斂時間太長．啟發式因子α，預期啟發式因子β，信息素強度Q，信息素揮發因子ρ等參數的設置均基于經驗，沒有足夠的理論依據［4］．為了解決這方面的問題，國內的段海濱、高尚、孫燾、丁建立、陳崚、楊勇、汪鐳等，國外的GutjahrWJ、MarcoDorigo、StützleT、HouYH、YooJH、BadrA等許多學者對蟻群算法的方法或模型或策略進行了改進．在一定程度上，減少了蟻群算法的計算時間，提高了收斂速度，避免了局部最優．StützleT和HolgerHoos在1997年提出了最大－最小螞蟻系統［5］(MAX-MINAntSystem，MMAS)，MMAS是一種基于協同搜索的元啟發式算法，它改進了傳統的蟻群算法(AntSystem，AS)，為組合優化問題的解決方案提供了自適應框架．MMAS在每次迭代中僅允許最佳的螞蟻更新路徑信息素強度，并且信息素強度在所有路徑上初始化為最大值τmax．在每次迭代之后，僅允許最佳路徑的信息素保持在較高水平，而其他路徑上的信息素將隨時間逐漸揮發．信息素的揮發使信息素強度降低一個因子，導致更少的后續螞蟻選擇這條路徑，信息素強度持續降低．如果不及時處理，信息素的強度將降至零，為此需要設置信息素的強度不能低于一個最小值τmin．換句話說，需要將信息素的強度τ設置為τmin≤τ≤τmax．這種處理方法有效地克服了蟻群算法容易出現停滯現象的缺陷，但是最大－最小螞蟻系統每一步搜索結束之后都要對所有路徑上的信息素進行實時更新，導致消耗大量的時間．此外許多參數(如τmax、τmin等)的設置仍然憑借經驗，沒有嚴謹的數學證明作為理論依據．StützleT和HolgerHoos在2000年發表了《MAX-MINAntSystem》對最大－最小螞蟻系統進行了改進—信息素平滑處理［6］．當MMAS搜索停止時，比較每條路徑的信息素差值，并且當差異大時，對每條路徑的信息素強度進行加權平均．加權平均后每條路徑的信息素間隙減小，有利于生成新的搜索路徑，但算法的搜索效率會較慢．楊延慶等［7］從信息素τ的限制、信息素的更新方式兩方面對最大－最小螞蟻系統進行了改進，將傳統最大－最小螞蟻系統的信息素強度τ設置為固定值，可在一定程度上提高計算效率．另外，在完成每個循環之后，MMAS對各條路徑長度進行加和平均，路徑長度小于平均值，則基于原始信息素強度適當增強．相反，如果路徑長度大于平均值，則基于原始信息素強度適當減弱;最短路徑上的信息素和螞蟻行進的最遠路徑被更新，而另一條路徑上的信息素不被處理．然而，由于信息素隨時間揮發，因此最短路徑上的信息素與最遠路徑之間的差異增大，從而提高了算法的搜索效率．王勝等［8］通過禁忌策略改進蟻群算法，避免局部最短路徑中的蟻群停滯．由于缺乏參數的自適應調整策略，需要改進算法旅行商問題的尋優能力．張軍英等人［9］從城市選擇策略的參數選擇，信息量更新方式和局部搜索策略等方面對蟻群算法進行了改進．改進的算法加速了算法的收斂，降低了早熟收斂和搜索停滯的可能性．段海濱等人［10］提出利用云模型理論實現蟻群算法，避免了在大搜索空間條件下出現局部最優解，能夠更快地找到全局最優解．GambardellaLM等［11］在1999年提出了多重蟻群算法(MultipleAntColonySystem，MACS)的概念，并利用該算法解決了多目標優化問題，大大降低了最優解的求解速率．CSolnon［12］提出了Ant-P-solver，這是一種基于蟻群優化的元啟發式算法，通過與本地搜索技術相結合求解約束滿足問題(ConstraintSatisfactionProblem，CSP)，將問題建模為在圖中搜索最佳路徑，人工螞蟻以隨機的方式走過該圖，人工螞蟻通過在圖的邊緣釋放信息素進行通信，尋找最優路徑．DGaertner和KLClark［13］使用遺傳算法(GeneticAlgorithms，GA)的思想修改了ACO實例，以形成遺傳基因改進的蟻群系統(GeneticallyModifiedAntColonySystem，GMACS)．在該算法中，每個螞蟻用隨機參數組合初始化，其中參數值從合理范圍中選擇．隨著時間的推移，螞蟻的數量不斷增加，使用更好的參數組合培育螞蟻，從而找到改進的解決旅行商問題實例的方案．

3蟻群算法在航海上的應用

自1991年引入蟻群算法以來，許多學者積極探索并大膽嘗試，在蟻群算法研究方面取得重大進展和突破．如旅行商問題、指派問題(QuadraticAssignmentProblem，QAP)、序列排序問題(SequentialOrderingProblem，SOP)、圖形著色問題(GraphColoringProblem，GCP)、車輛路徑問題(VehicleRoutingProblem，VRP)、車間作業調動問題(Job-shopScheduleProblem，JSP)、以及網絡路由問題(QuantityofService，QoS)、線性系統參數辨識問題、最優PID控制問題、故障診斷問題、圖像處理、聚類分析、數據挖掘、航跡規劃、空戰決策、巖土工程問題(如邊坡非圓弧臨界滑動面搜索問題)、化學工業問題(如2－氯苯酚在超臨界水中氧化反應動力學參數估計問題)、生命科學問題(如蛋白質折疊問題)、機器人路徑規劃問題、無人駕駛車輛路徑規劃、無人機路徑規劃等．蟻群算法在這些方面的應用前人多有闡述，本文重點闡述蟻群算法在航海領域的應用，如無人船路徑規劃、無人水下航線器路徑規劃、船舶航線自動設計、潛艇導航規劃、船舶避碰規劃等．何立居，李啟華［14］以電子海圖顯示和信息系統為基礎，采用前向策略和后向策略作為搜索策略．蟻群算法從海域網格劃分，網格點信息素，信息素更新，搜索策略，路徑選擇和路徑平滑等方面進行了改進．通過實例證明了蟻群算法用于航線自動生成的可行性．劉利強［15］提出了一種改進的基于協同和空間收縮的蟻群優化算法，以及一種改進的連續域蟻群優化算法，具有收斂速度快，搜索能力強的特點．采用空間網格法模擬三維空間環境，為潛艇進行三維空間導航．陳曉等［16］利用構造自由空間的Maklink圖論法對海圖進行預處理，生成無向網絡圖，接著采用動態規劃Dijkstra算法生成初始路徑，最后用蟻群算法進行路徑優化．這與在傳統的紙質海圖上手繪航線或者在電子海圖顯示與信息系統(ElectronicChartDisplayandInformationSystem，ECDIS)中輸入航路點生成航線相比，能夠節省較多時間，給船員減輕了負擔，但是由于沒有考慮到動態障礙物避險以及風、浪、流等自然因素的影響，有待進一步研究．趙紅［17］將人工勢場法與蟻群算法相結合，形成了一種用于波浪動態滑翔機路徑規劃的勢場蟻群算法．在基于改進勢場蟻群算法的波浪動態滑翔機路徑規劃仿真實驗中，文獻考慮了導航過程中的動態障礙，以及波浪、海流等自然因素的影響，設置了波浪權重和水下海流權重等海洋環境參數．該方法提高了算法全局優化的能力，提高了波動力滑翔機的導航速度，縮短了波動力滑翔機的行駛時間．最重要的是使波動滑翔機能夠成功避開動態障礙物并產生了一條安全的最短路徑．陳立家等［18］論述了基于電子海圖的在多約束條件下(風浪、水深、船速、航行費用等)綜合成本最低的最優航線生成算法(optimalroutegenerationAlgorithm，ORGA)．基于航線網絡圖，該算法使用Dijkstra算法找到最短路徑，并使用改進的蟻群算法找到最優路徑．該算法提高了搜索效率，可以更快地找到最佳路徑．朱青［19］介紹了基于分布均勻性的自適應蟻群算法，利用連接圖法(Maklink方法)動態調整信息素更新策略和狀態轉移概率，來解決算法收斂速度慢和早熟收斂的現象．最后，平滑路線以獲得最佳路徑．張金水等［20］將遺傳算法與蟻群算法向融合，以獲取最優航線．先用蟻群算法產生航線初始種群，然后用遺傳算法對之前產生的航線初始種群進行遺傳操作—選擇、交叉、變異、刪除［21］，得到最優航線．AgnieszkaLazarowska［22］介紹了在導航決策支持系統(DecisionSupportSystem，DSS)中使用蟻群優化技術的智能應用程序，以及在導航DSS中實現的ACO原理和基于ACO的算法，開發的導航DSS體系結構以及路徑規劃和避碰問題等．該系統解決問題的能力包括在公海和限制水域中的船舶的路徑規劃和船舶避碰，增強了船舶安全控制過程的自動化程度．JBEscario［23］基于細胞自動機(CellularAutomata)和改進蟻群優化算法給自動船舶操縱進行最優或次優路徑規劃．細胞自動機是對的連續搜索空間進行粗略的離散化，并提供推薦的船舶姿態的集合，而沒有任何明確的船舶動力學參考．考慮到船舶動力學所施加的限制，這些姿態將成為蟻群算法計算連續軌跡的起點而提出的改進蟻群優化算法，則是用來處理具有動態特征的“螞蟻”(船只)，最終達到給自動船舶操縱進行最優或次優路徑規劃的目的．國內外眾多學者利用蟻群算法，圍繞船舶路徑規劃與優化、船舶避碰、波浪動態滑翔機路徑規劃、潛艇導航規劃等航海領域展開研究，取得了不錯的成績，但是蟻群算法在數學上缺少嚴謹的可靠性的理論證明，且很多參數的設置都是憑借經驗，沒有理論依據，再加上蟻群優化算法本身原理機制復雜，編程代碼復雜，實現難度較大．

4結論

隨著航運事業蓬勃發展，蟻群算法在航海領域的應用更有待挖掘，船舶路徑規劃和船舶自動避碰等航海領域問題需要進一步深入研究．為了給后續學者提供研究思路，特將研究中發現的問題總結如下:(1)海洋環境復雜多變，用柵格法、拓撲法、Maklink圖論法等對環境進行處理后，與真實環境存在差距，真實性和可靠性有待提高．環境建模多采用柵格法，建模后的分辨率大小問題也要考慮，如何采用動態柵格，是一種研究思路．(2)島嶼、暗礁、淺水區等航行過程中必須考慮的因素的處理方法有待改進．對這些因素進行膨化處理的尺度很難把控，膨化過大，設計出來的航線可能不是最優航線，膨化過小可能存在安全隱患．(3)航線路徑規劃多針對靜態環境(理想環境)，動態環境下，尤其是復雜動態環境下(風浪流等)，進行航線規劃難度較大．

作者：張文拴 徐海軍 閆哲 單位：大連海事大學