Contenus

Optimisation combinatoire

L’optimisation combinatoire, aussi appelée optimisation discrète, est une branche de l’optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l’algorithmique et la théorie de la complexité. L’optimisation combinatoire consiste à trouver dans un ensemble un sous-ensemble contenant les « meilleures solutions ».

Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d’essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure. Cependant, l’explosion combinatoire de solutions possibles de certains problèmes mathématiques ne permettent pas d’obtenir de solution en un temps « humain ».

Quelques problèmes d’optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme de programmation dynamique ou en montrant que le problème peut être formulé comme un problème d’optimisation linéaire en variables réelles. Dans la plupart des cas, le problème est Np-difficile et, pour le résoudre, il faut faire appel à des algorithmes adaptés.

En pratique, la complexité physiquement acceptable n’est souvent que polynomiale. On se contente alors d’avoir une solution approchée au mieux, obtenue par une heuristique ou une méta-heuristique. Il est important de noter que certaines de ces méthodes fournissent des optimaux globaux, la différence avec les méthodes exactes est le fait de ne pas avoir de de preuve formelle (preuve mathématique ou de finalité) de son optimalité globale.

Arbre des solutions

Soit E l’ensemble des solutions des problèmes. Il est supposé discret et fini. L’énumération des solutions se représente en arbre. Tous les éléments de E sont séparés en n sous-ensemble non vides disjoints contenant chacun une partie de l’ensemble des solutions. Par exemple, l’ensemble peut être séparé en deux dans le problème du sac à dos si on prend ou non un élément x_k dans le sac.

L’opération peut être réitérée pour chaque sous-ensemble jusqu’à ce que chaque ensemble ne contienne qu’un seul élément. Pour l’exemple du sac à dos, chaque sous-ensemble est séparé jusqu’à arriver à la décision sur le dernier élément.

La racine de l’arbre est E, les fils sont les sous-ensembles etc. comme le présente le schéma suivant :

Techniques de résolution

Exacte

Ces méthodes donnent une garantie de trouver la solution optimale pour une instance de taille finie dans un temps limité et de prouver son optimalité.

Heuristique

Lorsque la complexité d’un problème est exponentielle ou présente une explosion combinatoire, l’utilisation d’heuristiques est recommandée. Il s’agit d’une méthode fournissant rapidement une « bonne » solution au problème. Cette solution approchée peut ensuite fournir un point de départ pour l’utilisation d’une méthode exacte (comme le coin Nord-Ouest pour le problème de transport). Tous les algorithmes gloutons et naïfs sont des heuristiques.

Il est à noter que les heuristiques sont construites pour résoudre un problème donné, et ne sont pas utilisables dans d’autres conditions contrairement aux méta-heuristiques. L’heuristique est évaluée selon trois critères :

Qualité du résultat : l’heuristique est confrontée aux résultats optimaux pour un ensemble de valeurs du problème donné (on parle de benchmark). La qualité de la solution peut soit être une distance à la solution optimale, soit une probabilité de l’atteindre.
Cout de l’heuristique : complexité en temps et en espace.
Domaine d’application : le domaine d’admissibilité de l’ensemble des variables.

Le nombre d’heuristique pour un problème donné sont nombreuses, il est donc important d’en fournir une rapide et fournissant de « bons » résultats.

Méta-heuristique

Les méta-heuristiques ont un niveau d’abstraction plus élevé que les heuristiques puisqu’il s’agit de méthode pouvant s’adapter à un problème donné. Ainsi, les méthodes peuvent s’appliquer à des problèmes variés (sous forme de boîte noire) sans pour autant modifier leur fonctionnement. On parle aussi d’heuristique généraliste.

Il existe deux sortes de méta-heuristique : à population (a) ou à parcours (b). La plupart des algorithmes n’ont pas de population déterminée, il est alors possible d’utiliser l’algorithme pour un parcours ou une population.

Les deux sortes fonctionnent avec le même processus en quatre étapes :

Voisinage : le voisinage d’une solution est un sous-ensemble de solutions atteignables par une transformation de la solution initiale (par permutation, par extension, par mutation, par éjection, etc).
Exploration : l’exploration consiste à récolter les données sur l’ensemble du voisinage.
Exploitation : l’exploitation se sert des informations récoltées pour définir les zones « intéressantes » de l’espace de recherche formée par le voisinage.
Mémoire : la mémoire prend en compte l’apprentissage et permet de déterminer les zones susceptibles de posséder un optimum global. Si les nouvelles solutions ou que les critères d’arrêt ne permettent plus d’améliorer la solution, l’algorithme s’arrête. Sinon, retour à l’étape 1. Certain algorithme ne fonctionnent qu’avec des critères d’arrêt, nous parlons alors de méta-heuristiques sans mémoire.