Evolutionary Many-Objective Algorithms for Combinatorial Optimization Problems: A Comparative Study

被引:33
作者
Behmanesh, Reza [1 ]
Rahimi, Iman [2 ]
Gandomi, Amir H. [3 ]
机构
[1] Islamic Azad Univ, Dept Accounting, Isfahan Khorasgan Branch, Esfahan, Iran
[2] Islamic Azad Univ, Young Researchers & Elite Club, Esfahan, Iran
[3] Univ Technol Sydney, Fac Engn & Informat Technol, Ultimo, NSW 2007, Australia
关键词
NONDOMINATED SORTING APPROACH; DECOMPOSITION; DIVERSITY;
D O I
10.1007/s11831-020-09415-3
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Many optimization problems encountered in the real-world have more than two objectives. To address such optimization problems, a number of evolutionary many-objective optimization algorithms were developed recently. In this paper, we tested 18 evolutionary many-objective algorithms against well-known combinatorial optimization problems, including knapsack problem (MOKP), traveling salesman problem (MOTSP), and quadratic assignment problem (mQAP), all up to 10 objectives. Results show that some of the dominance and reference-based algorithms such as non-dominated sort genetic algorithm (NSGA-III), strength Pareto-based evolutionary algorithm based on reference direction (SPEA/R), and Grid-based evolutionary algorithm (GrEA) are promising algorithms to tackle MOKP and MOTSP with 5 and 10 while increasing the number of objectives. Also, the dominance-based algorithms such as MaOEA-DDFC as well as the indicator-based algorithms such as HypE are promising to solve mQAP with 5 and 10 objectives. In contrast, decomposition based algorithms present the best on almost problems at saving time. For example, t-DEA displayed superior performance on MOTSP for up to 10 objectives.
引用
收藏
页码:673 / 688
页数:16
相关论文
共 56 条
[1]   A Decomposition-Based Evolutionary Algorithm for Many Objective Optimization [J].
Asafuddoula, M. ;
Ray, Tapabrata ;
Sarker, Ruhul .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2015, 19 (03) :445-460
[2]   HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization [J].
Bader, Johannes ;
Zitzler, Eckart .
EVOLUTIONARY COMPUTATION, 2011, 19 (01) :45-76
[3]  
Caramia M, 2008, MULTI OBJECTIVE OPTI
[4]   A Many-Objective Evolutionary Algorithm With Enhanced Mating and Environmental Selections [J].
Cheng, Jixiang ;
Yen, Gary G. ;
Zhang, Gexiang .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2015, 19 (04) :592-605
[5]   A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization [J].
Cheng, Ran ;
Jin, Yaochu ;
Olhofer, Markus ;
Sendhoff, Bernhard .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2016, 20 (05) :773-791
[6]  
Coello C. C., 2007, EVOLUTIONARY ALGORIT
[7]  
Deb K., 2014, SEARCH METHODOLOGIES, P403, DOI DOI 10.1007/978-1-4614-6940-7_15
[8]  
Deb K, 2001, WIL INT S SYS OPT
[9]   An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints [J].
Deb, Kalyanmoy ;
Jain, Himanshu .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2014, 18 (04) :577-601
[10]   Two-Stage Optimization Problems with Multivariate Stochastic Order Constraints [J].
Dentcheva, Darinka ;
Wolfhagen, Eli .
MATHEMATICS OF OPERATIONS RESEARCH, 2016, 41 (01) :1-22