Mémoires de Fin d’Etudes
Etablissement
Université de M’Sila - Mohamed Boudiaf
Affiliation
Institut d’Informatique
Auteur
THARAFI, Abdallah
Directeur de thèse
GASMI Abdelkader (Maitre de conférence)
Filière
Informatique
Diplôme
Magister
Titre
CONCEPTION D’UNE METHODE HYBRIDE POUR LA RESOLUTION DES PROBLEMES D’OPTIMISATION DIFFICILE
Mots clés
Mots clés : Optimisation, Métaheuristiques, Algorithme génétique, Recherche Tabou. الكلمات المفتاحية : التحسين، الطرق التقريبية، خوارزميات الوراثة، البحث المحلي تابو. Key Words: Optimization, Métaheuristics, Genetic Algorithm, Search Tabu.
Résumé
La résolution des problèmes d’optimisation difficile font souvent appel aux métaheuristiques. Les techniques qui constituent des algorithmes de type métaheuristique vont de la simple procédure de recherche locale à des processus d’apprentissage complexes mais elles ne s’excluent pas mutuellement. Dans l’état actuel de la recherche, il est généralement impossible de prévoir avec certitude l’efficacité d’une méthode donnée, quand elle est appliquée à un problème particulier. Par conséquent, la tendance actuelle est l’émergence des algorithmes dits hybrides, qui s’efforcent de tirer parti des avantages spécifiques d’approches différentes en les combinant. Ses domaines d’applications sont multiples: fouille de données, bioinformatique, reconnaissance des formes, optimalisation combinatoire surtout pour les problèmes NP-complet et bien d’autres. Dans ce travail on s’intéresse à l’hybridation de deux métaheuristiques: les algorithmes génétiques et l’approche de Recherche Tabou pour l’optimisation difficile. جدولة التعليمات البرمجية هي خطوة أساسية لرسم معالم تنفيذ البرامج على مستوى مجموعة وحدات المعالجة داخل الحاسوب الكومبيوتر. الجدولة العير ملائمة لتنفيذ التعليمات تودي حتما للاستغلال السيئ لوحدات المعالجة. المواصفات السلوكية وتنتج جدولا زمنيا للتعليمات على مجموعة من وحدات المعالجة. والهدف من ذلك هو تقليل وقت الانتهاء من تطبيق معين مع استخدام فعال للموارد الحاسوبية.تصنف مشكلة جدولة التعليمات البرمجية في الصنف الحاد الصعوبة، وبالتالي اللجوء إلى الطرق التقريبية فعال بشكل جيد من أجل إعطاء حلول ذات نوعية جيدة. في هذه المذكرة، فإننا نقدم رؤية خوارزمية لجدولة التعليمات باستخدام AG_TSللنظام المشتق من نظام الوراثة عند الأحياء ، يستخدم نهجا هجينا عن طريق الجمع بين نظام البحث المحلي بطريقة تابو مع نظام خوارزميات الوراثة ، حيث يتم تعديلها بشكل حيوي يمزج بين المناهج التجريبية المحلية والكلية تطبيق فيها المدخلات بطريقة تكرارية. ، مقارنة هذه الخوارزمية ولد نتائج أفضل على كل المقاييس مع أفضل اختبار للاستقرار. The resolution of the problems of difficult optimization often calls upon the métaheuristics ones. The techniques which constitute algorithms of the métaheuristics type go from the simple procedure of local research to complex processes of training but they are not excluded mutually. In the actual position of research, it is generally impossible to envisage with certainty the effectiveness of a given method, when it is applied to a particular problem. Consequently, the current trend is the emergence of the algorithms known as hybrid, which endeavor to benefit from the specific advantages of different approaches by combining them. Its scopes of application are multiple: excavate data, bioinformatics, pattern recognition, combinative optimization especially for the problems Np-complete and well others. In this work one is interested in hybridization of two métaheuristics: genetic algorithms and approach of Tabu Search for difficult optimization.
Date de soutenance
28 / 06 / 2012
Pagination
103 p
Illusatration
relié
Format
30 cm
Notes
une copie papier + un cdrom
Statut
Soutenue