Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions

被引:537
作者
Deb, K [1 ]
Mohan, M
Mishra, S
机构
[1] Indian Inst Technol, KanGAL, Kanpur 208016, Uttar Pradesh, India
[2] Manikanth Mohan, Aranmula 689533, Kerala, India
[3] Univ Missouri, Dept Math & Comp Sci, St Louis, MO 63121 USA
关键词
multi-objective optimization; evolutionary algorithms; genetic algorithms; Pareto-optimal solutions; epsilon-dominance; computational effort; convergence measure; sparsity measure; hyper-volume metric;
D O I
10.1162/106365605774666895
中图分类号
TP18 [人工智能理论];
学科分类号
081104 [模式识别与智能系统]; 0812 [计算机科学与技术]; 0835 [软件工程]; 1405 [智能科学与技术];
摘要
Since the suggestion of a computing procedure of multiple Pareto-optimal solutions in multi-objective optimization problems in the early Nineties, researchers have been on the look out for a procedure which is computationally fast and simultaneously capable of finding a well-converged and well-distributed set of solutions. Most multi-objective evolutionary algorithms (MOEAs) developed in the past decade are either good for achieving a well-distributed solutions at the expense of a large computational effort or computationally fast at the expense of achieving a not-so-good distribution of solutions. For example, although the Strength Pareto Evolutionary Algorithm or SPEA (Zitzler and Thiele, 1999) produces a much better distribution compared to the elitist non-dominated sorting GA or NSGA-II (Deb et al., 2002a), the computational time needed to run SPEA is much greater. In this paper, we evaluate a recently-proposed steady-state MOEA (Deb et al., 2003) which was developed based on the epsilon-dominance concept introduced earlier(Laumanns et al., 2002) and using efficient parent and archive update strategies for achieving a well-distributed and well-converged set of solutions quickly. Based on an extensive comparative study with four other state-of-the-art MOEAs on a number of two, three, and four objective test problems, it is observed that the steady-state MOEA is a good compromise in terms of convergence near to the Pareto-optimal front, diversity of solutions, and computational time. Moreover, the epsilon-MOEA is a step closer towards making MOEAs pragmatic, particularly allowing a decision-maker to control the achievable accuracy in the obtained Pareto-optimal solutions.
引用
收藏
页码:501 / 525
页数:25
相关论文
共 24 条
[1]
[Anonymous], 1995, MASSACHUSETTS I TECH
[2]
Coello C. A. C., 2002, EVOLUTIONARY ALGORIT
[3]
Corne D. W., 2000, Parallel Problem Solving from Nature PPSN VI. 6th International Conference. Proceedings (Lecture Notes in Computer Science Vol.1917), P839
[4]
Deb K, 2002, IEEE C EVOL COMPUTAT, P825, DOI 10.1109/CEC.2002.1007032
[5]
Deb K, 2003, LECT NOTES COMPUT SC, V2632, P222
[6]
A fast and elitist multiobjective genetic algorithm: NSGA-II [J].
Deb, K ;
Pratap, A ;
Agarwal, S ;
Meyarivan, T .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (02) :182-197
[7]
Deb K., 1995, Complex Systems, V9, P115
[8]
Deb K., 1996, Comput. Sci. Inform., V26, P30, DOI DOI 10.1109/TEVC.2007.895269
[9]
DEB K, 2002, P 4 AS PAC C SIM EV, P13
[10]
Deb K., 2001, Multi-Objective Optimization using Evolutionary Algorithms