| Titre : | Comparaison expérimentale de quelques méta -heuristiques cas du problèmes APM |
| Auteurs : | Samira Mazouzi, Auteur ; Toufik Kalfali, Directeur de thèse |
| Type de document : | Monographie imprimée |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2017 |
| Format : | 1 vol. (74 p.) / 30 cm |
| Langues: | Français |
| Mots-clés: | Les problèmes d’Optimisation Combinatoire,Problème difficile,Problème Discret,méta heuristique,Problème affectation des produits aux machines,Recuit simulé,Recherche Tabou. |
| Résumé : |
La résolution des problèmes d’Optimisation Combinatoire par des métas heuristiques de recherche locale sont utilisés avec succès pour résoudre les problèmes difficiles (problèmes discret) de grande taille. Un problème d’affectation des produits aux machines APM est l’un des problèmes d’optimisation combinatoire, dans notre projet nous avons résolu ce problème par les deux métas heuristiques : recuit simulé et recherche Tabou Ce travail présent deux méthodes qui résulte Le problèmes l’APM, dans le but de faire une comparaison expérimentale entre les résultats des deux méthodes selon les deux contraintes : (fonction objectif) et (temps d’exécutions). Mots clés : Les problèmes d’Optimisation Combinatoire, Problème difficile, Problème Discret, méta heuristique, Problème affectation des produits aux machines, Recuit simulé, Recherche Tabou. |
| Sommaire : |
SOMMAIRE 1.1 Introduction ................................................................................. 4 1.2 Problèmes d’optimisation discrète ........................................................................... 4 1.3 L’Optimisation Combinatoire ......................................................................... 5 1.3.1 Définitions ................................................................................ 5 1.4 Classification des méthodes de résolution des problèmes d’Optimisation Combinatoire .. 7 1.4.1 Les méthodes exactes ................................................... 8 1.4.1.1 Programmation Linéaire ......................................................... 8 1.4.1.2 Programmation dynamique ................................................................... 9 1.4.1.3 Branch & Bound (procédure par évaluation séparation progressive) ............................ 10 1.4.2 Les méthodes approchées ..................................................... 11 1.4.2.1 Méthodes évolutionnaire ................................................................... 13 1.4.2.1.2 L’Algorithme des Colonies des Fourmis (Ant Colony Optimization) ................................ 16 1.4.2.2 Recherche locale ...................................... 19 1.4.2.2.1 La Méthode de descente ........................................................ 20 1.4.2.2.2 La Méthode du Recuit simulé ............................................................................. 24 1.4.2.2.4 Les méthodes Acceptation avec un seuil (Threshold algorithms) ...................................... 26 1.4.2.2.5 Les Méthodes de bruitage ...................................................... 26 1.4.2.2.6 La méthode GRASP .......................................................... 27 1.5 Des problèmes d’Optimisation Combinatoire ...................................... 28 1.5.1 Problème du voyageur de commerce ............................................................ 28 1.5.2 Problème du sac-à-dos ...................................................................... 29 1.5.3 Problème d’affectation ................................................................... 29 1.5.4 Problème d’ordonnancement ............................................................... 29 1.5.5 Le problème du couplage biparti ........................................................ 30 1.5.6 Le problème du flot max ........................................................... 30 1.6 Les Domaines d’applications ......................................................... 30 1.7 Conclusion ...................................................... 31 2.1 Introduction .............................................................................................. 32 2.2 Les Problèmes d’affectation ............................................................ 32 2.2.1 Formulations ................................................................... 34 2.2.2 Modèles de problème d’affectation ..................................................... 36 2.2.3 Algorithmes pour le problème d’affectation ........................................ 36 2.3 Problème Affectation produits–machines .......................................... 37 2.4 Conclusion .............................................................................. 39 3.1 Introduction .............................................................................. 40 3.2 Description générale du système ...................................................... 40 3.2.1 Le Module Utilisateurs ............................................................... 41 3.2.2 Le Module interface graphique ..................................................... 41 3.2.3 Le Module noyau .................................................................... 41 3.3 Description détaillé de système .................................................. 42 3.3.1 Le Module Utilisateur ....................................................... 42 3.3.2 Le Module interface graphique .............................................................. 42 3.3.2.1 Les Types des générations d’affectation des produits à la machines ............... 43 3.3.2.2 Module Affichage des résultats .......................................... 43 3.3.3 Le Module unité des données ................................................................ 44 3.3.3.1 Unité Des Types des Générations d’APM .......................................... 44 3.3.3.2 Unité de structuration des données ................................................. 46 3.3.3.3 Unité d’échange des informations ........................................... 46 3.3.4 La Module noyau ................................................................... 46 3.4 La méthode de recuit simulé .................................................... 47 3.5 La méthode de recherche taboue .......................................... 48 3.6 L’adaptation des deux méthodes RS & RT aux problèmes d’APM ..................... 50 3.6.1 Définition d’un cas d’une solution ........................................................ 50 3.6.2 Notion de voisinage ............................................................... 52 3.6.3 Fonction Objectif ................................................................ 52 3.7 Adaptation pour la méthode recuit simulé .................................... 52 3.7.1 Voisinage basé sur l’opérateur de changement (swap operator) .................... 52 3.7.2 La fonction Fitness .................................................... 54 3.7.3 Condition d’arrêt ........................................................ 54 3.8 Adaptation Pour la recherche Tabou ........................................ 54 3.8.1 Notion des Voisinage et fonction fitness pour RT ..................................... 55 3.8.2 Critère d’arrêt ................................................................... 59 3.9 Conclusion ........................................................................ 60 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/328 | Mémoire master | bibliothèque sciences exactes | Consultable |
