Parallelism in divide-and-conquer non-dominated sorting: a theoretical study considering the PRAM-CREW model

Sumit Mishra () and Carlos A. Coello Coello ()
Additional contact information
Sumit Mishra: CINVESTAV-IPN
Carlos A. Coello Coello: CINVESTAV-IPN

Journal of Heuristics, 2019, vol. 25, issue 3, No 5, 455-483

Abstract: Abstract Non-dominated sorting is a crucial component of Pareto-based multi- and many-objective evolutionary algorithms. As the number of objectives increases, the execution time of a multi-objective evolutionary algorithm increases, too. Since multi-objective evolutionary algorithms normally have a low data dependency, research-ers have increasingly adopted parallel programming techniques to reduce their execution time. Evidently, it is also desirable to parallelize non-dominated sorting. There are some recent proposals which focus on the parallelization of non-dominated sorting, with a particular emphasis on a very well-known approach called fast non-dominated sorting. In this paper, however, we explore the scope of parallelism in an approach called divide-and-conquer based non-dominated sorting (DCNS), which we recently introduced. This paper explores the parallelism from a theoretical point of view. The parallelization of the DCNS approach has been explored considering the PRAM-CREW (Parallel Random Access Machine, Concurrent Read Exclusive Write) model. The analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors are available. So, in our analysis, we have also considered the same assumption. The time and space complexities of the parallel version of the DCNS approach is obtained in different scenarios. The time complexity of the parallel version of the DCNS approach in different scenarios is proved to be $$\mathcal {O}(\log M + N)$$ O ( log M + N ) . We have also obtained the maximum number of processors which can be required by the parallel version of the DCNS approach. The comparison of the parallel version of the DCNS approach with respect to some other approaches is also performed.

Keywords: Non-dominated sorting; Dominance; Parallelism (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-019-09407-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:3:d:10.1007_s10732-019-09407-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-019-09407-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().