Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'UNIVERSITÉ DU QUÉBEC À CHICOUTIMI COM

UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'UNIVERSITÉ DU QUÉBEC À CHICOUTIMI COMME EXIGENCE PARTIELLE DE LA MAÎTRISE EN INFORMATIQUE par Arnaud Zinflou Système interactif d'aide à la décision basé sur des algorithmes génétiques pour l'optimisation multi-objectifs 29 juin 2004 bibliothèque Paul-Emile-Bouletj UIUQAC Mise en garde/Advice Afin de rendre accessible au plus grand nombre le résultat des travaux de recherche menés par ses étudiants gradués et dans l'esprit des règles qui régissent le dépôt et la diffusion des mémoires et thèses produits dans cette Institution, l'Université du Québec à Chicoutimi (UQAC) est fière de rendre accessible une version complète et gratuite de cette œuvre. Motivated by a desire to make the results of its graduate students' research accessible to all, and in accordance with the rules governing the acceptation and diffusion of dissertations and theses in this Institution, the Université du Québec à Chicoutimi (UQAC) is proud to make a complete version of this work available at no cost to the reader. L'auteur conserve néanmoins la propriété du droit d'auteur qui protège ce mémoire ou cette thèse. Ni le mémoire ou la thèse ni des extraits substantiels de ceux-ci ne peuvent être imprimés ou autrement reproduits sans son autorisation. The author retains ownership of the copyright of this dissertation or thesis. Neither the dissertation or thesis, nor substantial extracts from it, may be printed or otherwise reproduced without the author's permission. 11 RESUME Dans de nombreux secteurs de l'industrie, les décideurs sont confrontés à des problèmes complexes, de grande dimension et multi-objectifs. Prendre une décision, pour ce genre de problèmes, nécessite en général l'optimisation simultanée de plusieurs objectifs souvent contradictoires. Malheureusement, la complexité des problèmes industriels, le nombre sans cesse croissant d'objectifs à optimiser simultanément et la rapidité des changements de l'environnement raccourcissent considérablement les délais de prise de décision tout en rendant cette tâche plus difficile pour les gestionnaires. Des outils informatiques comme les systèmes interactifs d'aide à la décision (SIAD) s'avèrent donc d'une grande utilité pour le décideur car ils favorisent une répartition évolutive des compétences entre l'utilisateur et la machine et offrent une bonne intégration de l'homme et de la machine dans le processus de décision. Les SIAD permettent donc au décideur d'évaluer la situation, les diverses alternatives et leurs impacts éventuels. Récemment, les techniques d'optimisation multi-objectifs à l'aide d'algorithmes évolutionnaires, et plus particulièrement d'algorithmes génétiques, suscitent de plus en plus d'intérêt auprès des chercheurs notamment à cause de leur faculté à exploiter de vastes espaces de recherche et à générer des compromis multiples en une seule étape d'optimisation. Les algorithmes génétiques tentent de simuler le processus de sélection naturelle dans un environnement hostile lié au problème à résoudre en s'inspirant des théories de l'évolution proposées par Darwin et des méthodes de combinaison de gènes introduites par Mendel. Ce mémoire propose d'intégrer les systèmes interactifs d'aide à la décision, l'optimisation multi-objectifs et les algorithmes génétiques afin de proposer un outil performant permettant la résolution de problèmes d'optimisation multi-objectifs. Dans le SIAD proposé, le traitement d'un problème multi-objectifs se fera en deux phases. La première phase consiste à approximer l'ensemble Pareto optimal. Cette étape sera réalisée à l'aide d'un nouvel algorithme génétique multi-objectifs hybride. Cette approche combine un algorithme génétique basé sur les concepts d'élitisme, de niche et de dominance Pareto avec des opérateurs de recherche locale. La deuxième phase utilise l'expérience du décideur afin d'approfondir la recherche dans une zone plus spécifique de l'ensemble pseudo Pareto Optimal en fonction des préférences exprimées par celui-ci. Pour cela, une approche générique de recherche de solutions de compromis est combinée avec un algorithme génétique. Le SIAD proposé est un outil flexible et facile d'utilisation grâce à son interface homme-machine conviviale. Cet outil ne constitue qu'un support à la prise de décision, la décision finale restant du ressort du planificateur. Un exemple d'application du SIAD proposé a été réalisé pour aborder un problème d'ordonnancement industriel rencontré dans une entreprise de production d'aluminium. Cette application montre bien l'intérêt pratique de ce genre de système. Ill Bien qu'ayant produit des résultats très encourageants, ce travail de recherche représente surtout une première exploration des possibilités offertes par la combinaison de trois domaines de recherche en constante évolution : les SIAD, l'optimisation multi-objectifs et les algorithmes génétiques. L'union de ces trois champs de recherche laisse entrevoir des possibilités intéressantes pouvant mener à la conception de nouveaux outils de résolution permettant l'élaboration de scénarios pour éclairer la prise de décision. Ce travail peut donc être considéré comme une contribution vers l'élaboration et l'implantation de ce genre d'outils. IV REMERCIEMENTS Je tiens tout d'abord à remercier Mme Caroline Gagné, ma directrice de recherche pour sa disponibilité, son support et son implication dans ce travail de recherche. En particulier pour avoir été attentive à tous mes commentaires ou idées et pour avoir su répondre à mes nombreuses interrogations. Son optimisme et ses conseils ont été une aide précieuse sans laquelle ce travail de recherche n'aurait sans doute pas vu le jour. Mes remerciements vont aussi à tous les membres du Groupe de Recherche en Informatique de l'UQAC (GRI) pour la bonne ambiance qu'ils ont su mettre dans les locaux du GRI. En particulier, je remercie Daniel Bouchard avec qui j'ai partagé un bureau pendant une grande partie de ma maîtrise et qui, comme moi, est un grand amateur de jeux vidéo. Je remercie aussi M. Marc Gravel, M. Wilson Price et M. Bernard Lefebvre pour avoir accepté d'évaluer ce travail ainsi que pour leurs judicieux commentaires. Un travail de recherche ne pourrait être réalisé sans support financier. À ce titre, je voudrais remercier les fonds institutionnels de l'UQAC ainsi que les organismes subventionnaires CRSNG et FQRNT pour leur appui. Je tiens aussi à remercier Mlle Chitra Sewsagur pour sa patience, sa compréhension et son soutien. Je la remercie également pour avoir contribué à améliorer la qualité du français de ce document. J'aimerais aussi remercier sincèrement mes parents, mes deux frères, ma sœur et toute ma famille pour leur soutien et leur confiance. Je tiens, en particulier, à remercier mes parents qui m'ont toujours poussé à aller de l'avant et qui ont toujours cru en moi même quand moi-même je n'y croyais plus. Sans leur soutien et leur amour, ce travail n'aurait jamais pu être réalisé. Je me dois aussi de dire un merci particulier à ma petite sœur Corinne qui a, elle aussi, pris la peine de lire ce mémoire afin de m'aider à corriger les nombreuses fautes d'orthographe qui s'y étaient glissées. En terminant, j'ai une pensée spéciale pour ma tante Mme Marguerite Gbdamassi et ma grand-mère Mme Elisabeth Zinflou qui nous ont quitté toutes les deux pendant que je poursuivais mon séjour au Canada. Ce travail vous est dédié. Que la terre vous soit légère. VI TABLE DES MATIERES RÉSUMÉ. u REMERCIEMENTS. iv TABLE DES MA TIÈRES vi LISTE DES TABLEAUX ix LISTE DES FIGURES. x CHAPITRE 1 : INTRODUCTION 1 CHAPITRE 2 : LES SYSTÈMES INTERACTIFS D'AIDE À LA DÉCISION. 7 2.1 Introduction 8 2.2 La prise de décision 10 2.2.1 Le processus de décision 11 2.2.2 Niveau de structuration des problèmes de décisions 13 2.3LesSIAD 15 2.4 Barrières au succès des SIAD 21 2.5 Exemples de domaine d'application des SIAD 24 2.5.1 Un système d'allocation de wagon 24 2.5.2 La gestion de la production 25 2.5.3 Un système de surveillance pour les sites industriels à hauts risques 26 2.5.4 Pioneer Natural Resources 27 2.6 Conclusion 27 CHAPITRE 3 : ALGORITHMES GÉNÉTIQUES ET OPTIMISATIONMULTI- OBJECTIFS. 29 3.1 Introduction 30 3.2 Optimisation multi-objectifs 31 3.2.1 Problème multi-objectifs 31 3.2.2 Notion de dominance 32 3.2.3 Optimum Pareto 33 Vil 3.2.4 Classification 34 3.3 Les algorithmes génétiques 40 3.3.1 Représentation des individus 41 3.3.2 La sélection 42 3.3.3 Le croisement 44 3.3.4 La mutation 48 3.3.5 Les grandes lignes de l'algorithme 49 3.3.6 Le nichage 50 3.3.6 AG et optimisation multi-objectifs 52 3.4 Les approches basées sur la transformation du problème en un problème uni- objectif. 52 3.5 Les approches non Pareto 53 3.6 Les approches Pareto 54 3.6.2 Les techniques non élitistes 55 3.6.2.1 Multiple Objective Genetic Algorithm (MOGA) 55 3.6.2.2 Niched Pareto Genetic Algorithm (NPGA) 56 3.6.2.3 Non dominated Sorting Genetic Algorithm (NSGA) 56 3.6.3 Les techniques élitistes 58 3.6.3.1 NSGAII 58 3.6.3.2 Strength Pareto Evolutionary Algorithm (SPEA) 61 3.6.3.3 SPEA 2 63 3.7 Objectifs de la recherche 65 3.8 Conclusion 66 CHAPITRE 4 : BASE DE MODÈLE DUSIAD : AG MULTI-OBJECTIFS POUR UN CONTEXTE D'ORDONNANCEMENT INDUSTRIEL 68 4.1 Introduction 69 4.2 Exemple d'application : un problème d'ordonnancement industriel 71 4.3 Traitement uni-objectif à l'aide d'un algorithme génétique (AGU) 74 4.3.1 Description de l'algorithme 74 4.3.2 Essais numériques et résultats obtenus 78 4.4 Traitement multi-objectifs à l'aide d'algorithmes génétiques 83 4.4.1 Adaptation du NSGAII pour fins de comparaisons 84 4.4.1.1 Description de l'algorithme 85 4.4.1.2 Essais numériques et résultats obtenus 86 4.4.2 Phase 1 : proposition d'un nouvel AG (AGMOP/) 94 4.4.2.1 Description de l'algorithme 94 4.4.2.2 Essais numériques et résultats obtenus 98 4.4.3 Phase 2 : application de la procédure de recherche de compromis (AGCP) 107 uploads/Management/ universite-du-quebec-par-arnaud-zinflou.pdf