University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Fateh Seghir |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheAnalyse des images Méteosat Seconde Génération (MSG) pour l’estimation des précipitations / Osmani, Affef
Titre : Analyse des images Méteosat Seconde Génération (MSG) pour l’estimation des précipitations : Etude de cas en Algérie Type de document : texte imprimé Auteurs : Osmani, Affef, Auteur ; Fateh Seghir, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (49 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Estimation des Précipitations
k-means
MSGIndex. décimale : 004 Informatique Résumé : Ce travail porte sur l’estimation des précipitations en utilisant l’information infrarouge
du canal C9 (10.80 ¹m) du satellite Météosat Seconde Génération (MSG). Pour ce faire, nous
avons élaboré une méthode portant sur un seuil de température. Cette dernière constitue une
alternative permettant de simplifier la classification des nuages. Le principe est de définir une
valeur de seuil pour les données utilisées, à partir desquelles les pixels des images IR10.8 sont
considérés pluvieux ou non. Une approche d’estimation des précipitations basée sur le concept de
la classification non supervisée en k-means est proposée. Donc Le modèle élaboré ayant comme
sortie deux classes (clusters), dont l’une des classes est celle des pixels considérés précipitants
et l’autre pas de précipitation. Les données acquises par le capteur MSG-SEVIRI représentent
la période allant du 1er octobre 2016 au 31 mars 2017, et la région d’étude concerne le nord-est
de l’Algérie. Les résultats recueillis sont comparés aux données obtenues par le programme
d’estimation des précipitations par multicapteurs (MPE) de l’Organisation Européenne pour
l’exploitation des satellites météorologiques. Afin de valider le modèle développé.Note de contenu :
Sommaire
Remerciement i
Dédicaces ii
Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Liste des tableaux vi
Table des figures vii
0.1 Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 Les satellites MSG 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Dispositifs d’imagerie Satellitaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Les satellites météorologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1.1 Les satellites géostationnaires . . . . . . . . . . . . . . . . . . . . 4
1.2.1.2 Les satellites polaires . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Les satellites Météosat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2.1 Météosat de première génération . . . . . . . . . . . . . . . . . . . 5
1.2.2.2 Météosat seconde génération (MSG) . . . . . . . . . . . . . . . . . 6
1.3 Principe d’acquisition des images MSG . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Data Mining 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Processus d’extraction de connaissances à partir de données ECD . . . . 15
2.2.2 Techniques de data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2.2 Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.3 Les règle d’association . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.4 Clustering (segmentation) . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Réseaux de Neurones Artificiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Neurone biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
iv
TABLE DE MATIÈRE
2.3.2 Neurone artificiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.3 Architecture des réseaux neuronaux . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3.1 Les réseaux de neurones non bouclés (statiques) . . . . . . . . . 22
2.3.3.2 Les réseaux de neurones bouclés (dynamiques) . . . . . . . . . . 23
2.3.4 Apprentissage supervisé et non supervisé . . . . . . . . . . . . . . . . . . . 23
2.4 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 L’algorithme de K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Etat d’art 28
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Méthodes d’estimation des précipitations par satellite . . . . . . . . . . . . . . . . 32
3.4 Etude comparative des techniques de classification . . . . . . . . . . . . . . . . . . 33
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Conception et Implémentation 34
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Site d’étude et les données utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.1 Présentation du site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.2 Ensembles de données (Dataset) . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.1 Environnement et outils de mise en oeuvre . . . . . . . . . . . . . . . . . . 37
4.4.1.1 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.2 Méthode d’identification et de classification . . . . . . . . . . . . . . . . . . 38
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Bibliographie 42
Annexe 46
Les nuages et les précipitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Les nuages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Formation des nuages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Formation des nuages de convection . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Types de précipitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
v
LISTE DES TABLEAUCôte titre : MAI/0303 En ligne : https://drive.google.com/file/d/1uKdfzh0n9YAQ6X4684DFL7dMIG2K8Yfu/view?usp=shari [...] Format de la ressource électronique : Analyse des images Méteosat Seconde Génération (MSG) pour l’estimation des précipitations : Etude de cas en Algérie [texte imprimé] / Osmani, Affef, Auteur ; Fateh Seghir, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (49 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Estimation des Précipitations
k-means
MSGIndex. décimale : 004 Informatique Résumé : Ce travail porte sur l’estimation des précipitations en utilisant l’information infrarouge
du canal C9 (10.80 ¹m) du satellite Météosat Seconde Génération (MSG). Pour ce faire, nous
avons élaboré une méthode portant sur un seuil de température. Cette dernière constitue une
alternative permettant de simplifier la classification des nuages. Le principe est de définir une
valeur de seuil pour les données utilisées, à partir desquelles les pixels des images IR10.8 sont
considérés pluvieux ou non. Une approche d’estimation des précipitations basée sur le concept de
la classification non supervisée en k-means est proposée. Donc Le modèle élaboré ayant comme
sortie deux classes (clusters), dont l’une des classes est celle des pixels considérés précipitants
et l’autre pas de précipitation. Les données acquises par le capteur MSG-SEVIRI représentent
la période allant du 1er octobre 2016 au 31 mars 2017, et la région d’étude concerne le nord-est
de l’Algérie. Les résultats recueillis sont comparés aux données obtenues par le programme
d’estimation des précipitations par multicapteurs (MPE) de l’Organisation Européenne pour
l’exploitation des satellites météorologiques. Afin de valider le modèle développé.Note de contenu :
Sommaire
Remerciement i
Dédicaces ii
Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Liste des tableaux vi
Table des figures vii
0.1 Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 Les satellites MSG 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Dispositifs d’imagerie Satellitaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Les satellites météorologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1.1 Les satellites géostationnaires . . . . . . . . . . . . . . . . . . . . 4
1.2.1.2 Les satellites polaires . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Les satellites Météosat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2.1 Météosat de première génération . . . . . . . . . . . . . . . . . . . 5
1.2.2.2 Météosat seconde génération (MSG) . . . . . . . . . . . . . . . . . 6
1.3 Principe d’acquisition des images MSG . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Data Mining 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Processus d’extraction de connaissances à partir de données ECD . . . . 15
2.2.2 Techniques de data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2.2 Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.3 Les règle d’association . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2.4 Clustering (segmentation) . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Réseaux de Neurones Artificiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Neurone biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
iv
TABLE DE MATIÈRE
2.3.2 Neurone artificiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.3 Architecture des réseaux neuronaux . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3.1 Les réseaux de neurones non bouclés (statiques) . . . . . . . . . 22
2.3.3.2 Les réseaux de neurones bouclés (dynamiques) . . . . . . . . . . 23
2.3.4 Apprentissage supervisé et non supervisé . . . . . . . . . . . . . . . . . . . 23
2.4 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 L’algorithme de K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Etat d’art 28
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Méthodes d’estimation des précipitations par satellite . . . . . . . . . . . . . . . . 32
3.4 Etude comparative des techniques de classification . . . . . . . . . . . . . . . . . . 33
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Conception et Implémentation 34
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Site d’étude et les données utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.1 Présentation du site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.2 Ensembles de données (Dataset) . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.1 Environnement et outils de mise en oeuvre . . . . . . . . . . . . . . . . . . 37
4.4.1.1 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.2 Méthode d’identification et de classification . . . . . . . . . . . . . . . . . . 38
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Bibliographie 42
Annexe 46
Les nuages et les précipitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Les nuages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Formation des nuages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Formation des nuages de convection . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Types de précipitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
v
LISTE DES TABLEAUCôte titre : MAI/0303 En ligne : https://drive.google.com/file/d/1uKdfzh0n9YAQ6X4684DFL7dMIG2K8Yfu/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0303 MAI/0303 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Composition de services web sémantiques dans des systèmes ouverts et dynamiques Type de document : texte imprimé Auteurs : Fateh Seghir, Auteur ; Khababa,Abdellah, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (119 f .) Format : 29 cm Langues : Anglais (eng) Langues originales : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Sélection de service web
Qualité de service (QoS)
Optimisation combinatoire
Méta-heuristiques
Incertitude QoS
IntervallenombreIndex. décimale : 004 Informatique Résumé : Résumé
Avec la prolifération du cloud computing et de l'internet des objets, de plus en plus
de services web, orant des fonctionnalités similaires mais orant une qualité de service
(QoS) diérente, comme le temps d'exécution, le prix et le débit . . . seront proposés
sur le web. Par conséquent, la sélection des services Web optimaux pour créer un service
composite optimal répondant aux contraintes globales de QoS de bout en bout est
l'un des problèmes les plus importants de la composition de services, appelé QoSSCP.
Le QoSSCP est considéré comme un problème d'optimisation multi-objective dur non
polynomial; par conséquent, des approches robustes doivent être développées pour ré-
soudre ce problème complexe. Dans ce travail, trois contributions majeures basées sur
les algorithmes méta-heuristiques sont proposées pour résoudre le QoSSCP. Dans la premi
ère contribution, nous adaptons un algorithme d'optimisation stochastique récent appel
é algorithme d'optimisation de la mouche du fruit (FOA) comme une recherche locale
dans l'évolution de l'algorithme génétique (GA), et nous présentons une approche hybride
(HGA) pour résoudre le problème suggéré. Dans la deuxième contribution, une version
discrète de l'algorithme de concurrence impérialiste (DICA) est introduite pour résoudre
le problème susmentionné. Le processus d'assimilation du DICA est mis en oeuvre en
utilisant le mécanisme de recherche d'abeilles à partir de l'algorithme de la colonie arti
cielle d'abeilles (ABC). Dans la troisième contribution, nous proposons une approche
basées sur l'algorithme ABC. Contrairement aux approches proposées précédemment, où
le QoSSCP résolu est basé sur l'hypothèse de valeurs xes pour les attributs QoS des
services web élémentaires, les propriétés QoS incertaines sont considérées dans l'approche
proposée, qui sont exprimées sous forme de nombres d'intervalles. L'approche proposée
est une méthode d'optimisation multi-objective (IPMOABC); ainsi, un ensemble de solutions
optimales de Pareto peut être produit, ce qui fournit une décision de choix pour la
meilleure solution requise. Basés sur des bases de données réelles et aléatoires, les résultats
expérimentaux montrent que les HGA, DICA, et IPMOABC surpassent les versions
standards des métaheuristiques utilisées.Note de contenu :
Sommaire
List of gures iii
List of tables v
1 General Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 QoS-aware service composition: Research scope and challenges . . . . . . . 2
1.2.1 Scalability and optimality . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Uncertainty and dynamic environments . . . . . . . . . . . . . . . . 3
1.3 Motivating example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Research aims and contributions . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 A hybrid approach using genetic and fruit y optimization algorithms for QoS-aware cloud service composition 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 GA, FOA and problem description . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Genetic Algorithm(GA) . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Fruit y Optimization Algorithm(FOA) . . . . . . . . . . . . . . . . 11
2.2.3 Notations and problem description . . . . . . . . . . . . . . . . . . 13
2.3 The proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Encoding scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Population initialization . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2.1 Local optimization selection method . . . . . . . . . . . . 17
2.3.2.2 Improved initial population generation . . . . . . . . . . . 18
2.3.3 Fitness evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.4 Genetic phase (Global exploration) . . . . . . . . . . . . . . . . . . 22
2.3.4.1 Selection operator . . . . . . . . . . . . . . . . . . . . . . 22
2.3.4.2 Crossover operator . . . . . . . . . . . . . . . . . . . . . . 23
2.3.4.3 Mutation operator . . . . . . . . . . . . . . . . . . . . . . 24
2.3.5 FOA phase (Local exploitation) . . . . . . . . . . . . . . . . . . . . 25
2.3.6 The elitism operator . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.7 The stopping criterion . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.8 The framework of the proposed HGA . . . . . . . . . . . . . . . . 26
2.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 Parameter setting of HGA . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Comparisons and results . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2.1 Optimality and execution time . . . . . . . . . . . . . . . 31
2.4.2.2 Feasibility rate . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.2.3 Eects of user QoS preferences . . . . . . . . . . . . . . . 35
2.4.2.4 Eects of QoS value ranges . . . . . . . . . . . . . . . . . 37
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 A new discrete imperialist competitive algorithm for QoS-aware service composition in cloud computing 43
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 ICA and the QCSC problem formulation . . . . . . . . . . . . . . . . . . . 45
3.2.1 The imperialist competitive algorithm (ICA) . . . . . . . . . . . . . 45
3.2.2 The QCSC problem formulation . . . . . . . . . . . . . . . . . . . . 47
3.3 The proposed algorithm (DICA) . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Initialization of empires (initial population) . . . . . . . . . . . . . 49
3.3.2 Discrete assimilation policy process . . . . . . . . . . . . . . . . . . 51
3.3.3 Moving of imperialists toward strongest imperialist . . . . . . . . . 53
3.3.4 Revolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.5 Update the imperialist . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.6 Empires competition process . . . . . . . . . . . . . . . . . . . . . . 55
3.3.7 The ending criterion of DICA . . . . . . . . . . . . . . . . . . . . . 56
3.3.8 The framework of the proposed algorithm . . . . . . . . . . . . . . 57
3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.1 Optimality comparisons . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.2 Computation time comparisons . . . . . . . . . . . . . . . . . . . . 60
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 An interval-based multi-objective arti cial bee colony algorithm for solving the web service composition under uncertain QoS 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Uncertain QoS computing model . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1.1 Interval arithmetic . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1.2 Interval order relation . . . . . . . . . . . . . . . . . . . . 68
4.2.2 QoS model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.3 QoS aggregation for composite service . . . . . . . . . . . . . . . . 71
4.3 Problem description and arti cial bee colony algorithm . . . . . . . . . . . 72
4.3.1 Interval multi-objective optimization problem . . . . . . . . . . . . 72
4.3.2 The arti cial bee colony algorithm (ABC) . . . . . . . . . . . . . . 74
4.3.3 Multi-objective QoS uncertainty-aware service composition problem
(UQoSSCP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.3.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . 76
4.4 The proposed interval-based multi-objective arti cial bee colony algorithm (IPMOABC) . . . . . . . . 77
4.4.1 Encoding of food source and population initialization . . . . . . . . 77
4.4.2 Interval-based feasibility technique for handling constraints . . . . . 78
4.4.3 The uncertain-Pareto non-dominated solutions . . . . . . . . . . . . 81
4.4.4 Extended crowding distance based on a interval-distance de nition . 81
4.4.5 Update external repository . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.6 Behaviors of employed bees, onlookers and scouts . . . . . . . . . . 84
4.4.6.1 Employed bee phase . . . . . . . . . . . . . . . . . . . . . 84
4.4.6.2 Onlooker bee phase . . . . . . . . . . . . . . . . . . . . . . 86
4.4.6.3 Scoot bee phase . . . . . . . . . . . . . . . . . . . . . . . . 87
4.4.7 The framework of the proposed IPMOABC algorithm . . . . . . . . 88
4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5.1 Experimental datasets . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.5.2 Uncertain Pareto optimal front . . . . . . . . . . . . . . . . . . . . 91
4.5.3 Performance comparisons . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5.3.1 Comparisons on WSDream dataset . . . . . . . . . . . . . 98
4.5.3.2 Comparisons on WSRandom dataset . . . . . . . . . . . . 100
4.5.4 Eectiveness of the generating neighbors process . . . . . . . . . . . 102
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5 General conclusion and perspectives 108
5.1 Contributions and research summary . . . . . . . . . . . . . . . . . . . . . 108
5.1.1 A hybrid approach using genetic and fruit y optimization algorithms
for QoS-aware cloud service composition . . . . . . . . . . . 109
5.1.2 A new discrete imperialist competitive algorithm for QoS-aware service
composition in cloud computing . . . . . . . . . . . . . . . . . 109
5.1.3 An interval-based multi-objective arti cial bee colony algorithm for solving the web service composition under uncertain QoS . . . . . . 110
5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Bibliography 112
Côte titre : DI/0030 En ligne : https://drive.google.com/file/d/1P6sVN2h8vS51c5FaCq-r3UcifmtYxFv-/view?usp=shari [...] Format de la ressource électronique : Composition de services web sémantiques dans des systèmes ouverts et dynamiques [texte imprimé] / Fateh Seghir, Auteur ; Khababa,Abdellah, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (119 f .) ; 29 cm.
Langues : Anglais (eng) Langues originales : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Sélection de service web
Qualité de service (QoS)
Optimisation combinatoire
Méta-heuristiques
Incertitude QoS
IntervallenombreIndex. décimale : 004 Informatique Résumé : Résumé
Avec la prolifération du cloud computing et de l'internet des objets, de plus en plus
de services web, orant des fonctionnalités similaires mais orant une qualité de service
(QoS) diérente, comme le temps d'exécution, le prix et le débit . . . seront proposés
sur le web. Par conséquent, la sélection des services Web optimaux pour créer un service
composite optimal répondant aux contraintes globales de QoS de bout en bout est
l'un des problèmes les plus importants de la composition de services, appelé QoSSCP.
Le QoSSCP est considéré comme un problème d'optimisation multi-objective dur non
polynomial; par conséquent, des approches robustes doivent être développées pour ré-
soudre ce problème complexe. Dans ce travail, trois contributions majeures basées sur
les algorithmes méta-heuristiques sont proposées pour résoudre le QoSSCP. Dans la premi
ère contribution, nous adaptons un algorithme d'optimisation stochastique récent appel
é algorithme d'optimisation de la mouche du fruit (FOA) comme une recherche locale
dans l'évolution de l'algorithme génétique (GA), et nous présentons une approche hybride
(HGA) pour résoudre le problème suggéré. Dans la deuxième contribution, une version
discrète de l'algorithme de concurrence impérialiste (DICA) est introduite pour résoudre
le problème susmentionné. Le processus d'assimilation du DICA est mis en oeuvre en
utilisant le mécanisme de recherche d'abeilles à partir de l'algorithme de la colonie arti
cielle d'abeilles (ABC). Dans la troisième contribution, nous proposons une approche
basées sur l'algorithme ABC. Contrairement aux approches proposées précédemment, où
le QoSSCP résolu est basé sur l'hypothèse de valeurs xes pour les attributs QoS des
services web élémentaires, les propriétés QoS incertaines sont considérées dans l'approche
proposée, qui sont exprimées sous forme de nombres d'intervalles. L'approche proposée
est une méthode d'optimisation multi-objective (IPMOABC); ainsi, un ensemble de solutions
optimales de Pareto peut être produit, ce qui fournit une décision de choix pour la
meilleure solution requise. Basés sur des bases de données réelles et aléatoires, les résultats
expérimentaux montrent que les HGA, DICA, et IPMOABC surpassent les versions
standards des métaheuristiques utilisées.Note de contenu :
Sommaire
List of gures iii
List of tables v
1 General Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 QoS-aware service composition: Research scope and challenges . . . . . . . 2
1.2.1 Scalability and optimality . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Uncertainty and dynamic environments . . . . . . . . . . . . . . . . 3
1.3 Motivating example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Research aims and contributions . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 A hybrid approach using genetic and fruit y optimization algorithms for QoS-aware cloud service composition 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 GA, FOA and problem description . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Genetic Algorithm(GA) . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Fruit y Optimization Algorithm(FOA) . . . . . . . . . . . . . . . . 11
2.2.3 Notations and problem description . . . . . . . . . . . . . . . . . . 13
2.3 The proposed approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Encoding scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Population initialization . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2.1 Local optimization selection method . . . . . . . . . . . . 17
2.3.2.2 Improved initial population generation . . . . . . . . . . . 18
2.3.3 Fitness evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.4 Genetic phase (Global exploration) . . . . . . . . . . . . . . . . . . 22
2.3.4.1 Selection operator . . . . . . . . . . . . . . . . . . . . . . 22
2.3.4.2 Crossover operator . . . . . . . . . . . . . . . . . . . . . . 23
2.3.4.3 Mutation operator . . . . . . . . . . . . . . . . . . . . . . 24
2.3.5 FOA phase (Local exploitation) . . . . . . . . . . . . . . . . . . . . 25
2.3.6 The elitism operator . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.7 The stopping criterion . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.8 The framework of the proposed HGA . . . . . . . . . . . . . . . . 26
2.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 Parameter setting of HGA . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Comparisons and results . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2.1 Optimality and execution time . . . . . . . . . . . . . . . 31
2.4.2.2 Feasibility rate . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.2.3 Eects of user QoS preferences . . . . . . . . . . . . . . . 35
2.4.2.4 Eects of QoS value ranges . . . . . . . . . . . . . . . . . 37
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 A new discrete imperialist competitive algorithm for QoS-aware service composition in cloud computing 43
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 ICA and the QCSC problem formulation . . . . . . . . . . . . . . . . . . . 45
3.2.1 The imperialist competitive algorithm (ICA) . . . . . . . . . . . . . 45
3.2.2 The QCSC problem formulation . . . . . . . . . . . . . . . . . . . . 47
3.3 The proposed algorithm (DICA) . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Initialization of empires (initial population) . . . . . . . . . . . . . 49
3.3.2 Discrete assimilation policy process . . . . . . . . . . . . . . . . . . 51
3.3.3 Moving of imperialists toward strongest imperialist . . . . . . . . . 53
3.3.4 Revolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.5 Update the imperialist . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.6 Empires competition process . . . . . . . . . . . . . . . . . . . . . . 55
3.3.7 The ending criterion of DICA . . . . . . . . . . . . . . . . . . . . . 56
3.3.8 The framework of the proposed algorithm . . . . . . . . . . . . . . 57
3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.1 Optimality comparisons . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.2 Computation time comparisons . . . . . . . . . . . . . . . . . . . . 60
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 An interval-based multi-objective arti cial bee colony algorithm for solving the web service composition under uncertain QoS 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Uncertain QoS computing model . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1.1 Interval arithmetic . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1.2 Interval order relation . . . . . . . . . . . . . . . . . . . . 68
4.2.2 QoS model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.3 QoS aggregation for composite service . . . . . . . . . . . . . . . . 71
4.3 Problem description and arti cial bee colony algorithm . . . . . . . . . . . 72
4.3.1 Interval multi-objective optimization problem . . . . . . . . . . . . 72
4.3.2 The arti cial bee colony algorithm (ABC) . . . . . . . . . . . . . . 74
4.3.3 Multi-objective QoS uncertainty-aware service composition problem
(UQoSSCP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.3.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . 76
4.4 The proposed interval-based multi-objective arti cial bee colony algorithm (IPMOABC) . . . . . . . . 77
4.4.1 Encoding of food source and population initialization . . . . . . . . 77
4.4.2 Interval-based feasibility technique for handling constraints . . . . . 78
4.4.3 The uncertain-Pareto non-dominated solutions . . . . . . . . . . . . 81
4.4.4 Extended crowding distance based on a interval-distance de nition . 81
4.4.5 Update external repository . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.6 Behaviors of employed bees, onlookers and scouts . . . . . . . . . . 84
4.4.6.1 Employed bee phase . . . . . . . . . . . . . . . . . . . . . 84
4.4.6.2 Onlooker bee phase . . . . . . . . . . . . . . . . . . . . . . 86
4.4.6.3 Scoot bee phase . . . . . . . . . . . . . . . . . . . . . . . . 87
4.4.7 The framework of the proposed IPMOABC algorithm . . . . . . . . 88
4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5.1 Experimental datasets . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.5.2 Uncertain Pareto optimal front . . . . . . . . . . . . . . . . . . . . 91
4.5.3 Performance comparisons . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5.3.1 Comparisons on WSDream dataset . . . . . . . . . . . . . 98
4.5.3.2 Comparisons on WSRandom dataset . . . . . . . . . . . . 100
4.5.4 Eectiveness of the generating neighbors process . . . . . . . . . . . 102
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5 General conclusion and perspectives 108
5.1 Contributions and research summary . . . . . . . . . . . . . . . . . . . . . 108
5.1.1 A hybrid approach using genetic and fruit y optimization algorithms
for QoS-aware cloud service composition . . . . . . . . . . . 109
5.1.2 A new discrete imperialist competitive algorithm for QoS-aware service
composition in cloud computing . . . . . . . . . . . . . . . . . 109
5.1.3 An interval-based multi-objective arti cial bee colony algorithm for solving the web service composition under uncertain QoS . . . . . . 110
5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Bibliography 112
Côte titre : DI/0030 En ligne : https://drive.google.com/file/d/1P6sVN2h8vS51c5FaCq-r3UcifmtYxFv-/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0030 DI/0030 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : Description and composition of Internet of Things (IoT)- Services based on Quality of Service(QoS) Type de document : texte imprimé Auteurs : Kouachi,Renda, Auteur ; Fateh Seghir, Directeur de thèse Editeur : Setif:UFA Année de publication : 2020 Importance : 1 vol (55 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Optimisation multicritères
La méthode VIKOR
L’algorithme génétiqueIndex. décimale : 004 - Informatique Résumé :
La composition d’un ensemble de services web à base de qualité de service (Quality of
Service : QoS) avec des contraintes-utilisateur globales de QoS dans les environnements IoT
dynamiques est un problème NP-difficile, où les valeurs QoS des services IoT sont souvent
de nature ambiguës et imprécise en raison de diverses raisons, telles que les changements
de topologie du réseau, mobilité des appareils de l’internet des objets (IoT), congestion
des systèmes et politiques économiques. Puisque le nombre d’intervalle (Interval-number)
est un modèle efficace et simple pour exprimer l’imprécision et l’ambiguïté des propriétés
QoS, le QSC dans les environnements IoT incertains est formulé comme un problème
d’optimisation multicritères d’intervalle (INQSC). De plus, pour résoudre l’INQSC modélisé,
nous fournissons une approche d’optimisation basée sur l’algorithme génétique(GA), qui
intègre une méthode VIKOR d’intervalle pour traiter le classement des solutions réalisables,
trier les violations de contrainte de QoS d’intervalle pour les solutions irréalisables et un
opérateur de recherche local avec un remplacement d’élitisme pour améliorer à la fois les
capacités d’exploitation et d’exploration de l’approche d’optimisation fournie. Les résultats
de la comparaison expérimentale de notre proposition avec une approche GAP récemment
fournie démontrent les performances et l’efficacité de l’approche d’optimisation basée sur
l’AG proposée. De plus, le taux de faisabilité élevé de notre proposition dans la résolution du
problème INQSC avec des contraintes-utilisateur sévères de QoS ainsi que l’efficacité deCôte titre : MAI/0423 En ligne : https://drive.google.com/file/d/1SDqFrIhGwyLqopne7xOCIdEvhyn23y8S/view?usp=shari [...] Format de la ressource électronique : Description and composition of Internet of Things (IoT)- Services based on Quality of Service(QoS) [texte imprimé] / Kouachi,Renda, Auteur ; Fateh Seghir, Directeur de thèse . - [S.l.] : Setif:UFA, 2020 . - 1 vol (55 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Optimisation multicritères
La méthode VIKOR
L’algorithme génétiqueIndex. décimale : 004 - Informatique Résumé :
La composition d’un ensemble de services web à base de qualité de service (Quality of
Service : QoS) avec des contraintes-utilisateur globales de QoS dans les environnements IoT
dynamiques est un problème NP-difficile, où les valeurs QoS des services IoT sont souvent
de nature ambiguës et imprécise en raison de diverses raisons, telles que les changements
de topologie du réseau, mobilité des appareils de l’internet des objets (IoT), congestion
des systèmes et politiques économiques. Puisque le nombre d’intervalle (Interval-number)
est un modèle efficace et simple pour exprimer l’imprécision et l’ambiguïté des propriétés
QoS, le QSC dans les environnements IoT incertains est formulé comme un problème
d’optimisation multicritères d’intervalle (INQSC). De plus, pour résoudre l’INQSC modélisé,
nous fournissons une approche d’optimisation basée sur l’algorithme génétique(GA), qui
intègre une méthode VIKOR d’intervalle pour traiter le classement des solutions réalisables,
trier les violations de contrainte de QoS d’intervalle pour les solutions irréalisables et un
opérateur de recherche local avec un remplacement d’élitisme pour améliorer à la fois les
capacités d’exploitation et d’exploration de l’approche d’optimisation fournie. Les résultats
de la comparaison expérimentale de notre proposition avec une approche GAP récemment
fournie démontrent les performances et l’efficacité de l’approche d’optimisation basée sur
l’AG proposée. De plus, le taux de faisabilité élevé de notre proposition dans la résolution du
problème INQSC avec des contraintes-utilisateur sévères de QoS ainsi que l’efficacité deCôte titre : MAI/0423 En ligne : https://drive.google.com/file/d/1SDqFrIhGwyLqopne7xOCIdEvhyn23y8S/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0423 MAI/0423 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
Titre : Intelligent Optimization Approaches for the QoS-Driven Services Composition Problem in Dynamic IoT Environments Type de document : texte imprimé Auteurs : Sifeddine Abbaoui, Auteur ; Saad eddine Kharmouche, Auteur ; Fateh Seghir, Directeur de thèse Année de publication : 2022 Importance : 1 vol (45 f .) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Services IoT
Qualité des Services
Composition des services IoTIndex. décimale : 004 Informatique Résumé :
Ce travail porte une étude sur Le problème de sélection de services basé sur la qualité
de service (QoS) dans un environnement IoT dynamique, où les paramètres QoS sont
incertains ou ambigües à cause des phénomènes liés aux réseaux tel-que la mobilité
des appareils IoT et la congestion des réseaux. Dans un premier temps, ce problème a
été formulé selon un modèle d’optimisation mono-objectif avec des paramètres et des
contraintes flous. Il est classé comme un problème NP-difficile, qui est résolut par une
approche méta-heuristique amélioré de la version original de l’algorithme FPA. Les
résultats de comparaisons vis-à -vis d’autres approches existantes comme PSO, EFPA,
ITL-QCA ont montrés l’efficacité, la stabilité et l’optimalité de l’approche proposée.Côte titre : MAI/0571 En ligne : https://drive.google.com/file/d/1YeXCaCGkVBpnxTWEOAf3iz-ji57eM-rd/view?usp=share [...] Format de la ressource électronique : Intelligent Optimization Approaches for the QoS-Driven Services Composition Problem in Dynamic IoT Environments [texte imprimé] / Sifeddine Abbaoui, Auteur ; Saad eddine Kharmouche, Auteur ; Fateh Seghir, Directeur de thèse . - 2022 . - 1 vol (45 f .) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Services IoT
Qualité des Services
Composition des services IoTIndex. décimale : 004 Informatique Résumé :
Ce travail porte une étude sur Le problème de sélection de services basé sur la qualité
de service (QoS) dans un environnement IoT dynamique, où les paramètres QoS sont
incertains ou ambigües à cause des phénomènes liés aux réseaux tel-que la mobilité
des appareils IoT et la congestion des réseaux. Dans un premier temps, ce problème a
été formulé selon un modèle d’optimisation mono-objectif avec des paramètres et des
contraintes flous. Il est classé comme un problème NP-difficile, qui est résolut par une
approche méta-heuristique amélioré de la version original de l’algorithme FPA. Les
résultats de comparaisons vis-à -vis d’autres approches existantes comme PSO, EFPA,
ITL-QCA ont montrés l’efficacité, la stabilité et l’optimalité de l’approche proposée.Côte titre : MAI/0571 En ligne : https://drive.google.com/file/d/1YeXCaCGkVBpnxTWEOAf3iz-ji57eM-rd/view?usp=share [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0571 MAI/0571 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
Titre : Mobile Robot Path Planning Techniques in Dangerous and Dynamic Environments Type de document : texte imprimé Auteurs : Asma Boutalbi, Auteur ; Latifa Guerra ; Fateh Seghir, Directeur de thèse Editeur : Setif:UFA Année de publication : 2024 Importance : 1 vol (49 f .) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : path planning
Robotic systems
Meta-heuristic PSO
Global optimization
Obstacle avoidanceIndex. décimale : 004 - Informatique Résumé :
This research addressed the problem of paths planning for robots in environments
characterized by forbidden areas caused by obstacles and different dangers. After giving an
overview of the most popular algorithms in this field, some concepts related to optimization tasks
were also given. Finally, based on these studies, an approach based on Particle Swarm
Optimization Algorithm PSO and the weighted sum method has been proposed to generate safe
paths for robotic systems. Practical tests have been carried out to confirm the effectiveness and
validity of the proposed method.Note de contenu : Sommaire
List of Figures x
List of Tables xi
General introduction 1
1 Mobile Robot Path Planning Techniques 4
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Definition of Geometric Path Planning Problem . . . . . . . . . . . . . . . 4
3 Path planning classification . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Heuristic planning approaches . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1 Graph-based algorithms . . . . . . . . . . . . . . . . . . . . . . . 5
4.1.1 Dijkstra algorithm . . . . . . . . . . . . . . . . . . . . . 6
4.1.2 Astar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Road-map methods . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2.1 Visibility graph . . . . . . . . . . . . . . . . . . . . . . 7
4.2.2 Voronoi diagram . . . . . . . . . . . . . . . . . . . . . . 8
4.2.3 Cell decomposition . . . . . . . . . . . . . . . . . . . . 8
4.3 Sampling-based (probabilistic) methods . . . . . . . . . . . . . . . 8
4.3.1 Probabilistic Roadmaps . . . . . . . . . . . . . . . . . . 9
4.3.2 Rapidly exploring random tree . . . . . . . . . . . . . . 9
4.4 Artificial Potential Fields . . . . . . . . . . . . . . . . . . . . . . . 9
5 Meta-Heuristic planning approaches . . . . . . . . . . . . . . . . . . . . . 10
5.1 Genetic Algorithm Technique . . . . . . . . . . . . . . . . . . . . 11
5.2 Ant Colony Optimization : . . . . . . . . . . . . . . . . . . . . . . 11
5.3 Bacterial Foraging Technique . . . . . . . . . . . . . . . . . . . . 11
5.4 Bee Colony Technique . . . . . . . . . . . . . . . . . . . . . . . . 12
5.5 Firefly Algorithm Technique . . . . . . . . . . . . . . . . . . . . . 12
5.6 Grey Wolf Optimizer (GWO) . . . . . . . . . . . . . . . . . . . . 12
5.7 simulated Annealing (SA)) . . . . . . . . . . . . . . . . . . . . . . 12
6 Artificial intelligence techniques . . . . . . . . . . . . . . . . . . . . . . . 13
6.1 Fuzzy Logic Technique . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2 Artificial Neural Networks Techniques . . . . . . . . . . . . . . . . 14
6.3 Machine and Deep Learning . . . . . . . . . . . . . . . . . . . . . 14
7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Notes on Optimization and PSO algorithm 16
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Single objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Multi-objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Dominance and Pareto optimally . . . . . . . . . . . . . . . . . . . 18
3.2 Weighted sum method . . . . . . . . . . . . . . . . . . . . . . . . 19
4 PSO algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1 General description . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Initialisation Process . . . . . . . . . . . . . . . . . . . . 22
4.2.2 Positions and velocities update . . . . . . . . . . . . . . 23
4.2.3 Repair process . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.4 Update local and global bests . . . . . . . . . . . . . . . 23
4.2.5 Termination condition . . . . . . . . . . . . . . . . . . . 24
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Path planning by using PSO algorithm 25
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Path definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Path parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 Intersection with obstacles . . . . . . . . . . . . . . . . 27
2.2.2 Path length . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Path planing problem reformulation . . . . . . . . . . . . . . . . . 29
3 Proposed solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1 Objective function . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 PSO-based path planners . . . . . . . . . . . . . . . . . . . . . . . 29
4 Numerical tests and discussion . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Test1 : A simple illustrative example . . . . . . . . . . . . . . . . . 31
......Côte titre : MAI/0861 Mobile Robot Path Planning Techniques in Dangerous and Dynamic Environments [texte imprimé] / Asma Boutalbi, Auteur ; Latifa Guerra ; Fateh Seghir, Directeur de thèse . - [S.l.] : Setif:UFA, 2024 . - 1 vol (49 f .) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : path planning
Robotic systems
Meta-heuristic PSO
Global optimization
Obstacle avoidanceIndex. décimale : 004 - Informatique Résumé :
This research addressed the problem of paths planning for robots in environments
characterized by forbidden areas caused by obstacles and different dangers. After giving an
overview of the most popular algorithms in this field, some concepts related to optimization tasks
were also given. Finally, based on these studies, an approach based on Particle Swarm
Optimization Algorithm PSO and the weighted sum method has been proposed to generate safe
paths for robotic systems. Practical tests have been carried out to confirm the effectiveness and
validity of the proposed method.Note de contenu : Sommaire
List of Figures x
List of Tables xi
General introduction 1
1 Mobile Robot Path Planning Techniques 4
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Definition of Geometric Path Planning Problem . . . . . . . . . . . . . . . 4
3 Path planning classification . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Heuristic planning approaches . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1 Graph-based algorithms . . . . . . . . . . . . . . . . . . . . . . . 5
4.1.1 Dijkstra algorithm . . . . . . . . . . . . . . . . . . . . . 6
4.1.2 Astar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Road-map methods . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2.1 Visibility graph . . . . . . . . . . . . . . . . . . . . . . 7
4.2.2 Voronoi diagram . . . . . . . . . . . . . . . . . . . . . . 8
4.2.3 Cell decomposition . . . . . . . . . . . . . . . . . . . . 8
4.3 Sampling-based (probabilistic) methods . . . . . . . . . . . . . . . 8
4.3.1 Probabilistic Roadmaps . . . . . . . . . . . . . . . . . . 9
4.3.2 Rapidly exploring random tree . . . . . . . . . . . . . . 9
4.4 Artificial Potential Fields . . . . . . . . . . . . . . . . . . . . . . . 9
5 Meta-Heuristic planning approaches . . . . . . . . . . . . . . . . . . . . . 10
5.1 Genetic Algorithm Technique . . . . . . . . . . . . . . . . . . . . 11
5.2 Ant Colony Optimization : . . . . . . . . . . . . . . . . . . . . . . 11
5.3 Bacterial Foraging Technique . . . . . . . . . . . . . . . . . . . . 11
5.4 Bee Colony Technique . . . . . . . . . . . . . . . . . . . . . . . . 12
5.5 Firefly Algorithm Technique . . . . . . . . . . . . . . . . . . . . . 12
5.6 Grey Wolf Optimizer (GWO) . . . . . . . . . . . . . . . . . . . . 12
5.7 simulated Annealing (SA)) . . . . . . . . . . . . . . . . . . . . . . 12
6 Artificial intelligence techniques . . . . . . . . . . . . . . . . . . . . . . . 13
6.1 Fuzzy Logic Technique . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2 Artificial Neural Networks Techniques . . . . . . . . . . . . . . . . 14
6.3 Machine and Deep Learning . . . . . . . . . . . . . . . . . . . . . 14
7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Notes on Optimization and PSO algorithm 16
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Single objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Multi-objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Dominance and Pareto optimally . . . . . . . . . . . . . . . . . . . 18
3.2 Weighted sum method . . . . . . . . . . . . . . . . . . . . . . . . 19
4 PSO algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1 General description . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Initialisation Process . . . . . . . . . . . . . . . . . . . . 22
4.2.2 Positions and velocities update . . . . . . . . . . . . . . 23
4.2.3 Repair process . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.4 Update local and global bests . . . . . . . . . . . . . . . 23
4.2.5 Termination condition . . . . . . . . . . . . . . . . . . . 24
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Path planning by using PSO algorithm 25
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Path definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Path parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 Intersection with obstacles . . . . . . . . . . . . . . . . 27
2.2.2 Path length . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Path planing problem reformulation . . . . . . . . . . . . . . . . . 29
3 Proposed solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1 Objective function . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 PSO-based path planners . . . . . . . . . . . . . . . . . . . . . . . 29
4 Numerical tests and discussion . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Test1 : A simple illustrative example . . . . . . . . . . . . . . . . . 31
......Côte titre : MAI/0861 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0861 MAI/0861 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
PermalinkPermalink
Permalink
