蚁群算法在岛礁补给路径规划中的应用*

邓南明 王 栋 熊乾坤

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



蚁群算法在岛礁补给路径规划中的应用*

邓南明1王 栋2熊乾坤1

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

派遣人员驻扎岛礁对维护我国海洋主权具有十分重要的意义，而岛礁通常远离大陆，上面物资匮乏，必须要定期由大陆派遣补给舰(船)对其进行物资补给，我国岛礁数量众多，岛礁补给路径规划问题易于描述却难于求解，采用传统的最优路径规划计算方法，需要进行大量的计算，而蚁群算法是求解最短路径的有效方法，文章描述了岛礁补给最优路径规划问题，论证了利用最短长度作为最优指标的合理性，然后利用蚁群算法进行岛礁补给路径的规划。仿真结果证明，蚁群算法可以高效地解决岛礁最优路径规划问题。

蚁群算法; 岛礁补给; 路径规划

Class Number TP301.6

1 引言

我国海岸线长达3.2万千米，具有300多万平方千米的海洋面积，海洋面积相当于我国陆地面积的三分之一。在这广阔的海域上，面积大于500平米的岛屿有6500多个，我国南沙群岛有235个岛、礁、沙、滩，其中约有11个岛屿、5个沙洲和20个岛礁露出水面，可以安排人员驻扎[1]。目前，国家之间的海洋主权争夺异常激烈，一个国家或者地区要想拥有某个岛礁的主权，也就是想拥有岛礁的最高权利，包括所有权、使用权、占有权、控制权、收益权等，仅仅宣示是不够的，它必须能够实际占领、控制和管辖，否则仍将不断受到威胁和挑战，甚至可以说，海洋主权就是国家依靠武力对海洋实际占领、控制和管辖形成的。要进行实际的占领就必须派遣人员配备相应装备进行驻扎，而岛礁上物资匮乏，不仅仅装备所需的某些备品备件、维护主权所需的武器弹药等需要定期补给，就连人员日常生活所需的淡水，食品等基本生活物资可能都需要按时补给，由于岛礁通常远离大陆，其补给物资运输主要依靠补给舰(船)从港口运送过来，一艘补给舰(船)对多个岛屿进行补给，可以有多种路径，路径的好坏直接决定了补给的运输成本与效率，寻找一条最优的补给舰(船)航行路径，具有较大的现实意义与经济效益，而蚁群优化算法是一种元启发式的随机搜索技术，是目前解决组合优化问题最有效的工具之一，是求解最优路径的一种较好的方法，而岛礁补给最优路径规划实际上就是一个典型组合优化问题，易于描述却难于求解[2]，本文便基于蚁群算法对岛礁补给最优路径规划进行研究。

2 岛礁补给最优路径规划问题描述

一次完整的岛礁补给任务可以描述为:补给舰(船)按照固定计划，从港口装好物资出发，对多个岛礁进行补给，然后返回港口。一艘补给舰(船)对多个岛屿进行补给，可以有多种路径，不同的航行路径可能长度不同[3]，通常补给舰(船)的航速与在每个岛礁停留时间是一定的，路径长短直接决定了完成整个补给任务的时间，也可以称之为补给效率，同时也决定了补给所耗费的航行成本，航行路径最短可以实现补给任务完成时间最短，航行耗费的成本最低，具有较大的现实意义与较好的经济效益。所以文章选用路径长度最短作为岛礁补给路径规划的最优指标。

岛礁补给通常依靠补给舰(船)对其上面的装备、油料、食品以及淡水等进行补给。例如我国南沙群岛有n个岛礁派遣人员驻扎，其物资补给由海南某基地负责，该基地每隔固定时间派遣一艘补给舰(船)从某港口出发对所负责岛礁进行补给，以每一个岛礁作为一个访问地点，设连续访问两个岛礁之间的路径长度为lf(f=1,2,…,n+1)，该补给舰(船)的航行路径可以有n!种方案，且一次完整的补给任务，补给舰(船)访问每个岛礁的次数有且仅有一次，任意一种方案的路径长度均可描述为：

(1)

L的结果最多有n!种可能，最优路径规划的目的是在n!种结果中求取L的最小值，即最短路径长度，所以岛礁补给路径规划问题的实质就是求解L的最小值。

3 蚁群算法简介

意大利学者Mr.Dorigo发现蚂蚁在觅食时过程中会通过分泌信息素交流觅食信息，达到快速找到实物的目的，据此提出了一种利用信息正反馈的进化算法，即蚁群算法[4]。蚁群算法的基本思想是，蚂蚁从蚁穴出发进行觅食活动，当找到食物后会往返蚁穴与食物之间进行食物搬运工作，在其行走的路径上会分泌信息素，使得一定范围内的其他蚂蚁能够感受到信息素的存在而被吸引过来[5]。单只蚂蚁在某个地点上的信息素会随着时间推移挥发，强度会逐渐减弱，因而蚂蚁走的路程越短，则其信息素更新越快，信息素浓度越高，信息素浓度越高就会吸引更多的蚂蚁过来，当一些路径上的通过的蚂蚁越来越多时，留下的信息素也会越来越多，浓度会不断加大，最终所有蚂蚁都会选择信息浓度最强的路径，该路径也是最短路径[6]。另外，蚂蚁选择信息素浓度较高的路线时，可能会发生另辟蹊径的情况，也就是可能会发生新路线的探索行为，假如探索过程中发现了更短的路径，那么更多的蚂蚁就会被吸引过去，这样就可以避免局部最优解，达到寻找到蚁穴与食物之间的最短路径的目的[7]。

(2)

式中，Ik为蚂蚁需访问而未访问的地点集合，初始时刻Ik中有n-1个元素，随着时间的推移，Ik中的元素数量会越来越少，直至元素个数为0。α为信息素强度影响因子，其值越大代表信息素强度的影响越大[8]。β为想法强度影响因子，其值越大代表想法强度的影响越大。在蚂蚁行走的过程中，蚂蚁释放信息素的同时，信息素也在挥发，为了描述信息素的挥发情况，定义挥发因子ρ(0<ρ<1)来表示信息素挥发程度，则蚂蚁遍历所有地点后，各地点相连路径的信息素浓度可表示为[9]

(3)

式中，Δτij为所有蚂蚁在地点i与地点j连接路径上释放信息素所增加的浓度。

4 蚁群算法进行路径规划的流程

步骤1：计算各访问地点的距离。根据平面几何中两点距离公式，利用各地点的坐标计算出任意两个访问地点之间的距离。

步骤2：参数初始化。涉及的参数主要有蚂蚁数量m，信息素因子α，想法强度因子β，信息素挥发因子ρ，信息素强度Q，最大迭代次数等。这些参数的设定对结果的都有一定的影响，选择合适的参数非常重要。根据经验，通常设蚂蚁数量m为访问地点数量的1.5倍，信息素因子α取值在[1,4]范围内取值，想法强度因子在[3,4.5]范围内取值，挥发因子ρ在[0.2,0.5]范围内取值，Q在[10,1000]范围内取值，最大迭代次数在[100,500]范围内取值时可以获得较好的综合性能[10]。

步骤3：随机将蚂蚁放置于不同的地点，对蚂蚁计算其下一个访问地点，直至所有蚂蚁访问完所有地点。

步骤4：计算各个蚂蚁行走的路径长度，记录当前迭代结果中的最优解，同时对路径上信息素浓度进行更新。

步骤5：是否迭代完毕，若没有则重复执行步骤2。

步骤6：得到最优路径结果。

5 岛礁补给最优路径规划仿真

假设我国某海域有29个岛礁派驻了人员，其物资由某基地负责，该基地补给舰(船)出发港口位置坐标为(35,319)，设置其位置序号为1，29个岛礁与港口的分布图如图1所示，在该图中，各岛礁的坐标数据如表1所示。

表1 岛礁序号及坐标

如果采取传统的计算方法，即分别求出所有29!种结果，再求取其最小值，然后利用最小值对应访问岛礁顺序作为路径规划结果，需要迭代8.8418×1030次，L就有8.8418×1030种结果，然后再在里面寻找L最小值，计算量相当大。

图1 岛礁分布图

为验证蚁群算法在求解岛礁补给最优路径规划问题中的性能，笔者采用配置为：intel E6500CPU，4G内存，操作系统为Windows 7，软件平台为Matlab2013a，进行了模拟仿真试验。试验中根据蚁群算法路径规划的经验，设置初始化参数如下：蚂蚁数量m=45，信息素因子α=1，想法强度因子β=5，信息素挥发因子ρ=0.2，信息素强度Q=10，最大迭代次数为200次。

图2 航行补给最优路径线路图

经多次仿真得到最优补给路径的线路图均如图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)。每次仿真的收敛迭代次数与运行时间均有所不同，分别有收敛迭代次数为87次，程序运行时间29.546s，收敛迭代次数130，程序执行时间:25.694s等结果。由此可见蚁群算法执行相对于传统的最优路径计算方法，具有执行效率高计算量小的优点。但是也可以看出蚁群算法虽然初始参数不变，但是求解性能不一致的特点。

6 结语

论文针对岛礁补给路径规划问题，基于最短路径长度的原则，采用蚁群算法对其进行求解计算。通过仿真结果可见，蚁群算法是解决岛礁补给最优路径规划问题的有效方法，而且相对于传统的最短路径计算方法，具有更高的计算效率，能在较短的时间内，通过较小的计算量获得最优路径。但是也可以看到蚁群算法的不足，其初始参数设置对经验依赖性较大，参数设置存在一定的主观性，后续将开展蚁群算法与其它算法相结合，加强对蚁群算法参数调优的研究，进一步提高算法的性能，增强其实用性，创造更好的经济效益。该路径规划方法不仅可以用于补给舰补给岛礁的路径规划，还可以应用于无人平台、飞机等装备的最优路径规划。

[1] 董丽娃,李增刚.无政府状态下的产权形成与保护——兼论中国海洋权益维护[J].理论学刊,2011(12):48-52.

[2] 宗德才,王康康,丁勇.蚁群算法求解旅行商问题综述[J].计算机与数字工程,2014(11):2004-2013.

[3] 余鹏,何学军.基于蚁群算法的舰艇编队海上补给路径规划方法[J].海军工程大学学报,2014(2):108-112.

[4] 张琦,马家辰,谢玮,等.基于改进蚁群算法的移动机器人路径规划[J].东北大学学报(自然科学版),2013(11):1521-1524.

[5] 郭平,鄢文晋.基于TSP问题的蚁群算法综述[J].计算机科学,2007(10):181-184,194.

[6] 李勇,段正澄.动态蚁群算法求解TSP问题[J].计算机工程与应用,2003(17):103-106.

[7] 喻剑,佘湖清.蚁群算法在水下滑翔器航路规划中的应用[J].水雷战与舰船防护,2009(1):1-4.

[8] 方文超.基于改进蚁群算法的物流配送优化研究[J].渤海大学学报(哲学社会科学版),2014(6):74-77.

[9] 马文龙,王铮,赵燕伟.基于改进蚁群算法的制造云服务组合优化[J].计算机集成制造系统,2016(1):113-121.

[10] 卓金武.MATLAB在数学建模中的应用(第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

熊乾坤，男，硕士，工程师，研究方向：水下装备试验总体技术。