基于遗传算法的远海岛礁补给模型研究*

李 东 滕 哲 张炜灵

（海军大连舰艇学院 大连 116018）

1 引言

我国岛礁众多，面积达500m2以上的岛屿为6500多个，岛礁对于海洋主权意义重大。占领岛礁意味着可以获取所有权、使用权、收益权、控制权等，但是仅仅通过宣示的方式往往是不够的，只有实际占领、控制和管辖才能更好地维护正当权益。要进行岛礁的实际占领就必须派遣人员驻扎，而多数岛礁自然资源匮乏，交通不便，驻扎所需的一切物资几乎全需要依靠外部补给。很多礁距离大陆较远、位置相对分散、靠泊条件各异、物资需求量和储存量各不相同，如何研究制定科学合理、安全高效的物资补给策略，一直是我军后勤保障部门关注的重要课题。

通常情况下，由后勤保障中心根据实际需求，以一个月为一个补给周期，制定补给方案，分别由不同型号的补给船和运输机执行物资补给任务。补给船和运输机都是从物资保障中心出发，为各岛礁运送所需物资，回程运回垃圾及其他材料等。补给方案应当包括补给船（或运输机）种类、补给路线、补给数量、转运方式、物资装卸与回收材料的数量等。

综合考虑上述因素，本文建立了一个数学模型，尝试给出一个补给周期的岛礁物资补给方案。

2 模型基本假设

为了便于问题的研究，对题中某些条件进行合理假设：

1）补给中心及岛礁之间不存在障碍，可沿欧式几何的平面最短路径通行。

2）所有补给船只、飞机及补给设备工作稳定，所有时间内均保持相同航行速度、补给速度。

3）岛礁上需回收的固体不计储存成本。

4）所有补给船只在补给时可以同时补给固体和液体。

5）一个补给周期（一月）时长为30天。

对于模型中将要用到的物理量，定义如表1所示。

表1 模型中的物理量

3 方案建模

本文的课题是研究我补给舰船在某海域岛礁之间的物资补给问题，目的是统筹补给时间、岛礁现状和经济性等多要素，设计一个详实、合理的补给方案。这类问题可以归类为非线性规划问题，但由于数据要素较多，模型复杂，需要在现有理论上开展进一步思考。因此，在广泛查阅了相关参考文献［1～3］基础之上，对问题展开探索。

3.1 分块处理，问题简化

在进行补给方案设计时，应顾及岛屿之间的相对位置、最大储存量、剩余物资量、日消耗量、固体回收量、补给时间、经济成本等，要素多，情况极为复杂，因此首先考虑将问题分块解决。

首先，针对补给的经济情况进行建模。补给开销主要分为岛礁物资储存成本和补给舰船运输成本两方面，设所有岛礁的储存成本总和为E储，所有补给舰船的运输成本总和为E运，补给方案的总开支为E总，则其关系可表示如下：

同样地，可以对液体物资也列出类似公式、进行类似变换，综合起来，可以得到总的岛礁储存成本表达式和单个岛礁的储存成本表达式：

从中可以明显地看出，无论对岛礁补充量如何，只要当补充量不为零时所对应的j越大（即补充时间越迟）时，所得岛礁储存成本越小。

综上，物资储存模型和物资运送模型已经建立，并且对物资储存成本同补给时间的关系进行了探索，推导了补给时间点的一般通式，为下一步优化处理打下了基础。

3.2 问题变换，优化参数

对于岛礁而言，希望尽量能减少物资的储存成本。基于补给时间关于每次补给量之间的关系，将寻求最优的存储成本问题，转变为寻求最合适的补给量，将问题转化成了一个非线性优化问题。

在寻优问题中，利用了格雷码的遗传算法［4～5］将每次补给量进行优化，在指定补给次数的前提下达到最低存储成本。遗传算法表述如下：

初始化种群数量为M，设定遗传代数为D，各参数编码长度为L。

编码选择。由于遗传算法的随机特性，使得二进制编码的搜索能力较差，又为了能方便交叉和变异操作，本文采用格雷码的编码方式。

假设有一个二进制编码为

其对应的格雷码为

格雷码和二进制码转换如下：

其中“⊕”表示异或运算。

格雷码中一个基因座的差别对应的参数也只是微小的差别，这使得在最优解附近，格雷码能快速收敛到最优解，从而提高遗传算法的整体效率。采用随机单点交叉［6］，交叉的概率 pc。格雷码十分方便进行基因变异，本文采用模拟生物基因变异过程中的单点变异［7］，变异概率为 pv。将储存成本作为目标函数。

优化函数为储存成本的倒数：

采用最为实用的轮盘赌比例选择算子［8］，子代的数量仍为M。在每次选择中，表现型越优秀的父代被选择成为子代的概率越大。

设定初始化种群数量为M=100，设定遗传代数为D=500，各参数编码长度为L=15，交叉概率 pc=0.3，变异概率 pv=0.03。程序流程图如图1所示。

图1 程序流程图

3.3 依据模型，给出方案

通过上述计算，各岛礁的补给次数及每次物资补给量已经通过遗传算法寻优得到，但所选用的舰船型号、舰船的补给路线还未确定，因而需要进一步对模型进行细化。通过分析岛礁数据和舰船数据，一个较为初步的认知可以很容易地建立［9～11］：

1）装载量小的补给舰、燃油经济性适中，适合保障中远距离的中型规模岛礁。

2）装载量大的补给舰、燃油经济性差，适合保障近距离大型岛屿并为其它舰船提供物资保障。

3）拖船装载量小、燃油经济性好，适合保障中小型岛礁，但岛礁区域的拖船数量会严重限制岛礁的补给需求。

4）补给舰所拥有的补给小艇补给效率低，保障岛礁时间长，同时需要补给舰开至距岛礁1海里处，虽不考虑其燃油经济性，但需将补给舰的运输成本算入，隐含经济性差的涵义。

5）运输机效费比极低，无特殊情况时无需使用。

接下来需要考虑的就是怎样通过寻找最短路径，挑选最经济适用的船进行运输。最短路径的选择可以采用Dijkstra算法，比较容易实现，而运输工具的选择上述推论可作参考，至此，便可形成一个完整的补给方案［12～13］。

4 结语

通过所建立的数学模型，一个较为严密的理论闭合已经形成。首先，分析物资储存模型，设计并实现遗传算法进行寻优，得到了不同补给次数下的物资补给量；紧接着，综合考虑不同补给次数下物资储存成本与物资运输成本的总和，结合岛礁自身储存上限情况，得到了包含不同岛礁之间补给次数、补给量在内的补给方案；最后，考虑不同补给舰船的经济性和承载能力，通过最短路径寻优的方式，确定舰船补给路线，形成一个补给周期的岛礁补给完整方案。