Shadow sort - a hybrid non-dominated sorting algorithm

Trankle, Nicholas Albert (2022-04)

Thesis (MEng)--Stellenbosch University, 2022.

Thesis

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/124608
This item appears in the following collections: