Mémoires de Fin d’Etudes
Etablissement
Université d’Oran1 - Ahmed Ben Bella
Affiliation
Département d’Informatique
Auteur
BENGHABRIT, Nawel
Directeur de thèse
YAGOUBI B. (Maitre de conférence)
Co-directeur
LOUKIL L. (Maitre de conférence)
Filière
Système d’Information
Diplôme
Magister
Titre
Résolution des problèmes combinatoires de grande taille sur grilles de calcul : Application au problème des règles de Golomb
Mots clés
Problème d’optimisation combinatoire; Grid’5000; Règles de Golomb;Algorithme génétique; Métaheuristiques hybrides et parallèles; ParadisEO.
Résumé
La Recherche des règles de Golomb optimales est un problème d’optimisation combinatoire réputé difficile, différentes approches ont été proposées ces dernières années pour la résolution de ce problème telles que les méthodes de programmation exactes, les métas heuristiques hybrides et les algorithmes évolutionnaires (AE).Dans ce mémoire, nous proposons plusieurs approches, la première étant basée sur un algorithme génétique hybride et parallèle inspirée de la théorie de l’hérédité de Mendel afin de générer des règles de Golomb optimales et quasi-optimales pour différentes instances (différents nombres de marques) et dans des délais raisonnables, la seconde étant basée sur un modèle insulaire asynchrone à transformations parallèles. Le principe de la méthode proposée est de combiner une méthode de recherche locale à un algorithme génétique en utilisant la plateforme d’implémentation parallèle ParadisEO-PEO et la plateforme d’expérimentations Grid’5000, au final notre approche est capable de résoudre des règles de grandes taille avec une efficacité raisonnable.
Date de soutenance
2011
Cote
TH3489
Pagination
80F.
Illusatration
ILL
Format
30 cm
Notes
BIBLIOG.77-80F.RESUME ET MOTS CLES EN FRANCAIS ET EN ANGLAIS.
Statut
Soutenue