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