一种栅格图下的基于混合算法的无人船路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN114355948A(43)申请公布日2022.04.15(21)申请号202210028238.X(22)申请日2022.01.11(71)申请人大连海事大学地址116026辽宁省大连市高新园区凌海路1号(72)发明人黄耀倞高舒萍(74)专利代理机构大连东方专利代理有限责任公司21212代理人姜玉蓉李洪福(51)Int.Cl.G05D1/02(2020.01)权利要求书2页说明书5页附图2页(54)发明名称一种栅格图下的基于混合算法的无人船路径规划方法(57)摘要本发明提供一种栅格图下的基于混合算法的无人船路径规划方法，以人工蜂群算法为基础算法，首先通过在粒子群中引入K‑means算法对粒子进行初始化设置，经过粒子群算法计算得出全局最优解；然后以粒子群算法得出的全局最优解作为人工蜂群算法的初始蜂源位置进行二次搜索，在人工蜂群算法运行过程中引入禁忌搜索策略避免重复搜索；最后通过循环计算获得获得全局最优解，即一条距离最短、平滑度最优的路径。本发明的方法规划出来的无人船航行路径的距离更短，使得航行成本低具有经济型。且规划的路径平滑度更优，使得航行环境更加安全，更加符合无人船在实际航行过程的航行路径。同事本发明方法在无人航行过程中搜索路径的时间更短，具有实时性。CN114355948ACN114355948A权利要求书1/2页1.一种栅格图下的基于混合算法的无人船路径规划方法，其特征在于，包括以下步骤：S1：通过栅格图构建海上航行环境，将无人船航行环境转化为一个二维栅格图，通过黑色栅格来表示障碍物，即不可航行区域，用白色栅格来表示可航行区域；S2：通过粒子群算法，进行参数初始化；其中参数包括：群体个数m、权重因子ω、学习因子c1、c2和最大速度Vm；S3：引入K‑means算法对粒子位置进行初始化；S4：更新粒子最优解和位置，具体方程为：T其中，Vi＝(Vi1，Vi2，Vi3，…，ViD)表示粒子速度，表示第k次迭代中第d维的速度，XiT＝(Xi1，Xi2，Xi3，…，XiD)表示粒子的位置，代表第k次迭代中第d维的位置，Pid表示粒子i每个practice到目前为止所出现的个体极值，Pgd表示粒子所有practice到目前为止所出的全局极值；S5：更新全局最优解Pgd和最优位置生成搜索路径次优解；S6：通过人工蜂群算法，进行参数初始化，包括蜜源数量SN、控制参数limit、最大迭代次数MCN；S7：将步骤S4输出的全局最优解的位置做为蜜源位置，再次通过人工蜂群算法进行搜索全局最优解；S8：更新蜜源的位置，即更新最优解；S9：经过算法循环计算，搜索得到全局最优解，即距离最短、平滑度最优的航行路径；最后，直到所有跟随峰完成搜索之后，抛弃那些经过limit次循环后仍没有更新的解，即这些解陷入了局部最优，则其对应的跟随蜂转变成侦察蜂，产生新的蜂源来代替原蜂源；然后返回雇佣蜂搜索过程，开始重复循环，最后通过循环搜索找到最优解。2.根据权利要求1所述的一种栅格图下的基于混合算法的无人船路径规划方法，其特征在于，所述引入K‑means算法对粒子位置进行初始化具体包括以下步骤；S31：从粒子群集合中随机抽取k个粒子作为初始簇的中心；S32：计算每一个粒子到每一个簇中心的欧氏距离，将每个粒子划分到距离它最近的中心点所代表的簇中，距离公式为：其中，Xi表示第i个粒子，Cj表示第j个簇中心，i的取值范围为：[1，n]，j的取值范围为：[1，k]；Xit表示第i粒子的第t个属性，Cjt表示第j个簇中心的第t个属性，t的取值范围为：[1，m]；S33：通过各个簇中所有样本点的中心点代表簇的中心点：S34：重复S32和步骤S33，直到簇的中心点不变或达到设定的迭代次数。3.根据权利要求1所述的一种栅格图下的基于混合算法的无人船路径规划方法，其特征在于，所述步骤S6中，所述人工蜂群算法在搜索过程的初始阶段，即雇佣蜂阶段，每个雇佣蜂寻找新蜜源的公式为：2CN114355948A权利要求书2/2页其中：k取值于{1，2，…，SN}，j取值于{1，2，…，D}，且取值于[‑1，1]；在确定新蜜源的位置之后，即找到了新的解，计算新解的fiti值并与原解进行比较，即与步骤S4得出的次优解进行比较，若是新解大于原解，则以新解代替旧解；否则继续保留原解答；在人工蜂群算法的蜜源质量是越大越好，即fiti值越大解的质量越好，其中，fiti值的计算公式为：在对新蜜源评价时采取贪婪选择方式，具体公式为：其中，在搜索过程中引入禁忌搜索避免重复搜索，通过用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，这些点中其中就包括由粒子算法计算得出的次优解。4.根据权