Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Shadow sort - a hybrid non-dominated sorting algorithm
Thesis (MEng)--Stellenbosch University, 2022.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2022
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614100114112512 |
|---|---|
| access_status_str | Open Access |
| author | Trankle, Nicholas Albert |
| author2 | Bekker, James |
| author_browse | Bekker, James Trankle, Nicholas Albert |
| author_facet | Bekker, James Trankle, Nicholas Albert |
| author_sort | Trankle, Nicholas Albert |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MEng)--Stellenbosch University, 2022. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/124608 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:40.081Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/124608 Shadow sort - a hybrid non-dominated sorting algorithm Trankle, Nicholas Albert Bekker, James Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. Non-dominated sorting Evolutionary algorithm Multi-objective optimisation UCTD Thesis (MEng)--Stellenbosch University, 2022. ENGLISH ABSTRACT: In this study a novel, hybrid, non-dominated sorting algorithm called Shadow Sort is presented. The algorithm was developed bearing in mind real-world, practical requirements of non-dominated sorting algorithms. The majority of non-dominated sorting algorithms are employed in conjunction with a multi-objective optimisation algorithm, many of which make use of population-based meta-heuristic techniques. The outputs of each population-based meta-heuristic iteration typically include hundreds, if not thousands of solutions, which need to be sorted in order to prime the next evolutionary iteration. However, of all the solutions proposed by any given metaheuristic iteration, a relatively low number of those solutions are of any use. Therefore, Shadow Sort approaches all non-dominated sorting by eliminating dominated solutions as early as possible, rather than processing all solutions in order to nd their respective Pareto set. Shadow Sort was developed in Matlab, and is rstly compared to other non-dominated sorting algorithms, namely Deductive Sort, E - cient Non-dominated Sort and Best Order Sort. Next, a use-case test is performed where Shadow Sort is compared to the best-performing competitor non-dominated sorting algorithm by implementing both into state-of-the-art multi-objective evolutionary algorithms. Several cases of Shadow Sort are proposed based on the number of objectives in the population. It was found that Shadow Sort is competitive when optimising two and three objectives, for various population sizes. AFRIKAANS OPSOMMING: In hierdie studie word 'n nuwe, hibriede, nie-gedomineerde sorteeralgoritme, genoem Skadusortering (\Shadow Sort"), voorgestel. Die algoritme is ontwikkel met inagneming van die werklike, praktiese vereistes van nie-gedomineerde sorteeralgoritmes. Die meeste niegedomineerde sorteeralgoritmes, waarvan baie populasie-gebaseerde meta-heuristiese tegnieke gebruik, word saam met 'n veeldoelige optimeringsalgoritme aangewend. Die uitsette van elke populasiegebaseerde meta-heuristiese iterasie bevat gewoonlik honderde, indien nie duisende nie, oplossings wat gesorteer moet word om die volgende evolusion^ere iterasie te genereer. Dit is egter net 'n relatief klein aantal oplossings wat deur 'n bepaalde meta-heuristiese iterasie voorgestel word, wat bruikbaar is. Daarom hanteer Skadusortering alle nie-gedomineerde sorterings deur gedomineerde oplossings so vroeg moontlik uit te skakel, eerder as om alle oplossings te verwerk ten einde hul onderskeie Pareto-subversamelings te identi seer. Skadusortering is in Matlab ontwikkel, en word eers vergelyk met ander nie-gedomineerde sorteeralgoritmes, naamlik Deduktiewe Sortering (\Deductive Sort"), E ektiewe Nie-gedomineerde Sortering (\Ef- cient Non-dominated Sort") en Besgeordende Sortering (\Best Order Sort"). Daarna word 'n toepassingsgevalle-toets uitgevoer waarin Skadusortering vergelyk word met die nie-gedomineerde mededingingsorteeralgoritme wat die beste presteer deur albei algoritmes in die jongste veeldoelige evolusion^ere algoritmes te implementeer. Gebaseer op die aantal doelstellings in die populasie, word verskeie gevalle van Skadusortering voorgestel. Daar is bevind dat Skadusortering vir verskillende populasiegroottes mededingend optree wanneer twee en drie doelwitte geoptimeer word. 2022-02-10T08:00:16Z 2022-04-29T09:22:07Z 2022-02-10T08:00:16Z 2022-04-29T09:22:07Z 2022-04 Thesis http://hdl.handle.net/10019.1/124608 en_ZA Stellenbosch University xvi, 142 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Non-dominated sorting Evolutionary algorithm Multi-objective optimisation UCTD Trankle, Nicholas Albert Shadow sort - a hybrid non-dominated sorting algorithm |
| title | Shadow sort - a hybrid non-dominated sorting algorithm |
| title_full | Shadow sort - a hybrid non-dominated sorting algorithm |
| title_fullStr | Shadow sort - a hybrid non-dominated sorting algorithm |
| title_full_unstemmed | Shadow sort - a hybrid non-dominated sorting algorithm |
| title_short | Shadow sort - a hybrid non-dominated sorting algorithm |
| title_sort | shadow sort a hybrid non dominated sorting algorithm |
| topic | Non-dominated sorting Evolutionary algorithm Multi-objective optimisation UCTD |
| url | http://hdl.handle.net/10019.1/124608 |
| work_keys_str_mv | AT tranklenicholasalbert shadowsortahybridnondominatedsortingalgorithm |