Résolution du problème d'allocation optimale de ressources multiples à l'aide d'un algorithme génétique

Authors: Ben Jabeur, Marouene
Advisor: Lamontagne, Luc D.
Abstract: Les opérations de recherche et de sauvetage font partie des activités humanitaires que le gouvernement canadien offre. Ces opérations doivent être mises à la disposition de tous les vols aériens dans un espace de plus de vingt millions de kilomètres carrés et de tous les bateaux naviguant dans les eaux maritimes du gouvernement fédéral dont les océans, le fleuve Saint-Laurent et les Grands Lacs. L'ultime objectif que se fixe le gouvernement canadien en mettant à l'oeuvre ce genre d'opérations consiste à "prévenir les pertes de vie et les blessures en utilisant les ressources privées et publiques pour alerter, répondre et aider dans les situations de détresse". Leur travail, humanitaire, consiste à trouver un objet perdu dans les meilleurs délais afin de ne pas risquer de perdre des vies. Ce but pourrait être atteint si l'on arrive à trouver un moyen d'affecter d'une manière optimale les ressources dont on dispose à des secteurs sur lesquels les opérations de recherche vont être effectuées. L'objectif de nos travaux est d'examiner de plus près et d'essayer de résoudre le problème d'allocation de ressources multiples que vivent les centres de coordination des opérations de recherche et de sauvetage. Ce problème se résume à mettre en place un plan d'affectation des ressources à des zones de recherche permettant de maximiser l'efficience de leurs utilisations et d'augmenter les chances de trouver des survivants en peu de temps. Pour ce faire, nous définissons un algorithme génétique capable de trouver une solution au problème à résoudre. Ensuite, nous adapterons la solution proposée afin de prendre en charge et manipuler les contraintes imposées par le problème. Lors de nos expérimentations, nous avons cherché à améliorer la performance et l'efficacité de notre algorithme en y introduisant plusieurs méthodes basées sur le principe de la satisfaction des contraintes. Notre bilan nous indique que nos meilleurs résultats sont obtenus en mettant en place un algorithme génétique dont le fonctionnement des opérateurs de reproduction ne tolère aucune violation de contraintes. En les comparant à ceux obtenus en résolvant le problème par l'approche d'optimisation combinatoire, nous avons constaté qu'on n'a pas pu égaler le niveau de succès atteint. Ceci est dû à l'aspect aléatoire sur lequel les algorithmes génétiques se basent pour parcourir l'espace de recherche, sélectionner et améliorer une solution.
Document Type: Mémoire de maîtrise
Issue Date: 2010
Open Access Date: 16 April 2018
Permalink: http://hdl.handle.net/20.500.11794/21396
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
27261.pdf28.7 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.