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ée 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 chaque ité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 objets sé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.
A draft version is available as a research report LIRIS RR-2006-005 (pdf)