Etablissement
Ecole Nationale Supérieure d'informatique
Affiliation
Département de Post-Graduation
Auteur
MAHMOUDI, Aicha
Directeur de thèse
BENATCHBA Karima (Professeur)
Filière
Informatique
Diplôme
Doctorat
Titre
Des approches évolutives basées sur l’intelligence en essaim pour les Problèmes d’Affectation de Fréquences (PAF).
Mots clés
PAF, colorations des graphes, intelligence en essaim, algorithmes génétiques, systèmes immunitaires artificiels (AIS), Hybridation des méta-heuristiques évolutives, CSP.
Résumé
Le Problème d’affectation des fréquences (PAF) dans les réseaux de télécommunication GSM est un problème d‘optimisation combinatoire NP-difficile. Il est donc invraisemblable, en dépit de la puissance de calcul de nos ordinateurs, de trouver une solution optimale à un PAF de grande taille en un temps de calcul raisonnable. Un PAF peut être modélisé en un des problèmes de coloration de graphes selon l’objectif visé par ce problème et les contraintes à satisfaire lors de l’établissement des solutions. Les méta-heuristiques évolutives basés sur l‘intelligence en essaim offrent une alternative prometteuse à la résolution des problèmes d‘optimisation difficiles notamment ceux qui sont modélisable sous forme d‘un graphe. Leur grand intérêt réside dans leur capacité à s’adapter aux changements de l’environnement. L’hybridation de ces approches est la tendance actuelle qui a comme but de faire coopérer différentes approches et donc combiner leurs différents avantagesafin d‘être efficace pour un plus large panel d‘instances. Cependant, un très grand nombre de problèmes combinatoires réels et théoriques, entre autre le PAF, appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP). Ces problèmes partagent une description commune, basée sur un formalisme très simple, qui autorise en général une modélisation claire et intuitive. En effet, un CSP est défini par un ensemble X de variables, un ensemble D de domaines de définition qui encadrent les valeurs que peuvent prendre ces variables, et un ensemble C de contraintes (unaires, binaires ou n-aires) qui conditionnent les valeurs que pourront prendre les variables appartenant à X. Les enjeux de la résolution de ces problèmes sont très importants, sur le plan scientifique pour produire du savoir algorithmique, et sur le plan économique pour améliorer la performance de systèmes de toutes natures. Les méthodes sont classées essentiellement en deux familles. La première, qui est la base de la Programmation Par Contraintes (PPC), englobe les méthodes dites complètes ou exactes, qui peuvent prouver la réalisabilité d’un problème, ou son contraire le cas échéant. En général ces méthodes permettent également d’extraire l’ensemble des solutions d’un problème. La deuxième famille englobe les méthodes dites incomplètes ou approchées qui ont été proposées pour faire face à l’explosion combinatoire sans garantir l’optimalité. Ce genre de méthode aborde généralement la résolution d’un CSP comme un problème d’optimisation combinatoire. Une activité intense existe depuis une dizaine d’années sur l’hybridation entre des approches complètes et incomplètes, et particulièrement entre la recherche locale et la programmation par contraintes. Des progrès importants ont été réalisés sur la résolution de certains problèmes et ont même parfois donné lieu à la conception de méthodes assez génériques telles que CN-Tabu et Decision-Repair toutes deux basées sur des configurations partielles consistantes. Cependant, peu de travaux se basent sur l’hybridation des méthodes évolutives et celles de propagation des contraintes. Cette thèse, qui présente et étudie quelques approches méta-heuristiques évolutionnaires basées sur l‘intelligence en essaim pour les PAF, s‘inscrit dans un contexte opérationnel de résolution de problèmes combinatoires NP-difficiles. Elle propose des approches (hybrides ou non) de résolution basées sur des techniques de l‘intelligence en essaim (algorithme génétiques et systèmes immunitaires artificiels) et les techniques de propagation et satisfaction des contraintes.
Statut
Vérifié