Méthodes exactes pour les problèmes combinatoires bi-objectif

Optimisation combinatoire multi-objectif

 Ce chapitre traite de l’optimisation combinatoire multi-objectif où plusieurs fonctions objectif doivent être optimisées simultanément. À la fin du dix-neuvième siècle, l’économiste Vilfredo Pareto (1896) a défini l’optimum dit de Pareto comme un état de société où l’on ne peut améliorer le bien-être d’un individu sans détériorer celui d’un autre. Par la suite, cette définition a amené les notions mathématiques de dominance de Pareto et de front de Pareto utilisées dans l’optimisation multi-objectif. Depuis lors, cette branche de l’optimisation combinatoire est de plus en plus étudiée puisqu’elle reflète de véritables enjeux industriels. En effet, les problèmes réels sont souvent représentés par un unique objectif, même s’ils possèdent de nombreuses caractéristiques qui seraient mieux représentées par l’utilisation de plusieurs fonctions objectif. Cependant, la présence de multiples objectifs entraîne une complexité accrue par rapport aux modèles mono-objectif. 6 Chapitre 1. Optimisation combinatoire multi-objectif : état de l’art Ce chapitre introduit les concepts de base de l’optimisation multi-objectif en Section 1.2. Ensuite, les méthodes exactes pour résoudre les problèmes multi-objectif sont présentées en Section 1.3. De multiples méthodes approchées sont proposées dans la littérature (AbdelBasset et al. (2018)), mais elles ne seront pas traitées dans ce manuscrit. Enfin, la conclusion est en Section 1.4. 

Notions de base 

Dans cette section, les définitions et les notions de base sont abordées. En premier lieu, la partie 1.2.1 donne la définition de l’optimisation combinatoire multi-objectif. Ensuite, les caractérisations des solutions d’un problème multi-objectif sont présentées, ainsi que les bornes supérieures et inférieures. Enfin, la dernière partie 1.2.4 aborde la notion d’hypervolume pour évaluer les bornes. 

Principe 

En optimisation combinatoire mono-objectif, le problème consiste à déterminer l’élément optimisant un critère parmi un ensemble fini ordonnable d’éléments. Cet élément est la solution optimale et la valeur de son critère est l’optimum. Dans le domaine multiobjectif, les problèmes visent à optimiser p objectifs simultanément et ils sont définis comme suit : (MOP) ( min c(x) = (c 1 (x), c2 (x), .., cp (x)) t.q. x ∈ X Dans cette formulation, les critères sont représentés par un vecteur de fonctions objectif c de taille p qui doit être optimisé. L’ensemble X ⊆ N n , où n est le nombre de variables, représente l’espace des solutions. Les contraintes et l’espace de définition du problème sont implicitement données par la définition de X . Tout élément x de X est une solution du problème. L’image de X par c forme l’espace des objectifs Y ⊆ N p . Tout élément y de Y est l’image d’une solution x ∈ X telle que y i = c i (x), ∀i ∈ [[1; p]] et est un point dans l’espace des objectifs. Pour alléger les notations, les coûts des objectifs d’un point y ∈ Y, associé à la solution x ∈ X , peuvent être représentés avec les notations y i , i ∈ [[1; p]] au lieu des coûts de la solution c i (x), i ∈ [[1; p]]. La Figure 1.1 montre un exemple de la correspondance entre X et Y. L’ensemble des solutions réalisables d’un problème multi-objectif combinatoire est un ensemble fini ayant pour image un ensemble, potentiellement non convexe, de points dans l’espace des objectifs. L’optimum est donc un ensemble de points qui peuvent être caractérisés de plusieurs manières. 1.2. Notions de base 7 x 1 x 2 • ♦ (a) Espace des solutions. c 1 c 2 • ♦ (b) Espace des objectifs. Figure 1.1: Correspondance entre l’espace des solutions et l’espace des objectifs dans un problème bi-objectif pour n = 2, p = 2, c 1 (x) = 2x 1 + x 2 et c 2 (x) = x 1 + x 2 , x ∈ X .

 Caractérisation des solutions 

Pour pouvoir comparer les solutions obtenues en résolvant (MOP), la Définition 1 de dominance de Pareto est utilisée. Définition 1. Wicksell et al. (1913) Soit x et x 0 deux solutions de X . — x domine faiblement x 0 , noté x 5 x 0 ⇔ c i (x) ≤ c i (x 0 ) ∀i ∈ [[1; p]] — x domine x 0 , noté x ≤ x 0 ⇔    c i (x) ≤ c i (x 0 ) ∀i ∈ [[1; p]] c i (x) < ci (x 0 ) ∃i ∈ [[1; p]] — x domine strictement x 0 , noté x < x0 ⇔ c i (x) < ci (x 0 ) ∀i ∈ [[1; p]] Les Définitions 2, 3, 4 et 5 caractérisent les solutions recherchées dans un problème multi-objectif et sont illustrées dans la Figure 1.2. Définition 2. Une solution x ∈ X est dite solution efficace (ou Pareto-optimale) s’il n’existe pas de solution x 0 ∈ X , x 0 6= x, telle que x 0 ≤ x. Une solution x ∈ X est dite solution faiblement efficace (ou faiblement Pareto-optimale) s’il n’existe pas de solution x 0 ∈ X , x 0 6= x, telle que x 0 < x. Définition 3. Un point y ∈ Y est dit point non dominé si la solution x ∈ X telle que c(x) = y est une solution efficace. Un point y ∈ Y est dit point faiblement non dominé si la solution x ∈ X telle que c(x) = y est une solution faiblement efficace. Définition 4. Un point non dominé y ∈ Y est dit supporté s’il est sur l’enveloppe convexe de Y. Un point non dominé y ∈ Y est dit non supporté s’il est à l’intérieur de l’enveloppe convexe de Y. Définition 5. Un point non dominé supporté y ∈ Y est dit extrême s’il est un point extrême de l’enveloppe convexe de Y. 8 Point supporté non extrême ◦ Point non dominé non supporté ♦ Point faiblement non dominé × Point dominé × Enveloppe convexe de Y Front de Pareto Figure 1.2: Différentes caractérisations des points de l’espace des objectifs d’un problème bi-objectif. Les points non dominés supportés qui ne sont pas des points extrêmes de l’enveloppe convexe de Y sont appelés non extrêmes. Dans ce manuscrit, résoudre (MOP) revient à trouver l’ensemble des points non dominés du problème, supportés et non supportés, noté YN . Un même point y ∈ Y peut être associé à plusieurs solutions distinctes de X . De ce fait, le nombre de solutions efficaces est plus grand que le nombre de points non dominés. Ainsi, la Définition 6 permet de distinguer deux ensembles complets. Définition 6. Hansen (1980) L’ensemble complet minimal de (MOP) est l’ensemble des points non dominés avec au moins une solution efficace associée par point non dominé. L’ensemble complet maximal est l’ensemble des points non dominés avec toutes les solutions associées par point. Note 1. Dans un problème comportant deux fonctions objectif à minimiser, les points non dominés de YN peuvent être ordonnés selon un ordre naturel qui est la valeur croissante du premier objectif c 1 , pour un problème de minimisation. Deux points non dominés y et y 0 sont dits consécutifs s’il n’existe pas de point non dominé yˆ tel que y 1 < ˆy 1 < y01 (et par conséquent y 2 > yˆ 2 > y02 ). La Figure 1.3 présente l’ordre naturel entre les points non dominés yi , i ∈ {1, .., 5} d’un problème bi-objectif avec minimisation des deux fonctions objectif. Les points yi et yi+1 pour i ∈ {1, .., 5} sont dits consécutifs. La notion de dominance de Pareto permet de définir les solutions d’un problème multiobjectif. Cependant, cette relation de dominance est un ordre partiel.