CROWDING DISTANCE BASED NON-DOMINATED SORTING GENETIC ALGORITHM II FOR MULTI-OBJECTIVE OPTIMIZATION

Abstract

Generating Pareto front of multi-objective optimization problems is a difficult task, it needs to simultaneously optimize multiple conflicting objectives. This thesis improves the crowding distance operator of the NSGA-II algorithm. When evaluating the validity of an improved crowding distance-based NSGA-II (CD-NSGA-II) algorithm for multi-objective optimization problems, two kinds of indices are often considered simultaneously, that is convergence to Pareto Front and the diversity of solution. Actually the closer to the Pareto Front a solution is, the higher priority it should have. In CD-NSGA-II, the improved crowding distance plays an important role to get better convergence to the Pareto front and maintenance of diversity among solutions. The standard crowding distance operator in NSGA-II, cannot maintain solution diversity and convergence to the Pareto front well. Two solutions with the same fitness value have the property that they have different crowding distances depending on the individual’s position in the Pareto front. The proposed algorithm is real coded in MATLAB R2018b and evaluated on ten multi-objective benchmark test functions. Comparative experiments with the standard NSGA-II were performed to demonstrate the effectiveness of the proposed method. Convergence metrics and diversity metrics are used as performance evaluation criteria. By analyzing the closeness to Pareto front of the two algorithms, the solutions based on the improved crowding distance have better performance while maintaining slightly similar diversity. The final Pareto front produced by the proposed CD-NSGA-II algorithm is also significantly better in some cases and less affected in others. This suggests that an individual with the same fitness presented in the population is better computed by the improved crowding distance. From the valuable features, it can be seen that this improvement does not affect other operators such as the non-dominant sorting procedure, the elitist strategy, and the parameter-less method in NSGA-II, so it is very easy to apply.