Optimisation combinatoire multiobjectif

Optimisation combinatoire multiobjectif 

Notions de base et définitions

Optimisation mono-objectif

La recherche opérationnelle s’est dans un premier temps adressée aux problèmes d’optimisation mono-objectif (Optimization Problem – OP). Aujourd’hui encore de nombreux travaux de recherche concerne ce type de problèmes, notamment en proposant de nouvelles théories évolutionnaires ou encore des approches coopératives. De plus, dans le cas de l’optimisation multiobjectif certaines approches visent à réduire le nombre d’objectifs pour appliquer les algorithmes, souvent plus simples, disponibles pour résoudre les problèmes d’optimisation mono-objectif.

Définition 6 (Problème d’optimisation mono-objectif) Dans le cas général, un problème d’optimisation mono-objectif consiste à maximiser (ou minimiser) une fonction f(x) : OP  max z = f(x) tel que : x ∈ X (3.1) x est ici le vecteur de n variables de décision x = (x1, x2, …, xn) t , avec t l’opérateur de transposition. X désigne l’espace de recherche regroupant toutes les solutions réalisables.

Définition 7 (Optimum global) Etant donné un problème d’optimisation, la solution x ∗ est dite maximum global ssi : ∀x ∈ X : f(x ∗ ) ≥ f(x) (3.2) Souvent, lors de la résolution de problèmes réels, il n’est pas possible de garantir qu’une solution est l’optimum global sur l’ensemble de l’espace de recherche. On explore alors un sous-espace X1 ⊂ X de l’espace de recherche pour trouver l’optimum global x ∗ 1 de X1, vérifiant f(x ∗ ) ≥ f(x ∗ 1 ) toujours pour un problème de maximisation. Nous le voyons ici, le contexte mono-objectif permet toujours d’identifier la solution optimale, au moins sur X1. Lorsque le problème d’optimisation devient multiobjectif, nous verrons qu’il en est tout autre chose.

Formulation d’un problème d’optimisation multiobjectif

La formulation générale d’un problème d’optimisation multiobjectif (Multiobjective Optimization Problem – MOP) est de la forme : MOP    max z = f(x) où f(x) = (f1(x), f2(x), …, fn(x)) tel que : x ∈ X (3.3) avec n ≥ 2 le nombre de fonctions objectif, X l’ensemble des solutions réalisables dans l’espace de décision, x = (x1, …, xk) ∈ X est le vecteur regroupant les variables de décision.

Dans le cadre de problèmes combinatoires X est un ensemble discret. De plus soit Z ⊆ R n tel que Z = f(X), Z est l’ensemble des solutions réalisables dans l’espace objectif. L’unique différence avec les problèmes d’optimisation mono-objectif réside dans le fait que f(x) ne prend plus ses valeurs dans R mais dans R n .

Espace de décision vs espace objectif

L’espace de décision regroupant les variables x = (x1, …, xk) ∈ X est de dimension k. Il s’agit de l’espace dans lequel sont représentées les solutions. Figure 3.1 – Espace de décision / espace objectif L’espace objectif, également appelé espace des critères, de dimension n permet de projeter l’évaluation des solutions. La Figure 3.1 illustre ces deux espaces, avec à gauche l’espace de décision de taille k = 3 dans lequel est représentée la solution x.

A droite se trouve l’évaluation correspondante pour n = 2 fonctions à optimiser. 3.2. Notions de base et définitions 83 Sur cette figure représentant un problème de maximisation z = f(x) appartient au front de Pareto : x est une solution Pareto optimale. Dans la plupart des situations en optimisation le choix d’une solution se fait sur la base de l’étude de l’espace objectif. Il apparait cependant parfois intéressant d’observer également les solutions dans l’espace de décision.

Optimisation combinatoire et métaheuristiques

Le cadre dans lequel s’inscrit les travaux de cette thèse concerne l’optimisation combinatoire. La fonction à optimiser, souvent appelée fonction coût ou fonction objectif, est définie sur un ensemble discret. Il s’agit donc de trouver l’optimum (maximum ou minimum) parmi un ensemble fini. Bien que dans la théorie il suffirait d’énumérer toutes les solutions possibles et de retenir la meilleure, il n’est bien souvent matériellement pas possible d’effectuer cet inventaire exhaustif dans un temps « raisonnable ».

Le temps de calcul constitue alors une contrainte forte à prendre en compte. Selon le problème considéré, une durée acceptable pour que le programme propose une solution sera de quelques millisecondes – dans une situation d’urgence à bord d’un véhicule par exemple – à quelques semaines lorsqu’il s’agit de planifier une nouvelle ligne de production dans un site industriel par exemple