基于遗传粒子群算法的无人船集群目标分配

翟泽宇，许志远，邱文轩，曲胜，张晓鹏，许航

（大连海洋大学航海与船舶工程学院，辽宁 大连116023 ）

随着海上通信、协同控制和人工智能等技术的不断发展，多智能体在海上协同作业变为可能[1]。无人船因具有独立性高、灵活性强和成本低等优势，在救助搜查、水底探测和环境监控等领域得到了广泛应用。无人船集群在执行海面各项任务中，会更加关注于各个成员之间的协作与分工。不同的任务需要不同的集群队形来完成，因此对无人船集群目标分配路径、时间和效率都提出了更高要求。

关于多无人船集群的目标任务分配问题，朱晓军等[2]使编队的部署能力用遗传算法进行优化；Wei等[3]提出了基于粒子群算法的双级任务分配法，使任务完成精度和可靠性得到提升；牛晓博等[4]采用带精英策略的快速非支配遗传算法，较好完成编队分配问题，又解决了单目标分配优化的局限性。Chopra等[5]通过改进匈牙利算法，解决并行分配任务的问题；吕光颢等[6]提出最大迭代次数的拍卖终止机制，解决改进传统拍卖算法在重构分配中存在无可行解的问题；马硕等[7]采用分层聚类拍卖算法，解决多任务分组的问题；李磊等[8]提出采用布谷鸟优化方法，为目标点附近的过程规划能耗最优的运动方案。解决目标分配的算法，都会涉及到提高计算效率、空间内全面搜索、并行运行、提升分配精准度等问题。

为解决上述问题提出基于遗传粒子群算法的无人船集群目标分配方法，以粒子群算法为基础与遗传算法相结合，通过对无人船分配到的劣势目标点进行不断地替换，寻找到更具有优势的目标点，完成无人船集群目标分配任务。

1 算法原理

1.1 目标分配原理

目标分配是指将多个目标点分配给多艘无人船，使其分别到达指定目标点的分配问题。无人船作为抵达目标点的主体，用表示，n为无人船数量。无人船的初始位置表示为；目标点表示为；n 为目标点数目，与无人船数目相同。目标点的位置为；无人船与目标点为一一对应关系，如式1；其中：xij为目标点分配的结果，无人船ui的目标点分配是目标点pj；如果xij=1，无人船ui和目标点pj配对成功。C 为无人船和目标点一一对应的所有集合。

目标分配的优劣影响整个集群构建队形的效率，并且直接关系到集群中各艘无人船是否能尽快到达目标点，避免占用更多的资源。

1.2 粒子群算法

粒子群算法在无人船集群目标分配中，每艘无人船寻找目标点的最终方向受三个影响因素，如图1 所示。

图1 粒子所受的影响因素

如果设无人船当前时刻的速度向量为vid，当前位置为xid，用式2 和式3 表示；其中，为惯性因子，取值为1；C1为个体影响因子；C2为整体影响因子；id为粒子自身最优点；gd 为群体最优点；r1和r2为[0,1]之间的随机值。

粒子群算法的本质是利用2 个最优点来指导粒子下一步位置。当有无人船找到目标点后，未找到目标点的无人船，受已找到目标点无人船的位置影响，其位置和速度会发生改变，会造成无人船无效行程和分配时间的增加。

1.3 遗传算法

遗传算法在无人船集群目标分配操作如下：第一步确定无人船集群数量，设置最大进化代数并根据无人船初始位置和当前分配到的目标点位置进行编码；第二步确定适应度函数，并计算每艘无人船初始位置和目标点对应组合的适应度值，根据适应度值选择进入下一代的组合，对未被选择的组合进行交叉和变异操作；第三步对产生新的无人船初始位置和目标点的对应组合计算，不断迭代，直到所有无人船得到对应目标点后，算法停止。

遗传算法采用群体搜索提高寻找目标点的效率。但在操作时无人船缺乏指导方向，导致算法收敛慢。因此将粒子群算法和遗传算法相结合[9]，减少最优点对粒子的影响，使无人船寻找目标点的效率提升。

2 基于遗传粒子群算法的无人船集群目标分配

2.1 遗传粒子群算法

通过粒子群算法得到无人船当前分配的目标点，并进行编码；再对无人船和目标点的组合进行自适应函数计算，自适应函数如式4。对适应度值由高到低排序，选择算子采用精英保留算法将排名在前的组合保留，不继续后面的操作。

2.2 交叉算法

遗传算法的交叉操作在粒子群算法的具体步骤是让两个最优点进行交叉操作，产生的解为新的粒子速度，也就是先将式2 中的项中的项C1，C2定义为一个概率组合。pc1和pc2分别代表个体最优点和群体最优点交叉操作的概率，通常情况下pc1=pc2=pc；其次，从种群中没有进入下一代的随机选择两个，进行个体配对；最后，在个体编码串中随机设置两个交叉点进行单点交叉操作。根据给定的交叉概率从而得到两个新个体；通过交叉算子处理后的式2 更新为式5。

2.3 变异算法

通过遗传操作之后，位置更新式3 表中速度项就是一个交换序列无人船迭代前后位置变化就是该交换序列作用于无人船迭代前位置的结果。由此得到第k 次迭代后位置x（k+1）和迭代前位置x（k）与这个速度交换序列v（k）之间的关系表示为式7；将得出的较优目标点的编码替换原目标点编码。

3 实验结果及分析

通过MATLAB 对随机分布的无人船集群进行队形构建，并比较两种算法所用时间和路程。

实验假设某一海域内存在需要预设成DHD 队形，构建编队是由48 艘随机分布的无人船组成，对此分配问题进行仿真。无人船的初始位置及目标点位置，如图2 所示。粒子群算法的分配结果如图3 所示；遗传粒子群算法的分配结果如图4 所示；两种算法的实验仿真数据，如表1 所示。

表1 两种算法仿真结果对比

图2 DHD 队形中无人船与目标点分布图

图3 粒子群算法实验结果

图4 遗传粒子群算法实验结果

目标分配结果可得，遗传粒子群算法对无人船分配得目标点会更为合理化，无人船之间相交的路线明显减少；遗传粒子群算法的分配时间减少约27.4%，所行使的路径长度也缩短了约10.9%；对于粒子群算法无法保证目标分配的成功率，而遗传粒子群算法可以维持100%的分配成功率。

4 结论

以粒子群算法为基础，结合遗传算法对无人船集群的目标分配问题进行优化，结合后的算法具有搜索面积广和灵活性高的特点，对目标点的搜索和确认速度明显加快。与粒子群算法相比，遗传粒子群算法得到目标点的分配时间和路径长度有明显减少，也使到达分配目标的路径更加合理，目标分配的成功率也有很好的保证，对于无人船集群队形构建起到了较好的辅助作用。