| Titre : | Résolution de problémes d'optimisation par les systémes multi-agentsn et les approches évolutionnaires |
| Auteurs : | Aziza Béchir, Auteur ; kamal Eddine Melkemi, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2016 |
| ISBN/ISSN/EAN : | TINF/92 |
| Format : | 1 vol. (111 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
La plupart des problèmes d’optimisation combinatoire sont des problèmes très difficiles à résoudre et que l’on trouve dans plusieurs domaines à savoir la fabrication,l’énergie, les télécommunications, la médecine, la robotique etc .... Malgré l’existence d’un nombre important de méthodes de résolution de ce type de problèmes, elles restent limitées et insuffisantes dans la plupart de problèmes, spécialement pour la résolution des problèmes d’optimisations dans les systèmes critiques.Pour cela, nous essayons de proposer des solutions adéquates pour résoudre ces problèmes. Nous utilisons des approches hybrides distribués efficaces.Dans ce mémoire, nous traitons le problème de l’optimisation combinatoire en faisant une hybridation entre les approches inspirées de la nature et les systèmes multiagents.Nous appliquons cette approche pour la résolution d’un problème l’ordonnancement de tâches.Dans un premier temps, nous proposerons une hybridation entre les algorithmes génétique et l’informatique quantique et par la suite nous intégrons cette hybridation dans un système multi-agent. |
| Sommaire : |
Introduction générale : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 CHAPITRE 1 : L’OPTIMISATION COMBINATOIRE : : : : : : : : : : 4 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Définition formelle de l’optimisation . . . . . . . . . . . . . . 5 1.2.2 Complexité et NP-difficulté . . . . . . . . . . . . . . . . . . . 6 1.2.3 Les modèles d’optimisation classique . . . . . . . . . . . . . . 8 1.3 Classification des méthodes d’optimisation . . . . . . . . . . . . . . . . 10 1.4 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Algorithmes approchés . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.1 Les Meta-heuristiques . . . . . . . . . . . . . . . . . . . . . . 12 1.5.2 Méthodes basées population . . . . . . . . . . . . . . . . . . . 12 1.5.3 Les approches inspirées de la nature . . . . . . . . . . . . . . . 13 CHAPITRE 2 : SYSTÈMES MULTI-AGENTS : : : : : : : : : : : : : : : 20 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Agent et ses caractéristiques . . . . . . . . . . . . . . . . . . . 21 2.2.2 Classes d’Agents . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Système multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.1 Domaines d’application . . . . . . . . . . . . . . . . . . . . . 24 2.3.2 Intérêts des MAS . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.3 Interaction entre agents . . . . . . . . . . . . . . . . . . . . . . 25 2.3.4 La communication dans un MAS . . . . . . . . . . . . . . . . 25 2.4 L’avantage de la plate-forme multi-agents Jade . . . . . . . . . . . . . 28 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 CHAPITRE 3 : SYSTÈMES EMBARQUÉS DISTRIBUÉS TEMPS RÉEL 30 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.1 Système embarqué . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.2 Système temps réel . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.3 Système distribué . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.4 Systèmes embarqués temps réel . . . . . . . . . . . . . . . . . 32 3.2.5 Systèmes embarqués distribués . . . . . . . . . . . . . . . . . . 32 3.3 Systèmes embarqués distribués temps réels . . . . . . . . . . . . . . . 32 3.3.1 Définition des systèmes embarqués distribués temps réels . . . . 32 3.3.2 Le deadline dans les systèmes embarqués temps réel . . . . . . 33 3.3.3 Systèmes temps réel durs et souple . . . . . . . . . . . . . . . . 33 3.4 Ordonnancement temps réel . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.1 Définition d’ordonnancement temps réel embarqué . . . . . . . 33 3.4.2 Un modèle de système . . . . . . . . . . . . . . . . . . . . . . 34 3.4.3 Ordonnancement temps réel mono-processeur . . . . . . . . . . 34 3.4.4 Modèle de tâches temps réel . . . . . . . . . . . . . . . . . . . 35 3.4.5 Ordonnancement temps réel multiprocesseur . . . . . . . . . . 46 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 CHAPITRE 4 : LES ALGORITHMES GÉNÉTIQUES QUANTIQUES ET PROBLÈMES D’ORDONNANCEMENT CLASSIQUES ET TEMPS RÉEL : : : : : : : : : : : : : : : : : : : : : : : : 49 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2 Algorithme génétique classique . . . . . . . . . . . . . . . . . . . . . . 50 4.2.1 Le principe de base des GAs . . . . . . . . . . . . . . . . . . . 51 4.2.2 Avantages et inconvénients . . . . . . . . . . . . . . . . . . . . 59 4.2.3 Un état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Algorithmes Génétiques Quantiques . . . . . . . . . . . . . . . . . . . 63 4.3.1 Introduction à L’informatique Quantique . . . . . . . . . . . . 63 4.3.2 Algorithmes génétiques quantiques . . . . . . . . . . . . . . . 67 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 CHAPITRE 5 : L’APPROCHE PROPOSÉE MAS-QGA POUR L’ORDONNANCEMENT DE TÂCHES DANS LES SYSTÈMES EMBARQUÉS TEMPS RÉEL : : : : : : : : : : : : : : : : : 73 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 I La partie conception 76 5.2 La méthode GA classique pour l’ordonnancement dans un système embarqué distribué temps réel . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2.1 Codage des chromosomes . . . . . . . . . . . . . . . . . . . . 77 5.2.2 Initialisation de la population . . . . . . . . . . . . . . . . . . 78 5.2.3 Réparation du chromosome . . . . . . . . . . . . . . . . . . . 79 5.2.4 Évaluation des individus . . . . . . . . . . . . . . . . . . . . . 79 5.2.5 Sélection dans les GAs . . . . . . . . . . . . . . . . . . . . . . 81 5.2.6 Le croisement (Crossover) . . . . . . . . . . . . . . . . . . . . 81 5.2.7 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.8 Remplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2.9 Critère d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.3 Un QGA pour l’ordonnancement dans un système embarqué distribué temps réel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3.1 Codage des chromosomes . . . . . . . . . . . . . . . . . . . . 86 5.3.2 Génération de la population initiale . . . . . . . . . . . . . . . 86 5.3.3 Évaluation des individus . . . . . . . . . . . . . . . . . . . . . 86 5.4 Un MAS-QGA pour l’ordonnancement dans un système embarqué distribué temps réel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.4.1 Politique d’intégration . . . . . . . . . . . . . . . . . . . . . . 88 5.4.2 Politique de migration . . . . . . . . . . . . . . . . . . . . . . 88 5.4.3 Critère d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 II La partie expérimentale 93 5.5 Matériels et Logiciels utilisés . . . . . . . . . . . . . . . . . . . . . . . 94 5.6 Tests et comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.6.1 La méthode GA classique . . . . . . . . . . . . . . . . . . . . 94 5.6.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.6.3 Expérimentation sur la méthode QGA . . . . . . . . . . . . . . 98 5.6.4 Expérimentation sur l’approche MAS-QGA . . . . . . . . . . . 98 5.6.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Conclusion et perspectives : : : : : : : : : : : : : : : : : : : : : : : : : : : : 104 BIBLIOGRAPHIE : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 105 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/2592 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/92 | Mémoire de magister | bibliothèque sciences exactes | Consultable |
