Problèmes d’optimisation mono-objectif

Problèmes d’optimisation mono-objectif

Résoudre un problème d’optimisation consiste à trouver une solution, appartenant à un espace de recherche X, qui minimise ou maximise un critère particulier f. Dans la plupart des cas, l’optimum découvert n’est pas unique. Ainsi il existe un ensemble de solutions minimisant ou maximisant le critère considéré. Dans la suite de ce document, nous aborderons les problèmes d’optimisation essentiellement sous l’aspect minimisation, maximiser une fonction f étant équivalent à minimiser -f.

De plus, un problème d’optimisation peut présenter des contraintes d’égalité et/ou d’inégalité sur les solutions candidates ∈ . Nous pouvons alors décrire formellement un problème d’optimisation comme suit : Minimiser ( ) Sous les contraintes ( ) avec i de 1..m (m le nombre de contraintes) Avec ∈

Vocabulaire et définitions

Dans cette section, nous détaillons les principaux concepts, hypothèses et notations sur lesquels nous nous sommes basés dans notre étude.

Vecteur des variables ou vecteur de décision

Il est formé par les différentes variables du problème, qui peuvent être de natures diverses. Ces variables expriment des données qualitatives ou quantitatives. 5 Considérons un problème ayant n variables. Dans ce cas le n-uplet ( x x n ) , formé par x …. 1 les variables du problème, définit son vecteur de variables . 2 Ce vecteur peut prendre plusieurs valeurs définissant chacune une solution éventuelle.

Espace d’état

Il est défini par les domaines de définition des différentes variables du problème. Dans la plupart des problèmes, cet espace est fini.

Fonction objectif

Elle représente le but à atteindre par le décideur. C’est le nom donné à la fonction f (appelée aussi fonction de coût ou critère d’optimisation).

L’ensemble des contraintes

Il définit des conditions supplémentaires sur l’espace d’état que les variables doivent satisfaire. Ces contraintes sont souvent sous forme d’égalité ou d’inégalité et permettent de limiter l’espace de recherche. Les contraintes seront notées : Ci( ), avec i de 1 à m, avec m le nombre de contraintes.

Problèmes d’optimisation multiobjectif

La plupart des problèmes d’optimisation réels sont décrits à l’aide de plusieurs objectifs ou critères souvent contradictoires devant être optimisés simultanément. Alors que, pour les problèmes n’incluant qu’un seul objectif, l’optimum cherché est clairement défini, celui-ci reste à formaliser pour les problèmes d’optimisation multiobjectif. En effet, pour un problème à deux objectifs contradictoires, la solution optimale cherchée est un ensemble de points correspondant aux meilleurs compromis possibles pour résoudre ce problème.

Les problèmes d’optimisation multiobjectif sont une généralisation à n fonctions objectif des problèmes d’optimisation classiques. Ils sont définis formellement comme suit : 6 7 D’après cette définition, il est clair que l’optimum n’est plus une simple valeur comme pour les problèmes à un objectif, mais un ensemble de points, appelé l’ensemble des meilleurs compromis ou le front de Pareto.

Dans le cas multiobjectif, le concept d’optimum n’est pas le même que dans le cas mono objectif. En effet, on n’est plus ici à la recherche d’un unique optimum global, mais plutôt d’une surface de solutions qui offrent un bon compromis entre les différents objectifs.

Relations d’ordre et de dominance

Comme la solution optimale est une multitude de points, il est vital, pour identifier ces meilleurs compromis, de définir une relation d’ordre entre ces éléments. Dans le cas des problèmes d’optimisation multiobjectif, ces relations d’ordre sont appelées relations de dominance. Plusieurs relations de dominance ont déjà été présentées. Mais la plus célèbre et la plus utilisée est la dominance au sens de Pareto.

C’est cette relation de dominance que nous allons définir et utiliser dans cette thèse. De manière à définir clairement et formellement cette notion, les relations =, ≤ et < usuelles sont étendues aux vecteurs. Définition 2 (Principe de dominance): Soient u et v deux vecteurs de même dimension n u=v ssi ∀ ∈ 1,…, , = u≤v ssi ∀∈ 1,…, , ≤ u et ≥ sont définies de manière analogue. Les relations définies précédemment ne couvrent pas tous les cas possibles.

En effet, il est impossible de classer les points a = (1, 2) et b = (2, 1) à l’aide d’une de ces relations. Contrairement aux problèmes à un seul objectif où les relations usuelles <, ≤, . . . suffisent pour comparer les points, elles sont insuffisantes pour comparer des points issus de problèmes multiobjectif.

Nous définissons donc maintenant la relation de dominance au sens de Pareto permettant de prendre en compte tous les cas de figures rencontrés lors de la comparaison de deux points (ici des vecteurs). Définition 3 ( ɛ-dominance) : Soient u et v deux vecteurs de même dimension n u ɛ-domine v si et seulement si : ui ≤ ɛvi ∀i ∈ {1, …,n}. Cette relation est notée u ≤v. Minimiser ( )= ( ( ), ( ),…, ( )) (k le nombre d’objectifs) Sous les contraintes ( ) avec i de 1..m (m le nombre de contraintes).