一种大规模多目标智能移动路径选择的蚁群优化处理方法

摘要

本发明公开了一种大规模多目标智能移动路径选择的蚁群优化处理方法，在获取NTSP个目标物流送货地址和两两地址之间的距离、经过每段路径的成本等M个代价的数据后，采用蚁群优化技术对路径规划单元进行求解以获得智能移动主体送货的具体行走路径并输出至执行机构予以实现。本发明方法在求解大规模多目标智能移动路径选择问题时，优化性能好，具有并行性、自组织性和强鲁棒性等优点，所获得的解的数量多、质量优，向真实Pareto解集逼近能力强；获得的解集分布均匀；计算速度快。可用于物流配送、智能交通、互联网和机器人等领域中路径规划系统的智能处理单元中。

主权项

1.一种大规模多目标智能移动路径选择的蚁群优化处理方法，在获取N_TSP个目标物流送货地址和两两地址之间的距离、经过每段路径的成本等M个代价的数据后，在路径规划单元进行求解以获得智能移动主体送货的具体行走路径并输出至执行机构予以实现，所述路径规划单元采用如下的步骤：1.初始化算法参数；2.采用切比雪夫分解法将多目标路径选择问题分解为N个单目标子问题，第n个子问题的适应度函数为：$g_n\left(\pi \right|{\lambda }^n,z)=\underset{1\le m\le M}{\max }\left\{{\lambda }_m^n\right|f_m\left(\pi \right)-z\left|\right\}---\left(1\right)$式中，为第n个子问题的目标权重向量，且z＝(z₁，z₂，L，z_M)为参考点向量，π为子问题的一个可行解，f_m(π)为该可行解第m个目标函数值，M为多目标路径选择问题的目标数据个数；3.由N只蚂蚁构成的蚁群根据权向量以重叠方式划分为N个子蚁群，每个子蚁群求解一个子问题；求解第n个子问题的子蚁群S(n)包含K个蚂蚁，即S(n)＝{i₁，i₂，L，i_K}，n＝1，2，L，N，其中i_j为与λⁿ具有第j个最佳距离的权重向量λ的上标；4.确定蚁群中每只蚂蚁求解的子问题集合A(k)，A(k)＝{n|k∈S(n)，n＝1，2，L，N}，k＝1，2，L，N；5.初始化每个子问题的信息素矩阵τⁿ、启发式信息矩阵ηⁿ和初始信息素n＝1，2，L，N，初始化方式为：${\tau }_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\Sigma }}{\lambda }_m^n{f}_m\left({\pi }^m\right)---\left(2\right)$${\eta }_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\Sigma }}{\lambda }_m^k{c}_{\mathrm{ij}}^m---\left(3\right)$${\tau }_0^n=1/\underset{m=1}{\overset{M}{\Sigma }}{\lambda }_m^k{f}_m\left({\pi }^m\right)---\left(4\right)$式中，π为初始可行解，为第n个子问题中城市i和城市j之间的信息素量，为第n个子问题中城市i和城市j之间的启发式信息量；为城市i和城市j之间的第m个目标代价；为第n个子问题的初始信息素量；6.循环次数t增加1，即t←t+1，且子问题索引n取为0；7.子问题索引n增加1，即n←n+1；8.子蚁群S(n)中的每只蚂蚁随机选择一个城市作为遍历起点；9.S(n)中的K只蚂蚁依次按公式(5)所示转移规则选择城市j前进，并按照公式(7)更新信息素τⁿ：${\tau }_{\mathrm{ij}}^n=(1-\xi ){\tau }_{\mathrm{ij}}^n+\xi {\tau }_0^n---\left(7\right)$式中，α为信息素权重，β为启发式信息权重，Ω(i)为位于城市i的蚂蚁下一个可访问的城市集合，ξ为局部信息素挥发系数，q₀为概率常数；10.若S(n)中的所有蚂蚁均未回到出发城市，则跳转到第9步，否则继续到下一步，即第11步；11.按照公式(1)计算子蚁群S(n)中K只蚂蚁构建路径的适应度函数值，并计算对应路径的M个目标值；12.按照公式(8)确定子蚁群S(n)中的最优蚂蚁b_n，即$b_n=\arg \underset{k\in S\left(n\right)}{\min }\left\{g_n\left({\pi }^k\right|{\lambda }^n,z)\right\}---\left(8\right)$13.利用S(n)中蚂蚁构建的解的目标函数值按式(9)更新参考点z的分量z_m，m＝1，2，L，M，即$z_m=\underset{k\in S\left(n\right)}{\min }\left(f_m\left({\pi }^k\right)\right)---\left(9\right)$14.利用S(n)中蚂蚁构建的解的目标函数值按式(10)更新子问题n的初始信息素即${\tau }_0^n=1/\underset{m=1}{\overset{M}{\Sigma }}{\lambda }_m^n{\hat{f}}_m^n---\left(10\right)$${\hat{f}}_m^n=\underset{k\in S\left(n\right)}{\Sigma }{f}_m\left({\pi }^n\right)/K---\left(11\right)$15.利用最优蚂蚁路径并按照公式(12)更新所有l∈A(b_n)的信息素矩阵τ^l，即${\tau }_{\mathrm{ij}}^l=(1-\rho ){\tau }_{\mathrm{ij}}^l+\mathrm{\rho \Delta }{\tau }^l---\left(12\right)$$\Delta {\tau }^l=1/\underset{m=1}{\overset{M}{\Sigma }}{\lambda }_m^l{f}_m\left({\pi }^l\right)---\left(13\right)$16.将S(n)中蚂蚁构建的解的目标函数值加入到非支配解集Φ中，然后移除非支配解集中的支配解；17.当前循环中还有子问题没有求解，即n≠N，则算法跳转到第7步，否则继续到下一步，即第18步；若该算法满足结束条件，即如果循环次数t≥T，则循环结束，并输出非支配解集Φ，否则，算法跳转到第6步。