University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Chikhi ,Rima |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
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 modelNote 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
viiCôte titre : MAI/0319 En ligne : https://drive.google.com/file/d/1JocEjEMfHmiCcNLvEVOppxE6AC20ZeTN/view?usp=shari [...] Format de la ressource électronique : 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 modelNote 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
viiCôte titre : MAI/0319 En ligne : https://drive.google.com/file/d/1JocEjEMfHmiCcNLvEVOppxE6AC20ZeTN/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0319 MAI/0319 Mémoire Bibliothéque des sciences Français Disponible
Disponible
