PFE. Implémentation parallèle des systèmes immunitaires pour la résolution du problème de la coloration par listes. Application au problème d’affectation de fréquence.

 Candidat :

Sujet  proposé par:  Melle Benatchba, Mme Bessedik et Mr Hadji

 

Intitulé du sujet :

 

Implémentation parallèle  des systèmes immunitaires pour la résolution du problème de la  coloration par listes. Application au problème d’affectation de fréquence.

Domaine : Recherche Opérationnelle

Organisme d’accueil : LMCS, ESI.

Mots-Clés : Optimisation combinatoire, coloration par listes, méta–heuristique évolutive, parallélisation, affectation de fréquences,  système immunitaire.

Résumé :

La coloration de graphes est un problème classique de la théorie des graphes et de l’optimisation combinatoire. Il s’agit de colorier les sommets d’un graphe afin que deux sommets adjacents n’aient pas la même couleur. Ce problème a donné lieu à de nombreuses extensions telles que  la T-coloration ou la coloration par liste où seul un sous-ensemble des couleurs appelées couleurs permises est autorisé pour chaque sommet.

Généralement, le but d’une coloration par liste est de minimiser le nombre de couleurs ainsi que la cardinalité de la plus grande liste utilisée.

Le problème de la coloration par listes étant NP-difficile, l’utilisation des méthodes exactes pour le résoudre prend beaucoup de temps de calcul surtout pour les instances de grandes tailles. Les méthodes approchées ou plus exactement les méta-heuristiques représentent une alternative qui donne des bonnes solutions en un temps de résolution réduit.

Parmi ces méthodes, on retrouve les systèmes immunitaires artificiels qui sont une méta-heuristique évolutive qui s’inspire du comportement des systèmes immunitaires biologiques des vertèbres. Ce dernier est composé d’un ensemble de cellules, d’organes et de molécules qui interagissent pour combattre les agents infectieux étrangers. Le but du système immunitaire est donc de les reconnaitre et de les détruire.

 

D‘autre part, pour gagner en temps de calcul et concevoir des méthodes de recherche parallèles et coopératives, il convient d’intégrer à l’optimisation combinatoire des techniques de parallélisation. En effet, ces dernières années, les méthodes de recherche parallèles ont permis d’obtenir des résultats satisfaisants sur des instances de très grandes tailles.

Dans ce travail, nous proposons d’adapter une technique de recherche parallèle basée sur les systèmes immunitaires artificiels pour la résolution du problème de la coloration par listes. Pour évaluer notre travail, l’algorithme sera appliqué pour résoudre des instances du problème d’affectation de fréquences, et une comparaison des résultats obtenus avec ceux déjà trouvé dans la littérature sera faite également.

Références Bibliographiques :

 

[ABB95] F. Abbastita, N. Abbastita, & L. Caponetti. An evolutionary and cooperative agent model for optimization. IEEE Int. Conf. on Evolutionary Computation ICEC’95, pp. 668-671, Perth, Australia, décembre 1995.

[BAC99] V. Bachelet. Métaheuristiques Parallèles hybrides : Application au problème d’affectation quadratique. Thèse de doctorat de l’USTL, France, 1999.

[CAS99] L. De Castro, F. Von Zuben. Artificial Immune Systems: Part I: Basic theory and applications. Rapport technique TR-DCA. Department of computer Engineering and industrial Automation. School of Electrical and Computer Engineering. State University of Campinas. Brésil.2000.

 

[COS93] M. Cosnard, D. Trystram. Algorithmes Et Architecture Parallèle. Iia, Interedition, 1993.

 

[CRA97a] T .G Crainic, M. Toulouse, & M. Gendreau. Toward A Taxonomy Of Parallel Tabu Search  Heuristics. Informs Journal On Computing, Vol.9, N°1, pp. 61-72, 1997.

[CRA97b] T .G Crainic, A. Nguyen, & M. Gendreau. Cooperative multi-thread parallel tabu search with evolutionary adaptive memory. 2nd Int. Conf. On Metaheuristics. Sofia Antipolis, France, juillet 1997.

 

[HAL90] W.K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE68,1497 – 1514, 1990 .

 

[Pre97] P. Preux & E-G. Talbi. Towards Hybrid Evolutionary Algorithms. Technical Report Lil-97-15, Laboratoire D’informatique Du Littoral, 1997.

 

[REI00]		P. Reininger. Modélisation pour l’Optimisation des Réseaux Cellulaires GSM. Thèse de doctorat, Université Louis Pasteur Strasbourg, Juillet 2000.
	[TAL91] E.G. Talbi, Et P. Bressiere. A Parallel Genetic Algorithm For The Graph Partitioning Problem. Acm Int. Conf. On Supercomputing, Cologne, Germany, June 1991.
	[TAL99b] E-G Talbi. A Taxonomy Of Hybrid Metaheuristics. Journal Of Combinatorial Optimization, Kap, 1999.