| Titre : | un algorithme génétique pour l'optimisation multi objectif. |
| Auteurs : | Radjia Rezgui, Auteur ; WISSEM TORCHI, Auteur ; Keltoum Touil, Directeur de thèse |
| Type de document : | Mémoire magistere |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2015 |
| ISBN/ISSN/EAN : | MINF/98 |
| Format : | 36 / ill., couv. ill. en coul |
| Langues: | Français |
| Langues originales: | Français |
| Résumé : |
Dans notre quotidien on a confronté des problèmes qu’ont plusieurs solutions, souvent on ne peut pas choisir une solution déterministe parmi l’ensemble de solutions par ce que le problème a des plusieurs objectifs contradictoires et si on a satisfait un objectifs, il est possible que l’autres objectifs ne sont pas satisfaites.
Pour résoudre des problèmes complexes de ce genre, les méthodes de l’optimisation multi objectif sont apparues, parmi lesquelles on a les algorithmes évolutionnaires. Car il est difficile de décider le choix d’une solution satisfaite tous les objectifs, il y’a des méthodes évolutionnaires basée sur l’obtention d’une ensemble des meilleurs solutions (ensemble de Pareto) parmi tous les solutions disponibles. L’objectif de ce mémoire est de définir un algorithme génétique pour la résolution d’un problème d’optimisation multi-objectif. Dans notre travail, nous avons proposé une application de l’algorithme génétique pour résoudre le problème TSP. Plan du mémoire : Notre mémoire de fin d’études se compose de quatre chapitres organisés comme suit : Dans le premier chapitre on a présenté les problèmes d’optimisation multi objectifs définis comme des problèmes recherchant un ensemble de solutions qui s’appelle l’ensemble de solution Pareto, les différents algorithmes évolutionnaires a été décrit. Dans le deuxième chapitre on a présenté le principe d’un algorithme génétique, et la présentation de la notion de la complexité des algorithmes et la classification de problèmes ainsi que la définition du problème TSP Dans le troisième chapitre décrit la conception de notre système qui basée sur l’algorithme génétique SPEA1, et la présentation de problème voyageur de commerce, ainsi que les applications de l’algorithme. Dans le quatrième chapitres sera dédié au vif du sujet, à savoir l’étude de cas, l’implémentation du notre système ou nous présentons les résultats obtenus. Nous présentons les différentes étapes d'algorithme, l’architecture d’application, et quelques tests ont été effectués, ainsi une étude comparative avec les algorithmes génétique. Nous terminerons par une conclusion générale sur le travail effectué. |
| Sommaire : |
1. Introduction 2
2. Historique..……………………………………………………………………………….2 3. Définitions 2 3.1 Problème 2 3.2 Types des problèmes 3 3.3 Un problème combinatoire 3 3.4 Un problème d’optimisation 3 3.4.1 Résolution d’un problème d’optimisation 3 4. Problème d’optimisation multi objectifs 4 4.1 Formalisme mathématique 4 4.2 La convexité 4 4.3 La classification des problèmes multi objectifs 4 5. La dominance 5 5.1 La dominance au sens Pareto 5 6. Approches de résolution 6 6.1 Les méthodes de résolution exactes 6 6.2 Méthodes approchées 6 6.2.1 Heuristique 6 6.2.2 Méta heuristique 6 7. Conclusion ………...………………...………………………………………………….8 Chapitre 2 : Les algorithmes génétiques Introduction................9 Historique……...………………………………………………………………………9 Définition……..……………………………………………………………………….9 3.1. Définition…..………………………………………………………………….9 3.2 Principe de base d’un AG standard…………………………………………....9 3.3. Vocabulaire……………………………………………………………….......11 Mécanisme de fonctionnement d’un algorithme génétique………………………….11 4.2. Operateurs génétique………………………………………………………....12 Algorithme génétique pour l’optimisation multi objectif………………………….....13 Les méthodes de résolution …………………………………………………..……....13 6.1. Les principaux métas heuristiques pour l’optimisation multi objectif …………13 Exemples de problèmes combinatoires ……………………..………………………..17 7.1. Problème le voyageur de commerce « TSP / PVC »……………………………17 conclusion …………………………………………………………………..………...20 Chapitre 3 : Conception 1. Introduction…………………………………………………………………………...21 2. Conception générale ………………………………………………………………….21 2.1. L’objectif du système ………………………………………………………..21 2.2. Conception du système ………………………………………………………21 2.3. Conception générale …………………………………………………………21 3. Conception détaillée ………………………………………………………………….22 3.1. Les données utilisées ………………………………………………………...22 3.2. Explication théorique d’AG………………….……………………………….23 4. Conclusion……….……………………………………………………………………..28 Chapitre 4 : Implémentation 1. Introduction …………………………………………………………………………...29 2. Environnement et outils de développement…………………………………………..29 3. Structure de données ………………………………………………………………….29 4. Algorithmes utilisés …………………………………………………………………..30 4.1. Class population ………………………………………………………………30 4.2. Les méthodes ………………………………………………………………….31 5. Présentation de l’application ………………………………………………………….32 6. Conclusion …………………………………………………………………………….35 Conclusion Générale Bibliographie |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/98 | Mémoire | bibliothèque sciences exactes | Consultable |
