Titre :
Une approche hybride basée sur les Algorithme génétique muti objectifs et les systèmes immunitaires pour la résolution du problème d’affectation de fréquences dynamique
Proposé par : Mme Bessedik et Mme Si-Tayeb
Résumé :
Depuis quelques années, les études portant sur le problème d’affectation de fréquences (PAF) se sont multipliées. Ceci est dû essentiellement à la vaste implémentation des réseaux de la téléphonie sans-fil (par exemple les réseaux GSM) et des communications satellites.
En effet, alors que le nombre de fréquences disponibles est limité la demande augmente sans cesse. Chaque transmetteur nécessite une fréquence à attribuer à tous les terminaux situés dans sa région de service. Sachant que des fréquences différentes doivent être affectées aux transmetteurs proches (ayant une zone d’émission commune), l’allocation de la bande de fréquence définit donc un problème, difficile et largement étudié dans la littérature, c’est le problème d’affectation de fréquences FAPs (FrequencyAssignmentProblem.
Ce problème peut se modéliser par un graphe. Chaque transmetteur est représenté par un sommet, et deux sommets sont reliés par une arête quand les deux transmetteurs ont une zone d’émission commune. En outre, il existe une bijection intuitive entre une fréquence et une couleur. Aussi pour des raisons technologiques, la gamme de fréquences pour chaque transmetteur n’est pas nécessairement la même ce qui a conduit à de nouvelles variantes du problème de la coloration des graphes comme la coloration par listes où une liste de couleurs permises est affectée à chaque sommet.
Les algorithmes génétiques forment une approche métaheuristique évolutive qui a prouvé son efficacité face à plusieurs problèmes NP-difficiles de l’optimisation combinatoire. De plus, ils sont les plus adaptés pour l’optimisation multi objectif
Le principal avantage des algorithmes génétiques est leur rapidité. Cependant, le fait qu’ils se basent sur des opérateurs génétiques n’utilisant aucune connaissance du problème traité, a pour effet de limiter considérablement leur efficacité.
L’optimisation par système immunitaire est une famille récente de méta-heuristique qui s’inspire du comportement du Système Immunitaire Naturel (SIN). Les Systèmes Immunitaires Artificiels (AIS pour Artifcial Immune System en anglais) sont des systèmes informatiques abstraits utilisant les idées, les théories et les composants du système immunitaire naturel. Les AIS apportent d’un point de vue informatique, des propriétés telles que la reconnaissance, la discrimination, la mémorisation, l’apprentissage, l’auto organisation et l’adaptation. Toutes ces caractéristiques permettent aux algorithmes basés sur les systèmes immunitaires artificiels de palier à plusieurs obstacles lors de la résolution des problèmes combinatoires difficiles.
Pour palier aux faiblesses des algorithmes génétiques, nous proposons dans ce travail de développer un algorithme génétique muti objectif pour la résolution du PAF dynamique utilisant des crossovers inspirés des AIS. La modélisation du PAF est basée sur la muti coloration par listes.
Une étude empirique faisant varier les différents paramètres de l’approche proposée sera faite. Pour évaluer notre travail, nous proposons aussi de comparer les résultats obtenus avec ceux des travaux relatifs au même problème.
Mots-Clés : Affectation de fréquences, PAF dynamique, algorithme génétique, SPEA2, NSGA2, la coloration par liste.