基于阶段结构捕食‑食饵模型的输送路径组合优化方法

摘要

本发明公开了一种基于阶段结构捕食‑食饵模型的输送路径组合优化方法，假设在一个生态系统中生长若干个动物种群，每个种群分为成年种群和幼年种群两个阶段类型；成年种群以一定的出生率产生其幼年种群，幼年种群经过一段时间后变为成年种群；种群之间的相互争夺生存资源对每个种群的影响就表现在对其特征的影响上；一个种群在所有种群中所占的比例越大，该种群的影响也就越大，该种群会将其影响传播给其他种群；优势和强势种群将其优质特征传播给其它种群；若一个种群不断受到其它种群的影响，其生长状态就会不断发生变化，利用这种变化和具有阶段结构的多种群捕食‑食饵系统模型能够快速确定输送路径组合优化问题的全局最优解决方案。

主权项

一种基于阶段结构捕食‑食饵模型的输送路径组合优化方法，简称TPO_MYPPSS方法，其特征在于：设要解决的输送路径组合优化模型为：min f(X)$\begin{array}{cc}s.t.& \left\{\begin{array}{c}{g}_{i_a}\left(X\right)\ge 0,i_a\in I\\ h_{i_b}\left(X\right)=0,i_b\in E\\ X\in H⋐R^n\end{array}\right.\end{array}---\left(1\right)$式中：(1)Rⁿ是n维欧氏空间，n为该优化模型所包含的变量总数；(2)X＝(x₁，x₂，…，x_m，x_m+1，…，x_n)是一个n维决策向量，其中，前m个变量x₁，x₂，…，x_m是连续实数型变量，用来表示模型中涉及到的流量型参数；后n‑m个变量x_m+1，…，x_n是0、1整数型变量，用来表示n个站点中的哪些站点可要成为一条最优输送路径中一些结点，即对于任意x_j∈{x_m+1，…，x_n}，若x_j＝1，则表示第j个站点被选中为该最优输送路径中的一个结点，若x_j＝0，则表示第j个站点未被选中；(3)f(X)为目标函数，用来表示输送路径的总输送成本；(4)表示站点选择时所需满足的第i_a个不等式约束条件；I为不等式约束条件编号的集合；(5)表示站点选择时所需满足的第i_b个等式约束条件；E为等式约束条件编号的集合；(6)f(X)、的数学表达式没有限制条件；(7)H为搜索空间，又称解空间；(8)计算时，决策向量X也称为试探解；若试探解X不满足约束条件，则令f(X)＝+∞；所述TPO_MYPPSS方法，采用具有阶段结构的多种群捕食‑食饵系统动力学理论，假设在一个生态系统中生长若干个动物种群，每个种群分为两个阶段类型的种群，即成年种群和幼年种群；成年种群又称成体，幼年种群又称幼体；这些种群以相同的资源为食；成年种群以一定的出生率产生其幼年种群，幼年种群经过一段时间后变为成年种群；该生态系统中的种群之间的相互争夺生存资源对每个种群的影响就表现在对其成年种群和幼年种群的特征的影响上，而且这种影响是随时间随机变化的；一个种群在所有种群中所占的比例越大，该种群在该生态系统中的影响也就越大，该种群会将其影响传播给其他种群；一个种群的生长能力强弱程度采用PGI指数进行描述；一个种群的PGI指数越高，该种群生长能力越强，此类种群称为优势种群；优势种群会将其优势传播给其它种群；一个种群既具有较高的PGI指数，又具有较大的占比，该类种群称为强势种群；强势种群更会将其强势溢出给其它种群；若一个种群受到其它种群的影响，则这种影响会在其特征上体现出来；种群P_i^u的PGI指数计算方法为：式中，u表示种群的阶段类型，u＝M表示成年种群，u＝Y表示幼年种群；为阶段类型为u的种群P_i^u所对应的试探解；N为成年种群或幼年种群数目；i表示种群P_i^u编号；所述TPO_MYPPSS方法包括如下步骤：(S1)初始化：a)令时期t＝0；按表1初始化本方法中涉及到的所有参数；表1 参数的取值方法b)在搜索空间H随机选择N个成年种群所对应的试探解和N个幼年种群所对应的试探解c)在(0，1)内随机确定食饵的初始密度z(0)；d)在[0，1]内随机确定N个成年种群的初始密度：{w₁(0)，w₂(0)，…，w_N(0)}；e)在[0，1]内随机确定N个幼年种群的初始密度：{y₁(0)，y₂(0)，…，y_N(0)}；(S2)执行下列操作：(S3)令时期t从0到G，循环执行步骤(S4)～步骤(S30)，其中G为演化时期数；(S4)计算：r^t＝Rand(r₀，r₁)，K^t＝Rand(K₀，K₁)，h^t＝Rand(h₀，h₁)，b^t＝Rand(b₀，b₁)；i＝1，2，…，N；s＝1，2，…，N；式中，r^t，K^t，b^t，h^t，分别为参数r，K，c_i，b，h，k_s，d_i，e_i，τ_i在时期t的取值；r表示食饵的产生率；K表示食饵的环境容量，K>0；c_i表示种群P_i的成年种群P_i^M的生育率，c_i>0；b表示食饵捕获率，b>0；h表示捕食者对食饵的平均处理时间，h>0；k_s为捕食者种群P_s之间的干扰率常数，k_s>0；d_i和e_i分别表示种群P_i的成年种群P_i^M和幼年种群P_i^Y的死亡率，d_i>0，e_i>0；τ_i表示种群P_i的幼年种群P_i^Y的成熟期长度，τ_i>0；r₀和r₁表示r^t取值的下限和上限，且满足r₀≥0，r₁≥0，r₀≤r₁；K₀和K₁表示K^t取值的下限和上限，且满足K₀≥0，K₁≥0，K₀≤K₁；c₀和c₁表示取值的下限和上限，且满足c₀≥0，c₁≥0，c₀≤c₁；b₀和b₁表示b^t取值的下限和上限，且满足b₀≥0，b₁≥0，b₀≤b₁；h₀和h₁表示h^t取值的下限和上限，且满足h₀≥0，h₁≥0，h₀≤h₁；k₀和k₁表示取值的下限和上限，且满足k₀≥0，k₁≥0，k₀≤k₁；d₀和d₁表示取值的下限和上限，且满足d₀≥0，d₁≥0，d₀≤d₁；e₀和e₁表示取值的下限和上限，且满足e₀≥0，e₁≥0，e₀≤e₁；τ₀和τ₁表示取值的下限和上限，且满足τ₀≥0，τ₁≥0，τ₀≤τ₁；Rand(A，B)表示在[A，B]区间产生一个均匀分布随机数，A和B为给定的常数，要求A≤B；INT(w)表示将实数w按四舍五入取整；(S5)按式(6)、式(7)计算r_i^u(t)，i＝1，2，…，N，u∈{M，Y}；${r_i}^M\left(t\right)=\frac{w_i\left(t\right)}{\underset{s=1}{\overset{N}{\Sigma }}{w}_s\left(t\right)},i=1,2,...,N---\left(6\right)$${r_i}^Y\left(t\right)=\frac{y_i\left(t\right)}{\underset{s=1}{\overset{N}{\Sigma }}{y}_s\left(t\right)},i=1,2,...,N---\left(7\right)$式(6)、(7)中，r_i^M(t)为时期t种群P_i的成年种群P_i^M在所有成年种群中所占的比例，r_i^M(t)又称为时期t种群P_i的成年种群P_i^M的占比；r_i^Y(t)为时期t种群P_i的幼年种群P_i^Y在所有幼年种群中所占的比例，r_i^Y(t)又称为时期t种群P_i的幼年种群P_i^Y的占比；w_i(t)和y_i(t)分别表示种群P_i在时期t的成年种群P_i^M和幼年种群P_i^Y的密度，w_i(t)≥0，y_i(t)≥0；w_s(t)和y_s(t)分别表示种群P_s在时期t的成年种群P_s^M和幼年种群P_s^Y的密度，w_s(t)≥0，y_s(t)≥0；u表示种群的阶段类型，u＝M表示成年种群，u＝Y表示幼年种群；(S6)对于所有u∈{M，Y}，生成特征种群集合QS^u、PS^u、PQS^u、HZ、HP、HSP；其中，时期t的特征种群集合生成方法如下：a)产生有序种群集合QS^u：将各种群中的处于阶段类型为u的种群按序列值从大到小将种群进行排序，形成有序的种群序列Q^u；从序列Q^u中挑选出前L个种群，其编号形成集合QS^u；u∈{M，Y}；L又称施加影响的种群数；b)产生优势种群集合PS^u：从处于阶段类型为u的N个种群中随机挑选出L个种群，这些种群的PGI指数比当前种群P_i^u的PGI指数高，形成优势种群集合PS^u，即u∈{M，Y}；c)产生强势种群集合PQS^u：设有序种群序列若当前种群为P_i，则从中按照i₁，i₂，…，i_N的顺序挑选出L个种群，其PGI指数高于当前种群P_i^u的PGI指数，形成强势种群集合PQS^u，即u∈{M，Y}；d)产生混杂有序种群集合HZ：将所有种群的成年种群和幼年种群进行混排，按照序列的值从大到小将种群进行排序，形成有序的阶段类型混杂的种群序列HZ；从序列HZ中挑选出前L个种群，其编号形成集合HZ；e)产生混杂优势种群集合HP：从所有种群的成年种群和幼年种群中随机挑选出L个种群，这些种群的PGI指数比当前种群P_i中的成年种群和幼年种群的PGI指数都高，形成混杂优势种群集合HP，即f)产生混杂强势种群集合HSP：从所有种群的成年种群和幼年种群中随机挑选出L个种群，这些种群的PGI指数比当前种群P_i中的成年种群和幼年种群的PGI指数都高，且其占比都比当前种群P_i中的成年种群和幼年种群的占比都高，形成混杂优势种群集合HSP，即(S7)令i从1到N，循环执行下述步骤(S8)～步骤(S27)；(S8)令u从M到Y，循环执行下述步骤(S9)～步骤(S26)；(S9)按式(8)、式(9)、式(10)计算z(t+1)、w_i(t+1)和y_i(t+1)；$z(t+1)=z\left(t\right)+r^{t}z\left(t\right)(1-\frac{z\left(t\right)}{K^t})-\frac{b^{t}z\left(t\right)\underset{s=1}{\overset{N}{\Sigma }}{k}_s^t{y}_s\left(t\right)}{1+h^{t}z\left(t\right)+\underset{i=1}{\overset{N}{\Sigma }}{k}_s^t{y}_s\left(t\right)}---\left(8\right)$$w_i(t+1)=w_i\left(t\right)+\frac{c_i^t{b}^t{e}^{-e_i^t{\tau }_i^t}z(t-{\tau }_i)w_i(t-{\tau }_i)}{1+h^{t}z(t-\tau )+\underset{s=1}{\overset{N}{\Sigma }}{k}_s^t{w}_s(t-{\tau }_s)}-d_i{w}_i\left(t\right),i=1,2,...,N---\left(9\right)$式中，z(t)表示时期t食饵的密度，z(t)≥0；(S10)令j从1到n，循环执行下述步骤(S11)～步骤(S24)；(S11)计算：p＝Rand(0,1)，其中p为种群P_i的特征因种群的影响扩散、优势传播和强势溢出而受到影响的实际概率；(S12)若p≤E₀，则执行步骤(S13)～(S22)，其中E₀为种群特征因其它种群的影响扩散、优势传播和强势溢出而受到影响的最大概率；否则，转步骤(S23)；(S13)计算：q＝Rand(0,1)，其中q为影响扩散算子、优势传播算子和强势溢出算子被执行的实际概率；(S14)若q≤1/9，则按式(11)执行影响平行扩散算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in {\mathrm{QS}}^u}{\Sigma }{\alpha }_s{x}_{s,j}^u\left(t\right)& j\le m\\ most({\mathrm{QS}}^u,j)& j>m\end{array}\right.,u\in \{M,Y\}---\left(11\right)$式中：为时期t+1种群P_i^u的特征j的状态值；为时期t种群P_s^u的特征j的状态值；α_s为种群影响传播系数，α_s＝Rand(0.4，0.6)；most(QS^u，j)的含义是：当集合QS^u中的第j个特征的状态值为1的种群的个数大于第j个特征的状态值为0的种群的个数时，most(QS^u，j)＝1；当集合QS^u中的第j个特征的状态值为1的种群的个数小于第j个特征的状态值为0的种群的个数时，most(QS^u，j)＝0；当集合QS^u中的第j个特征的状态值为1的种群的个数等于第j个特征的状态值为0的种群的个数时，most(QS^u，j)的值在0或1两者之中随机选取；(S15)若1/9<q≤2/9，则按式(12)执行影响交叉扩散算子，得到式中：为时期t种群P_s^v的特征j的状态值；(S16)若2/9<q≤1/3，则当j≤m时按式(13)执行优势平行传播算子，得到当j>m时按式(14)执行优势平行传播算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in {\mathrm{PS}}^u}{\Sigma }{\alpha }_s{x}_{s,j}^u\left(t\right)& \left|{\mathrm{PS}}^u\right|>0\\ x_{s,j}^u\left(t\right)& \left|{\mathrm{PS}}^u\right|=0\end{array}\right.,u\in \{M,Y\}---\left(13\right)$$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}most({\mathrm{PS}}^u,j)& \left|{\mathrm{PS}}^u\right|>0\\ x_{i,j}^u\left(t\right)& \left|{\mathrm{PS}}^u\right|=0\end{array}\right.,u\in \{M,Y\}---\left(14\right)$(S17)若1/9<q≤4/9，则当j≤m时按式(15)执行优势交叉传播算子，得到当j>m时按式(16)执行优势交叉传播算子，得到(S18)若4/9<q≤5/9，则当j≤m时按式(17)执行强势平行溢出算子，得到当j>m时按式(18)执行强势平行溢出算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in {\mathrm{PQS}}^u}{\Sigma }{\alpha }_s{x}_{s,j}^u\left(t\right)& \left|{\mathrm{PQS}}^u\right|>0\\ x_{s,j}^u\left(t\right)& \left|{\mathrm{PQS}}^u\right|=0\end{array}\right.,u\in \{M,Y\}---\left(17\right)$$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}most({\mathrm{PQS}}^u,j)& \left|{\mathrm{PQS}}^u\right|>0\\ x_{s,j}^u\left(t\right)& \left|{\mathrm{PQS}}^u\right|=0\end{array}\right.,u\in \{M,Y\}---\left(18\right)$(S19)若5/9<q≤2/3，则当j≤m时按式(19)执行强势交叉溢出算子，得到当j>m时按式(20)执行强势交叉溢出算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}most({\mathrm{PQS}}^v,j)& \left|{\mathrm{PQS}}^v\right|>0\\ x_{i,j}^v\left(t\right)& \left|{\mathrm{PQS}}^v\right|=0\end{array}\right.,v,u\in \{M,Y\},v\ne u---\left(20\right)$(S20)若2/3<q≤7/9，则按式(21)执行影响混杂扩散算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in HZ}{\Sigma }{\beta }_s^u{x}_{s,j}\left(t\right)& j\le m\\ most(HZ,j)& j>m\end{array}\right.,u\in \{M,Y\}---\left(21\right)$式中，为种群影响传播系数，(S21)若7/9<q≤8/9，则当j≤m时按式(22)执行优势混杂传播算子，得到当j>m时按式(23)执行优势混杂传播算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in HP}{\Sigma }{\beta }_s^u{x}_{s,j}\left(t\right)& \left|HP\right|>0\\ x_{i,j}^u\left(t\right)& \left|HP\right|=0\end{array}\right.,u\in \{M,Y\}---\left(22\right)$$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}most(HP,j)& \left|HP\right|>0\\ x_{i,j}^u\left(t\right)& \left|HP\right|=0\end{array}\right.,v,u\in \{M,Y\},v\ne u---\left(23\right)$(S22)若8/9<q≤1，则当j≤m时按式(24)执行强势混杂溢出算子，得到当j>m时按式(25)执行强势混杂溢出算子，得到$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}\underset{s\in HSP}{\Sigma }{\beta }_s^u{x}_{s,j}\left(t\right)& \left|HSP\right|>0\\ x_{i,j}^u\left(t\right)& \left|HSP\right|=0\end{array}\right.,u\in \{M,Y\}---\left(24\right)$$v_{i,j}^u(t+1)=\left\{\begin{array}{cc}most(HSP,j)& \left|HSP\right|>0\\ x_{i,j}^u\left(t\right)& \left|HSP\right|=0\end{array}\right.,v,u\in \{M,Y\},v\ne u---\left(25\right)$(S23)若p>E₀，则令(S24)令j＝j+1，若j≤n，则转步骤(S11)，否则转步骤(S25)；(S25)按式(26)执行生长算子，得到即对于，有式中：$X_i^u\left(t\right)=\left(x_{i,1}^u\right(t),x_{i,2}^u(t),...,x_{i,n}^u(t\left)\right);$$V_i^u(t+1)=\left(v_{i,1}^u\right(t+1),v_{i,2}^u(t+1),...,v_{i,n}^u(t+1\left)\right);$PGI(V_i^u(t+1))，的计算方法按式(2)计算；(S26)若u＝M，则令u＝Y，转步骤(S9)；若u＝Y，则转步骤(S27)；(S27)令i＝i+1，若i≤N，则转步骤(S8)，否则转步骤(S28)；(S28)若新得到的全局最优解X^*t+1与最近一次获得的全局最优解之间的误差满足最低要求ε，则转步骤(S31)，否则转步骤(S29)；(S29)保存新得到的全局最优解X^*t+1；(S30)令t＝t+1，若t≤G，则转上述步骤(S4)，否则转步骤(S31)；(S31)结束。