University Sétif 1 FERHAT ABBAS Faculty of Sciences
Résultat de la recherche
1 résultat(s) recherche sur le mot-clé 'Sélection de service web Qualité de service (QoS) Optimisation combinatoire Méta-heuristiques Incertitude QoS Intervallenombre'
Ajouter le résultat dans votre panier Affiner la recherche Générer le flux rss de la recherche
Partager le résultat de cette recherche
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 articial 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 articial bee colony algorithm . . . . . . . . . . . 72
4.3.1 Interval multi-objective optimization problem . . . . . . . . . . . . 72
4.3.2 The articial 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 articial 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 denition . 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 articial 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 articial 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 articial bee colony algorithm . . . . . . . . . . . 72
4.3.1 Interval multi-objective optimization problem . . . . . . . . . . . . 72
4.3.2 The articial 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 articial 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 denition . 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 articial 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