| Titre : | Implementation and Parallelization of Multi-objective Evolutionary Algorithm Based on Decomposition and Directed Mating |
| Auteurs : | Nedjma ABIDALLAH, Auteur ; Laïd Kahloul, Directeur de thèse |
| Type de document : | Monographie imprimée |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2020 |
| Format : | 1 vol. (56 p.) / ill. / 29 cm |
| Langues: | Anglais |
| Mots-clés: | CMOP,CMOEA,PEA,CMOEA/D-DMA,PCMOEA/D-DMA |
| Résumé : | As an evolutionary approach to solve constrained multi-objective optimization problems (CMOPs), a multi objective evolutionary algorithm (MOEA) using the two-stage nondominated sorting and the directed mating (TNSDM) [21] has been proposed. However,since TNSDM uses the non-dominated sorting, its search performance deteriorates when the number of objectives is increased. For multi-objective optimization, the decomposing objective space is a promising approach, and MOEA/D [34] is known as its representative algorithm. However, in the conventional MOEA/D only feasible solutions are selected as parents. For solving constrained multi-objective optimization problems (CMOPs), recently a constrained multi-objective optimization evolutionary algorithm (CMOEA) that combines the directed mating concept and the decomposition approach has been proposed which is CMOEA/D-DMA [19] (Constrained Multi-objective Optimization Evolutionary Algorithms based on Decomposition and directed mating). Although, CMOEA/D-DMA has been improved its e?ciency in solving CMOPs with large scale, being an evolutionary algorithm means that it will certainly be characterized by long execution time. One of the reasons that push us to adopt parallel evolutionary algorithms (PEAs) is to obtain best results with an execution time much lower than the one of their sequential versions.In this thesis, we propose a new parallel version of CMOEA/D-DMA (i.e., PCMOEA/DDMA).The experimental results using modi?ed constrained DTLZ problem (mcDTLZ),show that the proposed parallel algorithm achieves higher search performance by utilizing infeasible solutions even if it doesn't surpass its sequential version in the hypervolume HV values, but a notable time reduction has been achieved. |
| Sommaire : |
I STATE OF THE ART 1
1 Constrained Multi-objective Optimization Evolutionary Algorithm 2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1 Constrained optimization problem . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Constrained multi-objective optimization problem . . . . . . . . . . . . . . . 3 1.3 Constraint-handling in MOEAs . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 CMOEA/D-DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.1 TNSDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.2 CMOEA/D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.3 The chosen algorithm CMOEA/D-DMA . . . . . . . . . . . . . . . . 8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Parallel Computing 14 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 De?nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Why parallel computing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Types of Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Parallel Computing Applications . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Concepts and Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.1 Parallel Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.2 Von Neumann Computer Architecture . . . . . . . . . . . . . . . . . 17 2.5.3 Instruction Stream and Data Stream . . . . . . . . . . . . . . . . . . 17 2.5.4 Flynn's Classi?cation . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.5 Limits and Costs of Parallel Programming . . . . . . . . . . . . . . . 19 2.6 Parallel Computer Memory Architectures . . . . . . . . . . . . . . . . . . . . 19 2.6.1 Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6.2 Distributed Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6.3 Hybrid Distributed-Shared Memory . . . . . . . . . . . . . . . . . . . 21 2.7 Parallel Programming Models . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7.1 Shared Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.7.2 Threads Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.7.3 Distributed Memory / Message Passing Model . . . . . . . . . . . . . 22 2.7.4 Data Parallel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7.5 Hybrid Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.7.6 SPMD and MPMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 II PARALLELIZATION OF CMOEA/D-DMA 26 3 Analysis & Design 28 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 project cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Application Global Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Hypervolume HV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.5 Sequential CMOEA/D-DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5.2 Global Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5.3 Detailed Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.6 Parallel CMOEA/D-DMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.6.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.6.2 Global Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.6.3 Detailed Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4 Implementation & Experimental study 42 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.1 Development Tools and Languages . . . . . . . . . . . . . . . . . . . . . . . 42 4.1.1 Python programming language . . . . . . . . . . . . . . . . . . . . . 42 4.1.2 PyCharm Programming Editor . . . . . . . . . . . . . . . . . . . . . 43 4.1.3 Tool Kit Interface \Tkinter" Package . . . . . . . . . . . . . . . . . . 43 4.1.4 Plotting Library \matplotlib" . . . . . . . . . . . . . . . . . . . . . . 43 4.1.5 Process-based "threading" \interface" . . . . . . . . . . . . . . . . . 43 4.1.6 Document Preparation System LATEX . . . . . . . . . . . . . . . . . . 43 4.1.7 Typesetting Editor (TEX MAKER) . . . . . . . . . . . . . . . . . . . 44 4.1.8 UML and BPMN modeling tool \Modelio" . . . . . . . . . . . . . . . 44 4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.1 Software and Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.2 Main Application: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Test & Experimental Study . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.2 Experimental results of CMOEA/D-DMA . . . . . . . . . . . . . . . 49 4.3.3 Experimental results of PDMOEA: . . . . . . . . . . . . . . . . . . . 51 4.4 Comparative study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4.1 CMOEA/D-DMA Vs CMOEAs . . . . . . . . . . . . . . . . . . . . . 53 4.4.2 CMOEA/D-DMA Vs PCMOEA/D-DMA . . . . . . . . . . . . . . . 54 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/549 | Mémoire master | bibliothèque sciences exactes | Consultable |
