(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111544105.X (22)申请日 2021.12.16 (71)申请人 青岛科技大 学 地址 266000 山东省青岛市崂山区松岭路 99号 (72)发明人 邓芳　于敦敬　杨化林　靳磊磊　 张翰林　 (74)专利代理 机构 青岛中天汇智知识产权代理 有限公司 37241 代理人 孟琦 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) G06F 111/08(2020.01) (54)发明名称 一种基于改进遗传算法的无人船航线规划 方法 (57)摘要 本发明涉及一种基于改进遗传算法的无人 船航线规划方法， 其包括： 采用限制随机初始化 种群生成无碰撞路径， 以提高初始种群质量； 在 选择算子上使用Pareto原理和二元锦标赛选择 出一半种群进行交叉和变异操作； 采用自适应遗 传算法中的交叉概率和变异概率提高算法的收 敛能力； 引入安全算子， 使无人船路径保持在安 全距离之外； 以路径最短和平滑度最优作为适应 度函数； 使用删除算子和安全算子， 删除无用的 路径点以及判断路径点是否在安全距离之外， 如 果没在重新生成路径点。 本发明使无人船在航行 之前预先规划好航线， 为船舶安全航行提供基 础。 权利要求书3页 说明书9页 附图4页 CN 114282435 A 2022.04.05 CN 114282435 A 1.一种基于改进遗传算法的无 人船航线规划方法， 其特 征在于： 该 方法包括以下步骤： 步骤1、 环境建模， 建立无人船航行环境， 所建立的环境包含阴影区域和空白区域， 阴影 区域表示障碍物， 空白区域表示无 人船可行走区域； 步骤2、 设置无 人船的起点和终点， 起 点和终点在所建立的环境 地图内； 步骤3、 使用改进遗传算法对无 人船最优路径进行规划， 包括： 步骤3.1采用限制随机初始化种群对随机初始化种群加以限制， 初始化为无碰撞的路 径， 提高初始种群质量； 步骤3.2计算所有个 体目标函数值及适应度值； 步骤3.3将Pareto算子和二元锦标赛算子相结合执行选择操作， 采用Pareto作为主选 择算子， 二元锦标赛 算子作为补充， 使选择 出来的个 体为种群的一半； 步骤3.4采用八领域方法执 行安全算子， 将障碍物区域分为八邻域； 步骤3.5执 行自适应交叉、 变异操作； 步骤3.6判断是否 达到最大迭代次数， 如果是 执行步骤3.7 ‑3.8， 否则执 行步骤3.2； 步骤3.7使用删除算子以减少无效的路径点； 步骤3.8使用安全算子， 对距离障碍物过近的路径点按照八邻域方法重新 生成。 2.根据权利要求1所述的一种基于改进遗传算法的无人船航线规划方法， 其特征在于： 所述步骤3.1种群初始化方式为限制随机初始化， 其过程主要分为2步： 首先根据染色体长 度M生成一条从起点到终点的M+1个直线路径段， 之后将在障碍物内的路径 点限制随机初始 化为不在障碍物内的路径点； 其次判断两个路径 点连线是否穿越障碍物， 如果穿越障碍物， 则对路径点采用限制随机初始化为连线不穿越障碍物的路径点， 种群初始化公式如下所 示： 其中： 权　利　要　求　书 1/3 页 2 CN 114282435 A 2式中： (xi,yi)是路径点i的坐标； (xe,ye)是设置的边界坐标， 其值决定着搜索范围； (xs, ys)是起始点坐标； (xt,yt)是终止点坐标； k是起始点和目标点组成 的斜率； b是过等分点垂 线与y轴截距； (xq,yq)是路径经过等分之后形成的坐 标； a是过等分点与y轴的交点； c是过等 分点与x轴交点； d是决定xi的最小取值； M是染色体长度； Ri＝[R(i,1),R(i,2)]决定路径点变化 范围， R(i,1),R(i,2)变化范围分别由边界坐标确定。 当计算的路径点在障碍物内或者两个路 径点的连线穿越障碍物， 则重新运行上述公式对路径点重新生成， 直到生成满足条件的初 始种群。 3.根据权利要求1所述的一种基于改进遗传算法的无人船航线规划方法， 其特征在于： 所述步骤3.3执行选择操作方法包括： 将Pareto算子和二元锦标赛算子相结合执行选择操 作， 采用Paret o作为主选择算子， 二元锦标赛算子作为补 充， 使选择出来的个体始终为初始 种群数量的一半； Pareto ‑二元锦标赛选择算子的基本步骤如下： (1)设i＝1； (2)对于所有种群j＝1,2,.......,N， 且j≠i， 按照以上定义， 比较种群Xi和种群Xj之间 的支配与非支配关系； (3)当不存在任何一个种群Xj在三个目标函数上优于Xi时， 则Xi称为非支配个体， 并将 其选择下来； (4)令i＝i+1， 循环步骤(2)、 (3)， 直到找到所有的非支配 个体； (5)令j＝j+1， 再循环步骤(1) ‑(4)， 依此类推， 直至循环至整个种群。 值得注意的是将 已经选择的非支配 个体不再进行比较； (6)判断选择出来的个体数量是否为初始种群数量的一半， 如果是一半则结束； 否则执 行步骤(7) ‑(8)； (7)如果选择出来的个体数量大于初始种群数量的一半， 从选择出来的个体中随机选 择2个个体； 如果选择出来的个体数量小于初始种群数量的一半， 从剩余的初始种群中随机 选择2个个体； 然后将选择 出来的两个 个体中适应度值高的那个 个体进入下一代种群； (8)重复步骤(7)， 直到 选择出的个体数量为初始种群数量的一半。 4.根据权利要求1所述的一种基于改进遗传算法的无人船航线规划方法， 其特征在于： 所述步骤3.4执 行安全操作的方法包括： 将障碍物周围的区域分为八邻域； 当路径点或者路径段的连线距离障碍物太近， 不满足本发明设置的安全距离时， 路径 点应当根据障碍物邻域范围决定路径点变化方向。 5.根据权利要求1所述的一种基于改进遗传算法的无人船航线规划方法， 其特征在于： 所述步骤3.5执行 交叉、 变异操作方法包括： 交叉方式采用双点交叉， 当满足交叉概率时， 在 种群中随机选择两个个体， 选择相同的部位进行交叉操作； 采用改进自适应交叉和变异概 率， 引入自然e指数， 在改进自适应交叉和变异概率中考虑迭代 次数的影响， 随着迭代 次数 的增加以及适应度函数不断趋于最优， 交叉概率和变异 概率在不断地减小以防止最优个体 被破坏， 其表达式为：权　利　要　求　书 2/3 页 3 CN 114282435 A 3