Optimisation par colonies de fourmis pour le problème du sac à dos multidimensionnel
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. Dans l’algorithme
ACO proposé, 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 d’objets
sélectionnés. On compare le comportement de ces trois variantes sur un ensemble d’instances
de référence et on étudie l’influence de la phéromone sur le processus de résolution. On compare
enfin l’algorithme ACO proposé avec des approches génétiques de l’état de l’art montrant
qu’il obtient des résultats compétitifs.
We propose an algorithm based on the Ant Colony Optimization (ACO) metaheuristic 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. We propose three different variants of this ACO algorithm, corresponding to three different ways of laying and exploiting pheromone trails. We experimentally compare these three different variants. We then experimentally compare our ACO algorithm with two state-of-the-art genetic algorithms, showing that it obtains competitive results.
I.ALAYA, C.SOLNON, K.GHÉDIRA
Reçu le 4 mars 2005.
Accepté le 20 février 2006.
optimisation par colonies de fourmis, problème du sac à dos multidimensionnel.
ant colony optimization, multidimensional knapsack problem.
Français
|
