鄧南明 王 棟 熊乾坤

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

?

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

鄧南明1王 棟2熊乾坤1

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

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

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

Class Number TP301.6

1 引言

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

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

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

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

(1)

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

3 蟻群算法簡(jiǎn)介

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

(2)

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

(3)

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

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

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

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

步驟3：隨機(jī)將螞蟻放置于不同的地點(diǎn)，對(duì)螞蟻計(jì)算其下一個(gè)訪問地點(diǎn)，直至所有螞蟻訪問完所有地點(diǎn)。

步驟4：計(jì)算各個(gè)螞蟻行走的路徑長(zhǎng)度，記錄當(dāng)前迭代結(jié)果中的最優(yōu)解，同時(shí)對(duì)路徑上信息素濃度進(jìn)行更新。

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

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

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

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

表1 島礁序號(hào)及坐標(biāo)

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

圖1 島礁分布圖

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

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

經(jīng)多次仿真得到最優(yōu)補(bǔ)給路徑的線路圖均如圖2所示。最短路徑長(zhǎng)度均為為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ù)與運(yùn)行時(shí)間均有所不同，分別有收斂迭代次數(shù)為87次，程序運(yùn)行時(shí)間29.546s，收斂迭代次數(shù)130，程序執(zhí)行時(shí)間:25.694s等結(jié)果。由此可見蟻群算法執(zhí)行相對(duì)于傳統(tǒng)的最優(yōu)路徑計(jì)算方法，具有執(zhí)行效率高計(jì)算量小的優(yōu)點(diǎn)。但是也可以看出蟻群算法雖然初始參數(shù)不變，但是求解性能不一致的特點(diǎn)。

6 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

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

[10] 卓金武.MATLAB在數(shù)學(xué)建模中的應(yīng)用(第2版)[M].北京：北京航空航天大學(xué)出版社,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日

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

TP301.6

10.3969/j.issn.1672-9730.2016.11.027

熊乾坤，男，碩士，工程師，研究方向：水下裝備試驗(yàn)總體技術(shù)。