Titre :	Implementation of a Parallel Genetic Algorithm on Hadoop MapReduce
Type de document :	texte imprimé
Auteurs :	Chikhi ,Rima, Auteur ; Nasri,Khaled, Directeur de thèse
Editeur :	Setif:UFA
Année de publication :	2019
Importance :	1 vol (50 f .)
Format :	29 cm
Langues :	Français (fre)
Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Genetic algorithms parallel genetic algorithms Hadoop MapReduce model, grid model, island models.
Index. décimale :	004 Informatique
Résumé :	Genetic Algorithms (GAs) are powerful metaheuristic techniques mostly used in many real-world applications. The sequential execution of GAs requires considerable computational power both in time and resources.The need to improve the scalability of Genetic Algorithms (GAs) has motivated the research on Parallel Genetic Algorithms (PGAs), and different technologies and approaches have been used.Nevertheless, GAs are naturally parallel and accessing a parallel platform such as Cloud is easy and cheap. Hadoop MapReduce represents one of the most mature technologies to develop parallel algorithms.However, using Hadoop to develop a parallel version of GAs is not simple without facing its inner workings. In this work we describe the design and the implementation details of a framework that supports three different models for parallel GAs, namely the global model, the grid model and the island model
Note de contenu :	Sommaire Abstract i Acknowledgement ii Dedication iii Contents iv List of Figures vi General Introduction 1 1 Genetic algorithm State of Art 3 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Genetic Algorithms (GAs) . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Methodology Used In Genetic Algorithm . . . . . . . . . . . . . 5 2.2 Sequential Genetic Algorithm (SGA) . . . . . . . . . . . . . . . 6 3 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 PGA for the Global Model . . . . . . . . . . . . . . . . . . . . . 8 3.2 PGA for the Grid Model . . . . . . . . . . . . . . . . . . . . . . 9 3.3 PGA for the Island Model . . . . . . . . . . . . . . . . . . . . . 10 4 Hadoop MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1 Introduction of Hadoop . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Advantages of Hadoop: . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Architecture of Hadoop . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 HDFS(Hadoop Distributed File System): . . . . . . . . . . . . . 13 5 MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.1 The Algorithms of MapReduce: . . . . . . . . . . . . . . . . . . 15 5.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 Maven Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 iv 7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 implementation of parallel genetic algorithm in hadoop ecosystem 21 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Set up of Environments Configuration . . . . . . . . . . . . . . . . . . . 21 3 Implementation Environment . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 VMware Workstation . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Hadoop 2.7.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Installation And Configuration of Hadoop: . . . . . . . . . . . . 23 4 Apache Maven Installation . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Elephant56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Core Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2.1 Core.common . . . . . . . . . . . . . . . . . . . . . . 31 5.2.2 Core.input . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.3 Core.output . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.4 Core.generator . . . . . . . . . . . . . . . . . . . . . . 32 5.2.5 Core.reporter . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 User Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Implementation of ’oneMax’ problem . . . . . . . . . . . . . . . . . . . 35 6.1 Individual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Fitness value . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 Fitness Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.6 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.7 Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 General Conclusion 41 Bibliography 42 v List of Figures 1.1 Objectif Function [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 working mechanism of genetic algorithms[7] . . . . . . . . . . . . . . . 4 1.3 The execution of a Genetic Algorithm[1] . . . . . . . . . . . . . . . . . . 6 1.4 psaudo code[2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 The workflow for the global model[5] . . . . . . . . . . . . . . . . . . . 9 1.6 The workflow for the grid model[5] . . . . . . . . . . . . . . . . . . . . 9 1.7 The workflow for the grid model[5] . . . . . . . . . . . . . . . . . . . . 10 1.8 Hadoop Architecture[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9 HDFS Architecture[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.10 Operation phases in Map/Reduce programming model[6] . . . . . . . . . 14 1.11 MapReduce framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.12 Input and Output of MapReduce[7] . . . . . . . . . . . . . . . . . . . . . 15 1.13 Apache Maven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.14 Comparison of two models of parallel GA from scalability aspect; option 1 – All nodes uses same population; option 2 – each node has its own population[6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.15 Architecture of MRPGA[10] . . . . . . . . . . . . . . . . . . . . . . . . 19 1.16 Architectur of the proposed PGA[11] . . . . . . . . . . . . . . . . . . . . 20 2.1 Ubuntu virtual machine in VMware Workstation software. . . . . . . . . 22 2.2 hadoop logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 All the daemons are running . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 the Hadoop browser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Name node information . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Hadoop cluster YARN Framework (MapReduce) . . . . . . . . . . . . . 28 2.7 Apache Maven successfully installed . . . . . . . . . . . . . . . . . . . . 30 2.8 The core package class diagram[5] . . . . . . . . . . . . . . . . . . . . . 31 2.9 The Driver class.[5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.10 The generator package class diagram.[5] . . . . . . . . . . . . . . . . . . 32 vi 2.11 The reporter package class diagram.[5] . . . . . . . . . . . . . . . . . . . 34 2.12 The user package class diagram.[5] . . . . . . . . . . . . . . . . . . . . . 34 vii
Côte titre :	MAI/0319
En ligne :	https://drive.google.com/file/d/1JocEjEMfHmiCcNLvEVOppxE6AC20ZeTN/view?usp=shari [...]
Format de la ressource électronique :	pdf

Implementation of a Parallel Genetic Algorithm on Hadoop MapReduce [texte imprimé] / Chikhi ,Rima, Auteur ; Nasri,Khaled, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (50 f .) ; 29 cm.
Langues : Français (fre)

Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Genetic algorithms parallel genetic algorithms Hadoop MapReduce model, grid model, island models.
Index. décimale :	004 Informatique
Résumé :	Genetic Algorithms (GAs) are powerful metaheuristic techniques mostly used in many real-world applications. The sequential execution of GAs requires considerable computational power both in time and resources.The need to improve the scalability of Genetic Algorithms (GAs) has motivated the research on Parallel Genetic Algorithms (PGAs), and different technologies and approaches have been used.Nevertheless, GAs are naturally parallel and accessing a parallel platform such as Cloud is easy and cheap. Hadoop MapReduce represents one of the most mature technologies to develop parallel algorithms.However, using Hadoop to develop a parallel version of GAs is not simple without facing its inner workings. In this work we describe the design and the implementation details of a framework that supports three different models for parallel GAs, namely the global model, the grid model and the island model
Note de contenu :	Sommaire Abstract i Acknowledgement ii Dedication iii Contents iv List of Figures vi General Introduction 1 1 Genetic algorithm State of Art 3 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Genetic Algorithms (GAs) . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Methodology Used In Genetic Algorithm . . . . . . . . . . . . . 5 2.2 Sequential Genetic Algorithm (SGA) . . . . . . . . . . . . . . . 6 3 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 PGA for the Global Model . . . . . . . . . . . . . . . . . . . . . 8 3.2 PGA for the Grid Model . . . . . . . . . . . . . . . . . . . . . . 9 3.3 PGA for the Island Model . . . . . . . . . . . . . . . . . . . . . 10 4 Hadoop MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1 Introduction of Hadoop . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Advantages of Hadoop: . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Architecture of Hadoop . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 HDFS(Hadoop Distributed File System): . . . . . . . . . . . . . 13 5 MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.1 The Algorithms of MapReduce: . . . . . . . . . . . . . . . . . . 15 5.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 Maven Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 iv 7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 implementation of parallel genetic algorithm in hadoop ecosystem 21 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Set up of Environments Configuration . . . . . . . . . . . . . . . . . . . 21 3 Implementation Environment . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 VMware Workstation . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Hadoop 2.7.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Installation And Configuration of Hadoop: . . . . . . . . . . . . 23 4 Apache Maven Installation . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Elephant56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Core Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2.1 Core.common . . . . . . . . . . . . . . . . . . . . . . 31 5.2.2 Core.input . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.3 Core.output . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.4 Core.generator . . . . . . . . . . . . . . . . . . . . . . 32 5.2.5 Core.reporter . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 User Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Implementation of ’oneMax’ problem . . . . . . . . . . . . . . . . . . . 35 6.1 Individual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Fitness value . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 Fitness Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.6 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.7 Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 General Conclusion 41 Bibliography 42 v List of Figures 1.1 Objectif Function [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 working mechanism of genetic algorithms[7] . . . . . . . . . . . . . . . 4 1.3 The execution of a Genetic Algorithm[1] . . . . . . . . . . . . . . . . . . 6 1.4 psaudo code[2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 The workflow for the global model[5] . . . . . . . . . . . . . . . . . . . 9 1.6 The workflow for the grid model[5] . . . . . . . . . . . . . . . . . . . . 9 1.7 The workflow for the grid model[5] . . . . . . . . . . . . . . . . . . . . 10 1.8 Hadoop Architecture[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9 HDFS Architecture[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.10 Operation phases in Map/Reduce programming model[6] . . . . . . . . . 14 1.11 MapReduce framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.12 Input and Output of MapReduce[7] . . . . . . . . . . . . . . . . . . . . . 15 1.13 Apache Maven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.14 Comparison of two models of parallel GA from scalability aspect; option 1 – All nodes uses same population; option 2 – each node has its own population[6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.15 Architecture of MRPGA[10] . . . . . . . . . . . . . . . . . . . . . . . . 19 1.16 Architectur of the proposed PGA[11] . . . . . . . . . . . . . . . . . . . . 20 2.1 Ubuntu virtual machine in VMware Workstation software. . . . . . . . . 22 2.2 hadoop logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 All the daemons are running . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 the Hadoop browser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Name node information . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Hadoop cluster YARN Framework (MapReduce) . . . . . . . . . . . . . 28 2.7 Apache Maven successfully installed . . . . . . . . . . . . . . . . . . . . 30 2.8 The core package class diagram[5] . . . . . . . . . . . . . . . . . . . . . 31 2.9 The Driver class.[5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.10 The generator package class diagram.[5] . . . . . . . . . . . . . . . . . . 32 vi 2.11 The reporter package class diagram.[5] . . . . . . . . . . . . . . . . . . . 34 2.12 The user package class diagram.[5] . . . . . . . . . . . . . . . . . . . . . 34 vii
Côte titre :	MAI/0319
En ligne :	https://drive.google.com/file/d/1JocEjEMfHmiCcNLvEVOppxE6AC20ZeTN/view?usp=shari [...]
Format de la ressource électronique :	pdf