Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement. Les heuristiques manquent d’une vue d’ensemble sur l’évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l’agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l’aide de l’apprentissage, l’agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s’échanger des informations, comme ils peuvent déclencher l’agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l’affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l’état de l’art. / We elaborate a multi-agent based optimization method for combinatorial optimization problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOMCOP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOMCOP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature

Le fonctionnement d'un SRI est constitué de plusieurs étapes : l'étape de présentation des besoins par l'utilisateur, celle du traitement de la requête de l'utilisateur par le système, celle de l'évaluation des solutions du système par l'utilisateur et celle de la modification ou mise à jour de la requête par le système ou par l'utilisateur. Dans chacune de ces étapes, la prise en compte des particularités de chaque utilisateur est nécessaire pour rendre le système plus efficace, en particulier par rapport à la pertinence des réponses du système. On exige de l'utilisateur de bien définir ses besoins et d'être capable de les traduire dans le langage du système. Le jugement de pertinence d'une réponse par l'utilisateur dépend des paramètres qui lui sont propres.<br /><br />En ce qui concerne l'utilisateur, nous travaillons sur trois types de connaissance pour le représenter : ses habitudes évocatives, son niveau de connaissance basé sur la notion de catégorie fondamentale, et ses jugements de pertinence sur les solutions du système en réponse à ses requêtes. Par l'observation du fonctionnement d'un centre de documentation et par l'efficacité des résultats obtenus par le dialogue entre l'utilisateur et un médiateur du centre, nous avons orienté nos travaux vers le développement d'un système de recherche coopérative d'information (SRCI). Dans un SRCI, l'utilisateur pourra effectuer sa recherche en collaboration avec un médiateur sur des postes de travail distants.<br /><br />Les perspectives à court terme sont de représenter chaque utilisateur par l'historique de ses activités. Ces activités sont représentées sous forme de documents qui pourront être analysés par notre méthode d'accès et d'analyse de l'information. Nous comptons employer les techniques de raisonnement à base de cas pour exploiter ces analyses pour personnaliser les réponses du système et exploité par un médiateur dans un contexte de recherche coopérative d'information.<br /><br />A plus long terme, nous pensons qu'il faudra étudier le processus de communication (ou de dialogue) entre l'utilisateur et le médiateur dans un contexte de SRCI. Les systèmes que nous avons développé pourront servir d'outils d'observation des comportements de l'utilisateur. Il faudra également étudier l'intégration de ces outils dans un environnement de recherche documentaire permettant non seulement d'obtenir et d'analyser les informations d'une base mais permettant d'accéder aux documents primaires.