航海上蟻群算法研究及應(yīng)用范文
本站小編為你精心準(zhǔn)備了航海上蟻群算法研究及應(yīng)用參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。
摘要:本文介紹了自然界中蟻群的覓食行為、基本蟻群算法的數(shù)學(xué)模型和程序結(jié)構(gòu)流程、蟻群算法的改進(jìn)以及蟻群算法在航海上的應(yīng)用等方面，最后將蟻群算法在航海領(lǐng)域中的研究問題和未來研究方向進(jìn)行了總結(jié)，對從事船舶路徑規(guī)劃和船舶自動避碰等問題的學(xué)者來講，具有重要參考價值．
關(guān)鍵詞:蟻群算法;路徑規(guī)劃;自動避碰
在計算機(jī)技術(shù)飛速發(fā)展的21世紀(jì)，隨著科技的成熟，人類正朝著智能化、機(jī)械化、自動化穩(wěn)步邁進(jìn)，無人車、無人飛機(jī)、無人船等紛紛問世．隨著海運(yùn)強(qiáng)國戰(zhàn)略的實施，航運(yùn)事業(yè)飛速發(fā)展，近年來涌現(xiàn)出一大批專家和學(xué)者，圍繞無人駕駛船舶路徑規(guī)劃和航線自動生成等問題展開研究．在此之前，機(jī)器人路徑規(guī)劃技術(shù)已經(jīng)趨于成熟，鑒于機(jī)器人路徑規(guī)劃與無人駕駛船舶路徑規(guī)劃、航線自動生成的相似性，例如遺傳算法、人工勢場算法、粒子群優(yōu)化算法、蟻群算法等，都可以應(yīng)用于無人駕駛船舶路徑規(guī)劃或船舶航線自動生成等航海問題．蟻群算法因其強(qiáng)大的魯棒性，廣泛的適用性，優(yōu)良的分布式計算以及與其他算法的簡單組合而得到廣泛應(yīng)用．其他學(xué)者大多寫蟻群算法在非航海方面的應(yīng)用，并無學(xué)者將蟻群算法在航海上的應(yīng)用總結(jié)出來，本文將蟻群算法在航海方面的應(yīng)用(如無人船路徑規(guī)劃、潛艇導(dǎo)航規(guī)劃、船舶避碰規(guī)劃等)以及研究中發(fā)現(xiàn)的問題和未來研究方向總結(jié)出來，對從事無人駕駛船舶路徑規(guī)劃或船舶航線自動生成等與航海相關(guān)的學(xué)者來講具有參考價值．
1蟻群算法的算法原理
蟻群算法(antcolonyoptimization，ACO)，又稱螞蟻算法或蟻群優(yōu)化算法，是由意大利學(xué)者M(jìn)arcoDorigo等人于1991年在法國巴黎召開的第一屆歐洲人工生命會議(EuropeanConferenceonArtificialLife，ECAL)上提出［1］．然而，截至1996年，它一直沒有引起國內(nèi)外學(xué)者的廣泛關(guān)注，直到后來MarcoDorigo又發(fā)表了“Antsystem:optimizationbyacolonyofcooperationagents”這篇文章，蟻群算法這才引起了學(xué)術(shù)界的關(guān)注．
1．1蟻群行為描述仿生學(xué)家通過對螞蟻生活習(xí)性的長期觀察，發(fā)現(xiàn)螞蟻并不像其他動物那樣擁有視覺，且個體螞蟻的智慧并不高，然而，群體螞蟻在尋找食物的過程中尋找路徑的行為反映出了高度組織的結(jié)構(gòu)化．該研究發(fā)現(xiàn)，在覓食的過程中，螞蟻會分泌一種特殊的化學(xué)信息素，螞蟻通過這些信息素傳遞信息，協(xié)同合作，形成集體自催化行為，然后找到從蟻巢到食物來源的最短路徑［2］．螞蟻選擇特定路徑的趨勢與發(fā)現(xiàn)的路徑上的信息素濃度正相關(guān)，即通過路徑的螞蟻越多，螞蟻留下的信息越多，道路上存在的信息素濃度就越大，其他螞蟻選擇這條道路的可能性就越大．在尋找食物的過程中，螞蟻尋找路徑的這種行為形成了積極的正反饋機(jī)制［2］．由于信息素的濃度隨時間逐漸降低，因此路徑越長，信息素的濃度越小．圖1是自然界螞蟻的覓食原理［3］．A為食物源，D為蟻巢，B和C為障礙物的端點(diǎn)．如圖(a)所示，在通往食物源的途中，如果沒有障礙物，螞蟻將始終選擇最短的路徑．如圖(b)所示，如果蟻巢和食物源之間存在障礙物，螞蟻將以相同的概率選擇DBA和DCA路徑．如圖(c)所示，因為路徑DCA的長度小于路徑DBA，所以等時通過路徑DCA的螞蟻比通過路徑DBA的螞蟻多．然后，螞蟻在DCA上分泌的信息素濃度高于螞蟻在DBA上分泌的信息素濃度．后續(xù)螞蟻就傾向于選擇路徑DCA．如圖(d)所示，最終螞蟻都會選擇路徑DCA，蟻群正是通過這種方法，才用最短的路徑尋找到了食物源．
1．2基本蟻群算法的數(shù)學(xué)模型本文借助于經(jīng)典的旅行商問題(TravelingSalesmanProblem，TSP)，對基本蟻群算法的數(shù)學(xué)模型進(jìn)行說明．即人工螞蟻k(k=1，2，3，…，m)從n個城市中任選一個作為起點(diǎn)，隨機(jī)前往下一個城市，中途不能折回，一個城市不能重復(fù)走過，最后返回起點(diǎn)，最終找到一條最短的路徑．為了確保螞蟻k不重復(fù)經(jīng)過一個城市，這里用禁忌表tabuk(k=k=1，2，3，…，m)記錄螞蟻k當(dāng)前走過的城市，則人工螞蟻t時刻從一個城市i到另外一個城市j的轉(zhuǎn)移概率為:式中，α為信息啟發(fā)式因子，表示軌跡的相對重要程度，其值越大，其他螞蟻選擇該路徑的可能性越大;β為期望啟發(fā)式因子，表示能見度的相對重要程度，其值越大，其他螞蟻選擇該路徑的可能性越大．τis(t)為t時刻城市i到城市j路徑上存在的信息量，ηis(t)為t時刻螞蟻從城市i到城市j的期望程度，且，ηis(t)越小，pkij(t)就越小，即轉(zhuǎn)移概率就越小．為了避免殘留信息素淹沒啟發(fā)信息，需要對殘留信息素進(jìn)行更新處理，t+n時刻，路徑(i，j)上的信息素調(diào)整為:式中，1－ρ為信息素殘留因子，且ρ［0，1］;Δτijk(t)表示第k只螞蟻在路徑(i，j)上留下的信息量;Δτij(t)表示循環(huán)結(jié)束后路徑(i，j)上信息素的增加量;Q表示信息素強(qiáng)度;Lk表示第k只螞蟻在本次循環(huán)中行走的路徑長度．
1．3基本蟻群算法的程序結(jié)構(gòu)流程以旅行商問題為例，基本蟻群算法的程序結(jié)構(gòu)流程如圖2所示:
2蟻群算法的改進(jìn)
盡管蟻群算法具有許多優(yōu)點(diǎn)，但必須考慮其存在的缺陷．蟻群算法需要花費(fèi)大量時間進(jìn)行計算，搜索速度太慢，算法收斂時間太長．啟發(fā)式因子α，預(yù)期啟發(fā)式因子β，信息素強(qiáng)度Q，信息素?fù)]發(fā)因子ρ等參數(shù)的設(shè)置均基于經(jīng)驗，沒有足夠的理論依據(jù)［4］．為了解決這方面的問題，國內(nèi)的段海濱、高尚、孫燾、丁建立、陳崚、楊勇、汪鐳等，國外的GutjahrWJ、MarcoDorigo、StützleT、HouYH、YooJH、BadrA等許多學(xué)者對蟻群算法的方法或模型或策略進(jìn)行了改進(jìn)．在一定程度上，減少了蟻群算法的計算時間，提高了收斂速度，避免了局部最優(yōu)．StützleT和HolgerHoos在1997年提出了最大－最小螞蟻系統(tǒng)［5］(MAX-MINAntSystem，MMAS)，MMAS是一種基于協(xié)同搜索的元啟發(fā)式算法，它改進(jìn)了傳統(tǒng)的蟻群算法(AntSystem，AS)，為組合優(yōu)化問題的解決方案提供了自適應(yīng)框架．MMAS在每次迭代中僅允許最佳的螞蟻更新路徑信息素強(qiáng)度，并且信息素強(qiáng)度在所有路徑上初始化為最大值τmax．在每次迭代之后，僅允許最佳路徑的信息素保持在較高水平，而其他路徑上的信息素將隨時間逐漸揮發(fā)．信息素的揮發(fā)使信息素強(qiáng)度降低一個因子，導(dǎo)致更少的后續(xù)螞蟻選擇這條路徑，信息素強(qiáng)度持續(xù)降低．如果不及時處理，信息素的強(qiáng)度將降至零，為此需要設(shè)置信息素的強(qiáng)度不能低于一個最小值τmin．換句話說，需要將信息素的強(qiáng)度τ設(shè)置為τmin≤τ≤τmax．這種處理方法有效地克服了蟻群算法容易出現(xiàn)停滯現(xiàn)象的缺陷，但是最大－最小螞蟻系統(tǒng)每一步搜索結(jié)束之后都要對所有路徑上的信息素進(jìn)行實時更新，導(dǎo)致消耗大量的時間．此外許多參數(shù)(如τmax、τmin等)的設(shè)置仍然憑借經(jīng)驗，沒有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明作為理論依據(jù)．StützleT和HolgerHoos在2000年發(fā)表了《MAX-MINAntSystem》對最大－最小螞蟻系統(tǒng)進(jìn)行了改進(jìn)—信息素平滑處理［6］．當(dāng)MMAS搜索停止時，比較每條路徑的信息素差值，并且當(dāng)差異大時，對每條路徑的信息素強(qiáng)度進(jìn)行加權(quán)平均．加權(quán)平均后每條路徑的信息素間隙減小，有利于生成新的搜索路徑，但算法的搜索效率會較慢．楊延慶等［7］從信息素τ的限制、信息素的更新方式兩方面對最大－最小螞蟻系統(tǒng)進(jìn)行了改進(jìn)，將傳統(tǒng)最大－最小螞蟻系統(tǒng)的信息素強(qiáng)度τ設(shè)置為固定值，可在一定程度上提高計算效率．另外，在完成每個循環(huán)之后，MMAS對各條路徑長度進(jìn)行加和平均，路徑長度小于平均值，則基于原始信息素強(qiáng)度適當(dāng)增強(qiáng)．相反，如果路徑長度大于平均值，則基于原始信息素強(qiáng)度適當(dāng)減弱;最短路徑上的信息素和螞蟻行進(jìn)的最遠(yuǎn)路徑被更新，而另一條路徑上的信息素不被處理．然而，由于信息素隨時間揮發(fā)，因此最短路徑上的信息素與最遠(yuǎn)路徑之間的差異增大，從而提高了算法的搜索效率．王勝等［8］通過禁忌策略改進(jìn)蟻群算法，避免局部最短路徑中的蟻群停滯．由于缺乏參數(shù)的自適應(yīng)調(diào)整策略，需要改進(jìn)算法旅行商問題的尋優(yōu)能力．張軍英等人［9］從城市選擇策略的參數(shù)選擇，信息量更新方式和局部搜索策略等方面對蟻群算法進(jìn)行了改進(jìn)．改進(jìn)的算法加速了算法的收斂，降低了早熟收斂和搜索停滯的可能性．段海濱等人［10］提出利用云模型理論實現(xiàn)蟻群算法，避免了在大搜索空間條件下出現(xiàn)局部最優(yōu)解，能夠更快地找到全局最優(yōu)解．GambardellaLM等［11］在1999年提出了多重蟻群算法(MultipleAntColonySystem，MACS)的概念，并利用該算法解決了多目標(biāo)優(yōu)化問題，大大降低了最優(yōu)解的求解速率．CSolnon［12］提出了Ant-P-solver，這是一種基于蟻群優(yōu)化的元啟發(fā)式算法，通過與本地搜索技術(shù)相結(jié)合求解約束滿足問題(ConstraintSatisfactionProblem，CSP)，將問題建模為在圖中搜索最佳路徑，人工螞蟻以隨機(jī)的方式走過該圖，人工螞蟻通過在圖的邊緣釋放信息素進(jìn)行通信，尋找最優(yōu)路徑．DGaertner和KLClark［13］使用遺傳算法(GeneticAlgorithms，GA)的思想修改了ACO實例，以形成遺傳基因改進(jìn)的蟻群系統(tǒng)(GeneticallyModifiedAntColonySystem，GMACS)．在該算法中，每個螞蟻用隨機(jī)參數(shù)組合初始化，其中參數(shù)值從合理范圍中選擇．隨著時間的推移，螞蟻的數(shù)量不斷增加，使用更好的參數(shù)組合培育螞蟻，從而找到改進(jìn)的解決旅行商問題實例的方案．
3蟻群算法在航海上的應(yīng)用
自1991年引入蟻群算法以來，許多學(xué)者積極探索并大膽嘗試，在蟻群算法研究方面取得重大進(jìn)展和突破．如旅行商問題、指派問題(QuadraticAssignmentProblem，QAP)、序列排序問題(SequentialOrderingProblem，SOP)、圖形著色問題(GraphColoringProblem，GCP)、車輛路徑問題(VehicleRoutingProblem，VRP)、車間作業(yè)調(diào)動問題(Job-shopScheduleProblem，JSP)、以及網(wǎng)絡(luò)路由問題(QuantityofService，QoS)、線性系統(tǒng)參數(shù)辨識問題、最優(yōu)PID控制問題、故障診斷問題、圖像處理、聚類分析、數(shù)據(jù)挖掘、航跡規(guī)劃、空戰(zhàn)決策、巖土工程問題(如邊坡非圓弧臨界滑動面搜索問題)、化學(xué)工業(yè)問題(如2－氯苯酚在超臨界水中氧化反應(yīng)動力學(xué)參數(shù)估計問題)、生命科學(xué)問題(如蛋白質(zhì)折疊問題)、機(jī)器人路徑規(guī)劃問題、無人駕駛車輛路徑規(guī)劃、無人機(jī)路徑規(guī)劃等．蟻群算法在這些方面的應(yīng)用前人多有闡述，本文重點(diǎn)闡述蟻群算法在航海領(lǐng)域的應(yīng)用，如無人船路徑規(guī)劃、無人水下航線器路徑規(guī)劃、船舶航線自動設(shè)計、潛艇導(dǎo)航規(guī)劃、船舶避碰規(guī)劃等．何立居，李啟華［14］以電子海圖顯示和信息系統(tǒng)為基礎(chǔ)，采用前向策略和后向策略作為搜索策略．蟻群算法從海域網(wǎng)格劃分，網(wǎng)格點(diǎn)信息素，信息素更新，搜索策略，路徑選擇和路徑平滑等方面進(jìn)行了改進(jìn)．通過實例證明了蟻群算法用于航線自動生成的可行性．劉利強(qiáng)［15］提出了一種改進(jìn)的基于協(xié)同和空間收縮的蟻群優(yōu)化算法，以及一種改進(jìn)的連續(xù)域蟻群優(yōu)化算法，具有收斂速度快，搜索能力強(qiáng)的特點(diǎn)．采用空間網(wǎng)格法模擬三維空間環(huán)境，為潛艇進(jìn)行三維空間導(dǎo)航．陳曉等［16］利用構(gòu)造自由空間的Maklink圖論法對海圖進(jìn)行預(yù)處理，生成無向網(wǎng)絡(luò)圖，接著采用動態(tài)規(guī)劃Dijkstra算法生成初始路徑，最后用蟻群算法進(jìn)行路徑優(yōu)化．這與在傳統(tǒng)的紙質(zhì)海圖上手繪航線或者在電子海圖顯示與信息系統(tǒng)(ElectronicChartDisplayandInformationSystem，ECDIS)中輸入航路點(diǎn)生成航線相比，能夠節(jié)省較多時間，給船員減輕了負(fù)擔(dān)，但是由于沒有考慮到動態(tài)障礙物避險以及風(fēng)、浪、流等自然因素的影響，有待進(jìn)一步研究．趙紅［17］將人工勢場法與蟻群算法相結(jié)合，形成了一種用于波浪動態(tài)滑翔機(jī)路徑規(guī)劃的勢場蟻群算法．在基于改進(jìn)勢場蟻群算法的波浪動態(tài)滑翔機(jī)路徑規(guī)劃仿真實驗中，文獻(xiàn)考慮了導(dǎo)航過程中的動態(tài)障礙，以及波浪、海流等自然因素的影響，設(shè)置了波浪權(quán)重和水下海流權(quán)重等海洋環(huán)境參數(shù)．該方法提高了算法全局優(yōu)化的能力，提高了波動力滑翔機(jī)的導(dǎo)航速度，縮短了波動力滑翔機(jī)的行駛時間．最重要的是使波動滑翔機(jī)能夠成功避開動態(tài)障礙物并產(chǎn)生了一條安全的最短路徑．陳立家等［18］論述了基于電子海圖的在多約束條件下(風(fēng)浪、水深、船速、航行費(fèi)用等)綜合成本最低的最優(yōu)航線生成算法(optimalroutegenerationAlgorithm，ORGA)．基于航線網(wǎng)絡(luò)圖，該算法使用Dijkstra算法找到最短路徑，并使用改進(jìn)的蟻群算法找到最優(yōu)路徑．該算法提高了搜索效率，可以更快地找到最佳路徑．朱青［19］介紹了基于分布均勻性的自適應(yīng)蟻群算法，利用連接圖法(Maklink方法)動態(tài)調(diào)整信息素更新策略和狀態(tài)轉(zhuǎn)移概率，來解決算法收斂速度慢和早熟收斂的現(xiàn)象．最后，平滑路線以獲得最佳路徑．張金水等［20］將遺傳算法與蟻群算法向融合，以獲取最優(yōu)航線．先用蟻群算法產(chǎn)生航線初始種群，然后用遺傳算法對之前產(chǎn)生的航線初始種群進(jìn)行遺傳操作—選擇、交叉、變異、刪除［21］，得到最優(yōu)航線．AgnieszkaLazarowska［22］介紹了在導(dǎo)航?jīng)Q策支持系統(tǒng)(DecisionSupportSystem，DSS)中使用蟻群優(yōu)化技術(shù)的智能應(yīng)用程序，以及在導(dǎo)航DSS中實現(xiàn)的ACO原理和基于ACO的算法，開發(fā)的導(dǎo)航DSS體系結(jié)構(gòu)以及路徑規(guī)劃和避碰問題等．該系統(tǒng)解決問題的能力包括在公海和限制水域中的船舶的路徑規(guī)劃和船舶避碰，增強(qiáng)了船舶安全控制過程的自動化程度．JBEscario［23］基于細(xì)胞自動機(jī)(CellularAutomata)和改進(jìn)蟻群優(yōu)化算法給自動船舶操縱進(jìn)行最優(yōu)或次優(yōu)路徑規(guī)劃．細(xì)胞自動機(jī)是對的連續(xù)搜索空間進(jìn)行粗略的離散化，并提供推薦的船舶姿態(tài)的集合，而沒有任何明確的船舶動力學(xué)參考．考慮到船舶動力學(xué)所施加的限制，這些姿態(tài)將成為蟻群算法計算連續(xù)軌跡的起點(diǎn)而提出的改進(jìn)蟻群優(yōu)化算法，則是用來處理具有動態(tài)特征的“螞蟻”(船只)，最終達(dá)到給自動船舶操縱進(jìn)行最優(yōu)或次優(yōu)路徑規(guī)劃的目的．國內(nèi)外眾多學(xué)者利用蟻群算法，圍繞船舶路徑規(guī)劃與優(yōu)化、船舶避碰、波浪動態(tài)滑翔機(jī)路徑規(guī)劃、潛艇導(dǎo)航規(guī)劃等航海領(lǐng)域展開研究，取得了不錯的成績，但是蟻群算法在數(shù)學(xué)上缺少嚴(yán)謹(jǐn)?shù)目煽啃缘睦碚撟C明，且很多參數(shù)的設(shè)置都是憑借經(jīng)驗，沒有理論依據(jù)，再加上蟻群優(yōu)化算法本身原理機(jī)制復(fù)雜，編程代碼復(fù)雜，實現(xiàn)難度較大．
4結(jié)論
隨著航運(yùn)事業(yè)蓬勃發(fā)展，蟻群算法在航海領(lǐng)域的應(yīng)用更有待挖掘，船舶路徑規(guī)劃和船舶自動避碰等航海領(lǐng)域問題需要進(jìn)一步深入研究．為了給后續(xù)學(xué)者提供研究思路，特將研究中發(fā)現(xiàn)的問題總結(jié)如下:(1)海洋環(huán)境復(fù)雜多變，用柵格法、拓?fù)浞āaklink圖論法等對環(huán)境進(jìn)行處理后，與真實環(huán)境存在差距，真實性和可靠性有待提高．環(huán)境建模多采用柵格法，建模后的分辨率大小問題也要考慮，如何采用動態(tài)柵格，是一種研究思路．(2)島嶼、暗礁、淺水區(qū)等航行過程中必須考慮的因素的處理方法有待改進(jìn)．對這些因素進(jìn)行膨化處理的尺度很難把控，膨化過大，設(shè)計出來的航線可能不是最優(yōu)航線，膨化過小可能存在安全隱患．(3)航線路徑規(guī)劃多針對靜態(tài)環(huán)境(理想環(huán)境)，動態(tài)環(huán)境下，尤其是復(fù)雜動態(tài)環(huán)境下(風(fēng)浪流等)，進(jìn)行航線規(guī)劃難度較大．
作者：張文拴 徐海軍 閆哲 單位：大連海事大學(xué)
