Optimisation par colonies de fourmis pour le problème du sac-à-dos multi-dimensionnel

National audienceWe propose an algorithm based on the Ant Colony Optimization (ACO) meta-heuristic for solving the Multidimensional Knapsack Problem (MKP), the goal of which is to find a subset of objects that maximizes a given objective function while satisfying some resource constraints. The proposed ACO algorithm is generic, and we propose three different instantiations, corresponding to three different ways of laying and exploiting pheromone trails. We experimentally compare these three different instanciations. We then experimentally compare our ACO algorithm with two state-of-the-art genetic algorithms, showing that it obtains competitive results.Dans cet article, nous proposons d'utiliser la métaheuristique d'optimisation par colonies de fourmis (Ant Colony Optimization / ACO) pour résoudre le problème du sac à dos multidimensionnel. L'objectif est de sélectionner un sous-ensemble d'objets qui maximise une fonction utilité donnée tout en respectant certaines contraintes de ressources. Nous proposons un algorithme ACO générique pour ce problème. L'idée est de construire des solutions de façon incrémentale, par ajouts successifs d'objets à une solution partielle. A chaqueitération, l'objet à ajouter est choisi selon une probabilité dépendant de traces de ``phéromone'' et d'une information heuristique locale. On étudie trois façons de déposer (et d'exploiter) les traces de phéromone : sur les objetssélectionnés, sur les couples d'objets sélectionnés consécutivement ou sur tous les couples de sommets sélectionnés. On compare le comportement de ces trois variantes sur un ensemble d'instances ``benchmarks'' et on étudie l'influence de la phéromone sur le processus de résolution. On compare enfin l'algorithme ACO proposé avec d'autres approches