蟻群算法在島礁補給路徑規(guī)劃中的應用*

鄧南明 王 棟 熊乾坤

(1.91388部隊 湛江 524022) (2.92326部隊 湛江 524005)

?

蟻群算法在島礁補給路徑規(guī)劃中的應用*

鄧南明1王 棟2熊乾坤1

(1.91388部隊 湛江 524022) (2.92326部隊 湛江 524005)

派遣人員駐扎島礁對維護我國海洋主權具有十分重要的意義，而島礁通常遠離大陸，上面物資匱乏，必須要定期由大陸派遣補給艦(船)對其進行物資補給，我國島礁數(shù)量眾多，島礁補給路徑規(guī)劃問題易于描述卻難于求解，采用傳統(tǒng)的最優(yōu)路徑規(guī)劃計算方法，需要進行大量的計算，而蟻群算法是求解最短路徑的有效方法，文章描述了島礁補給最優(yōu)路徑規(guī)劃問題，論證了利用最短長度作為最優(yōu)指標的合理性，然后利用蟻群算法進行島礁補給路徑的規(guī)劃。仿真結果證明，蟻群算法可以高效地解決島礁最優(yōu)路徑規(guī)劃問題。

蟻群算法; 島礁補給; 路徑規(guī)劃

Class Number TP301.6

1 引言

我國海岸線長達3.2萬千米，具有300多萬平方千米的海洋面積，海洋面積相當于我國陸地面積的三分之一。在這廣闊的海域上，面積大于500平米的島嶼有6500多個，我國南沙群島有235個島、礁、沙、灘，其中約有11個島嶼、5個沙洲和20個島礁露出水面，可以安排人員駐扎[1]。目前，國家之間的海洋主權爭奪異常激烈，一個國家或者地區(qū)要想擁有某個島礁的主權，也就是想擁有島礁的最高權利，包括所有權、使用權、占有權、控制權、收益權等，僅僅宣示是不夠的，它必須能夠?qū)嶋H占領、控制和管轄，否則仍將不斷受到威脅和挑戰(zhàn)，甚至可以說，海洋主權就是國家依靠武力對海洋實際占領、控制和管轄形成的。要進行實際的占領就必須派遣人員配備相應裝備進行駐扎，而島礁上物資匱乏，不僅僅裝備所需的某些備品備件、維護主權所需的武器彈藥等需要定期補給，就連人員日常生活所需的淡水，食品等基本生活物資可能都需要按時補給，由于島礁通常遠離大陸，其補給物資運輸主要依靠補給艦(船)從港口運送過來，一艘補給艦(船)對多個島嶼進行補給，可以有多種路徑，路徑的好壞直接決定了補給的運輸成本與效率，尋找一條最優(yōu)的補給艦(船)航行路徑，具有較大的現(xiàn)實意義與經(jīng)濟效益，而蟻群優(yōu)化算法是一種元啟發(fā)式的隨機搜索技術，是目前解決組合優(yōu)化問題最有效的工具之一，是求解最優(yōu)路徑的一種較好的方法，而島礁補給最優(yōu)路徑規(guī)劃實際上就是一個典型組合優(yōu)化問題，易于描述卻難于求解[2]，本文便基于蟻群算法對島礁補給最優(yōu)路徑規(guī)劃進行研究。

2 島礁補給最優(yōu)路徑規(guī)劃問題描述

一次完整的島礁補給任務可以描述為:補給艦(船)按照固定計劃，從港口裝好物資出發(fā)，對多個島礁進行補給，然后返回港口。一艘補給艦(船)對多個島嶼進行補給，可以有多種路徑，不同的航行路徑可能長度不同[3]，通常補給艦(船)的航速與在每個島礁停留時間是一定的，路徑長短直接決定了完成整個補給任務的時間，也可以稱之為補給效率，同時也決定了補給所耗費的航行成本，航行路徑最短可以實現(xiàn)補給任務完成時間最短，航行耗費的成本最低，具有較大的現(xiàn)實意義與較好的經(jīng)濟效益。所以文章選用路徑長度最短作為島礁補給路徑規(guī)劃的最優(yōu)指標。

島礁補給通常依靠補給艦(船)對其上面的裝備、油料、食品以及淡水等進行補給。例如我國南沙群島有n個島礁派遣人員駐扎，其物資補給由海南某基地負責，該基地每隔固定時間派遣一艘補給艦(船)從某港口出發(fā)對所負責島礁進行補給，以每一個島礁作為一個訪問地點，設連續(xù)訪問兩個島礁之間的路徑長度為lf(f=1,2,…,n+1)，該補給艦(船)的航行路徑可以有n!種方案，且一次完整的補給任務，補給艦(船)訪問每個島礁的次數(shù)有且僅有一次，任意一種方案的路徑長度均可描述為：

(1)

L的結果最多有n!種可能，最優(yōu)路徑規(guī)劃的目的是在n!種結果中求取L的最小值，即最短路徑長度，所以島礁補給路徑規(guī)劃問題的實質(zhì)就是求解L的最小值。

3 蟻群算法簡介

意大利學者Mr.Dorigo發(fā)現(xiàn)螞蟻在覓食時過程中會通過分泌信息素交流覓食信息，達到快速找到實物的目的，據(jù)此提出了一種利用信息正反饋的進化算法，即蟻群算法[4]。蟻群算法的基本思想是，螞蟻從蟻穴出發(fā)進行覓食活動，當找到食物后會往返蟻穴與食物之間進行食物搬運工作，在其行走的路徑上會分泌信息素，使得一定范圍內(nèi)的其他螞蟻能夠感受到信息素的存在而被吸引過來[5]。單只螞蟻在某個地點上的信息素會隨著時間推移揮發(fā)，強度會逐漸減弱，因而螞蟻走的路程越短，則其信息素更新越快，信息素濃度越高，信息素濃度越高就會吸引更多的螞蟻過來，當一些路徑上的通過的螞蟻越來越多時，留下的信息素也會越來越多，濃度會不斷加大，最終所有螞蟻都會選擇信息濃度最強的路徑，該路徑也是最短路徑[6]。另外，螞蟻選擇信息素濃度較高的路線時，可能會發(fā)生另辟蹊徑的情況，也就是可能會發(fā)生新路線的探索行為，假如探索過程中發(fā)現(xiàn)了更短的路徑，那么更多的螞蟻就會被吸引過去，這樣就可以避免局部最優(yōu)解，達到尋找到蟻穴與食物之間的最短路徑的目的[7]。

(2)

式中，Ik為螞蟻需訪問而未訪問的地點集合，初始時刻Ik中有n-1個元素，隨著時間的推移，Ik中的元素數(shù)量會越來越少，直至元素個數(shù)為0。α為信息素強度影響因子，其值越大代表信息素強度的影響越大[8]。β為想法強度影響因子，其值越大代表想法強度的影響越大。在螞蟻行走的過程中，螞蟻釋放信息素的同時，信息素也在揮發(fā)，為了描述信息素的揮發(fā)情況，定義揮發(fā)因子ρ(0<ρ<1)來表示信息素揮發(fā)程度，則螞蟻遍歷所有地點后，各地點相連路徑的信息素濃度可表示為[9]

(3)

式中，Δτij為所有螞蟻在地點i與地點j連接路徑上釋放信息素所增加的濃度。

4 蟻群算法進行路徑規(guī)劃的流程

步驟1：計算各訪問地點的距離。根據(jù)平面幾何中兩點距離公式，利用各地點的坐標計算出任意兩個訪問地點之間的距離。

步驟2：參數(shù)初始化。涉及的參數(shù)主要有螞蟻數(shù)量m，信息素因子α，想法強度因子β，信息素揮發(fā)因子ρ，信息素強度Q，最大迭代次數(shù)等。這些參數(shù)的設定對結果的都有一定的影響，選擇合適的參數(shù)非常重要。根據(jù)經(jīng)驗，通常設螞蟻數(shù)量m為訪問地點數(shù)量的1.5倍，信息素因子α取值在[1,4]范圍內(nèi)取值，想法強度因子在[3,4.5]范圍內(nèi)取值，揮發(fā)因子ρ在[0.2,0.5]范圍內(nèi)取值，Q在[10,1000]范圍內(nèi)取值，最大迭代次數(shù)在[100,500]范圍內(nèi)取值時可以獲得較好的綜合性能[10]。

步驟3：隨機將螞蟻放置于不同的地點，對螞蟻計算其下一個訪問地點，直至所有螞蟻訪問完所有地點。

步驟4：計算各個螞蟻行走的路徑長度，記錄當前迭代結果中的最優(yōu)解，同時對路徑上信息素濃度進行更新。

步驟5：是否迭代完畢，若沒有則重復執(zhí)行步驟2。

步驟6：得到最優(yōu)路徑結果。

5 島礁補給最優(yōu)路徑規(guī)劃仿真

假設我國某海域有29個島礁派駐了人員，其物資由某基地負責，該基地補給艦(船)出發(fā)港口位置坐標為(35,319)，設置其位置序號為1，29個島礁與港口的分布圖如圖1所示，在該圖中，各島礁的坐標數(shù)據(jù)如表1所示。

表1 島礁序號及坐標

如果采取傳統(tǒng)的計算方法，即分別求出所有29!種結果，再求取其最小值，然后利用最小值對應訪問島礁順序作為路徑規(guī)劃結果，需要迭代8.8418×1030次，L就有8.8418×1030種結果，然后再在里面尋找L最小值，計算量相當大。

圖1 島礁分布圖

為驗證蟻群算法在求解島礁補給最優(yōu)路徑規(guī)劃問題中的性能，筆者采用配置為：intel E6500CPU，4G內(nèi)存，操作系統(tǒng)為Windows 7，軟件平臺為Matlab2013a，進行了模擬仿真試驗。試驗中根據(jù)蟻群算法路徑規(guī)劃的經(jīng)驗，設置初始化參數(shù)如下：螞蟻數(shù)量m=45，信息素因子α=1，想法強度因子β=5，信息素揮發(fā)因子ρ=0.2，信息素強度Q=10，最大迭代次數(shù)為200次。

圖2 航行補給最優(yōu)路徑線路圖

經(jīng)多次仿真得到最優(yōu)補給路徑的線路圖均如圖2所示。最短路徑長度均為為1602.1247，具體路線為(1，6，7，8，9，10，15，14，16，13，17，18，19，30，29，28，27，26，25，24，23，22，21，20，11，12，5，4，3，2，1)。每次仿真的收斂迭代次數(shù)與運行時間均有所不同，分別有收斂迭代次數(shù)為87次，程序運行時間29.546s，收斂迭代次數(shù)130，程序執(zhí)行時間:25.694s等結果。由此可見蟻群算法執(zhí)行相對于傳統(tǒng)的最優(yōu)路徑計算方法，具有執(zhí)行效率高計算量小的優(yōu)點。但是也可以看出蟻群算法雖然初始參數(shù)不變，但是求解性能不一致的特點。

6 結語

論文針對島礁補給路徑規(guī)劃問題，基于最短路徑長度的原則，采用蟻群算法對其進行求解計算。通過仿真結果可見，蟻群算法是解決島礁補給最優(yōu)路徑規(guī)劃問題的有效方法，而且相對于傳統(tǒng)的最短路徑計算方法，具有更高的計算效率，能在較短的時間內(nèi)，通過較小的計算量獲得最優(yōu)路徑。但是也可以看到蟻群算法的不足，其初始參數(shù)設置對經(jīng)驗依賴性較大，參數(shù)設置存在一定的主觀性，后續(xù)將開展蟻群算法與其它算法相結合，加強對蟻群算法參數(shù)調(diào)優(yōu)的研究，進一步提高算法的性能，增強其實用性，創(chuàng)造更好的經(jīng)濟效益。該路徑規(guī)劃方法不僅可以用于補給艦補給島礁的路徑規(guī)劃，還可以應用于無人平臺、飛機等裝備的最優(yōu)路徑規(guī)劃。

[1] 董麗娃,李增剛.無政府狀態(tài)下的產(chǎn)權形成與保護——兼論中國海洋權益維護[J].理論學刊,2011(12):48-52.

[2] 宗德才,王康康,丁勇.蟻群算法求解旅行商問題綜述[J].計算機與數(shù)字工程,2014(11):2004-2013.

[3] 余鵬,何學軍.基于蟻群算法的艦艇編隊海上補給路徑規(guī)劃方法[J].海軍工程大學學報,2014(2):108-112.

[4] 張琦,馬家辰,謝瑋,等.基于改進蟻群算法的移動機器人路徑規(guī)劃[J].東北大學學報(自然科學版),2013(11):1521-1524.

[5] 郭平,鄢文晉.基于TSP問題的蟻群算法綜述[J].計算機科學,2007(10):181-184,194.

[6] 李勇,段正澄.動態(tài)蟻群算法求解TSP問題[J].計算機工程與應用,2003(17):103-106.

[7] 喻劍,佘湖清.蟻群算法在水下滑翔器航路規(guī)劃中的應用[J].水雷戰(zhàn)與艦船防護,2009(1):1-4.

[8] 方文超.基于改進蟻群算法的物流配送優(yōu)化研究[J].渤海大學學報(哲學社會科學版),2014(6):74-77.

[9] 馬文龍,王錚,趙燕偉.基于改進蟻群算法的制造云服務組合優(yōu)化[J].計算機集成制造系統(tǒng),2016(1):113-121.

[10] 卓金武.MATLAB在數(shù)學建模中的應用(第2版)[M].北京：北京航空航天大學出版社,2014:180-183.

Application of Ant Colony Algorithm in Reefs Supply Path Planning

DENG Nanming1WANG Dong2XIONG Qiankun1

(1. No. 91388 Troops of PLA, Zhanjiang 524022)(2. No. 92326 Troops of PLA, Zhanjiang 524005)

Sending personnel stationed reefs have great significance for maintaining the maritime sovereignty to our country, the reefs are usually far from the mainland,and short of materials,it must be supplied by ship (boat) from the mainland regularly. Our country has many reefs, and reefs supply path planning problem is easy to describe but difficult to solve using traditional method. The ant colony algorithm is an effective method for solving the shortest path, the article describes the reefs supply optimal path planning question and demonstrates the rationality of using minimum length as the best indicatoris, then the ant colony algorithms in used to plan reefs supply path. Simulation results show that ant colony algorithm can efficiently solve reefs optimum path planning.

ant colony algorithm, reefs supply, path planning

2016年5月11日,

2016年6月27日

鄧南明，男，碩士，工程師，研究方向：水下裝備試驗總體技術。王棟，男，工程師，研究方向：裝備維修。

TP301.6

10.3969/j.issn.1672-9730.2016.11.027

熊乾坤，男，碩士，工程師，研究方向：水下裝備試驗總體技術。