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 bi-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-II. 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(N²) ) of NSGA-II, the time complexity of new algorithm is reduced to O(kN+MogN), 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.