A improved NSGA-II algorithm based on sub-regional search
Hai‐Lin Liu, Fangqing Gu · 2011
By dividing the objective space into several small regions, this paper proposes an improved NSGA-II algorithm, which updates the population in each sub-region by using non-dominated sorting and crowded distance selection operator (NSGA-II). Since performing the evolutionary operator is independent in each sub-region and the number of the individuals in a sub-region is far less than the size of the population, the computational complexity at each generation is lower than NSGA-II. The computational complexity of each generation in the proposed algorithm is O(mN3/2), where m is the number of the objective and N is its population size. For enhancing the capability of proposed algorithm, The algorithm exchanges the information between sub-regions through re-dividing their offsprings and the evolutionary operators between individuals are operated in the same sub-region. Such evolutionary operators can largely play a role of exploring the good individuals in this area and improve the local search capabilities of the algorithm. A specific selection in this paper surmounts the intrinsic shortcoming of the sub region decomposition technique, which there may be no Pareto optimal solutions in some sub-region. Numerical results show that the proposed algorithm has a good performance.