Reducing the Run-Time Complexity of NSGA-II for Bi-objective Optimization Problem
NSGA-II is a multi-objective evolutionary algorithm, and its performance is so good that it has become very popular in the last few years. To improve the efficiency of NSGA-Ii for hi-objective optimization problem, in this paper, a new bi objective non-dominated sorting algorithm is proposed to replace the original non-dominated sorting method of NSGA-IL In the new algorithm, a layering strategy according to need is adopted to avoid generating unnecessary non-dominated fronts, and a forward comparison operator is designed to identify the non-dominated individual quickly. Compared with the time complexity (O(N2)) of NSGA-ll, the time complexity of new algorithm is reduced to O(kN+NlogN), where k is the number of non-dominated fronts, and k<<N. The experiment results also show that there are fewer non-dominated fronts, number of dominance comparisons and much less CPU run-time in the new algorithm, compared with NSGA-II.
multi-objective optimization non-dominated front layering strategy according to need forward comparison
Min Liu Wenhua Zeng
Cognitive Science Department Xiamen University Xiamen, China Dept.of Computer Science and Engineerin Software School Xiamen University Xiamen, China
国际会议
厦门
英文
546-549
2010-10-29（万方平台首次上网日期，不代表论文的发表时间）