Les métaheuristiques pour la résolution des problèmes d’optimisation

les métaheuristiques pour la résolution des problèmes d’optimisation

Un problème d’optimisation combinatoire est défini par un ensemble d’instances.A chaque instance du problème est associé un ensemble discret de solutions S, un sousensemble X de S représentant les solutions admissibles (réalisables) et une fonction de coût f (ou fonction objectif) qui assigne à chaque solution s ∈ X lenombre réel (ou entier) f(s). Résoudre un tel problème (plus précisément une telleinstance du problème) consiste à trouver une solution s* ∈ X optimisant la valeur dela fonction de coût f. Une telle solution s* s’appelle une solution optimale ou un optimum global[PS82]. Nous avons donc la définition suivante : Définition:Une instance I d’un problème de minimisation est un couple (X, f) où X ⊆ S est un ensemble fini de solutions admissibles, et f une fonction de coût (ou objectif) à minimiser f : X → R. Le problème est de trouver s* ∈ X tel que f(s*) ≤ f(s) pour tout élément s ∈ X[PS82]. Notons que d’une manière similaire, on peut également définir les problèmes de maximisation en remplaçant simplement ≤ par ≥. L’optimisation combinatoire trouve des applications dans des domaines aussi variés que la gestion, l’ingénierie, la conception, la production, les télécommunications, les transports, l’énergie, les sciences sociales et l’informatique elle-même. 1.2 Les métaheuristiques pour la résolution Il existe deux grandes catégories des méthodes de résolution des problèmes d’optimisation combinatoires : les méthodes exactes et les méthodes approchées. Les méthodes exactes se basent sur l’énumération de l’ensemble des solutions potentielles et permettent d’obtenir la solution optimale on a par exemple l’algorithme de séparation et évaluation (branche and bound) et la programmation dynamique, la taille du problème influe rationnellement sur l’efficacité (temps d’exécution) des méthodes de cette approche, par contre on a les méthodes approchées, encore appelées heuristiques, qui permettent d’obtenir une bonne solution, qui n’est pas toujours la solution optimale, mais avec un temps raisonnable. 

Feignebaum et Feldman (1963) définissent une heuristique comme une règle d’estimation, une stratégie, une astuce, une simplification, ou tout autre sorte de système qui limite drastiquement la recherche des solutions dans l’espace des solutions possibles. Newell, Shaw et Simon (1957) précisent qu’un processus heuristique peut résoudre un problème donné, mais n’offre pas la garantie de le faire. Dans la pratique, certaines heuristiques sont connues et ciblées sur un problème particulier. Il existe d’autres méthodes qui se placent à un niveau plus général, et interviennent dans toutes les situations où l’ingénieur ne connaît pas d’heuristique efficace pour résoudre un problème donné,ces méthodes sont les métaheuristiques. En 1996, I.H. Osman et G. Laporte définissaient la métaheuristique comme « un processus itératif qui subordonne et qui guide une heuristique, en combinant intelligemment plusieurs concepts pour explorer et exploiter tout l’espace de recherche. Des stratégies d’apprentissage sont utilisées pour structurer l’information afin de trouver efficacement des solutions optimales, ou presque-optimales ». En 2006, le réseau Metaheuristic (metaheuristics.org) définit les métaheuristiques comme « un ensemble de concepts utilisés pour définir des méthodes heuristiques, pouvant être appliqués à une grande variété de problemes. Comme on voir la metaheuristique comme une « boîte à outils » algorithmique, utilisable pour résoudre différents problèmes d’optimisation, et ne nécessitant que peu de modifications pour qu’elle puisse s’adapter à un problème particulier ». Elles ontdonc pour objectif de pouvoir être programmées et testéesrapidement sur un problème [BA06 ].

Les méthodes de recherche locale

 Le principe de la recherche locale est le suivant : l’algorithme débute avec une solution initiale realizable.Sur cette solution initiale, on applique une série de modifications locales (définissant un voisinage de la solution courante), tant que celles-ci améliorent la qualité de la fonction objectif. [HS05] La figure1illustre bien le fonctionnement de l’algorithme général des méthodes de recherche locale. Le passage d’unesolution ver une autre se fait grâce à la définition de structure de voisinage qui est un élément très important dans la définition de ce type de méthode. Le voisinage d’une solution est défini en fonction du problème à résoudre. On définit l’espace de recherche comme l’espace dans lequel la recherche locale s’effectue. Cet espace peut correspondre à l’espace des solutions possibles du problème étudié. Habituellement, chaque solution candidate a plus d’une solution voisine, le choix de celle vers laquelle se déplacer est pris en utilisant seulement l’information sur les solutions voisines de la solution courante, d’où le terme de recherche locale [AK97]. D’une manièreabstraite, une recherche locale peut se résumer de la façon suivante : 1. Démarrer avec une solution. 2. Améliorer la solution. 3. Répéter le processus jusqu’à la satisfaction des critères d’arrêt.  

La descente récursive

 Le principe de la méthode de descente (dite aussi basic local search) consiste à partir d’une solution s on choisit une solution s’ qui appartient au voisinage de s, telle que s’ améliore la recherche (généralement telle que f(s’) < f(s)). On peut décider : soit d’examiner toutes les solutions du voisinage et prendre la meilleure de toutes (ou prendre la première trouvée), soit d’examiner un sous-ensemble du voisinage. La méthode de descente est la méthode de recherche locale la plus élémentaire. On peut la schématiser comme suit : En général, l’efficacité des méthodes de descente simples est très peu satisfaisante. D’abord, par définition, la recherche s’arrête au premier minimum local rencontré, c’est là leur principal défaut. Pour améliorer les résultats, on peut lancer plusieurs fois l’algorithme en partant d’un jeu de solutions initiales différentes, mais la performance de cette technique décroît rapidement. 

Le recuit simulé

 La méthode du Recuit Simulé (RS) est une technique de recherche locale inspirée du processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lents et de réchauffage ou de recuit qui tendent à minimiser l’énergie du matériel. Le recuit simulé s’appuie sur l’algorithme de Metropolis-Hastings, qui permet de décrire l’évolution d’un système thermodynamique. Par analogie avec le processus physique, la fonction à minimiser deviendra l’énergie E du système. On introduit également un paramètre fictif, la température T du système L’algorithme du recuit simulé part d’une solution donnée, et la modifie itérativement jusqu’au refroidissement du Système. Les solutions trouvées peuvent améliorer le critère que l’on cherche à optimiser, on dit alors qu’on a fait baisser l’énergie du système, comme elles peuvent le dégrader. Si on accepte une solution qui améliore le critère, on tend ainsi à chercher l’optimum dans le voisinage de la solution de départ. Contrairement autres méthodes de recherche locale, le recuit simulé peut accepter des solutions dont la qualité est moins bonne en fonction de la dégradation de la solution considérée [AK89]. 

Explication 

Initialement on donne le système une très haute température puis on le refroidit petit à petit Le refroidissement du système doit se faire très lentement pour avoir l’assurance d’atteindre un état d’équilibre à chaque température T.Le voisinage N(s) d’une solution s. s’appartient à l’ensemble des états atteignables depuis l’état courant en faisant subir des déplacements élémentaires aux atomes du système physique.A chaque itération, une seule solution voisine s’est générée et elle est acceptée si elle est meilleure que la solution courante s dans le cas contraire on a les cas :si T grande, exp(-∆Ε/T) est de l’ordre de 1, on garde toujours le mouvement, même il est mauvais.si T très petit, exp(-∆Ε/T) est de l’ordre de 0, donc les mouvements qui augmentent l’énergie (la différence) sont disqualifiés.Méthode : on tire au hasard dans l’intervalle [0,1[, si le nombre est <exp(-∆Ε/T) , on garde sinon on jette.La meilleure solution trouvée est mémorisée dans la variable s*.La méthode recuite simulée donne des très bons résultats pour le problème de voyageur de commerce mais pas pour le problème d’affectation ; leur performance est liée fortement au schéma de refroidissement [Wid01].Les avantages de recuit simulé:Parmi les avantages de la méthode on cite Traite les fonctions de coût avec les degrés tout à fait arbitraires de non linéarité, la discontinuité, et l’imprévisibilité.Processus assez arbitraire sur les conditions limites et les contraintes imposées sur les fonctions de coût.Simple à implémenter.Garantie Statistique de trouver une solution optimale.Les inconvénients de recuit simuléLa méthode comprend quelques inconvénients parmi lesquelles :le non déterminisme.Difficulté de choisir les paramètres efficaces ; par exemple le schéma Le compromis entre la vitesse et l’optimisation.