Hybridation Et Auto-configuration Des Metaheuristiques Pour La Résolution Du Problème D'affectation Quadratique À Trois Dimensions

Résumé: Les métaheuristiques sont des méthodes d'optimisation compétitives qui ont été utilisées pour résoudre une pléthore de problèmes d'optimisation et en particulier pour résoudre le problème de l'affectation. Ils sont traditionnellement conçus selon un processus manuel et de développement d'algorithmes itératifs. Bien que ce processus conduise parfois à des algorithmes très performants, il demande beaucoup de travail, est susceptible d'erreurs, difficile à reproduire et n'explore qu'un nombre limité d'alternatives de conception. Une nouvelle façon de traiter les algorithmes est la configuration automatique des algorithmes, une technique qui a montré son efficacité pour trouver des réglages optimisant les performances des paramètres de nombreuses décisions basées sur la recherche et des algorithmes d'optimisation. Cette thèse rapporte l'approche des algorithmes inspirés de la nature qui est la méthode d'optimisation des essaims particulaires (PSO) hybridé avec une recherche locale itérative comprenant un algorithme de recherche tabou (ILS(TS)) pour résoudre le problème d'affectation tridimensionnelle quadratique (Q3AP).Le Q3AP est un problème d'optimisation combinatoire qui s'est avéré difficile à résoudre (NP-hard). Il s'agit d'une extension du problème d'affectation quadratique (QAP). Nous avons testé l'algorithme hybride proposé sur de nombreuses instances dont certaines n'ont pas été explorées dans les travaux précédents pour résoudre Q3AP. Les résultats montrent que l'algorithme hybride PSO-ILS(TS) proposé est prometteur pour trouver une solution (quasi-)optimale. Ensuite, une configuration automatique a été appliquée à PSO-ILS(TS) et à quelques-unes de ses variances en utilisant l'outil irace pour trouver les meilleurs réglages de paramètres qui améliorent la performance des algorithmes.

Publié dans la revue: