# 一种基于子问题动态消减的改进多目标蚁群优化算法An Improved Multi-Objective Ant Colony Optimization Algorithm Based on Sub-Problems Dynamic Subtraction

DOI: 10.12677/SEA.2020.96054, PDF, HTML, XML, 下载: 111  浏览: 177  科研立项经费支持

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. 引言

2. IMOEA/D-ACO算法

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

${P}_{a}=\frac{count{1}_{a}}{\underset{b\in B}{\sum }count{1}_{b}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(a\in \left\{1,\text{\hspace{0.17em}}2,\text{\hspace{0.17em}}\cdots ,\text{\hspace{0.17em}}Q\right\}\right)$ (1)

Step 1：采用切比雪夫方法将带求解问题分解为Q个子问题，每个子问题 $i\in \left[1,\text{\hspace{0.17em}}Q\right]$ 对应的权重向量为 ${\lambda }_{i}=\left({\lambda }_{i}^{1},\text{\hspace{0.17em}}\cdots ,{\lambda }_{i}^{M}\text{\hspace{0.17em}}\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算法的复杂度分析：

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

$\text{\hspace{0.17em}}O\left(\text{MOEA}/\text{D-ACO}\right)=\left(N\ast \text{ITER}\right)\ast O\left(f\right)+{C}_{2}$

3. 实验与结果

3.1. 参数调整

(a) Parameter U (b) Parameter Q

Figure 1. The parameter adjustments of U and Q

3.2. 与相关算法比较

Figure 2. The box plot for H-indicator

Table 1. The comparative results of related algorithm

Figure 3. The approximated PFs

4. 总结

 [1] Zuo, L.Y., Shu, L., et al. (2015) A Multi-Objective Optimization Scheduling Method Based on the Ant Colony Algo-rithm in Cloud Computing, IEEE Access, 3, 2687-2699. https://doi.org/10.1109/ACCESS.2015.2508940 [2] Juang, C.-F., Jeng, T.-L. and Chang, Y.-C. (2015) An Inter-pretable Fuzzy System Learned through Online Rule Generation and Multi-Objective ACO with a Mobile Robot Control Application. IEEE Transactions on Cybernetics, 46, 2706-2718. https://doi.org/10.1109/TCYB.2015.2486779 [3] Wang, L.J. and Shen, J. (2016) Multi-Phase Ant Colony System for Multi-Party Data-Intensive Service Provision. IEEE Transactions on Services Computing, 9, 264-276. https://doi.org/10.1109/TSC.2014.2358213 [4] García-Martínez, C., Cordón, O. and Herrera, F. (2007) A Tax-onomy and an Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-Criteria TSP. European Journal of Operational Research, 180, 116-148. https://doi.org/10.1016/j.ejor.2006.03.041 [5] Barán, B. and Schaerer, M. (2003) A Multiobjective Ant Colony System for Vehicle Routing Problem with Time Windows. The 21st IASTED International Multi-Conference on Applied Informatics, Innsbruck, 10-13 February 2003, 97-102. [6] Doerner, K., Gutjahr, W.J., Hartl, R.F., et al. (2004) Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection. Annals of Operations Re-search, 131, 79-99. https://doi.org/10.1023/B:ANOR.0000039513.99038.c6 [7] Iredi, S., Merkle, D. and Middendorf, M. (2001) Bi-Criterion Optimization with Multi Colony Ant Algorithms. International Conference on Evolutionary Multi-Criterion Optimization, 8, 359-372. https://doi.org/10.1007/3-540-44719-9_25 [8] López-Ibánez, M. and Stützle, T. (2012) The Automatic Design of Multiobjective Ant Colony Optimization Algorithms. IEEE Transactions on Evolutionary Computation, 16, 861-875. https://doi.org/10.1109/TEVC.2011.2182651 [9] Idid, A. and Tgi, F. (2015) Performance Analysis of the Multi-Objective Ant Colony Optimization Algorithms for the Traveling Salesman Problem. Swarm and Evolutionary Computation, 23, 11-26. https://doi.org/10.1016/j.swevo.2015.02.003 [10] Ke, L., Zhang, Q.F. and Battiti, R. (2013) MOEA/D-ACO: A Multi-Objective Evolutionary Algorithm Using Decomposition and Ant Colony. IEEE Transactions on Cybernetics, 43, 1845-1859. https://doi.org/10.1109/TSMCB.2012.2231860 [11] Ning, J.X., Zhang, Q., Zhang, C.S. and Zhang, B. (2018) A Best-Path-Updating Information-Guided Ant Colony Optimization Algorithm. Information Science, 433-434, 142-162. https://doi.org/10.1016/j.ins.2017.12.047