Optimisation multiobjectif et ordonnancement de workflows dans le cloud computing

Optimisation multiobjectif

Concepts et définitions Nous présentons, dans cette section, les principaux concepts, définitions et notations liées au domaine de l’optimisation multiobjectif, notamment, la relation de dominance de Pareto, l’optimalité Pareto et le front de Pareto. 

Formulation générale d’un problème d’optimisation multiobjectif

Définition 2.1 Un problème d’optimisation combinatoire multiobjectif, MOP (MultiObjective combinatorial Optimization Problem) peut être défini par : (2.1) où n est le nombre d’objectifs (n ≥ 2), Le vecteur représente le vecteur de k variables de décision, X représente l’ensemble de solutions réalisables dans l’espace décisionnel. Dans le cas combinatoire, X est un ensemble discret.

À chaque solution x X est associé un vecteur objectif z Z sur la base d’un vecteur de fonctions f : X → Z tel que z = f(x) = ( . L’ensemble Z = f(X) représente les points réalisables dans l’espace objectif. La figure 2.1 présente la liaison entre l’espace décisionnel et l’espace objectif. Sans perte de généralité, nous supposerons par la suite que Z ⊆ R n et que les fonctions objectif sont à minimiser. Contrairement à l’optimisation monoobjectif, la solution d’un problème multiobjectif n’est pas unique, mais c’est un ensemble de solutions non dominées, connu comme l’ensemble des solutions Pareto optimales. Figure 2.1. Espace décisionnel et espace objectif d’un MOP (cas de deux variables de décision X1 et X2 et de deux fonctions objectif f1 et f2).

Notions de dominance

Dans le cadre de l’optimisation multiobjectif, le décideur raisonne souvent en termes d’évaluation d’une solution sur chaque critère et se place dans l’espace objectif. Néanmoins, contrairement à l’optimisation monoobjectif où il existe une relation d’ordre total entre les solutions réalisables, il n’existe généralement pas une solution unique qui serait à la fois optimale pour chaque objectif, en raison de la nature conflictuelle des objectifs. Ainsi, une relation d’ordre partiel, appelée relation de dominance, est généralement définie.

Définition 2.2 (Dominance de Pareto). Un vecteur objectif z Z domine un vecteur objectif z′ Z si les deux conditions suivantes sont vérifiées : ′ (2.2) ′ (2.3) Si z domine z′, cette relation sera notée . Par extension, une solution x X domine une solution x′ X, notée , ssi . La figure 2.2 illustre la définition de la notion de dominance. Il existe des relations de dominance autres que celle de Pareto. Elles sont énoncées ci-dessous. Définition 2.3 (Vecteur non-dominé) Un vecteur objectif z Z est non-dominé ssi (voir figure 2.2).

Définition 2.4 (Dominance faible) Un vecteur objectif z Z domine faiblement un vecteur objectif z′ Z ssi . Cette relation sera notée . Définition 2.5 (Dominance stricte) Un vecteur objectif z Z domine strictement un vecteur objectif z′ Z ssi . Cette relation sera notée . Définition 2.6 (ε-dominance) Un vecteur objectif z Z ε-domine un vecteur objectif z′ Z avec ε >1, ssi .

Cette relation sera notée . 2.2.1.3. Optimalité de Pareto La définition de solution Pareto optimale provient directement du concept de dominance. Le concept a été proposé initialement par F.Y. Edgeworth (Edgeworth, 1881) et généralisé par V. Pareto (Pareto, 1896). Définition 2.7 (solution Pareto optimale) Une solution x X est Pareto optimale (ou nondominée) ssi ′ ′ .