一种基于子问题动态消减的改进多目标蚁群优化算法

An Improved Multi-Objective Ant Colony Optimization Algorithm Based on Sub-Problems Dynamic Subtraction

摘要: 为进一步提高基于分解的多目标蚁群优化算法的性能，提出了一种子问题动态消减方法并将其结合到MOEA/D-ACO算法中，以此提出了一种基于子问题动态消减的改进多目标蚁群优化算法IMOEA/D-ACO。该算法通过在运行早期识别没有前途的子问题并及时抛弃对其进行搜索来提高搜索资源的利用率。从而在搜索资源总量一定的前提下，能够进一步提升算法的性能。为了验证算法性能分别与其他相关算法在不同规模的TSP问题测试用例上进行了实验比较。结果表明IMOEA/D-ACO算法在求解质量上优于被比较算法。

Abstract: To further improve the performance of decomposition based multi-objective ant colony algorithm, a dynamic sub-problem reduction method is proposed and combined with the MOEA/D-ACO algo-rithm. Based on this, a sub-problem dynamic reduction improved multi-objective ant colony algo-rithm called IMOEA/D-ACO is designed. Through identifying the unpromising sub-problems during the early optimizing process and giving them up in time for optimizing, the utilization of the searching resource is further increased. Thus the algorithm performance can be improved when the total consumed resources are fixed. To verify its performance, it is tested on some TSP instances with different scale, and compared with some related algorithms. The results show that the proposed algorithm is superior to the compared algorithms.

1. 引言

近年来，在解决多目标优化问题尤其是路径优化问题时，多目标蚁群算法(multi-objective ant colony optimization algorithms, MOACOs)相对于其他元启发式算法被更广泛采用 [1] [2] [3]，因此对其进行研究具有一定价值。

目前多目标蚁群算法可分为基于非支配排序和基于分解两类。基于非支配排序的多目标蚁群算法产生解的个数比较多，但分布不均匀，通常集中在某一方向上。根据使用信息素矩阵的个数的不同，这类算法又可分为单信息素矩阵多目标蚁群优化算法如MOAQ [4] 和MACS算法 [5]，以及多信息素矩阵多目标蚁群优化算法如PACO [6]、BicriterionAnt [7] 和MOACO算法 [8]。2015年I. D. I. D Ariyasingha等 [9] 对2012年之前的7个基于非支配排序的多目标蚁群算法在多个TSP测试用例上进行了详细的对比分析。Liangjun Ke等 [10] 结合了多目标进化算法(EA)，提出了基于进化分解的蚁群算法(MOEA/D-ACO)，该方法中每个子问题对应一个启发式信息和一个历史最优解，将蚂蚁分为若干组，每只蚂蚁只能分配在一个群组中，每组蚂蚁有自己的信息素矩阵，每只蚂蚁解决一个子问题，并通过聚合它所属组的信息素、子问题的启发式信息和历史最优解来构造新解。2018年作者 [11] 提出了基于分解的多目标蚁群优化算法MOACO/D-ACS，将一个多目标问题分解为多个单目标子问题，蚂蚁分为多个子群，每个子群有各自的信息素矩阵和启发式矩阵，每只蚂蚁可以属于多个子群，也就是说算法每次迭代，在不同组中的同一只蚂蚁都会产生一个解，并用其构造的解更新所在子群的信息素矩阵。

基于分解的多目标蚁群算法获得的帕累托前沿分布相对比较均匀，而且求解质量和效率都好于已有的基于支配的多目标蚁群优化算法。在已有的基于分解的多目标蚁群算法中，在初始化阶段普遍采用切比雪夫方法对多目标优化问题进行分解，通过生成N个权重向量 $\left({\lambda }^1,\cdots ,{\lambda }^n\right)$ 将一个多目标问题划分为N个单目标子问题，优化过程中每个子问题与一只蚂蚁相对应并且所有权重向量保持不变。当非支配解在搜索空间分布不均时，最优解不属于帕累托前沿的子问题数量会进一步增加。如果能够在算法优化过程中尽早识别并放弃针对这些子问题的求解能够进一步搜索资源的利用率，从而提高算法优化性能。为此，本文设计了一种子问题动态消减策略并将其结合到MOEA/D-ACO中，从而提出了改进算法IMOEA/D-ACO。为验证其有效性，应用不同规模的测试问题对算法进行了测试并与多种相关算法进行了比较，结果表明，结合动态消减策略的MOEA/D-ACO算法不但收敛速度快而且大部分测试问题上求解质量更佳。

2. IMOEA/D-ACO算法

IMOEA/D-ACO是在MOEA/D-ACO算法的基础上改进子问题资源分配机制，通过设计的子问题动态削减策略在优化过程中逐步识别并淘汰一些没有前途的子问题，直到子问题的个数等于或小于资源数。以此通过提高资源利用率的方式进一步提升算法性能。

在MOEA/D-ACO算法中蚂蚁数和子问题数相同，每只蚂蚁固定地解决一个子问题，不存在为子问题分配蚂蚁的情况。由于并不清楚非支配解会出现在哪些子问题上，为尽可能多的识别出有前途的子问题，本文在进行子问题分解时生成的子问题数量Q大于群体中的蚂蚁数量N。在蚂蚁构造解之前，首先要根据每个子问题的概率分配蚂蚁，并且算法前期迭代时，总会有一些子问题没有分配到蚂蚁，随着算法的运行，那些分配到蚂蚁的子问题如果连续几次没有产生非支配解，则将此子问题淘汰子问题，这样子问题的个数越来越接近于资源数，直到剩余的每个子问题每次迭代至少分配到一只蚂蚁。

为实现以上过程为每个子问题设置了两个属性：count1和count2。count1的值用于记录子问题产生的非支配解的个数，每次产生一个非支配解就增加1，以提高此子问题在下一次算法迭代时被蚂蚁选中的概率，而产生被支配解则保持不变。count2的值用于记录子问题被选中后连续产生被支配解的次数，如果count2值大于给定的阈值U并且子问题的数量大于N的情况下将其直接淘汰，而当产生非支配解时则将其值重置为零。对于当前的未被淘汰的一个子问题a，其被蚂蚁选择的概率计算公式如(1)所示：

$P_a=\frac{count{1}_a}{{\displaystyle \underset{b\in B}{\sum }count{1}_b}}\left(a\in \left\{1,2,\cdots ,Q\right\}\right)$ (1)

其中，count1a表示子问题a保存的count1的值；B是当前子问题的候选集合，b表示集合B中的一个未被访问的子问题。以此使得子问题产生的非支配解的个数越多即count1的值越大，该子问题下次迭代被蚂蚁选择的概率就越高。

基于以上描述IMOEA/D-ACO算法的基本过程如下：

Step 1：采用切比雪夫方法将带求解问题分解为Q个子问题，每个子问题 $i\in \left[1,Q\right]$ 对应的权重向量为 ${\lambda }_i=\left({\lambda }_i^1,\cdots ,{\lambda }_i^M\right)$ ，M为目标函数数量。

Step 2：初始化，与算法MOEA/D-ACO中Step2步骤一致。

Step 3：先判断子问题是否已经被淘汰。根据公式(3)计算每个子问题被选中的概率，为每只蚂蚁分配子问题，然后使用轮盘赌的方式为每个蚂蚁分配子问题。

Step 4：为每只蚂蚁构造路径，同MOEA/D-ACO中Step3步骤一致。

Step 5：对构建的路径进行评价，方法同算法MOEA/D-ACO中Step4步骤一致。

Step 6：根据每只蚂蚁产生的解是支配解还是非支配解更新子问题的参数count1和count2的值，并决定是否淘汰该子问题。

Step 7：利用蚂蚁构造的新解更新信息素矩阵。与MOEA/D-ACO算法中的Step5一致。

Step 8：更新每个子问题的历史最优解。与MOEA/D-ACO算法中的Step6一致。

Step 9：判断是否满足结束条件，满足则输出Abf；否则，返回到Step3继续下一次迭代。

通过自适应的资源分配策略，算法IMOEA/D-ACO能够在更精细的子问题划分情况下，通过逐步淘汰不好的子问题即其对应的PF难以求解，将有限的资源尽可能多的应用到剩余的比较好的子问题上，有效的提高了资源利用率，在同等条件、资源等情况下，有很高的概率可以产生相对于原算法的更多更好的非支配解。

IMOEA/D-ACO算法的复杂度分析：

设算法运行过程中产生的最多的子问题总数为Q*ITER (其中ITER为迭代次数)，目标函数运算的时间复杂度为 $O\left(f\right)$ ，IMOEA/D-ACO算法的时间复杂度为：

$O\left(\text{IMOEA}/\text{D-ACO}\right)=\left(S\ast \text{ITER}\right)\ast O\left(f\right)+C_1$

而MOEA/D-ACO算法的时间复杂度为：

$O\left(\text{MOEA}/\text{D-ACO}\right)=\left(N\ast \text{ITER}\right)\ast O\left(f\right)+C_2$

其中 $C_1$ 为IMOEA/D-ACO算法进行额外计算的复杂度， $C_2$ 为MOEA/D-ACO算法进行额外计算的复杂度，算法迭代次数为ITER，则有 $C_1=C_2+\text{ITER}\ast O\left(Q\right)$ ，即 $C_1>C_2$ ，又因为 $\left(S*\text{ITER}\right)*O\left(f\right)\gg \text{ITER}*O\left(Q\right)$ 且S与N相差为一个常量，其中S £ Q为每次迭代过程中待求解的子问题数量。所以可以认为 $C_1>C_2$ 对整体的运行时间不在一个量级上，可以忽略不计。即，改进后算法的时间复杂度与原算法相同。

3. 实验与结果

本节将通过在不同规模TSP问题上进行实验测试对IMOEA/D-ACO中的主要参数设置进行探讨，并将其与MOAQ、MACS、PACO、BicriterionAnt、MOACO、MOACO/D-ACS、MOEA/D-ACO等相关算法进行实验比较。实验中采用了4个标准的多目标TSP问题测试用例kroAB100、kroAC100、kroAB150、kroAB200，可以从http://eden.dei.uc.pt~paquete/tsp/下载。实验过程中各算法的终止条件为最大适应度评价次数：N ´ 300 ´ (n/100)²，其中N代表蚂蚁的数量，n代表城市的规模大小。被比较算法的其它参数均按原论文进行设置，IMOEA/D-ACO算法的参数Q和U的设置将在3.1节进行探讨，其他参数设置与MOEA/D-ACO算法相同。实验过程中采用Hypindicator (H-指标) [11] 对算法性能进行比较。

3.1. 参数调整

本小节选择了3个不同规模的测试用例kro-AB100、kro-AB150、kro-AB200对IMOEA/D-ACO算法中参数Q和U的设置对算法性能的影响进行分析。为了保证测试的公平性，对每种参数值配置独立运行30次，将实验结果转化为H-指标，然后取它们的平均值；H-指标默认越小越好。为了提高测试效率，采用固定一个参数值同时调整另一个参数的方式。IMOEA/D-ACO算法中Q的取值范围为[125, 150, 175, 200, 225]，U的范围为[30, 40, 50, 60, 70]。先将Q取中间数175，然后调整U的取值。从图1(a)中可以看出在测试用例kroAB100和kroAB150中，U取40时，H值最小；而对于测试用例kroAB200，U取20时H值最小。然后固定U=40，调整组数Q的值。从图1(b)可以看出，在测试用例kroAB100和kroAB150中，参数Q=150时H值最小；而对于测试用例kroAB200，Q = 175时H值最小。

(a) Parameter U (b) Parameter Q

Figure 1. The parameter adjustments of U and Q

图1. 参数调整

3.2. 与相关算法比较

本节首先使用H-指标来分析各个算法的性能，每个算法在各测试用例上独立运行30次，并将各个算法的实验结果转换成H-指标。实验过程中在所有测试用例上参数U = 40，Q = 150。

通过图2可以看出算法IMOEA/D-ACO在个测试问题上的求解质量明显好于其他被比较算法，并且在求解规模大小为150和200的两个测试问题上其优势更佳明显。通过把各个算法在每个问题上运行30次得出的非支配解集转换成H-指标，然后从最大值、最小值、均值、标准差四个方面进行了比较，结果如表1所示。通过表1也可以看出IMOEA/D-ACO算法在各测试问题上H-指标的最大值、最小值和均值都是最小的，最小值也是最好的。在标准差方面，虽然只在kroAB100这个问题上最小，但在其他几个问题上获得的标准差与最小值相差很小。这说明在这些问题上IMOEA/D-ACO算法不但求解质量最佳，稳定性也相对较好。图3给出了各算法独立运行30次得到的近似Pareto Front，可以看出算法IMOEA/D-ACO在各测试用例上获得的解集明显优于其他算法并且分布比较均匀，更加接近PF。

Figure 2. The box plot for H-indicator

图2. 基于H指标的盒子图

Table 1. The comparative results of related algorithm

表1. 相关算法结果比较

Figure 3. The approximated PFs

图3. 近似帕累托前沿

4. 总结

已有的基于分解的多目标蚁群优化算法在初始化时采用切比雪夫方法生成子问题并且在整个优化过程中固定不变。基于以上情况，本文在MOEA/D-ACO算法的基础上提出了子问题动态削减方法使得在资源有限的前提下，每次迭代时能够根据每个子问题的好坏自动地为每只蚂蚁分配子问题。随着迭代次数的增多，逐步地将不好的子问题删除，将更多的资源用在产生非支配解比较多的子问题上，以达到节约资源的目的。实验结果表明，本文提出的方法是有效的，在搜索资源总量一定的情况下，通过提高搜索资源的利用率能够进一步提高算法的性能。

基金项目

辽宁省博士启动基金项目(2020-BS-152)，沈阳理工大学校级大学生创新训练计划项目(202010144091)。