Stratégies d'échange d'informations dans un système de calcul distribué pour l'optimisation des problèmes combinatoires

This thesis describes my PHD work carried out within the computer science and operations research group of the CREAM3 laboratory, in collaboration with the LISA 4 laboratory, and the support of Angers's General Council. The reported work belongs at the same time to the multi-agent system (MAS), parallelism and metaheuristics domains, and more precisely to develop an intelligent distributed computing system and to compare different information exchange strategies in a distributed memory architecture for parallel computing (Networked PCs). This thesis combines different notions of parallelism, multi-agent paradigm and metaheuristics to provide a high performance method to solve real combinatorial problems. It proves that including information exchange and parallelisation strategies to a population-based algorithm can improve it ability. Instead of using expensive parallel computing facilities, in this work we propose to implement parallel computation model on easily available networked PCs, and present a multi-agent framework to support parallelism. In this model, agents can easily be programmed to initiate the execution of actions autonomously, and they can dynamically move from machine to machine to discover services and communicate with other agents. To evaluate the proposed approach, different kinds of experiments have been conducted to assess the developed system mainly on a vehicule routing problem and an industrial scheduling problem. Results obtained show the efficiency of our approach.Ce manuscrit décrit les travaux de recherche effectués au cours de ma thèse, au sein de l'équipe informatique et recherche opérationnelle du laboratoire CREAM1, en collaboration avec le laboratoire LISA 2, et avec le soutien du Conseil Général de la ville d'Angers. Ces travaux de recherche se situent à l'intersection des domaines de l'optimisation combinatoire et des systèmes multi-agents. Ils s'inscrivent dans la continuité des propositions de modèles ou de plates-formes pour les métaheuristiques parallèles. Ce rapport réunit différentes notions du parallélisme, du paradigme multi-agents et des métaheuristiques afin d'apporter des méthodes de résolution performantes (robustes et autoadaptatives) à des problèmes d'optimisation combinatoire réels. Il démontre que l'introduction de stratégies de parallélisation et d'échange d'informations à un algorithme à population permet à ce dernier d'améliorer considérablement ses facultés de recherche de solutions. En outre, l'utilisation des agents mobiles permet une exploitation optimale des ressources de calcul inutilisées dans un organisme (laboratoire, entreprise) et de favoriser ainsi l'autonomie des processus de calcul pour pouvoir gérer les éventuelles pannes dans un réseau. Le succès de cette approche dans la résolution d'un problème de tournées de véhicules et d'un problème d'ordonnancement de production, montre l'intérêt pratique de ces méthodes et leurs retombées économiques potentielles. Ce travail de recherche représente l'une des premières explorations des possibilités offertes par deux domaines fort prometteurs de l'intelligence artificielle distribuée et de la recherche opérationnelle. L'union de méthodes auto-adaptatives et d'une puissance de calcul imposante pourrait fort bien se révéler un outil performant pour la résolution de problèmes d'une telle envergure