Un objectif de cette thèse est de fournir des outils d'analyse, de conception et d'implantation des approches métaheuristiques pour l'optimisation combinatoire en les formulant dans le cadre des systèmes multi-agents. L'accent est mis sur la potentialité de mise en œuvre distribuée des approches et sur l'utilisation de techniques d'apprentissage permettant d'adapter dynamiquement des méthodes de recherche.<br /><br />Dans le cadre de cette thèse nous proposons tout d'abord, un framework organisationnel et multi-agent pour la modélisation et l'implantation de métaheuristiques. Ce framework nommé AMF (Agent Metaheuristic Framework), introduit un modèle organisationnel de métaheuristiques qui décrit le système sous la forme d'une organisation composée de rôles en interaction. Le premier objectif de ce modèle est de donner un cadre d'analyse et de comparaison des différentes métaheuristiques existantes. Ensuite, il doit faciliter la conception de nouveaux algorithmes en encourageant une approche multi-agent. L'intérêt de l'approche organisationnelle, actuellement utilisée dans les systèmes multi-agents, est de pouvoir décrire un système aussi bien comme un tout, le système multi-agent, que comme un assemblage de composants, les agents. De plus, cette approche permet de distinguer l'analyse des fonctions du système, de l'analyse de son architecture. Enfin, l'approche organisationnelle encourage la modularité et la réutilisation des modèles. Nous proposons en complément de ce modèle un guide méthodologique. Il définit un ensemble d'étapes permettant de passer du modèle organisationnel à une méthode d'optimisation exprimée en termes d'agent.<br /><br />Ensuite, nous présentons une métaheuristique fondée sur la métaphore de la coalition, CBM (Coalition Based Metaheuristic), mettant en avant l'intérêt d'utiliser les systèmes multi-agents pour la conception de métaheuristiques. Dans cette métaheuristique, la recherche de solution est effectuée par un ensemble d'agents regroupés dans une coalition. Chaque agent est capable d'effectuer indépendamment des autres une recherche dans l'espace des solutions à l'aide d'opérateurs de déplacement dans un voisinage de la solution courante et d'adapter sa stratégie par apprentissage par renforcement. Des mécanismes de coopération entre agents permettent d'améliorer l'efficacité de la recherche. La structure de coalition permet d'intégrer naturellement au système de résolution des aspects de distribution et de décentralisation du contrôle, de même que des procédés d'apprentissage individuels et collectifs. L'efficacité de notre approche est évaluée expérimentalement en traitant deux problèmes d'optimisation combinatoire : un problème de tournées de véhicules et un problème de positionnement.

Une voie permettant l'accélération l'apprentissage par renforcement est l'exploration à l'aide des connaissances du domaine. La plus part des algorithmes existants, intitulées transfert de connaissance, sont basés sur une hypothèse implicite : la bonne qualité de la connaissance disponible sur la tache courante. Lorsque cette hypothèse n'est pas respectée, les performances se dégradent bien en dessous des celles des méthodes standards. Ce travail de thèse propose des algorithmes de transfert capables de s'adapter à la qualité de la connaissance disponible. Pour le faire, nous introduisons un paramètre nommé le taux de transfert, qui contrôle à quel point l'algorithme se fiera à la connaissance disponible. De plus, nous optimisons ce taux afin de faire meilleur usage de cette politique, en ajoutant de la robustesse à nos algorithmes. Ces algorithmes sont évalués sur un problème jouet (le gridworld), et sur une application d'aide à l'entraineur qui simule une situation de jeu donnée.