(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111198123.7 (22)申请日 2021.10.14 (71)申请人 中国人民解 放军63628部队 地址 735000 甘肃省酒泉市东 风场区 (72)发明人 张雄锋　龙坤明　 (74)专利代理 机构 长沙中科启明知识产权代理 事务所(普通 合伙) 43226 代理人 谭勇 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) (54)发明名称 一种基于遗传算法的地面搜索分队布势算 法 (57)摘要 本发明涉及一种基于遗传算法的地面搜索 分队布势算法， 首先通过搜索区域建模和搜索分 队建模来建立分队的布势模型， 以分队抵达航天 器时间最短为目标， 以分队初始部署位置位于安 全区域内网格为约束条件， 将分队的布势问题转 化为数学最优化问题， 最后使用遗传算法和多分 辨率方法求解得到布势方案。 本发 明为地面搜索 分队的布势问题提供了数学 理论基础， 通过使用 遗传算法解决了布势方案计算的问题， 并通过多 分辨率网格技术提高求解效率， 有利于保证分队 安全性， 提升分队搜索效率， 缩短完成任务所需 时间。 权利要求书3页 说明书7页 附图1页 CN 113887140 A 2022.01.04 CN 113887140 A 1.一种基于 遗传算法的地 面搜索分队布 势算法， 其特 征在于： 包括 步骤： S1： 建立布 势模型 首先对搜索区域和搜索 分队进行建模， 然后使用最短抵达时间作为量化布势方案效能 的指标， 通过遗传算法实现对布 势方案的求 解； S1.1： 搜索区域建模 S1.1.1： 使用网格化 技术， 将搜索区域划分为 一系列规整的、 充分小的矩形网格； S1.1.2： 完成网格划分后， 需赋予网格相应的可通行属性， 以描述区域环境， 网格的可 通行属性是综合反映搜索分队在该网格内通行能力的指标； 假设搜索分队的最大速度为Vmax， 在网格i和网格j之间能达到的最大速度为Vij， 则通行 因子定义为γij＝Vij/Vmax， 根据定义， 通行因子为0～1之间的实数， 越接近 1， 表示通行能力 越高， 分队在该区域可达到的前进速度越大， 一般而言， 可通行属 性与网格区域地理环境、 分队属性和前进方向有关， 本发明采用加权有向图的方法直观描述通行因子， 为此， 将 每个 网格区域中心点抽象为图的顶点， 相 邻网格之 间使用有向边连接， 每条有向边被赋予权值， 权值即表示该分队从有向边的起点到有向边的终点的通行因子， 网格之间通行因子越大， 代表车辆通行能力越好； S1.2： 搜索分队建模 将地面搜索分队建模成具有位置和最大 行进速度的点目标， 具体步骤为： S1.2.1： 从通行因子有向图中获得搜索分队在相邻网格之间行进时可达到的最大速 度； S1.2.2： 使用网格中心点之间的距离除以S1.2.1中获得的最大速度， 即可获得分队在 相邻网格之间的通行时间； S1.2.3： 获得分队在各网格之间的通行时间后， 使用Dijkstra算法得到该分队与目标 网格之间的最优路径和所需最短时间。 S2： 建立布 势问题 为表征网格重要程度， 需赋予各网格一个权值， 权值为0～1之间的数， 越接近1表示该 网格重要程度越高， 权值的选取通过均匀权值法、 经验预估法或落 点概率法获得； 本发明将地面分队的最优布势问题描述如下： 已知返回器着陆区内每一个网格的权 值， 如何确定任务初始时刻各分队的待命位置， 使得各分队均在安全区域待命， 并且抵达返 回器着陆网格的加权时间最短， 其中抵达返回器着陆网格的时间是指 至少有一只分队到达 返回器着陆点的最小时间； 假设返回器可能着陆的网格区域对应的编号集合为UD＝{d1,…,dD}， 其中di表示第i个 网格编号， D为返回器可能着陆的网格总数， 为网格di赋予度量重要程度的非负权值ωi， 不 失一般性， 可假设 安全区域的网格编号集合记 为Ω， 为可布势第i支分队的网格编号集合， 在 有n支 搜救分队时， 使用集合S＝(P1,…,Pn)表示布势方案， 其中Pi∈Ωi为第i支搜救分队的待命 网格编号； 给定布势 方案S时， 若第i支搜救分队从初始位置Pi出发， 沿耗时最短路径抵达网格dk所权　利　要　求　书 1/3 页 2 CN 113887140 A 2需要时间为tik， 则至少一支分队抵 达dk的时间为 布势方案S对应的完成任务的加权时间为 因此， 地面分队布 势问题可描述 为求解最优化问题 S3： 布势问题求 解 当安全区域Ω中包含m个网格， 搜救分队数量为n时， 在每支分 队的布势区域均为Ω的 情况下， 可选的布势方案共有mn种， 使用多分辨率网格技术和遗传算法求解布势问题(4)， 具体步骤如下： S3.1： 确定编码方法， 安全区域的网格编号集合为Ω， 有n支搜救分队， 使用(3)式的倒 数 作为适应度函数G(S)， 假设设置遗传算法种群数K， 可将布势问题的解S编码为一个n 维向量S＝(P1,…,Pn)， 向量元 素从安全区域网格编号 集合Ω中选取； S3.2： 确定基因交叉操作， 对两个布势方案S＝(P1,…,Pn)和S'＝(P1',…,Pn')， 规定基 因交叉操作为生成的两个新解向量(P1,…,Pn/2,Pn/2+1',…,Pn')和(P1',…,Pn/2',Pn/2+1…, Pn)的过程； S3.3： 确定基因变异操作， 布势 方案S＝(P1,…,Pn)的变异操作规定为随机选择S的一个 元素， 将该元素替换为 集合Ω‑S中的一个随机元 素。 2.根据权利要求1所述基于遗传算法的地面搜索分队布势算法， 其特征在于： 所述遗传 算法求解布势问题的具体步骤如下： 1)随机生成2K个布势问题的解向量Sk， 构成遗传算法的初 始种群， 随机生成一个最优 解 Sop； 2)计算每个解向量对应的适应度函数G(Sk)， 并计算每个解向量对应的轮盘 赌概率函数 将适应度函数最高的解记为S'op， 将S'op和Sop进行比较， 如果S'op的适应度高 于Sop， 则更新Sop＝S'op， 若否， 则不更新Sop； 3)使用轮盘赌方法从2K个布势问题的解向量组成的集合中独立随机选取2个解， 解向 量Sk被选取的概率为Pk， 生成一个在 [0,1]之间均匀分布的随机数ξ， 如果ξ＜0.9则两个 解向 量进行交叉操作， 得到新 解， 若 ξ ≥0.9， 则直接将两个解作为 新解； 4)重复步骤(3)K次， 得到2K个由新 解构成的种群； 5)对由步骤(4)得到的种群 个体， 依次进行变异操作， 变异概 率设置为0.0 05； 6)重复步骤(2)至步骤(5)， 直至 重复次数超过设定阈值后停止， 将Sop作为最优解输出。 3.根据权利要求2所述基于遗传算法的地面搜索分队布势算法， 其特征在于： 使用多分 辨率网格技 术对本发明算法进行加速， 具体步骤如下： 1)首先使用大网格对区域进行划分， 通过遗传算法求 解得到初步布 势方案；权　利　要　求　书 2/3 页 3 CN 113887140 A 3