计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 7-13, 25.doi: 10.11896/j.issn.1002-137X.2017.10.002

• • 上一篇    下一篇

多目标蚁群优化研究综述

刁兴春,刘艺,曹建军,尚玉玲   

  1. 中国人民解放军理工大学指挥信息系统学院 南京210007,中国人民解放军理工大学指挥信息系统学院 南京210007,南京电讯技术研究所 南京210007,中国人民解放军理工大学指挥信息系统学院 南京210007
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金资助

Reviews of Multiobjective Ant Colony Optimization

DIAO Xing-chun, LIU Yi, CAO Jian-jun and SHANG Yu-ling   

  • Online:2018-12-01 Published:2018-12-01

摘要: 多目标蚁群优化是一类重要的多目标进化算法,它在解决多目标优化问题,尤其是多目标组合优化方面,具有优异的性能。首先,通过总结多目标蚁群优化的研究成果,将多目标蚁群优化分为基于帕累托的方法、基于指标函数的方法和目标分解法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

[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 5th 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.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .