| Titre : | Réalisation d’une méthode d’optimisation approchée pour la résolution d’un problème NP complet |
| Auteurs : | INES CHABIRA, Auteur ; Toufik Kalfali, Directeur de thèse |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2023 |
| Format : | 1vol.(60p.) / ill., couv. ill. en coul / 30cm |
| Note générale : | Optimisation combinatoire, Affectation de produits aux machines, Mé- thodes de résolution, Méthodes méta-heuristiques,Algorithme de recuit simulé,Minima locaux,Efficacité et rapidité |
| Langues: | Français |
| Langues originales: | Français |
| Résumé : |
Dans ce mémoire, nous avons exploré l’importance de l’optimisation combinatoire dans la résolution de problèmes pratiques, en particulier dans le domaine de l’affecta- tion de produits aux machines. Nous avons mis en évidence les différentes méthodes de résolution étudiées, telles que les méthodes exactes, les méthodes heuristiques et les méthodes méta-heuristiques, en soulignant leur applicabilité à différents types de problèmes. Pour enrichir davantage notre analyse, nous proposons d’ajouter l’algorithme de recuit simulé, une technique de recherche locale méta-heuristique. L’algorithme de recuit simulé est inspiré du processus de recuit utilisé en métallurgie, où un maté- riau est chauffé puis progressivement refroidi pour obtenir une structure cristalline de meilleure qualité. Dans le contexte de l’optimisation combinatoire, l’algorithme de re- cuit simulé explore l’espace des solutions en effectuant des mouvements de voisinage et en acceptant des solutions de moins bonne qualité avec une certaine probabilité, ce qui permet d’éviter les minima locaux. En ajoutant l’algorithme de recuit simulé à notre étude, nous pourrons comparer ses performances avec les autres méthodes déjà mentionnées. Nous pourrons discuter de ses avantages, notamment sa capacité à échapper aux minima locaux, et de ses limites, telles que sa sensibilité aux paramètres de refroidissement et aux choix de voisinage. De plus, nous pourrons examiner comment l’algorithme de recuit simulé s’applique spécifiquement à l’affectation de produits aux machines, en évaluant son efficacité et sa rapidité dans ce domaine. |
| Sommaire : |
Introduction générale 1 Etat de l’art 14 1.1 Introduction ... 15 1.2 Définition d’optimisation ............ 15 1.3 Problème d’optimisation ............................ 16 1.4 Problème d’optimisation combinatoire............. 16 1.5 Exemples des problèmes d’optimisation combinatoire................. 17 1.5.1 Le problème du sac à dos (KP) ................ 18 1.5.2 probleme de voyage de commerce (TSP) ................ 18 1.5.3 Problème d’affectation ............ 19 1.5.4 Problème d’ordonnancement ........................ 20 1.5.5 Problème de tournée de véhicule (VRP) ............ 20 1.5.6 Problème de docking moléculaire (MolecularDocking) .................... 21 1.5.7 Le problème d’affectation des produits aux machines(APM) ........... 21 1.6 Domaines d’application ........................ 22 1.7 Méthodes de résolution d’un problème d’optimisation ............ 22 1.7.1 Méthodes exactes ............. 23 1.7.1.1 Branch and Bound ................... 23 1.7.1.2 Programme linéaire .......................... 23 1.7.2 Méthodes approchées ........................ 24 1.7.2.1 Méthodes heuristiques classique ou constructives ............... 24 1.7.3 Méthodes MétaHeuristiques ............... 25 1.7.4 Différence entre heuristique et métaheuristique .......... 25 1.7.5 Méta-heuristiques à solution unique ............... 25 1.7.5.1 Méthode de descente (Hill Climbing) .......... 26 1.7.5.2 Recuit simulé ................. 26 1.7.6 Méta-heuristiques à population de solutions ....... 26 1.7.6.1 Algorithmes génétiques .................. 26 1.7.7 L’intelligence en essaim ................... 28 1.7.7.1 L’optimisation par essaim particulaire ........... 29 1.7.7.2 Algorithme de Colonie d’Abeilles Artificielles ............ 2 1.7.7.3 Les algorithmes de colonies de fourmis . . . 1.7.8 Méthodes Hybrides . . . . . . . . . . . . 1.8 Travaux connexes . . . . . . . . . . 1.8.1 Le problème d’affectation : . . . . . . 1.8.2 Le problème d’affectation produits aux machines : . . . . 1.9 Implantation des Algorithmes . . . . . . 1.9.1 Les problèmes NP-complets . . . . . . . 1.9.2 Terminologie . . . . . . . . . . . . 1.9.2.1 La Construction . . . . . . . . 1.9.2.2 La recherche locale . . . . . . . . . . 1.9.2.3 La recherche de voisinage . . . . . . . . . . 1.9.2.4 Espace de recherche et Solution admissible . . . 1.9.2.5 L’optimum global . . . . . . . . . . 1.9.2.6 L’optimum local . . . . . . . . . . 1.9.3.1 Historique . . . . . . . . . . . . 1.9.3.2 En Métallurgie . . . . . . . . . . . 1.9.3.4 L’algorithme de Metropolis . . . . . . . . . 1.9.4 Les paramètres de l’algorithme de recuit simulé . . . . . 1.9.4.1 Etat initial de l’algorithme . . . . . . . . . 1.9.4.2 Variation de la température . . . . . . . . . . 1.9.5 Fonctionnement de l’algorithme de recuit simulé . . . . 1.9.6 Application sur un exemple . . . . . . . 1.9.7 Domaines d’applications . . . . . . . 1.9.8 Avantages et Inconvénients . . . . . . . . 1.9.8.1 Avantages : . . . . . . .. 1.9.8.2 Inconvénients . . . . . 1.10 Conclusion . . . . . . . . . . .. 2 Conception 2.1 Introduction . . . . . . 2.2 Conception générale du système . . . . . . 02.2.1 La couche Interface . . . . . . . . 2.2.2 La couche module de données . . . . . . . 2.2.3 La couche noyau . . . . . 2.3 Conception détaillé de système . . . . . . . . . . 2.3.1 La couche interface . . . . . . . . . . . . . . . 2.3.1.1 Entrée de données . . . . .. 2.3.1.2 Saisir les paramètres de la méthode . . . . . 2.3.1.3 Affichage de résultats . . . . . . 2.3.1.4 Module graphique . . . . . 2.3.2 La couche module de données . . . . . 2.3.2.1 Module de structuration de données . . . 2.3.2.2 Module d’affectation de produits aux machines . . . . 2.3.2.3 Le module d’échange de données . . . . . 2.3.3 La couche noyau . . . . . . 2.4 L’architecture d’algorithme recuit simulé . . . . 2.5 L’adaptation de RS au problème d’APM ....... 46 2.5.2 Codage des solutions ..... 47 2.5.3 La génération des affectations produit-machine ........ 47 2.5.3.1 Affectation aléatoire ..... 2.5.3.2 Affectation par saisie utilisateur ..... 48 2.5.4 Définition d’une solution initiale .... 48 2.5.5 Le choix de la température ...... 48 2.5.5.1 Température initiale ..... 48 2.5.5.2 La décroissance de la température .... 49 2.5.5.3 Température finale ....49 2.5.6 La fonction de coût(énergie)....... 49 2.5.7 Génération de voisins ... 50 2.5.8 Critère d’acceptation ...... 51 2.5.9 Le nombre de sauts ........ 51 2.5.10 Le critère d’échange(Permutation d’affectation ) ...... 51 2.5.11 Le critère d’arrêt .......... 52 2.6 Conclusion ........ 52 3 Implementation 54 3.1 Introduction ... 55 3.2 Environnement de développement ......... 55 3.3 Langage de programmation .......... 56 3.4 Présentation de l’applicatio 56 3.4.1 Interface ...... 56 3.4.1.1 L’interface principale....... 56 3.4.1.2 Le composant de type de génération ....... 57 3.4.1.3 Le composant de type d’initialisation ......... 59 3.4.1.4 Le composant de Paramètres de l’algorithme de recuit simulé ...... 61 3.4.1.5 L’optimisation de l’algorithme de recuit simulé .................. 62 3.5 Structures de données utilisées ..... 62 3.5.1 Tableau bidimensionnel... 63 3.5.2 Default Table Model ..... 63 3.5.3 List_u ............ 63 3.5.4 Graphes ........ 63 3.6 Les procédures utilisées ... 63 3.6.1 Génération aléatoire des affectations : ..... 63 3.6.2 Calcul de l’énergie (le coût) : ....... 64 3.6.3 Algorithme de recuit si. 64 3.6.4 Affichage graphique :.. 65 3.7 Analyse et Optimisation des Paramètres de Contrôle ............ 66 3.7.1 Tests sur la solution initiale ......... 67 3.8 Conclusion .... 68 Conclusion générale |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/789 | Mémoire master | bibliothèque sciences exactes | Consultable |
