Mémoires de Fin d’Etudes
Etablissement
Université d’Oran1 - Ahmed Ben Bella
Affiliation
Département d’Informatique
Auteur
LOUKIL, Lakhdar
Directeur de thèse
BELDJILALI Bouziane (Professeur)
Co-directeur
MELAB Nouredine (Professeur)
Filière
Informatique
Diplôme
Doctorat
Titre
Métaheuristiques Hybrides Parallèles pour le Q3AP sur Environnements à Grande Echelle
Mots clés
Problème d’affectation quadratique à 3-dimensions; Métaheuristiques;Modèle insulaire; Méthodes de recherche locale; Hybridation; Algorithmes évolutionnaires parallèles; Grilles de calcul; Graphics Processing Units; CUDA.
Résumé
Les Métaheuristiques sont des méthodes génériques utilisées pour la résolution approchée de problèmes d’optimisation combinatoire (POC) NP-difficiles. De nombreuses métaheuristiques existent et peuvent être scindées en deux classes principales : les métaheuristique à solution unique et les métaheuristiques à population de solutions. Les métaheuristiques de la première classe les plus connues sont le recuit simulé, la recherche tabu, la méthode ILS (Iterated Local Search), VNS (Variable Neighborhood Search), etc. Les métaheuristiques les plus connues de la seconde classe sont les algorithmes évolutionnaires, la méthode GRASP (Greedy Randomized Adaptive Search Procedure), les colonies de fourmis, etc. Pour une résolution efficace, une métaheuristique doit avoir la capacité de diversifier la recherche dans les espaces de recherche et la capacité d’intensifier la recherche dans le voisinage des solutions prometteuses. Malheureusement, même si les méthodes ont été conçues pour atteindre ces deux objectifs, il n’en demeure pas moins qu’elles montrent une tendance vers l’un ou vers l’autre des deux objectifs. L’hybridation de métaheuristique à comportements complémentaires d’intensification et de diversification est une approche généralement adoptée pour construire des méthodes de résolution efficaces et robustes.
Date de soutenance
2010
Cote
TH3276
Pagination
VIII-89F.
Format
30 cm
Notes
BIBLIOG.83-89F.
Statut
Soutenue