An Approach to Obtain the Upper Bound on the Number of Non-dominated Fronts in a Population
Sumit Mishra, Sriparna Saha, Samrat Mondal · 2018
In this paper, we obtain the tight upper bound on the number of non-dominated fronts in a population. In general, the maximum number of non-dominated fronts in a population of size N can be N and the minimum number of non-dominated fronts can be 1. However, without sorting the entire population, it is very difficult to obtain an upper bound on the number of fronts. Here, we present an algorithm to obtain the tight upper bound on the number of non-dominated fronts and also prove that the time complexity of obtaining the upper bound is O(MN log N) where M is the number of objectives associate with each solution in the population. At the end we propose the parallel version of our approach and also prove the space and time complexities of the parallel version.