A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Kalyanmoy Deb , Samir Agrawal , Amrit Pratap , T Meyarivan

ABSTRACT

Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN3) 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(MN2) 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. More... »

PAGES

849-858

References to SciGraph publications

  • 1998. Multiobjective optimization using evolutionary algorithms — A comparative case study in PARALLEL PROBLEM SOLVING FROM NATURE — PPSN V
  • Book

    TITLE

    Parallel Problem Solving from Nature PPSN VI

    ISBN

    978-3-540-41056-0
    978-3-540-45356-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45356-3_83

    DOI

    http://dx.doi.org/10.1007/3-540-45356-3_83

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1019904657


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Kanpur", 
              "id": "https://www.grid.ac/institutes/grid.417965.8", 
              "name": [
                "Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, PIN 208 016, Kanpur, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deb", 
            "givenName": "Kalyanmoy", 
            "id": "sg:person.015166414023.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015166414023.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Kanpur", 
              "id": "https://www.grid.ac/institutes/grid.417965.8", 
              "name": [
                "Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, PIN 208 016, Kanpur, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Agrawal", 
            "givenName": "Samir", 
            "id": "sg:person.010422723653.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010422723653.02"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Kanpur", 
              "id": "https://www.grid.ac/institutes/grid.417965.8", 
              "name": [
                "Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, PIN 208 016, Kanpur, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pratap", 
            "givenName": "Amrit", 
            "id": "sg:person.015515513111.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015515513111.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Kanpur", 
              "id": "https://www.grid.ac/institutes/grid.417965.8", 
              "name": [
                "Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, PIN 208 016, Kanpur, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Meyarivan", 
            "givenName": "T", 
            "id": "sg:person.011420404145.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011420404145.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0056872", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008568979", 
              "https://doi.org/10.1007/bfb0056872"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1162/evco.1999.7.3.205", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012647124"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1162/106365600568202", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014057085"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1162/evco.1994.2.3.221", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026010259"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/3468.650320", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061157569"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cec.1999.781913", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094003336"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icec.1994.350037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095436217"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2000", 
        "datePublishedReg": "2000-01-01", 
        "description": "Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN3) 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(MN2) 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\u2014two other elitist multi-objective EAs which pay special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II\u2019s low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come.", 
        "editor": [
          {
            "familyName": "Schoenauer", 
            "givenName": "Marc", 
            "type": "Person"
          }, 
          {
            "familyName": "Deb", 
            "givenName": "Kalyanmoy", 
            "type": "Person"
          }, 
          {
            "familyName": "Rudolph", 
            "givenName": "G\u00fcnther", 
            "type": "Person"
          }, 
          {
            "familyName": "Yao", 
            "givenName": "Xin", 
            "type": "Person"
          }, 
          {
            "familyName": "Lutton", 
            "givenName": "Evelyne", 
            "type": "Person"
          }, 
          {
            "familyName": "Merelo", 
            "givenName": "Juan Julian", 
            "type": "Person"
          }, 
          {
            "familyName": "Schwefel", 
            "givenName": "Hans-Paul", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45356-3_83", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-41056-0", 
            "978-3-540-45356-7"
          ], 
          "name": "Parallel Problem Solving from Nature PPSN VI", 
          "type": "Book"
        }, 
        "name": "A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II", 
        "pagination": "849-858", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45356-3_83"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5ed647165d5e44c177c2dd3765c016f3d3542e5428d83d5118e2630fcaf1d4dc"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019904657"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45356-3_83", 
          "https://app.dimensions.ai/details/publication/pub.1019904657"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:37", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000346_0000000346/records_99839_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-45356-3_83"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-45356-3_83'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-45356-3_83'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45356-3_83'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45356-3_83'


     

    This table displays all metadata directly associated to this object as RDF triples.

    138 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45356-3_83 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N56101b1341b44b40a2d1f89c191fcb5c
    4 schema:citation sg:pub.10.1007/bfb0056872
    5 https://doi.org/10.1109/3468.650320
    6 https://doi.org/10.1109/cec.1999.781913
    7 https://doi.org/10.1109/icec.1994.350037
    8 https://doi.org/10.1162/106365600568202
    9 https://doi.org/10.1162/evco.1994.2.3.221
    10 https://doi.org/10.1162/evco.1999.7.3.205
    11 schema:datePublished 2000
    12 schema:datePublishedReg 2000-01-01
    13 schema:description Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN3) 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(MN2) 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.
    14 schema:editor Nf15682fcfbcc41dc87aa26fa1a2b44e3
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N2abd0e21fdef43b5ab295bd5a0b80c0c
    19 schema:name A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II
    20 schema:pagination 849-858
    21 schema:productId N2818801ca0ef4d8cbdc3d8013c4980b2
    22 N500481473bf24284a22897ad4ff9a7c0
    23 Nd13d68515bf343dfb5ac1873772b3f0a
    24 schema:publisher N0993db5e7a2845dd86e8b70d9e02b3e2
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019904657
    26 https://doi.org/10.1007/3-540-45356-3_83
    27 schema:sdDatePublished 2019-04-16T05:37
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N0b318673e3c64440829820bddadaf898
    30 schema:url https://link.springer.com/10.1007%2F3-540-45356-3_83
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N022861307c7f4302a8dc46890986f8e5 rdf:first Neb1c4e3dbabf46efa2b9aba7afed99c8
    35 rdf:rest N8dd4d940875447eda563b9f05c0c0844
    36 N0993db5e7a2845dd86e8b70d9e02b3e2 schema:location Berlin, Heidelberg
    37 schema:name Springer Berlin Heidelberg
    38 rdf:type schema:Organisation
    39 N0b318673e3c64440829820bddadaf898 schema:name Springer Nature - SN SciGraph project
    40 rdf:type schema:Organization
    41 N265d0f0ec5f4434d87e7e69b6a458f31 schema:familyName Rudolph
    42 schema:givenName Günther
    43 rdf:type schema:Person
    44 N2818801ca0ef4d8cbdc3d8013c4980b2 schema:name dimensions_id
    45 schema:value pub.1019904657
    46 rdf:type schema:PropertyValue
    47 N2abd0e21fdef43b5ab295bd5a0b80c0c schema:isbn 978-3-540-41056-0
    48 978-3-540-45356-7
    49 schema:name Parallel Problem Solving from Nature PPSN VI
    50 rdf:type schema:Book
    51 N500481473bf24284a22897ad4ff9a7c0 schema:name readcube_id
    52 schema:value 5ed647165d5e44c177c2dd3765c016f3d3542e5428d83d5118e2630fcaf1d4dc
    53 rdf:type schema:PropertyValue
    54 N56101b1341b44b40a2d1f89c191fcb5c rdf:first sg:person.015166414023.54
    55 rdf:rest Na6f7311db84641fdb1de169461bb6164
    56 N57e47830872e4db1843a8b5546aa60d2 schema:familyName Yao
    57 schema:givenName Xin
    58 rdf:type schema:Person
    59 N611a6c9bff554f3083911bae5d254c98 rdf:first Nac98823877824d09b783aeb60c249b97
    60 rdf:rest N8af60343f64d471584c2c1400db548c2
    61 N70001376882743ff9bf1330d765b798f rdf:first sg:person.011420404145.39
    62 rdf:rest rdf:nil
    63 N8af60343f64d471584c2c1400db548c2 rdf:first N265d0f0ec5f4434d87e7e69b6a458f31
    64 rdf:rest N8effeea38c9d4a99b6f8268305035717
    65 N8dd4d940875447eda563b9f05c0c0844 rdf:first Nf634b7fe0b3d4aaf9b046d6d2b693019
    66 rdf:rest rdf:nil
    67 N8effeea38c9d4a99b6f8268305035717 rdf:first N57e47830872e4db1843a8b5546aa60d2
    68 rdf:rest Nb98832c054ac4042943278ea32100c15
    69 N9a5c2a6b35c34d20ab71b62234a57e82 schema:familyName Lutton
    70 schema:givenName Evelyne
    71 rdf:type schema:Person
    72 N9d7ccee7e3b941d18d729111f3dc81d0 schema:familyName Schoenauer
    73 schema:givenName Marc
    74 rdf:type schema:Person
    75 Na6f7311db84641fdb1de169461bb6164 rdf:first sg:person.010422723653.02
    76 rdf:rest Nc07fa4c92bb04e099eef00a45d5f1132
    77 Nac98823877824d09b783aeb60c249b97 schema:familyName Deb
    78 schema:givenName Kalyanmoy
    79 rdf:type schema:Person
    80 Nb98832c054ac4042943278ea32100c15 rdf:first N9a5c2a6b35c34d20ab71b62234a57e82
    81 rdf:rest N022861307c7f4302a8dc46890986f8e5
    82 Nc07fa4c92bb04e099eef00a45d5f1132 rdf:first sg:person.015515513111.19
    83 rdf:rest N70001376882743ff9bf1330d765b798f
    84 Nd13d68515bf343dfb5ac1873772b3f0a schema:name doi
    85 schema:value 10.1007/3-540-45356-3_83
    86 rdf:type schema:PropertyValue
    87 Neb1c4e3dbabf46efa2b9aba7afed99c8 schema:familyName Merelo
    88 schema:givenName Juan Julian
    89 rdf:type schema:Person
    90 Nf15682fcfbcc41dc87aa26fa1a2b44e3 rdf:first N9d7ccee7e3b941d18d729111f3dc81d0
    91 rdf:rest N611a6c9bff554f3083911bae5d254c98
    92 Nf634b7fe0b3d4aaf9b046d6d2b693019 schema:familyName Schwefel
    93 schema:givenName Hans-Paul
    94 rdf:type schema:Person
    95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Information and Computing Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Computation Theory and Mathematics
    100 rdf:type schema:DefinedTerm
    101 sg:person.010422723653.02 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
    102 schema:familyName Agrawal
    103 schema:givenName Samir
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010422723653.02
    105 rdf:type schema:Person
    106 sg:person.011420404145.39 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
    107 schema:familyName Meyarivan
    108 schema:givenName T
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011420404145.39
    110 rdf:type schema:Person
    111 sg:person.015166414023.54 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
    112 schema:familyName Deb
    113 schema:givenName Kalyanmoy
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015166414023.54
    115 rdf:type schema:Person
    116 sg:person.015515513111.19 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
    117 schema:familyName Pratap
    118 schema:givenName Amrit
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015515513111.19
    120 rdf:type schema:Person
    121 sg:pub.10.1007/bfb0056872 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008568979
    122 https://doi.org/10.1007/bfb0056872
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/3468.650320 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061157569
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1109/cec.1999.781913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094003336
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/icec.1994.350037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095436217
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1162/106365600568202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014057085
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1162/evco.1994.2.3.221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026010259
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1162/evco.1999.7.3.205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012647124
    135 rdf:type schema:CreativeWork
    136 https://www.grid.ac/institutes/grid.417965.8 schema:alternateName Indian Institute of Technology Kanpur
    137 schema:name Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur, PIN 208 016, Kanpur, India
    138 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...