多目标蚁群优化研究综述

doi:10.11896/j.issn.1002-137X.2017.10.002

摘要/Abstract

摘要： 多目标蚁群优化是一类重要的多目标进化算法,它在解决多目标优化问题,尤其是多目标组合优化方面,具有优异的性能。首先,通过总结多目标蚁群优化的研究成果,将多目标蚁群优化分为基于帕累托的方法、基于指标函数的方法和目标分解法3类,并阐述了每类方法的特点和代表性算法;然后,展现了多目标蚁群优化在实际问题中的广泛应用；最后,探讨了目前多目标蚁群优化存在的问题。

关键词: 多目标蚁群优化,多目标进化算法,帕累托优化,指标函数,分解

Abstract: Multiobjective ant colony optimization is one of the important mutiobjective evolutionary algorithms,which has excellent performance in multiobjective optimization problems especially multiobjective combinational optimization problems.In this paper,we summarized the development of the multiobjective ant colony optimization and classified it into three classes,i.e.method based on pareto’s relation,method based on indicators and method based on decomposition.Besides,we also summarized each method’s characteristics and its classical algorithms.We showed its spread applications in real problems.In the end,we discussed the existing problems in multiobjective ant colony optimization.

Key words: Multiobjective ant colony optimization,Multiobjective evolutionary algorithms,Pareto optimality,Indicator function,Decomposition

刁兴春,刘艺,曹建军,尚玉玲. 多目标蚁群优化研究综述[J]. 计算机科学, 2017, 44(10): 7-13. https://doi.org/10.11896/j.issn.1002-137X.2017.10.002

DIAO Xing-chun, LIU Yi, CAO Jian-jun and SHANG Yu-ling. Reviews of Multiobjective Ant Colony Optimization[J]. Computer Science, 2017, 44(10): 7-13. https://doi.org/10.11896/j.issn.1002-137X.2017.10.002

参考文献

[1] ASAFUDDOULA M,RAY T,SARKER R.A Decomposition Based Evolutionary Algorithm for Many Objective Optimizaiton[J].IEEE Transactions on Evolutionary Computation,2015,19(3):445-460.
[2] MUKHOPADHYAY A,MAULIK U,BANDYOPADHYAY S,et al.A Survey of Multiobjective Evolutionary Algorithms for Data Mining:Part I[J].IEEE Transactions on Evolutionary Computation,2014,18(1):4-19.
[3] MUKHOPADHYAY A,MAULIK U,BBANDYOPADHYAYS,et al.Survey of Multiobjective Evolutionary Algorithms for Data BANDYOPADHYAY:Part II[J].IEEE Transactions on Evolutionary Computation,2014,18(1):20-35.
[4] WANG Z T,GUO J S,ZHENG M F,et al.Uncertain Multi-objective Traveling Salesman Problem[J].European Journal of Operational Research,2015,241(2):478-489.
[5] ISHIBUCHI H,AKEDO N,NOJIMA Y.Behavior of Multi-objective Evolutionary Algorithm on Many-Objective Knapsack Problem[J].IEEE Transactions on Evolutionary Computation,2015,19(2):264-283.
[6] ARIYASINGHA I D I D,FERNANDO T G I.A Performance Study for the Multiobjective Ant Colony Optimization Algorithms on the Job Shop Scheduling Problem[J].International Journal of Computer Applications,2015,132(14):1-8.
[7] ADHAM A M,MOHD-GHAZALI N,AHMAD R.Performance Optimization of A Microchannel Heat Sink Using the Improved Strength Pareto Evolutionary Algorithm(SPEA2)[J].Journal of Engineering Thermophysics,2015,24(1):86-100.
[8] ZHANG Q F,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[9] DEB K,JAIN H.An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach,Part I:Solving Problems With Box Constraints[J].IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.
[10] ARIYASINGHA I D I D, FERNANDO T G I.PerformanceAnalysis of the Multiobjective Ant Colony Optimization Algorithms for the Traveling Salesman Problem[J].Swarm and Evolutionary Computation,2015,23:11-26.
[11] XU G,LIU B B,SONG J,et al.Multiobjective Sorting-Based Learning Particle Swarm Optimization for Continuous Optimization[J/OL].Natural Computing,https//doi.org/io.1007/s11047-016-95-48-3.
[12] YANG S X.Bat Algorithm for Multiobjective Optimization[J].International Journal of Bio-Inspired Computation,2012,3(5):267-274.
[13] ANGELO J S,BERNARDINO H S,BARBOSA H J C.Ant Co-lony Approaches for Multiobjective Structural Optimization Problems with A Cardinality Constraint[J].Advances in Engineering Software,2014,80:101-115.
[14] WANG X Q,ZHAO Y,WANG D,et al.Improved Multiobjective Ant Colony Optimization Algorithm and Its Application in Complex Reasoning[J].Chinese Journal of Mechanical Engineering,2013,26(5):1031-1040.
[15] ANGELO J S,BERNARDINO H S,BARBOSA H J C.Ant Co-lony Approaches for Multiobjective Structural Optimization Problems with A Cardinality Constraint[J].Advances in Engineering Software,2015,80:1010-115.
[16] XU R,CHEN H P,LI X P.A Biobjective Scheduling Problem on Batch Machines Via A Pareto Based Ant Colony System[J].International Journal of Production Economics,2013,14(1):371-386.
[17] LI K Q,DIAO X C,CAO J J.Survey on Ant Colony Optimization Algorithms for Stochastic Combinatorial Optimization[J].Application Research of Computers,2010,27(12):4406-4409.(in Chinese) 李凯齐,刁兴春,曹建军.蚁群优化算法在求解随机组合优化问题中的应用综述[J].计算机应用研究,2010,27(12):4406-4409.
[18] TAN Y,SHI Y H,BUARQUE F,et al.Advances in Swarm and Computational Intelligence[M].Springer,2015:197-204.
[19] LIN P P,ZHANG J,CONTRERAS M A.Applying Pareto Ant Colony Optimization to Solve Biobjective Forest Transportation Planning Problems[C]∥IEEE International Conference on Information Reuse & Integration.2015:795-802.
[20] WANG L J,SHEN J,LUO J Z.Facilitating An Ant Colony Algorithm for Multiobjective Data Intensive Service Provision[J].Journal of Computer and System Sciences,2015,81(4):734-746.
[21] GAO Y Q,GUAN H B,QI Z W,et al.A Multiobjective Ant Colony System Algorithm for Virtual Machine Placement in Cloud Computing[J].Journal of Computer and System Sciences,2013,79(8):1230-1242.
[22] MALEKLOO M,KARA N.Multiobjective ACO Virtual Ma-chine Placement in Cloud Computing Environments[C]∥Globecom 2014 Workshop-Cloud Computing System,Networks,and Applications.2014:112-116.
[23] NOPBHORN L,PHONRATTANASAK P.Multiobjective Ant Colony Optimization for Fast Charging Stations Planning in Residential Area[C]∥2014 IEEE Innovative Smart Grid Technologies-Asia.2014:290-295.
[24] MONCAYO-MARTINEZ L A,RECIO G.Bi-criterion Optimization for Configuring An Assembly Supply Chain Using Pareto Ant Colony Meta-Heuristic[J].Journal of Manufacturing Systems,2014,33(1):188-195.
[25] SAGRADO J D,AGUILA I M D,ORELLANA F J.Multiobjective Ant Colony Optimization for Requirements Selection[J].Empirical Software Engineering,2015,20(3):577-610.
[26] CAO J J,DIAO X C,WANG T,et al.Research on Domain-Independent Data Cleaning:A Survey[J].Computer Science,2010,37(5):26-29.(in Chinese) 曹建军,刁兴春,汪挺,等.领域无关数据清洗研究综述[J].计算机科学,2010,37(5):26-29.
[27] TAN M C,DIAO X C,CAO J J.Survey on Entity Resolution[J].Computer Science,2014,41(4):9-12.(in Chinese) 谭明超,刁兴春,曹建军.实体分辨研究综述[J].计算机科学,2014,41(4):9-12.
[28] CAO J J,LIU Y,DIAO X C,et al.A New Design of Ensemble Classifiers for High-Dimension Entity Resolution[C]∥Procee-dings of International Conference on Information Quality (ICIQ 2016).Ciudad Real,Spain,2016.
[29] YU P L.Cone Convexity,Cone Extreme Points,and Nondominated Solutions in Decision Problems with Multiobjectives[J].Journal of Optimization Theory & Applications,1974,14(3):319-377.
[30] ZITZLER E,THIELE L,LAUMANNS M,et al.PerformanceAssessment of Multiobjective Optimizers:An Analysis and Review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.
[31] LI B D,LI J L,TANG K,et al.Many-Objective Evolutionary algorithms:a survey[J].ACM Computing Surveys,2015,48(1):1-35.
[32] BERRICHI A,YALAOUI F.Efficient Biobjective Ant Colony Approach to Minimize Total Tardiness and System Unavailability for A Parallel Machine Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2013,68(9-12):2295-2310.
[33] SUN X S,LU C,LIU S X,et al.Multiobjective ACO Algorithm for Slab Selecting and Charging Scheduling in Hot Rolling Production[C]∥The 5^th Annual IEEE International Conference on Cyber Technology in Automation,Control and Intelligent Systems.2015:703-708.
[34] ZHAO B X,GAO J M,CHEN K,et al.Two Generation Pareto Ant Colony Algorithm for Multiobjective Job Shop Scheduling Problem with Alternative Process Plans and Unrelated Parallel Machines[J/OL].Journal of Intelligent Manufacturing,https://doi.org/10.1007/s10845-015-1091-Z.
[35] LOPEZ I M,STUTZLE T.The Automatic Design of Multiobjective Ant Colony Optimization Algorithms[J].IEEE Transactions on Evolutionary Computation,2012,16(6):861-875.
[36] ALAYA I,SOLNON C,GHDIRA K.Ant Colony Optimization for Multiobjective Optimization Problems[C]∥IEEE ICTAI.2007:450-457.
[37] IREDI S,MERKLE D,MIDDENDOF M.Bi-criterion Optimization with Multi Colony Ant Algorithms[C]∥International Conference on Evolutionary Multi-Criterion Optimization.2001:359-372.
[38] BARN B,SCHAERER M.A Multiobjective Ant Colony System for Vehicle Routing Problem with Time Windows[C]∥The 21st IASTED Conference on Application Informatics.2003:97-102.
[39] DOERNER K,HARTL R F,REIMANN M.Are COMPETants More Competent for problem solving?—The case of a multiple objective transportation problem[J].Central Europe Journal of Operation,2003,11(2):115-141.
[40] DOERNER K,GTJAHR W,HARTL R,et al.Pareto Ant Colony Optimization:A Metaheuristic Approach to Multiobjective Portfolio Selection[J].Annals of Operations Research,2004,131(1-4):79-99.
[41] LPEZ-IBEZ M,STTZLE T.The Impact of DesignChoices of Multiobjective Ant Colony Optimization Algorithms on Performance:An Experimental Study on the Biobjective TSP[C]∥Genetic and Evolutionary Computation.2010:71-78.
[42] DILIP K,KUMAR T V V.Multicriteria Website Optimization Using Multiobjective ACO[C]∥International Conference on Reliablity.2015:1-6.
[43] FERNANDO T G I.Ant Colony Optimization Based Simulation of 3D Automatic Hose/Pipe Routing[D].London:Brunel University,2009.
[44] ZITZLER E,KNZLI S.Indicator Based Selection in Multiobjective Search[M]∥Parallel Problem Solving from Nature-PPSN VIII.Springer,2004.
[45] BADER J,ZITZLER E.HypE:An Algorithm for Fast Hypervolume Based Many-objective Optimization[J].IEEE Transactions on Evolutionary Computation,2011,19(1):45-76.
[46] FALCON C J G,COELLO C A C.IMOACOR:A New Indicator Based Multiobjective Ant Colony Optimization for Continuous Search Spaces[M].Springer,2015.
[47] MANSOUR I B,ALAYA I.Indicator Based Ant Colony Optimization for Multiobjective Knapsack Problem[J].Procedia Computer Science,2015,60(1):448-457.
[48] LI K,ZHANG Q F,BATTITI R.MOEA/D-ACO:A Multiobjective Evolutionary Algorithm Using Decomposition and Ant Colony[J].IEEE Transactions on Cybernetics,2013,43(6):1845-1859.
[49] STTZLE T,HOOS H H.Max Min Ant System[J].FutrureGeneration Computer Systems,2000,16(9):889-914.
[50] SOUZA M Z D,POZO A T R.Multiobjective Binary ACO for Unconstrained Binary Quadratic Programming[C]∥Brazilian Conference on Intelligent Systems.2015:86-91.
[51] WANG H D,JIAO L C,YAO X.Two_Arch2:An ImprovedTwo-Archive Algorithm for Many-Objective Optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(4):524-541.
[52] BATTI R,BRUNATO M,MASCIA F.Reactive Search andIntelligent Optimization[J].Operations Research/Computer Science Interfaces Series,2008,45(3):151-153.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed