Intégration de l'optimisation par colonies de fourmis dans CP Optimizer

Madjid Khichane 1, 2 Patrick Albert 3 Christine Solnon 1
1 M2DisCo - Geometry Processing and Constrained Optimization
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
2 ILOG SA [Gentilly]
3 IBM - Paris [Bois-Colombes]
Résumé : Nous présentons un algorithme générique-hybride pour la résolution de problèmes d'optimisation combinatoire. Cet algorithme est le fruit de la combinaison de l'algorithme d'optimisation par colonie de fourmis (ACO: Ant Colony Optimization) et IBM ILOG CP Optimizer (produit commercialisé dédié à la résolution de problèmes combinatoires). Le problème à résoudre est modélisé avec le langage de modélisation de CP Optimizer et il est résolu par l'algorithme que nous proposons. Cet algorithme fonctionne en deux phases séquentielles. La première phase sert à échantillonner l'espace des solutions et à construire des traces de phéromones par ACO. Durant la deuxième phase, CP Optimizer effectue une recherche arborescente exhaustive guidée par les traces de phéromones accumulées lors de la première phase. Nous avons testé l'algorithme proposé sur, principalement, trois problèmes à savoir: le problème du sac à dos, le problème d'affectation quadratique et le problème de l'ensemble stable maximum. Les premiers résultats sur ces trois problèmes montrent que ce nouvel algorithme améliore les performances de CP Optimizer.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.177-186, 2010
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00520276
Contributeur : Christophe Lecoutre <>
Soumis le : mercredi 22 septembre 2010 - 18:14:51
Dernière modification le : jeudi 1 novembre 2018 - 01:19:01
Document(s) archivé(s) le : jeudi 23 décembre 2010 - 03:13:37

Fichier

albert.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00520276, version 1

Collections

EC-LYON | LIRIS | JFPC2010 | INSA-LYON | UNIV-LYON1

Citation

Madjid Khichane, Patrick Albert, Christine Solnon. Intégration de l'optimisation par colonies de fourmis dans CP Optimizer. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.177-186, 2010. 〈inria-00520276〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

252

Téléchargements de fichiers

617

Contact


archive-ouverte@inria.fr