[发明专利]基于改进差分进化算法的作业路径动态优化方法

摘要

一种基于改进差分进化算法的作业路径动态优化方法，包括如下步骤：步骤1：编码；步骤2：优化求解；步骤3：解码最优解，获取其对应的路径规划方案，以便指导作业人员作业。本发明将实际问题转化成数学问题，通过求取目标函数的最优解，获得用于指导作业任务分配和作业任务排序的最佳方案，可实现作业任务的动态科学分配，以及作业路径的实时优化，从而从整体上提高完成作业任务的效率和对作业任务的响应速度；本发明对常规差分进化算法进行了改进，提高了算法的寻优速度和精度。

主权项

一种基于改进差分进化算法的作业路径动态优化方法，包括如下步骤：步骤1：编码1‑1)对于N个目标任务点，P个出勤作业人员，构建如下优化向量表达式：x＝(x₁,x₂,x₃,...,x_N)x_i∈{1,2,3,...,N}其中，x_i表示目标任务点编号，优化向量x中所有x_i的取值不重复，即优化向量x是1,2,…,N的一个排列，为全部出勤作业人员需要依次遍历的目标任务点编号；1‑2)根据出勤作业人员属性的不同，按照作业人员各自的工作能力，事先指定各作业人员的任务量，即负责的目标任务点的数量，分别为n₁,n₂,…,n_P，以优化向量x的前n₁维表示1号作业人员的有序任务列表，之后的n₂维表示2号作业人员的有序任务列表，依次类推，将优化向量x解码为P个有序的任务路径，即解码出优化向量x对应的路径规划方案；步骤2：优化求解2‑1)设置改进差分进化算法参数，包括种群规模NP、最大迭代次数Maxges、子种群数量N_sub，非线性遗忘因子α、变异因子F_M、交叉因子F_P以及多重变异选择因子P₁、P₂；2‑2)利用某个范围内的随机值初始化种群：j＝1,2,...,NP；2‑3)对种群中的每个个体x^j(0)中的各维度变量值进行大小排序，获取与各个体对应的、根据各个体x^j(0)中各维度变量值在序列中的排名确定的由1,2,…,N构成的排列；2‑4)将每个排列视为一个优化向量x，计算初始种群中每个个体的适应度值，即计算每个排列对应的作业路径总和，并比较得出初始全局最优个体x_gbest(0)；2‑5)将包含NP个个体的种群拆分成N_sub个子种群：NP₁,NP₂,...,NP_{N_sub}，并计算每一个子种群中的最优个体：m＝1,2,...,N_sub；2‑6)将N_sub个子种群按照环形拓扑结构进行连接，使每个子种群均拥有两个相邻的子种群；2‑7)对每个个体按照如下方式进行变异操作：$v^j\left(t\right)=\left\{\begin{array}{cc}{x}^j\left(t\right)+M\left(t\right)*\underset{ii=1}{\overset{t}{\mathrm{\Σ}}}\mathrm{\ξ}\left(ii\right)\[x_{gbest}\left(ii\right)-x^j\left(ii\right)\]+M{\left(t\right)}^{*}\left(x^{r1}\left(t\right)-x^{r2}\left(t\right)\right)& ifrand\left(0,1\right)\≤P_1\\ x^j\left(t\right)+M\left(t\right)*\underset{ii=1}{\overset{t}{\mathrm{\Σ}}}\mathrm{\ξ}\left(ii\right)\[x_{rbest}^m\left(ii\right)-x^j\left(ii\right)\]+M{\left(t\right)}^{*}\left(x^{r1}\left(t\right)-x^{r2}\left(t\right)\right)& if{P}_1\≤rand\left(0,1\right)\≤P_2\\ x^j\left(t\right)+M\left(t\right)*\underset{ii=1}{\overset{t}{\mathrm{\Σ}}}\mathrm{\ξ}\left(ii\right)\[x_{rbest}^n\left(ii\right)-x^j\left(ii\right)\]+M{\left(t\right)}^{*}\left(x^{r1}\left(t\right)-x^{r2}\left(t\right)\right)& otherwise\end{array}\right.$其中，v^j(t)表示第j个个体在第t代时产生的变异个体，x^j(t)为其变异之前的个体；x^r1(t)，x^r2(t)为种群中另外两个随机的个体；x_gbest(ii)为第ii代时的全局最优个体；为第ii代时第m个子种群中的最优个体；为第ii代时与第m个子种群相邻的两个子种群中的最优个体中的随机一个；M(t)为第t代的变异因子，其满足均值为F_M，方差为0.1的柯西分布；P₁，P₂为多重变异选择因子，分别满足均值为F_P1、F_P2，方差为0.1的高斯分布；此外，ξ(ii)满足：$\mathrm{\ξ}\left(ii\right)=\frac{{(t-ii)}^{-\mathrm{\α}}}{\underset{ii=1}{\overset{t-1}{\Σ}}{(t-ii)}^{-\mathrm{\α}}},(ii=1,2,...,t-1)$2‑8)对每个个体进行交叉操作，公式如下：$u_h^j\left(t\right)=\left\{\begin{array}{cc}{v}_h^j\left(t\right),& ifrand(0,1)\≤P_c\left(t\right)\\ x_h^j\left(t\right),& otherwise\end{array}\right.,h=1,2,...,N$其中，为第j个个体在第t代中其h维度的变量值；P_c(t)为第t代的交叉因子，满足均值为P_c，方差为0.1的高斯分布；2‑9)对每个个体进行选择操作，公式如下：$x^j(t+1)=\left\{\begin{array}{cc}{u}^j\left(t\right),& iff\left(u^j\right(t\left)\right)\≤f\left(x^j\right(t\left)\right)\\ x^j\left(t\right),& otherwise\end{array}\right.$其中，f为构建的用于表示作业路径总和的目标函数；2‑10)更新当前代的全局最优个体x_gbest(t)，各子种群中的最优个体2‑11)判断是否达到最大迭代次数Maxges，若否则返回步骤2‑7)；2‑12)获得最优解，终止算法优化过程；步骤3：解码最优解，获取其对应的路径规划方案，以便指导作业人员作业。