ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 26/3-4 - 2007  - pp.371-390  - doi:10.3166/tsi.26.371-390
TITRE
Optimisation par colonies de fourmis pour le problème du sac à dos multidimensionnel

RÉSUMÉ
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.

ABSTRACT
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.


AUTEUR(S)
Inès ALAYA, Christine SOLNON, Khaled GHÉDIRA

Reçu le 4 mars 2005.    Accepté le 20 février 2006.

MOTS-CLÉS
optimisation par colonies de fourmis, problème du sac à dos multidimensionnel.

KEYWORDS
ant colony optimization, multidimensional knapsack problem.

CITATIONS
tsi.revuesonline.com/revues/11/citation/9967.html

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (180 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier