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.
- S. Adra and P. Fleming. Diversity management in evolutionary many-objective optimization. IEEE Transactions on Evolutionary Computation, 15(2):183--195, 2011. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- K. McClymont and E. Keedwell. Deductive sort and climbing sort: New methods for non-dominated sorting. Evolutionary computation, 20(1):1--26, 2012. Google ScholarDigital Library
- S. Mishra, S. Mondal, and S. Saha. Improved solution to the non-domination level update problem. http://arxiv.org/abs/1510.04796.Google Scholar
- 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.Google Scholar
- F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer New York, 1985. Google ScholarDigital Library
- J. O'Rourke. Computational Geometry in C, 2nd Edition. Cambridge Tracts in Theoretical Computer Science, 1998. Google ScholarDigital Library
- H. Wang and X. Yao. Corner sort for pareto-based many-objective optimization. IEEE Transactions on Cybernetics, 44(1):92--102, 2014.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2):173--195, 2000. Google ScholarDigital Library
Index Terms
- Efficient Removal of Points with Smallest Crowding Distance in Two-dimensional Incremental Non-dominated Sorting
Recommendations
An efficient non-dominated sorting method for evolutionary algorithms
We present a new non-dominated sorting algorithm to generate the non-dominated fronts in multi-objective optimization with evolutionary algorithms, particularly the NSGA-II. The non-dominated sorting algorithm used by NSGA-II has a time complexity of O(...
Approximate non-dominated sorting for evolutionary many-objective optimization
Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...
Eliminating Non-dominated Sorting from NSGA-III
Evolutionary Multi-Criterion OptimizationAbstractThe series of non-dominated sorting based genetic algorithms (NSGA-series) has clearly shown their niche in solving multi- and many-objective optimization problems since mid-nineties. Of them, NSGA-III was designed to solve problems having three ...
Comments