Sujet proposé par: Mr Riad Hadji ( [email protected] )
Implémentation des systèmes immunitaires pour la résolution du problème de recouvrement d’ensembles.
Domaine : Recherche Opérationnelle
Organisme d’accueil : LMCS, ESI.
Mots-Clés : Optimisation Combinatoire, Recouvrement d’Ensembles, Méta-heuristique Évolutive, Système Immunitaire.
Résumé :
Le problème de recouvrement d’ensembles (SCP) est un problème classique de la théorie des graphes et de l’optimisation combinatoire. Plusieurs problèmes du monde réel peuvent être modélisés comme un SCP: l’ordonnancement des équipages, la simplification des expressions booléennes, l’ordonnancement du travail, le problème de localisation des émetteurs des réseaux cellulaires. Une description de ce problème peut être donnée comme suit: Soit E un ensemble ayant m éléments, E = {e1, e2, …, em}, et n sous-ensembles E1, E2, …, En de E. Chaque sous-ensemble Ej est caractérisé par un coût donné Cj. Il s’agit alors de trouver un ensemble F des sous-ensembles E1, E2, …, En telle que :
1. Tout élément de E soit contenu dans au moins un sous-ensemble Ej de l’ensemble F (La contrainte);
2. La somme des coûts Cj des sous-ensembles appartenants à l’ensemble F soit minimale (La fonction à oprimiser).
Le SCP est un problème NP-Complet; cependant; et dans des délais raisonnables, les algorithmes exacts peuvent trouver la solution optimale pour des instances de petites tailles. Ces algorithmes sont basés sur des procédures de recherche dans les structures d’arbres utilisant des techniques de branch and bound ou des techniques dérivées de la théorie des graphes.
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 pour les instance de grandes taille. 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.
Dans ce travail, nous proposons d’adapter une technique de recherche basée sur les systèmes immunitaires artificiels pour la résolution du problème de recouvrement d’ensembles. Pour évaluer ce travail, l’algorithme sera appliqué pour résoudre des instances disponibles dans la littérature , et une comparaison des résultats obtenus avec ceux déjà trouvé dans la littérature sera faite également.
Références Bibliographiques :
E. Balas. Cutting planes from conditional bounds : A new approach to Set Covering. Mathematical Programming Study, 12, 19-36, 1980.
E. Balas & M. C. Carrera. A dynamic subgradient-based branch and bound procédures for Set Covering. Managment Sciences Research Report N° MSSR 568, GSIA, Carnegie-Mellon University, October 1991. Revised May 1995, to appear in Operations Research.
E. Andersson, E. Housos, Kohl & D. Wedelin. Crew pairing optimisation. Operations Research in the Airline Industry. Kluwer Scientific Publishers, 1997.
J. E. Beasley & P. C. Chu. A genetic algorithm for the Set Covering Problem. European Journal of Operational Research, 95(2) : 393-404, 1996.
A. Carpara, M. Fischetti & P. Toth. A heuristic method for the Set Covering Problem. In W. H. Cuningham, T. S. McCornick, & M. Queyranne editors, Proc. Of the fifth IPCO Integer Programming and Comb. Optimization Conference, Springer-Verlag, 1996.
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.
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.
U.Aickelin et D.Dasgupta, Artificial Immune Systems, 2004.
L. N. de Castro and F. J. Von Zuben, Learning and Optimization Using the Clonal Selection Principle IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems, vol.6, pp. 239- 251, 2002.
V. Cutello, G. Nicosia, M. Pavone: “Exploring the capability of immune algorithms: A characterization of hypermutation operators” in Proc. of the Third Int. Conf. On Artificial Immune Systems (ICARIS’04), pp. 263-276, 2004.
D. Dasgupta , Advances in Artificial Immune Systems . IEEE Computational Intelligence Magazine . November.2006
R. Hadji, Optimisation parallèle & coopérative : Application au problème de recouvrement d’ensembles, thèse de magister, USTHB, 2002.