一种基于改进的微分进化算法的船舶航路规划方法

摘要

本发明是一种基于改进的微分进化算法的船舶航路规划方法，首先对待规划区域进行环境建模，选取实数编码方式进行航路编码并基于航线网络方法完成航路种群的初始化；然后对航路种群采用改进的微分进化算法进行变异和交叉操作，根据总性能评价函数进行选择操作；最后获得最优航路解。本发明基于固定航路点库随机选取初始航路点，生成初始种群，保证了初始种群的质量并避免了规划结果局限于固定航路点库的缺陷；所采用的改进的微分进化算法通过邻域权重系数进行调节，并在全局邻域模型中使用抖动缩放因子，提高全局搜索能力，保证不同的航路点组合之间进行充分的信息交流，以产生更优的航路解。

主权项

1.一种基于改进的微分进化算法的船舶航路规划方法，其特征在于，包括如下步骤：步骤1、采用二维平面为待规划区域进行建模，将待规划区域内的固定航路点集作为航路点库；步骤2、航路编码与种群初始化，具体是；步骤2.1：对每个航路点采用实数进行编码，航路点编码route_node＝{x,y}，其中，x、y分别表示航路点的经度和纬度坐标；为每条航路和航路种群进行编码：每条航路为从初始点到目标点的一组有序的航路点序列，航路种群是由各条航路组成的矩阵；步骤2.2：编码完成后，生成初始航路种群Path，航路种群Path采用NP*D维的矩阵表示，航路种群矩阵中的元素为航路点，第j个行向量为第j条航路Path_j；步骤3：首先设计航程最短性能指标和威胁代价最小性能指标，然后确定航路规划中判断航路优劣的总性能评价函数：C=k₁C_t+(1-k₁)C_u，代价权值k₁∈[0,1]，C表示航路的总性能评价值，C_t表示航路上各航路点的威胁代价，C_u表示航路上各航路点的油耗代价；步骤4：采用微分进化算法，对G世代的航路种群内部进化变异、交叉操作，生成候选航路种群，G初始为1，具体步骤4包括：步骤4.1：依据步骤3中给出的总性能评价函数，计算当前世代航路种群Path中各航路的总性能评价值，选取其中总性能评价值最小的航路，将该航路对应的行向量标记为最优参数向量定义NP*D维矩阵mutate_Path_glob用于存放每一世代的全局施予向量矩阵，G世代的全局施予向量矩阵的第i个行向量表示为步骤4.2：对G世代的航路种群矩阵中每个行向量选取在下标号i的前后邻域范围内的总性能评价值最小的行向量作为向量的邻域最优参数向量邻域半径为R，NP个邻域最优参数向量构成NP*D维局部最优个体矩阵Path_nbrr；定义NP*D维矩阵mutate_Path_lc，用于存放每一世代的局部施予向量矩阵，G世代的局部施予向量矩阵的第i个行向量表示为步骤4.3：定义NP*D维矩阵mutate_Path，用于存放每一世代的最终施于向量矩阵，G世代的最终施于向量矩阵的第i个行向量为：$\overrightarrow{V_{i,G}}={\omega }_{i,G}^{\prime }·\overrightarrow{g_{i,G}}+(1-{\omega }_{i,G}^{\prime })·\overrightarrow{L_{i,G}}$ω′_i,G表示进化变异得到的G世代航路种群矩阵中第i个行向量的邻域权重系数；步骤4.4：根据设置的交叉率Cr，将最终施予向量矩阵的行向量和当前时代航路种群矩阵的行向量进行交叉操作，生成试验向量矩阵cross_Path，试验向量矩阵就是候选航路种群；步骤5：进行选择操作，具体是：步骤5.1：将候选航路种群，按照步骤3中给出的总性能评价函数确定候选航路种群中各航路的总性能评价值，判断候选航路种群的第j条航路的总性能评价值是否小于当前世代的航路种群中的第j条航路的总性能评价值，若是，则将当前世代的航路种群中的第j条航路替换为侯选航路种群中的第j条航路；若否，保持当前世代的航路种群中的第j条航路不变；步骤5.2：判断当前世代的航路种群的所有航路是否都进行了选择操作，若否，转步骤5.1；若是，航路种群中NP个航路均完成选择操作，构成新一代航路种群，更新G＝G+1；步骤6：判断G世代航路种群的各个航路的总性能评价值的均方差是否小于均方差阈值C₀，若是，执行步骤7；若否，进一步判断当前代数G是否大于等于最大进化代数N，若是，则没有找到可行航路，结束本方法；若否，转步骤4执行；步骤7：选取G世代航路种群中总性能评价值最小的航路作为最优航路，输出，结束本方法。