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

Abstract

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

Description

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

所属技术领域

本发明涉及智能移动设备，尤其是智能移动主体优化选择合理路径技术领域。

背景技术

路径规划是物流配送领域，特别是在物联网技术支持下的智能物流中的关键问题。执行物流配送的智能移动主体欲对n个客户的订货完成送货，并使得费用消耗、路线距离等M个相互矛盾的代价尽可能同时达到最小。从数学处理方法的角度来看，以上问题可抽象为一个典型的数学问题，即所谓多目标旅行商问题(Multi-objective Traveling Salesman Problem，MTSP)，MTSP的一般描述为：给定n个城市及它们两两之间的M个代价，且各个代价之间相互矛盾，某一旅行商要访问这n个城市，从某一城市出发，遍访其余n-1个城市且仅遍访一次，最后返回到出发城市。需要求解的问题是，该旅行商应该如何选择遍访的路径，使得M个相互矛盾的遍访代价尽可能同时达到最小。

由于本发明智能移动主体优化选择合理路径欲解决的实际问题与上述MTSP的解决间接相关，我们可对MTSP求解的现状作以下的回顾。

传统的MTSP求解步骤包含两步：问题转换以及转换问题的求解。对MTSP进行转换的方法主要有两类：一类是将MTSP转化为标准TSP，具有代表性的转化方法有直接法、乘除法、Lamda-加权法、平方和加权法、理想点法，这类方法存在各目标权重设置和理想点选取难问题；另一类是将MTSP中的多个目标进行排序，并按照目标优先级进行求解，具有代表性的方法有序列法和主要目标法，这类方法需要有一些关于多个目标的先验认知。对转换问题的求解方法也包括两类：一类是精确求解法，具有代表性的有分支定界法、割平面法和动态规划等，这些方法能够保证得到转换问题的最优解，但是其运算时间随问题复杂程度呈指数增长，无法在多项式时间内求解，因而难以解决大规模问题；另一类是近似求解法，该类方法以在多项式时间内获得近似最优解为目标，这一类方法可进一步划分为三个子类：一是路径构造法，该方法从不可行解或不完全解开始，通过某种策略逐步构造，直到得到一个可行解，其中以最近邻法为代表；二是路径改进法，它是采用某种策略对可行解进行改进，典型策略包括遗传算法、边交换算法、禁忌搜索等；三是路径构造法和路径改进法的结合，其中路径构造法产生初始解，路径改进法对初始解进行改进。由于MTSP本身不存在最优解，而传统MTSP求解方法只能获得一个解，且这个解是对多个目标的一种折衷，但实际情况是，不同的情形应该采用不同的折衷方法。因此，如何产生一个包含尽可能多优质解的解集，交由决策人员根据不同实际情况在解集中进行选择是解决多目标问题的关键。此外，另一个问题是随着生产的发展，实际问题的规模越来越大，现有的方法在MTSP规模超过上千时性能非常差。因此，大规模MTSP是多目标组合优化技术领域的关键性问题。

蚁群优化是具有并行性、自组织性和强鲁棒性等特点的一种优化技术，适合用来解决TSP这类组合优化问题。目前，在采用蚁群优化解决MTSP的方法中，具有代表性的有MACS，BIANT和UNBI，但这些方法在解决大规模MTSP时性能退化严重。由此，发明一种能有效求解大规模MTSP的蚁群优化方法具有重要的实际意义。

发明内容

鉴于现有技术的以上缺点，本发明的目的是获得一种能有效求解大规模MTSP的蚁群优化多目标智能移动路径选择的处理方法，使之能克服现有技术在路径求解方面的缺点，更便利有效地提高智能移动主体的处理能力。

本发明为解决其技术问题，所采用的技术方案为：

一种大规模多目标智能移动路径选择的蚁群优化处理方法，在获取N_TSP个目标物流送货地址和两两地址之间的距离、经过每段路径的成本等M个代价的数据后，在路径规划单元进行求解以获得智能移动主体送货的具体行走路径并输出至行走机构予以实现，采用如下的步骤予以实现：

1.初始化算法参数；

2.采用切比雪夫分解法将MTSP分解为N个单目标子问题，第n个子问题的适应度函数为：

$g_n\left(\mathrm{\π}\right|{\mathrm{\λ}}^n,z)=\underset{1\≤m\≤M}{\max }\left\{{\mathrm{\λ}}_m^n\right|f_m\left(\mathrm{\π}\right)-z\left|\right\}---\left(1\right)$

式中，

为第n个子问题的目标权重向量，且

为参考点向量，π为子问题的一个可行解，f_m(π)为该可行解第m个目标函数值，M为MTSP目标数据个数；

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，初始化方式为：

${\mathrm{\τ}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{f}_m\left({\mathrm{\π}}^m\right)---\left(2\right)$

${\mathrm{\η}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{c}_{\mathrm{ij}}^m---\left(3\right)$

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{f}_m\left({\mathrm{\π}}^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)更新信息素τⁿ：

${\mathrm{\τ}}_{\mathrm{ij}}^n=(1-\mathrm{\ξ}){\mathrm{\τ}}_{\mathrm{ij}}^n+\mathrm{\ξ}{\mathrm{\τ}}_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\∈S\left(n\right)}{\min }\left\{g_n\left({\mathrm{\π}}^k\right|{\mathrm{\λ}}^n,z)\right\}---\left(8\right)$

13.利用S(n)中蚂蚁构建的解的目标函数值按式(9)更新参考点z的分量z_m，m＝1，2，L，M，即

$z_m=\underset{k\∈S\left(n\right)}{\min }\left(f_m\left({\mathrm{\π}}^k\right)\right)---\left(9\right)$

14.利用S(n)中蚂蚁构建的解的目标函数值按式(10)更新子问题n的初始信息素

即

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{\hat{f}}_m^n---\left(10\right)$

${\hat{f}}_m^n=\underset{k\∈S\left(n\right)}{\mathrm{\Σ}}{f}_m\left({\mathrm{\π}}^n\right)/K---\left(11\right)$

15.利用最优蚂蚁路径并按照公式(12)更新所有l∈A(b_n)的信息素矩阵τ^l，即

${\mathrm{\τ}}_{\mathrm{ij}}^l=(1-\mathrm{\ρ}){\mathrm{\τ}}_{\mathrm{ij}}^l+\mathrm{\ρ\Δ}{\mathrm{\τ}}^l---\left(12\right)$

$\mathrm{\Δ}{\mathrm{\τ}}^l=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^l{f}_m\left({\mathrm{\π}}^l\right)---\left(13\right)$

16.将S(n)中蚂蚁构建的解的目标函数值加入到非支配解集Φ中，然后移除非支配解集中的支配解；

17.当前循环中还有子问题没有求解，即n≠N，则算法跳转到第7步，否则继续到下一步，即第18步；

18.若该算法满足结束条件，即如果循环次数t≥T，则循环结束，并输出非支配解集Φ，否则，算法跳转到第6步。

采用本发明方法，在求解大规模MTSP时，优化性能好，具有并行性、自组织性和强鲁棒性等优点，所获得的解的数量多、质量优，向真实Pareto解集逼近能力强；获得的解集分布均匀；计算速度快。可用于物流配送、智能交通、互联网和机器人等领域中路径规划系统的智能处理单元中。

本发明提供一种求解大规模MTSP的有效技术途径，在如下三方面优于该领域中最为著名的三种方法(MACS，BIANT和UNBI)：

1.本发明获得的解集比MACS，BIANT和UNBI更逼近真实Pareto解集。解集越逼近真实Pareto解集，其度量值越小，质量越高。通过将MTSP分解为多个单目标问题以及将蚁群以重叠方式分解为多个子蚁群，且每个子蚁群求解一个单目标问题和所有单目标问题同时进行求解，本发明能获得高质量的解集。表1给出了本发明在求解8个典型双目标旅行商问题时，获得的解集逼近真实Pareto解集程度与MACS，BIANT和UNBI三种方法的对比，求解问题选自TSPLIB数据库，四种方法的结果来自每种方法对每个问题进行20次独立实验获得的平均值。在表1中，对于8个问题，本发明获得的值均远小于MACS，BIANT和UNBI三种方法的结果，表明本发明获得的解集最逼近真实Pareto解集，解的质量最好。

2.本发明获得的解集分布均匀程度优于MACS，BIANT和UNBI。解集分布均匀程度是指某方法获得的解集沿Pareto前沿分布的均匀程度，分布越均匀，则解集的质量越好，相应的度量值越大。表2给出了本发明在求解8个典型双目标旅行商问题时，获得的解集分布均匀程度与MACS，BIANT和UNBI三种方法的对比，表中结果来自每种方法对每个问题进行20次独立实验获得的平均值。在表2中，对于8个问题中6个，本发明获得的值均大于MACS，BIANT和UNBI，表明本发明获得的解集分布均匀程度优于MACS，BIANT和UNBI，质量最好。

表1本发明和MACS、BIANT、UNBI在逼近真实Pareto解集程度上的比较

表2本发明与MACS，BIANT和UNBI在解集分布均匀程度上的比较

3.本发明的计算复杂度小于MACS，BIANT和UNBI三种方法。计算复杂度越小的方法，在求解相同规模的问题时，需要的计算时间越少，性能越好。本发明在求解8个典型双目标旅行商问题时，所需的计算时间与MACS，BIANT和UNBI三种方法的对比结果如表3所示。表3中的结果为每种方法对每个问题进行20次独立实验获得的平均值。从表3可看出，随着问题复杂程度的增加，本发明与MACS，BIANT和UNBI三种方法消耗时间的差距越大，优势越明显。

表3本发明与MACS，BIANT和UNBI在计算时间上的比较(单位为秒)

附图说明

图1是本发明实施例在当循环次数为20时，四种方法的Pareto前沿对比；

图2是本发明实施例在当进化代数为40时，四种方法的Pareto前沿对比；

图3是本发明实施例在当进化代数为60时，四种方法的Pareto前沿对比；

图4是本发明实施例在当进化代数为80时，四种方法的Pareto前沿对比；

图5是本发明实施例在当进化代数为80时，四种方法的Pareto前沿对比；

在图1至图5中，横坐标为目标1的数值，纵坐标为目标2的数值，都没有单位，符号“·”表示本发明获得的Pareto前沿，符号“+”表示MACS方法获得的Pareto前沿，符号“o”表示BIANT方法获得的Pareto前沿，符号“*”表示UNBI方法获得的Pareto前沿。

具体实施方式

下面结合具体实施方式对本发明作进一步详细描述。

实施例

采用本发明求解由200个城市组成的双目标旅行商问题，该问题由标准数据库TSPLIB中两个单目标旅行商问题KroA200和KroB200构造而成。实验采用Matlab作为实现工具，在CPU为AMD Sempron 1.6GHz、内存为1GB、操作系统为Windows XP的计算机上进行求解。

本发明所提供的一种求解大规模多目标旅行商问题的蚁群优化方法的具体实现步骤如下：

Step 1：参数初始化：设置算法的参数α＝1，β＝2，ρ＝0.1，q₀＝0.9，ξ＝0.1，K＝5，N＝20，T＝100，Φ＝

，权重向量随机产生，本实施例中的权重向量为λ¹＝[0.0170 0.9830]，λ²＝[0.0541 0.9459]，λ³＝[0.2177 0.7823]，λ⁴＝[0.2444 0.7556]，λ⁵＝[0.2551 0.7449]，λ⁶＝[0.2579 0.7421]，λ⁷＝[0.3035 0.6965]，λ⁸＝[0.3882 0.6118]，λ⁹＝[0.4728 0.5272]，λ¹⁰＝[0.5002 0.4998]，λ¹¹＝[0.5194 0.4806]，λ¹²＝[0.5259 0.4741]，λ¹³＝[0.5265 0.4735]，λ¹⁴＝[0.5289 04711]，λ¹⁵＝[0.5533 0.4467]，λ¹⁶＝[0.5799 0.4201]，λ¹⁷＝[0.6068 0.3932]，λ¹⁸＝[0.7459 0.2541]，λ¹⁹＝[0.7707 0.2293]，λ²⁰＝[0.7851 0.2149]，本实施例中的参考点z为由200个城市依次连接构成的路径的目标函数向量，即z＝[373940 327450]；

Step 2：采用切比雪夫分解法将该旅行商问题分解为20个单目标子问题，第n个子问题的适应度函数由公式(1)描述，即

$g_n\left(\mathrm{\π}\right|{\mathrm{\λ}}^n,z)=\underset{1\≤m\≤2}{\max }\left\{{\mathrm{\λ}}_m^n\right|f_m\left(\mathrm{\π}\right)-z\left|\right\}$

式中，λ¹，λ²，L，λ²⁰和z如Step 1中所示，π为子问题的一个可行解，f_m(π)为该可行解第m个目标函数值；

Step 3：将20只蚂蚁根据权向量以交叠方式分解为20个子蚁群，每个子蚁群记为S(n)且包含5只蚂蚁，在本实施例中，S(1)＝[1 2 3 4 5]，S(2)＝[2 1 3 4 5]，S(3)＝[3 4 2 5 1]，S(4)＝[4 3 2 5 1]，S(5)＝[5 6 4 7 3]，S(6)＝[6 5 4 7 8]，S(7)＝[7 8 6 910]，S(8)＝[8 7 6 9 10]，S(9)＝[9 10 11 12 13]，S(10)＝[10 9 11 12 13]，S(11)＝[11 109 12 13]，S(12)＝[12 13 11 10 9]，S(13)＝[13 12 11 10 9]，S(14)＝[14 15 16 17 13]，S(15)＝[15 14 16 17 13]，S(16)＝[16 17 15 14 13]，S(17)＝[17 16 15 14 13]，S(18)＝[1819 17 16 15]，S(19)＝[19 18 17 16 15]，S(20)＝[20 9 10 11 8]；

Step 4：确定蚁群中每只蚂蚁求解问题集合A(k)，k＝1，2，L，20。本实施例中，A(1)＝[1 2 3 4]，A(2)＝[1 2 3 4]，A(3)＝[1 2 3 4 5]，A(4)＝[1 2 3 4 5 6]，A(5)＝[1 23 4 5 6]，A(6)＝[5 6 7 8]，A(7)＝[5 6 7 8]，A(8)＝[6 7 8 20]，A(9)＝[7 8 9 10 11 12 13 20]，A(10)＝[7 8 9 10 11 12 13 20]，A(11)＝[9 10 11 12 13 20]，A(12)＝[9 10 11 12 13]，A(13)＝[9 10 11 12 13 14 15 16 17]，A(14)＝[14 15 16 17]，A(15)＝[14 15 16 17 18 19]，A(16)＝[14 15 16 17 18 19]，A(17)＝[14 15 16 17 18 19]，A(18)＝[18 19]，A(19)＝[1819]，A(20)＝[20]；

Step 5：按照公式(2)、(3)和(4)分别初始化信息素矩阵τⁿ、启发式信息矩阵ηⁿ和初始信息素

n＝1，2，L，20，即

${\mathrm{\τ}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{2}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{f}_m\left({\mathrm{\π}}^m\right)$

${\mathrm{\η}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{2}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{c}_{\mathrm{ij}}^m$

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{2}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{f}_m\left({\mathrm{\π}}^m\right)$

式中，π为初始有效解，

为第n个子问题中城市i和城市j之间的信息素量，

为第n个子问题中城市i和城市j之间的启发式信息量；

为城市i和城市j之间的第m个目标代价；

为第n个子问题的初始信息素量；

Step 6：循环次数t增加1，即t←t+1，且子问题索引n取为0；

Step 7：子问题索引n增加1，即n←n+1；

Step 8：子蚁群S(n)中的5只蚂蚁随机选择一个城市作为遍历起点；

Step 9：S(n)中的5只蚂蚁依次按公式(5)选择城市j前进，并按照公式(7)更新信息素τⁿ：

${\mathrm{\τ}}_{\mathrm{ij}}^n=(1-0.1){\mathrm{\τ}}_{\mathrm{ij}}^n+{0.1\mathrm{\τ}}_0^n$

式中，Ω(i)为位于城市i的蚂蚁下一个可访问的城市集合；

Step 10：若S(n)中的所有蚂蚁均未回到出发城市，则跳转到第9步，否则继续到下一步，即第11步；

Step 11：按照公式(1)计算本次循环子蚁群S(n)中5只蚂蚁构建路径的适应度函数值，并计算对应路径的2个目标值；

Step 12：按照公式(8)确定子蚁群S(n)中的最优蚂蚁b_n；

$b_n=\arg \underset{k\∈S\left(n\right)}{\min }\left\{g_n\left({\mathrm{\π}}^k\right|{\mathrm{\λ}}^n,z)\right\}$

Step 13：利用S(n)中蚂蚁构建的解的目标函数值按式(9)更新参考点z的分量z_m，m＝1，2；

$z_m=\underset{k\∈S\left(n\right)}{\min }\left(f_m\left({\mathrm{\π}}^k\right)\right)$

Step 14：利用S(n)中蚂蚁构建的解的目标函数值按式(10)更新子问题n的初始信息素

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{2}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{\hat{f}}_m^n$

${\hat{f}}_m^n=\underset{k\∈S\left(n\right)}{\mathrm{\Σ}}{f}_m\left({\mathrm{\π}}^n\right)/5$

Step 15：利用最优蚂蚁路径并按照公式(12)更新所有l∈A(b_n)的信息素矩阵τ^l，即

${\mathrm{\τ}}_{\mathrm{ij}}^l=(1-\mathrm{\ρ}){\mathrm{\τ}}_{\mathrm{ij}}^l+\mathrm{\ρ\Δ}{\mathrm{\τ}}^l$

$\mathrm{\Δ}{\mathrm{\τ}}^l=1/\underset{m=1}{\overset{2}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^l{f}_m\left({\mathrm{\π}}^l\right)$

Step 16：将S(n)中蚂蚁构建的解的目标函数值加入到非支配解集Φ中，然后移除非支配解集中的支配解；

Step 17：当前循环中还有子问题没有求解，即n≠20，则跳转到第7步，否则继续到下一步，即第18步；

Step 18：若该算法满足结束条件，即如果循环次数t≥100，则循环结束，并输出非支配解集Φ，算法跳转到第6步。

对本实施例进行计算机仿真，Pareto解集进化过程如图1-图5所示。这些结果清楚表明，本发明的优化性能优于MACS、BIANT和UNBI三种方法，尤其是在进化过程早期获得的解集具有最好的逼近以及最均匀的分布。

显然，本发明可以在线或离线的方式用于智能移动主体(例如：物流机器人)的路径规划系统的智能处理单元中，鉴于本问题的实质抽象性和处理类似对象的广泛性，本发明方法还可应用到许多实际领域，比如：交通工具和交通系统的调配、智能交通、互联网的数据传输调配管理等。

Claims (1)

1.一种大规模多目标智能移动路径选择的蚁群优化处理方法，在获取N_TSP个目标物流送货地址和两两地址之间的距离、经过每段路径的成本等M个代价的数据后，在路径规划单元进行求解以获得智能移动主体送货的具体行走路径并输出至执行机构予以实现，所述路径规划单元采用如下的步骤：

1.初始化算法参数；

2.采用切比雪夫分解法将多目标路径选择问题分解为N个单目标子问题，第n个子问题的适应度函数为：

$g_n\left(\mathrm{\π}\right|{\mathrm{\λ}}^n,z)=\underset{1\≤m\≤M}{\max }\left\{{\mathrm{\λ}}_m^n\right|f_m\left(\mathrm{\π}\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，初始化方式为：

${\mathrm{\τ}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{f}_m\left({\mathrm{\π}}^m\right)---\left(2\right)$

${\mathrm{\η}}_{\mathrm{ij}}^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{c}_{\mathrm{ij}}^m---\left(3\right)$

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^k{f}_m\left({\mathrm{\π}}^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)更新信息素τⁿ：

${\mathrm{\τ}}_{\mathrm{ij}}^n=(1-\mathrm{\ξ}){\mathrm{\τ}}_{\mathrm{ij}}^n+\mathrm{\ξ}{\mathrm{\τ}}_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\∈S\left(n\right)}{\min }\left\{g_n\left({\mathrm{\π}}^k\right|{\mathrm{\λ}}^n,z)\right\}---\left(8\right)$

13.利用S(n)中蚂蚁构建的解的目标函数值按式(9)更新参考点z的分量z_m，m＝1，2，L，M，即

$z_m=\underset{k\∈S\left(n\right)}{\min }\left(f_m\left({\mathrm{\π}}^k\right)\right)---\left(9\right)$

14.利用S(n)中蚂蚁构建的解的目标函数值按式(10)更新子问题n的初始信息素

即

${\mathrm{\τ}}_0^n=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^n{\hat{f}}_m^n---\left(10\right)$

${\hat{f}}_m^n=\underset{k\∈S\left(n\right)}{\mathrm{\Σ}}{f}_m\left({\mathrm{\π}}^n\right)/K---\left(11\right)$

15.利用最优蚂蚁路径并按照公式(12)更新所有l∈A(b_n)的信息素矩阵τ^l，即

${\mathrm{\τ}}_{\mathrm{ij}}^l=(1-\mathrm{\ρ}){\mathrm{\τ}}_{\mathrm{ij}}^l+\mathrm{\ρ\Δ}{\mathrm{\τ}}^l---\left(12\right)$

$\mathrm{\Δ}{\mathrm{\τ}}^l=1/\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{\mathrm{\λ}}_m^l{f}_m\left({\mathrm{\π}}^l\right)---\left(13\right)$

16.将S(n)中蚂蚁构建的解的目标函数值加入到非支配解集Φ中，然后移除非支配解集中的支配解；

17.当前循环中还有子问题没有求解，即n≠N，则算法跳转到第7步，否则继续到下一步，即第18步；

若该算法满足结束条件，即如果循环次数t≥T，则循环结束，并输出非支配解集Φ，否则，算法跳转到第6步。

Images