Objective Reduction in Many-Objective Optimization: Linear and Nonlinear Algorithms

被引:240
作者
Saxena, Dhish Kumar [1 ]
Duro, Joao A. [1 ]
Tiwari, Ashutosh [1 ]
Deb, Kalyanmoy [2 ]
Zhang, Qingfu [3 ]
机构
[1] Cranfield Univ, Dept Mfg, Cranfield MK43 0AL, Beds, England
[2] Indian Inst Technol, Dept Mech Engn, Kanpur 208016, Uttar Pradesh, India
[3] Univ Essex, Sch Comp Sci & Elect Engn, Colchester CO4 3SQ, Essex, England
关键词
Evolutionary multiobjective optimization; many-objective optimization; maximum variance unfolding and kernels; principal component analysis; MULTIOBJECTIVE EVOLUTIONARY ALGORITHM; DIMENSIONALITY REDUCTION; PARETO;
D O I
10.1109/TEVC.2012.2185847
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
The difficulties faced by existing multiobjective evolutionary algorithms (MOEAs) in handling many-objective problems relate to the inefficiency of selection operators, high computational cost, and difficulty in visualization of objective space. While many approaches aim to counter these difficulties by increasing the fidelity of the standard selection operators, the objective reduction approach attempts to eliminate objectives that are not essential to describe the Pareto-optimal front (POF). If the number of essential objectives is found to be two or three, the problem could be solved by the existing MOEAs. It implies that objective reduction could make an otherwise unsolvable (many-objective) problem solvable. Even when the essential objectives are four or more, the reduced representation of the problem will have favorable impact on the search efficiency, computational cost, and decision-making. Hence, development of generic and robust objective reduction approaches becomes important. This paper presents a principal component analysis and maximum variance unfolding based framework for linear and nonlinear objective reduction algorithms, respectively. The major contribution of this paper includes: 1) the enhancements in the core components of the framework for higher robustness in terms of applicability to a range of problems with disparate degree of redundancy; mechanisms to handle input data that poorly approximates the true POF; and dependence on fewer parameters to minimize the variability in performance; 2) proposition of an error measure to assess the quality of results; 3) sensitivity analysis of the proposed algorithms for the critical parameter involved, and the characteristics of the input data; and 4) study of the performance of the proposed algorithms vis-a-vis dominance relation preservation based algorithms, on a wide range of test problems (scaled up to 50 objectives) and two real-world problems.
引用
收藏
页码:77 / 99
页数:23
相关论文
共 41 条
[1]
[Anonymous], LECT NOTES COMPUTER, DOI DOI 10.1007/3-540-36970-8_
[2]
[Anonymous], 2008, Proc. of 2008 IEEE Congress on Evolutionary Computation, DOI DOI 10.1109/CEC.2008.4631121
[3]
S-Metric Calculation by Considering Dominated Hypervolume as Klee's Measure Problem [J].
Beume, Nicola .
EVOLUTIONARY COMPUTATION, 2009, 17 (04) :477-492
[4]
CSDP, a C library for semidefinite programming [J].
Borchers, B .
OPTIMIZATION METHODS & SOFTWARE, 1999, 11-2 (1-4) :613-623
[5]
Brockhoff D, 2006, LECT NOTES COMPUT SC, V4193, P533
[6]
Objective Reduction in Evolutionary Multiobjective Optimization: Theory and Applications [J].
Brockhoff, Dimo ;
Zitzler, Eckart .
EVOLUTIONARY COMPUTATION, 2009, 17 (02) :135-166
[7]
Cohen J., 1988, Statistical power analysis for the behavioral sciences, VSecond
[8]
Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions [J].
Deb, K ;
Mohan, M ;
Mishra, S .
EVOLUTIONARY COMPUTATION, 2005, 13 (04) :501-525
[9]
Deb K, 2004, ADV INFO KNOW PROC, P105
[10]
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