Efficient Removal of Points with Smallest Crowding Distance in Two-dimensional Incremental Non-dominated Sorting

ABSTRACT

Many evolutionary multi-objective algorithms rely heavily on non-dominated sorting, the procedure of assigning ranks to individuals according to Pareto domination relation. The steady-state versions of these algorithms need efficient implementations of incremental non-dominated sorting, an algorithm or data structure which supports efficient addition of a new individual and deletion of the worst individual.

Recent research brought new advanced algorithms, but none of them can be cheaply adapted to sublinear location of the point having the smallest crowding distance, a measure used in the NSGA-II algorithm. In this paper we address this issue by reducing it to a series of extreme point queries to certain convex polygons. We present theoretical estimation of the worst-case running time, as well as experimental results which show that the proposed modifications reduce the running time significantly on benchmark problems for large population sizes.

References

1. S. Adra and P. Fleming. Diversity management in evolutionary many-objective optimization. IEEE Transactions on Evolutionary Computation, 15(2):183--195, 2011.
2. M. Buzdalov and V. Parfenov. Various degrees of steadiness in NSGA-II and their influence on the quality of results. In Proceedings of Genetic and Evolutionary Computation Conference Companion, pages 749--750, 2015.
3. M. Buzdalov and A. Shalyto. A provably asymptotically fast version of the generalized Jensen algorithm for non-dominated sorting. In Parallel Problem Solving from Nature -- PPSN XIII, number 8672 in Lecture Notes in Computer Science, pages 528--537. Springer, 2014.
4. M. Buzdalov, I. Yakupov, and A. Stankevich. Fast implementation of the steady-state NSGA-II algorithm for two dimensions based on incremental non-dominated sorting. In Proceedings of Genetic and Evolutionary Computation Conference, pages 647--654, 2015.
5. C. A. Coello Coello and M. Lechuga. MOPSO: A proposal for multiple objective particle swarm optimization. In Proceedings of Congress on Evolutionary Computation, pages 1051--1056, 2002.
6. K. Deb and H. Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4):577--601, 2013.
7. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6:182--197, 2000.
8. K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, pages 105--145. Springer, 2005.
9. F.-A. Fortin, S. Grenier, and M. Parizeau. Generalizing the improved run-time complexity algorithm for non-dominated sorting. In Proceedings of Genetic and Evolutionary Computation Conference, pages 615--622. ACM, 2013.
10. S. Gupta and G. Tan. A scalable parallel implementation of evolutionary algorithms for multi-objective optimization on GPUs. In Proceedings of IEEE Congress on Evolutionary Computation, pages 1567--1574, 2015.
11. S. Huband, P. Hingston, L. Barone, and R. L. While. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10(5):477--506, 2006.
12. M. T. Jensen. Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. Transactions on Evolutionary Computation, 7(5):503--515, 2003.
13. K. Li, K. Deb, Q. Zhang, and S. Kwong. Efficient non-domination level update approach for steady-state evolutionary multiobjective optimization. Technical Report COIN 2014014, Michigan State University, 2014.
14. K. Li, K. Deb, Q. Zhang, and Q. Zhang. Efficient non-domination level update method for steady-state evolutionary multi-objective optimization. Technical Report COIN 2015022, Michigan State University, 2015.
15. K. McClymont and E. Keedwell. Deductive sort and climbing sort: New methods for non-dominated sorting. Evolutionary computation, 20(1):1--26, 2012.
16. S. Mishra, S. Mondal, and S. Saha. Improved solution to the non-domination level update problem. http://arxiv.org/abs/1510.04796.
17. A. J. Nebro and J. J. Durillo. On the effect of applying a steady-state selection scheme in the multi-objective genetic algorithm NSGA-II. In Nature-Inspired Algorithms for Optimisation, number 193 in Studies in Computational Intelligence, pages 435--456. Springer Berlin Heidelberg, 2009.
18. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer New York, 1985.
19. J. O'Rourke. Computational Geometry in C, 2nd Edition. Cambridge Tracts in Theoretical Computer Science, 1998.
20. H. Wang and X. Yao. Corner sort for pareto-based many-objective optimization. IEEE Transactions on Cybernetics, 44(1):92--102, 2014.
21. I. Yakupov and M. Buzdalov. Incremental non-dominated sorting with $O(N)$ insertion for the two-dimensional case. In Proceedings of IEEE Congress on Evolutionary Computation, pages 1853--1860, 2015.
22. X. Zhang, Y. Tian, R. Cheng, and Y. Jin. An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 19(2):201--213, 2015.
23. E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2):173--195, 2000.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching