MÉTAHEURISTIQUES D’OPTIMISATION

Métaheuristiques pour l’optimisation mono-objectif difficile

Problème d’optimisation

Un problème d’optimisation au sens général est défini par un ensemble de variables, une fonction objectif f et un ensemble de contraintes d’égalité (ou d’inégalité) que les variables doivent satisfaire. L’ensemble des solutions possibles du problème forme l’espace de recherche E, où chaque dimension correspond à une variable. L’espace de recherche E est fini puisque le décideur précise exactement le domaine de définition de chaque variable entre autres pour des raisons de temps de calcul. Suivant le problème posé, nous cherchons à minimiser ou maximiser la fonction objectif f . Un problème d’optimisation peut être statique ou dynamique (i.e. la fonction objectif change avec le temps), monoobjectif ou multi-objectif (i.e. plusieurs fonctions objectifs doivent être optimisées) et avec ou sans contraintes.

Ainsi, un problème d’optimisation peut être, par exemple, à la fois continu et dynamique. Il existe de nombreuses méthodes déterministes (ou exactes) permettant de résoudre certains types de problèmes d’optimisation et d’obtenir la solution optimale du problème, en un temps raisonnable. Ces méthodes nécessitent que la fonction objectif présente un certain nombre de caractéristiques telles que la convexité, la continuité ou la dérivabilité. Nous pouvons citer, parmi les méthodes les plus connues, les méthodes de programmation linéaire [Schr 98], quadratique [Noce 00] et/ou dynamique [Bert 95], la méthode de Newton [Noce 00], la méthode du simplex [Neld 65] ou encore la méthode du gradient [Avri 76].

Optimisation difficile

Les méthodes de résolution exacte ne sont pas adaptées à toutes les problématiques, et donc certains problèmes sont trop complexes à résoudre par ces méthodes. Parmi ces 5 Métaheuristiques d’optimisation : état de l’art problématiques, nous pouvons citer l’existence de discontinuités, l’absence de convexité stricte, la non-dérivabilité, la présence de bruit ou encore la fonction objectif peut ne pas être définie précisément (e.g. quand c’est un cout). En outre, les méthodes de résolution exacte peuvent avoir un temps de résolution trop long.

Dans ce cas, le problème d’optimisation est dit difficile, car aucune méthode exacte n’est capable de le résoudre en un temps raisonnable. Il est alors nécessaire d’avoir recours à des heuristiques de résolution dites méthodes approchées, qui fournissent un résultat sans garantie de l’optimalité. L’optimisation difficile peut se diviser en deux types de problèmes : les problèmes à variables discrètes et les problèmes à variables continues : – Un problème d’optimisation à variables discrètes consiste à trouver, dans un ensemble discret, une solution réalisable. Le problème majeur réside ici dans le fait que le nombre de solutions réalisables est généralement très élevé, donc il est très difficile de trouver la meilleure solution dans un temps « raisonnable ».

Les problèmes à variables discrètes rassemble les problèmes de type NP-complets, tels que le problème du voyageur de commerce. L’utilisation d’algorithmes d’optimisation stochastiques, tels que les métaheuristiques, permettant de trouver une solution approchée en un temps raisonnable est donc courante. – Dans le deuxième type, les variables du problème d’optimisation sont continues. C’est le cas par exemple des problèmes d’identification, où l’on cherche à minimiser l’erreur entre le modèle d’un système et des observations expérimentales.

Ce type de problèmes est moins formalisé que le précédent, mais un certain nombre de difficultés sont bien connues, comme l’existence de nombreuses variables présentant des corrélations non identifiées, la présence de bruit ou plus généralement une fonction objectif accessible par simulation uniquement. En effet, la grande majorité des métaheuristiques existantes ont été créées pour résoudre des problèmes à variables discrètes [Dro 03]. Cependant, la nécessité croissante de méthodes pouvant résoudre ce type de problèmes a poussé les chercheurs à adapter leurs méthodes au cas continu. Il est à noter qu’il existe des problèmes à variables mixtes (i.e. le problème présente à la fois des variables discrètes et continues).