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

CWT 中国水运 202308 91基于遗传粒子群算法的无人船集群目标分配翟泽宇，许志远，邱文轩，曲胜，张晓鹏，许航（大连海洋大学航海与船舶工程学院，辽宁 大连 116023）摘要：针对粒子群算法中目标点易受其他粒子影响的问题，提出一种基于遗传粒子群算法的无人船集群目标分配的方法，用粒子群算法获得无人船的目标点，并结合遗传算法对一些无人船的劣势目标点替换成优势目标点，完成设定的目标分配任务。实验结果表明，在目标分配问题中，遗传粒子群算法比粒子群算法所用时间和所走路径长度都有明显的减少，目标分配的成功率也有很好保证。关键词：无人船集群；粒子群算法；遗传算法；目标分配中图分类号：U674.91 文献标识码：A 文章编号：10067973（2023）08-0091-03DOI 编码：10.13646/ki.42-1395/u.2023.08.035随着海上通信、协同控制和人工智能等技术的不断发展，多智能体在海上协同作业变为可能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）目标分配的优劣影响整个集群构建队形的效率，并且直接关系到集群中各艘无人船是否能尽快到达目标点，避免占用更多的资源。1.2 粒子群算法图 1 粒子所受的影响因素粒子群算法在无人船集群目标分配中，每艘无人船寻找目标点的最终方向受三个影响因素，如图 1 所示。如果设无人船当前时刻的速度向量为 vid，当前位置为 xid，用式 2 和式 3 表示；其中，为惯性因子，取值为 1；C1为个体影响因子；C2为整体影响因子；id为粒子自身最优点；gd 为群体最优点；r1和 r2为 0,1之间的随机值。（2）b.个体最优点影响a.自身速度方向最终方向c.群体最优点影响92 CWT 中国水运 202308 （3）粒子群算法的本质是利用 2 个最优点来指导粒子下一步位置。当有无人船找到目标点后，未找到目标点的无人船，受已找到目标点无人船的位置影响，其位置和速度会发生改变，会造成无人船无效行程和分配时间的增加。1.3 遗传算法遗传算法在无人船集群目标分配操作如下：第一步确定无人船集群数量，设置最大进化代数并根据无人船初始位置和当前分配到的目标点位置进行编码；第二步确定适应度函数，并计算每艘无人船初始位置和目标点对应组合的适应度值，根据适应度值选择进入下一代的组合，对未被选择的组合进行交叉和变异操作；第三步对产生新的无人船初始位置和目标点的对应组合计算，不断迭代，直到所有无人船得到对应目标点后，算法停止。遗传算法采用群体搜索提高寻找目标点的效率。但在操作时无人船缺乏指导方向，导致算法收敛慢。因此将粒子群算法和遗传算法相结合9，减少最优点对粒子的影响，使无人船寻找目标点的效率提升。2 基于遗传粒子群算法的无人船集群目标分配2.1 遗传粒子群算法通过粒子群算法得到无人船当前分配的目标点，并进行编码；再对无人船和目标点的组合进行自适应函数计算，自适应函数如式 4。对适应度值由高到低排序，选择算子采用精英保留算法将排名在前的组合保留，不继续后面的操作。（4）2.2 交叉算法遗 传 算 法 的 交 叉 操 作 在 粒 子 群 算 法 的 具体 步 骤 是 让 两 个 最 优 点 进 行 交 叉 操 作，产 生的 解 为 新 的 粒 子 速 度，也 就 是 先 将 式 2 中 的 项中 的 项 C1，C2定义为一个概率组合。pc1和 pc2分别代表个体最优点和群体最优点交叉操作的概率，通常情况下 pc1=pc2=pc；其次，从种群中没有进入下一代的随机选择两个，进行个体配对；最后，在个体编码串中随机设置两个交叉点进行单点交叉操作。根据给定的交叉概率从而得到两个新个体；通过交叉算子处理后的式 2 更新为式 5。（5）2.3 变异算法将式 2 中的项中的惯性权重系数定义为一个概率组合对应速度交换序列 vid 中第 i 只无人 船 位 置 发 生 概 率 为，。其 中，t为当前进化代数，T 为最大化进化代数，为确定非均匀程度的一个参数；通过交叉和变异操作处理后的式 5更新为式 6。（6）通过遗传操作之后，位置更新式 3 表中速度项就是一个交换序列无人船迭代前后位置变化就是该交换序列作用于无人船迭代前位置的结果。由此得到第 k 次迭代后位置 x（k+1）和迭代前位置 x（k）与这个速度交换序列 v（k）之间的关系表示为式 7；将得出的较优目标点的编码替换原目标点编码。（7）3 实验结果及分析通过 MATLAB 对随机分布的无人船集群进行队形构建，并比较两种算法所用时间和路程。实验假设某一海域内存在需要预设成 DHD 队形，构建编队是由 48 艘随机分布的无人船组成，对此分配问题进行仿真。无人船的初始位置及目标点位置，如图2 所示。粒子群算法的分配结果如图 3 所示；遗传粒子群算法的分配结果如图 4 所示；两种算法的实验仿真数据，如表 1 所示。图 2 DHD 队形中无人船与目标点分布图0204060801000102030405060708090100110 x位置y位置无人船目标点CWT 中国水运 202308 93图 3 粒子群算法实验结果图 4 遗传粒子群算法实验结果表 1 两种算法仿真结果对比目标分配结果可得，遗传粒子群算法对无人船分配得目标点会更为合理化，无人船之间相交的路线明显减少；遗传粒子群算法的分配时间减少约 27.4%，所行使的路径长度也缩短了约 10.9%；对于粒子群算法无法保证目标分配的成功率，而遗传粒子群算法可以维持100%的分配成功率。4 结论以粒子群算法为基础，结合遗传算法对无人船集群的目标分配问题进行优化，结合后的算法具有搜索面积广和灵活性高的特点，对目标点的搜索和确认速度明显加快。与粒子群算法相比，遗传粒子群算法得到目标点的分配时间和路径长度有明显减少，也使到达分配目标的路径更加合理，目标分配的成功率也有很好的保证，对于无人船集群队形构建起到了较好的辅助作用。参考文献：1 谢伟,陶浩,龚俊斌,等.海上无人系统集群发展现状及关键技术研究进展 J.中国舰船研究,2021,16(01):7-17+31.2 朱晓军,张涛,彭飞,等.基于遗传算法的编队条件下舰船修理周期结构优化 J.中国舰船研究,2011,6(05):103-107.3WEI H L,MAT ISA N A.Particle swarm optimization with dual-level task allocationJ.Engineering Appli-cations of Artificial Intelligence,2015,38:88-110.4 牛晓博,陈新来,朱飞,等.基于带精英策略遗传算法的舰艇编队目标分配 J.现代防御技术,2015,43(04):117-123.5CHOPRA S,NOTARSTEFANO G,RICE M,et al.A distributed version of the Hungarian method for multi-robot assignmentJ.IEEE Transactions on Robotics,2017,33(4):932-947.6 吕光颢,彭周华,王丹,等.无人船集群队形重构的目标任务分配 J.中国舰船研究,2018,13(06):101-106.7 李磊,姚申茂,杜度.基于协同探测的 UUV 集群低能耗动态优化控制策略 J.舰船科学技术,2020,42(23):80-85.8 马硕,马亚平.基于分层聚类拍卖的集群 UUV 多目标分配方法 J.舰船科学技术,2019,41(09):70-75.9 王文义,秦广军,王若雨.基于粒子群算法的遗传算法研究 J.计算机科学,2007(08):145-147.基金项目：辽宁省教育厅项目（QL201911）0204060801000102030405060708090100110 x位置y位置无人船目标点0204060801000102030405060708090100110 x位置y位置无人船目标点