Högskolan i Skövde

his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • apa-cv
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A New Algorithm Using the Non-dominated Tree to improve Non-dominated Sorting
University of Skövde, School of Engineering Science. University of Skövde, The Virtual Systems Research Centre. (Produktion och automatiseringsteknik, Production and automation engineering)ORCID iD: 0000-0001-8874-0676
University of Skövde, School of Engineering Science. University of Skövde, The Virtual Systems Research Centre. (Produktion och automatiseringsteknik, Production and automation engineering)ORCID iD: 0000-0003-3973-3394
2018 (English)In: Evolutionary Computation, ISSN 1063-6560, E-ISSN 1530-9304, Vol. 26, no 1, p. 89-116Article in journal (Refereed) Published
Abstract [en]

Non-dominated sorting is a technique often used in evolutionary algorithms to determine the quality of solutions in a population. The most common algorithm is the Fast Non-dominated Sort (FNS). This algorithm, however, has the drawback that its performance deteriorates when the population size grows. The same drawback applies also to other non-dominating sorting algorithms such as the Efficient Non-dominated Sort with Binary Strategy (ENS-BS). An algorithm suggested to overcome this drawback is the Divide-and-Conquer Non-dominated Sort (DCNS) which works well on a limited number of objectives but deteriorates when the number of objectives grows. This paper presents a new, more efficient, algorithm called the Efficient Non-dominated Sort with Non-Dominated Tree (ENS-NDT). ENS-NDT is an extension of the ENS-BS algorithm and uses a novel Non-Dominated Tree (NDTree) to speed up the non-dominated sorting. ENS-NDT is able to handle large population sizes and a large number of objectives more efficiently than existing algorithms for non-dominated sorting. In the paper, it is shown that with ENS-NDT the runtime of multi-objective optimization algorithms such as the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) can be substantially reduced.

Place, publisher, year, edition, pages
MIT Press, 2018. Vol. 26, no 1, p. 89-116
National Category
Other Engineering and Technologies not elsewhere specified
Research subject
Production and Automation Engineering
Identifiers
URN: urn:nbn:se:his:diva-13336DOI: 10.1162/EVCO_a_00204ISI: 000426562300004Scopus ID: 2-s2.0-85042773821OAI: oai:DiVA.org:his-13336DiVA, id: diva2:1068433
Note

© 2018 Massachusetts Institute of Technology

Available from: 2017-01-25 Created: 2017-01-25 Last updated: 2021-01-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gustavsson, PatrikSyberfeldt, Anna

Search in DiVA

By author/editor
Gustavsson, PatrikSyberfeldt, Anna
By organisation
School of Engineering ScienceThe Virtual Systems Research Centre
In the same journal
Evolutionary Computation
Other Engineering and Technologies not elsewhere specified

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 1314 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • apa-cv
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf