A parallel naive approach for non-dominated sorting: a theoretical study considering PRAM CREW model
- PDF / 601,087 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 40 Downloads / 141 Views
FOUNDATIONS
A parallel naive approach for non-dominated sorting: a theoretical study considering PRAM CREW model Sumit Mishra1,2 · Carlos A. Coello Coello1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Pareto-based multi-objective evolutionary algorithms use non-dominated sorting as an intermediate step. These algorithms are easy to parallelize as various steps of these algorithms are independent of each other. Researchers have focused on the parallelization of non-dominated sorting in order to reduce the execution time of these algorithms. In this paper, we focus on one of the initial approaches for non-dominated sorting also known as naive approach, proposed by Srinivas et al. and explore the scope of parallelism in this approach. Parallelism is explored in the considered approach in three different ways considering Parallel Random Access Machine, Concurrent Read Exclusive Write model. The time and space complexities of three different parallel versions are also analyzed. Analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors are available. Thus, the same assumption has been considered in our analysis too and we have obtained the maximum number of processors required for three parallel versions. Keywords Multi-objective optimization · Non-dominated sorting · Parallelism · PRAM CREW model
1 Introduction Pareto-based multi- and many-objective evolutionary algorithms use non-dominated sorting as an intermediate step (Deb et al. 2002; Deb and Jain 2014). Non-dominated sorting is also used in other domains such as economics, databases, game theory and computational geometry. In nondominated sorting, the solutions are sorted based on the dominance relationship between the solutions. Let P = {sol1 , sol2 , . . . , sol N } be a set of N solutions where each solution is associated with M objectives. The set of solutions is known as population. Actually, these solutions are in an M-dimensional objective space. A particular solution soli (1 ≤ i ≤ N ) in the population is represented as soli = Communicated by A. Di Nola.
B
Sumit Mishra [email protected] Carlos A. Coello Coello [email protected]
1
Departamento de Computación, CINVESTAV-IPN, 07360 Mexico City, Mexico
2
Department of Computer Science and Engineering , Indian Institute of Information Technology Guwahati, Guwahati, Assam 781015, India
{ f 1 (soli ), f 2 (soli ), . . . , f M (soli )} where f m (soli ), 1 ≤ m ≤ M is the value of soli for the m th objective. We consider here the optimization problems where the focus is to minimize all the objectives. For sorting the solutions, the dominance relation between them is required, which is defined as follows. Definition 1 (Dominance) A solution soli is said to dominate another solution sol j which is represented as soli ≺ sol j iff it satisfies the two following conditions: 1. f m (soli ) ≤ f m (sol j ), ∀m ∈ {1, 2, . . . , M} 2. f m (soli ) < f m (sol j ), ∃m ∈ {1, 2, . . . , M}. The notation soli ⊀ sol
Data Loading...
