Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

L’industrie d’aujourd’hui est constamment en quête de nouvelles méthodes pour améliorer ses processus et ses activités. Elle a recours à la recherche opérationnelle pour répondre à ses besoins. Les problèmes auxquels elle fait face peuvent être définis par l’utilisation de variables de décision entières (problèmes de nature discrète) ou de variables de décision réelles (problèmes de nature continue ou mixte). Les métaheuristiques permettent d’approcher ces problèmes lorsqu’ils sont NP-difficiles. Cette catégorie de méthodes offre un moyen de trouver une solution acceptable dans un délai raisonnable. L’objectif général de cette thèse consiste à améliorer les stratégies métaheuristiques pour la résolution de problèmes de grande taille. Parmi les métaheuristiques bien connues, la famille des algorithmes d’optimisation par essaims particulaires (PSO) offre d’excellentes performances pour la résolution de problèmes de nature continue. Le PSO a beaucoup évolué depuis sa conception. Deux stratégies sont utilisées afin d’améliorer ses performances : l’hybridation et la discrétisation. L’hybridation permet d’améliorer les performances en combinant les forces des méthodes d’optimisation utilisées. La discrétisation permet d’étendre l’applicabilité d’une méthode d’optimisation à une plus grande variété de problèmes. Il est bien connu que plus la dimension d’un problème augmente, plus il s’avère difficile de résoudre ce problème efficacement. Malgré les forces du PSO, cette métaheuristique éprouve de la difficulté à résoudre les problèmes de grande taille. Cette thèse propose tout d’abord la conception de trois algorithmes hybrides construits selon trois variantes de PSO : le Barebones PSO, le Comprehensive Learning PSO et le Cooperative Learning PSO. L’utilisation de fonctions continues bien connues (Rosenbrock, Ackley, etc.) et de fonctions provenant du CEC’15 benchmark set permettent de statuer sur les modèles hybrides les plus prometteurs permettant de pallier les lacunes du PSO à résoudre des instances de grande taille. Suivant cette idée, nous proposons par la suite différents processus de discrétisation pour la résolution de problèmes de support à complexité variable : les problèmes d’ordonnancement séquentiel et d’ordonnancement de projets avec contraintes de ressources. Les conclusions obtenues sur la performance des processus de discrétisation permettent d’amener le PSO à résoudre plus efficacement des problèmes complexes de nature entière. Les contributions précédentes sont réutilisées afin de valider l’extensibilité du PSO. Le problème d’alignement multiple de séquences (MSA) est un problème combinatoire bien connu offrant un grand niveau de complexité et des instances de très grande taille. Il est utilisé pour éprouver les améliorations apportées au PSO. Une version hybride et discrète du PSO est finalement proposée afin de résoudre le MSA. Pour ce faire, une codification de solutions sous forme d’anneau et spécialisée en fonction du MSA est définie. Une amélioration est ensuite proposée définissant un nouveau comportement pour le PSO permettant de reproduire le phénomène de magnétisme dans le but d’aider l’algorithme à générer de bonnes solutions. Les algorithmes proposés dans le cadre de cette thèse démontrent plusieurs stratégies permettant d’améliorer le PSO pour la résolution de grandes instances de problèmes. Ces stratégies peuvent être appliquées à davantage de métaheuristiques continues à base de population et permettent de contribuer à leur flexibilité. Elles peuvent également être appliquées pour résoudre une plus grande variété de problèmes discrets à complexité variable.