Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520276
Contributor : Christophe Lecoutre <>
Submitted on : Wednesday, September 22, 2010 - 6:14:51 PM
Last modification on : Wednesday, November 20, 2019 - 3:19:12 AM
Document(s) archivé(s) le : Thursday, December 23, 2010 - 3:13:37 AM

File

albert.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : inria-00520276, version 1

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. ⟨inria-00520276⟩

Share

Metrics

Record views

290

Files downloads

761