A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II Export

@incollection{citeulike:6095660, abstract = {Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN 3) computational complexity (where M is the number of objectives and N is the population size), (ii) non-elitism approach, and (iii) the need for specifying a sharing parameter. In this paper, we suggest a non-dominated sorting based multi-objective evolutionary algorithm (we called it the Non-dominated Sorting GA-II or NSGA-II) which alleviates all the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN 2) computational complexity is presented. Second, a selection operator is presented which creates a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) N solutions. Simulation results on five difficult test problems show that the proposed NSGA-II, in most problems, is able to find much better spread of solutions and better convergence near the true Pareto-optimal front compared to PAES and SPEA—two other elitist multi-objective EAs which pay special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II's low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come.}, address = {Berlin, Heidelberg}, author = {Deb, Kalyanmoy and Agrawal, Samir and Pratap, Amrit and Meyarivan, T.}, booktitle = {Parallel Problem Solving from Nature PPSN VI}, chapter = {83}, citeulike-article-id = {6095660}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-45356-3_83}, citeulike-linkout-1 = {http://www.springerlink.com/content/181751v0v1125574}, doi = {10.1007/3-540-45356-3_83}, editor = {Schoenauer, Marc and Deb, Kalyanmoy and Rudolph, G\"{u}nther and Yao, Xin and Lutton, Evelyne and Merelo, Juan J. and Schwefel, Hans-Paul}, isbn = {978-3-540-41056-0}, journal = {Parallel Problem Solving from Nature (PPSN VI)}, keywords = {genetic\_algorithms}, pages = {849--858}, posted-at = {2009-11-10 18:41:51}, priority = {2}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, title = {{A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II}}, url = {http://dx.doi.org/10.1007/3-540-45356-3_83}, volume = {1917}, year = {2000} }

TY - CHAP ID - citeulike:6095660 L3 - citeulike-article-id:6095660 N2 - Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN 3) computational complexity (where M is the number of objectives and N is the population size), (ii) non-elitism approach, and (iii) the need for specifying a sharing parameter. In this paper, we suggest a non-dominated sorting based multi-objective evolutionary algorithm (we called it the Non-dominated Sorting GA-II or NSGA-II) which alleviates all the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN 2) computational complexity is presented. Second, a selection operator is presented which creates a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) N solutions. Simulation results on five difficult test problems show that the proposed NSGA-II, in most problems, is able to find much better spread of solutions and better convergence near the true Pareto-optimal front compared to PAES and SPEA—two other elitist multi-objective EAs which pay special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II’s low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come. JF - Parallel Problem Solving from Nature (PPSN VI) SE - Lecture Notes in Computer Science SN - 978-3-540-41056-0 AD - Berlin, Heidelberg EP - 858 TI - {A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II} PB - Springer Berlin Heidelberg VL - 1917 T2 - Parallel Problem Solving from Nature PPSN VI SP - 849 KW - genetic_algorithms AU - Deb, Kalyanmoy AU - Agrawal, Samir AU - Pratap, Amrit AU - Meyarivan, T A2 - Schoenauer, Marc A2 - Deb, Kalyanmoy A2 - Rudolph, Günther A2 - Yao, Xin A2 - Lutton, Evelyne A2 - Merelo, Juan A2 - Schwefel, Hans-Paul PY - 2000/// UR - http://dx.doi.org/10.1007/3-540-45356-3_83 ER -