Speeding-up of the Non-Dominated Sorting Genetic Algorithm-II by Selective De-Correlation

Non-Dominated Sorting (NDS) algorithms are used widely in many fields and for a wide-range of applications. Primarily, NDS is used to rank tuples in a dataset, but this ranking is sometimes the intermediate results that is used for other downstream tasks. In this thesis, I aim to optimize NDS algorithms in an attempt to optimize pareto-dominance based genetic algorithms, specifically NSGA-II. I achieve this by studying correlations between objectives in a Multi-Objective Optimization (MOO) Problem and leverage this information to optimize NDS. We propose and evaluate two optimization methods leveraging the information of correlations between objective functions in an MOO problem. This thesis first presents a divide and conquer approach, D-NDS(De-correlate and Merge NDS) and then a second approach, SD-NDS (Selective De-Correlate NDS) which orders objectives in the objective tuple in the most optimal order to reduce the number of unnecessary dominance checks performed. Additionally, this thesis also explores optimizing each of the dominance check itself, this is something, to the best of my knowledge, that no one in the past has tried to optimize. This research also provide an algorithmic analysis which explains how and why SD-NDS works. The experiments on synthetic data and MOO problems presented in this thesis shows a clear reduction in time taken by NSGA-II when we use SD-NDS in conjunction with baseline NSGA-II compared to when we run vanilla NSGA-II.