his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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 & Automatiseringsteknik)ORCID iD: 0000-0001-8874-0676
University of Skövde, School of Engineering Science. University of Skövde, The Virtual Systems Research Centre. (Produktion & Automatiseringsteknik)ORCID iD: 0000-0003-3973-3394
2017 (English)In: Evolutionary Computation, ISSN 1063-6560, E-ISSN 1530-9304Article in journal (Refereed) Epub ahead of print
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, 2017.
National Category
Other Engineering and Technologies not elsewhere specified
Identifiers
URN: urn:nbn:se:his:diva-13336DOI: 10.1162/EVCO_a_00204OAI: oai:DiVA.org:his-13336DiVA: diva2:1068433
Available from: 2017-01-25 Created: 2017-01-25 Last updated: 2017-01-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

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

Altmetric score

Total: 99 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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