Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Optimisation sous contraintes par Intelligence Collective Auto-adaptative [PDF]
Madjid Khichane [LIRIS]
10/2010
Établissement : Université Claude Bernard
Soutenue le Oct 26, 2010
Jury
M. HAO Jin-Kao, Université d'Angers, Angers, France Rapporteur
M. VERFAILLIE Gérard , ONERA, Toulouse, France Rapporteur
M. JOLION Jean-Michel , Université de Lyon, Lyon, France Président
M. STÜTZLE Thomas , IRIDIA, Bruxelles, Belgique Examinateur
Mme SOLNON Christine, Liris, Lyon, France Directeur
M. ALBERT Patrick, IBM, Paris, France Co-directeur
Contact : madjid.khichane@gmail.com

TEL : tel-00720232

Résumé

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type « Ant Colony Optimization » (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO. Ci-après, nous donnons un résumé de chacune de ces trois contributions. Intégration d'ACO à un langage de PPC pour résoudre des CSP: Nous avons montré comment intégrer ACO dans un langage de programmation par contraintes pour résoudre les problèmes de satisfaction de contraintes: le problème à résoudre est décrit en termes de contraintes dans le langage d'IBM ILOG Solver et il est résolu de façon générique par un algorithme ACO intégré au langage et remplaçant l procédure de recherche "Branch&Propagate". Cet algorithme ACO utilise les procédures de propagation et de vérification des contraintes prédéfinies dans la bibliothèque d'ILOG Solver. Nous avons validé notre approche sur le problème d'ordonnancement de voitures. Ce dernier, est un problème de référence utilisé au sein de la communauté PPC pour tester les performances et l'efficacité de leurs algorithmes. Couplage d'ACO et de la PPC pour résoudre des COPs : Nous avons montré comment coupler ACO avec une procédure de recherche complète pour résoudre des COPs: le COP est décrit à l'aide du langage de modélisation par contraintes et est résolu par un algorithme générique intégré au langage. Cet algorithme générique couple ACO et recherche complète afin de bénéficier des avantages de chacune des deux approches: - ACO est utilisé dans une première phase pour échantillonner l'espace de recherche et identifier les zones prometteuses; pendant cette première phase, la recherche B&P est utilisée pour fournir à ACO des solutions cohérentes -La recherche complète de type B&P&B est utilisée dans une deuxième phase pour rechercher une solution optimale; ACO est utilisé pendant cette deuxième phase pour guider la recherche complète, comme heuristique de choix de variables et/ou de valeurs. Nous avons démontré l'efficacité de cet algorithme hybride sur des problèmes de sac-à-dos multidimensionnels, d'affectation quadratique et cliques maximum. Adaptation dynamique et automatique des paramètres d'ACO: Le niveau d'intensification et de diversification de la recherche réalisé par un algorithme ACO est donné par les valeurs de ses nombreux paramètres. Ces paramètres donc ont une forte influence sur le processus de résolution. Nous avons proposé une nouvelle stratégie adaptative qui permet à un algorithme ACO de régler lui-même ses propres paramètres pendant la résolution d'un problème de sorte qu'ils soient plus adaptés à la structure de l'instance traitée. Nous avons validé cette stratégie sur un algorithme ACO pour la résolution des problèmes de satisfaction de contraintes.

BibTex

Download

@PhDThesis{Liris-4817,
  title         = {{Optimisation sous contraintes par Intelligence Collective 
    Auto-adaptative}},
  author        = {Madjid {Khichane}},
  year          = {2010},
  month         = oct,
  school        = {Université Claude Bernard},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=4817}
}