Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Table des matières
1 optimisation combinatoire
1
...


4

1
...
1

Définition d’un problème
...
1
...


4

1
...


5

1
...


7

1
...


8

1
...


9

1
...
1

Le voyageur de commerce
...
5
...


10

2 Optimisation multi-objectif

12

2
...


12

2
...


13

2
...


14

2
...
1

dominance
...
3
...


14

2
...


16

2
...
1

Optimalité globale au sens de Pareto
...
4
...


16

2
...
3

La surface de compromis


...
4
...


17

2
...


19

2
...


21

2
...
1

a priori
...
6
...


23

2
...
3

interactive


...


24

2
...
4

1

2
...
5

Approche par traitement séparé des objectifs (approche non Pareto)
...
6
...


27

2

Introduction

3

Chapitre 1
optimisation combinatoire
1
...
1
...
Donc il est conçu comme une relation
Π ⊆ × s entre les entrées ou instances, et les sorties ou solutions
...
De même, la solution
d’une instance d’un tel problème est émise dans ce format
...


1
...
2

Type des problèmes

Les problèmes peuvent être classés selon les propriétés de l’ensemble des solutions :

problème de décision
C’est un problème dont la réponse est tout simplement OUI ou NON
...

L’algorithme doit être en mesure de fournir la solution si celle-ci existe
...


4

1
...
Ces problèmes occupent actuellement une place de choix dans la communauté scientifique
...

Un problème d’optimisation peut être défini par :

- L’espace d’état
Qui est l’ensemble de domaines de définition des variables du problème
...

• Entière ou booléenne : ont parle alors des problèmes discret ou bien combinatoire
...
Elle définit
un espace de solutions au problème
...

x
g x
x
− −
→(→) et →(→) représentent respectivement m contraintes d’inégalité et p contraintes
− −
ici les vecteurs g x
h x
d’égalité
...

• Plusieurs ⇒ multi-objectif
...
Ces
contraintes sont souvent des contraintes d’inégalité ou d’égalité et permettent en général de limiter l’espace de recherche
...

• si non ⇒ problème sans contraintes
...

• Fonction quadratique des variables de décision ⇒ quadratique
...

C’est le nom donné à la fonction f (on l’appelle encore fonction de coût ou critère d’optimisation)
...
Il est noté υ(s) et une solution s’∈ υ(s) est dite voisine de s
...
En particulier, à partir d’une solution donnée, on peut établir
plusieurs structures de voisinage selon la transformation que l’on s’autorise, celle-ci étant définie
comme une application υ :S → P(S)
...

Minimum global
−
Un « point »→∗ est un minimum global de la fonction f si on a :
x
→∗ ) ...

−
−
−
−
−
−
−
f( x
x
x
x
x
x
x

6

Minimum local faible
−
Un « point » →∗ est un minimum local faible de la fonction f si on a :
x
→∗ ) ≤ f (→) ∀x ∈ υ → et →∗ = → , où υ(→∗ ) définit un « voisinage de →∗
...
1 – Les différents Minima

1
...
La solution c’est un résultat de faire combiner
ces contraintes ensemble d’une manière qu’on maximise quelques uns et on minimise les autres,
ces contraintes ont une caractéristique primordiale, c’est que chaque contrainte influe sur les
autres soit quand on minimise sa valeur ou on la maximise, dans un autre terme on dit que les
contraintes sont conflictuelles
...
Si on maximise la première contrainte (une
bonne voiture) on va avoir un prix maximale, dans le contraire on va aboutir à une mauvaise
voiture mais avec un prix minimale dans les limites ; on constate dans cet exemple que c’est
difficile d’arranger ces deux contraintes dans nos besoins
...
2 – Une figure illustrant un problème combinatoire
...
4

Domaine d’application de l’OC

Les problèmes d’optimisation sont utilisés pour modéliser de nombreux problèmes appliqués
dans :
La conception des systèmes de l’industrie
...

Militaire (gestion des ressources, logistique)
...

Les secteurs économiques (la production manufacturière, les transports et la gestion du
personnel)
...

Civil (services publics, hôpitaux, transport public, informatique)
...

Le traitement d’images
...

8

La conception d’emplois du temps, etc
...
5

Exemple de problèmes combinatoires

1
...
1

Le voyageur de commerce

Parmi les problèmes les plus célèbres et connus dans le domaine d’optimisation multiobjectifs le problème de Voyageur de Commerce
...

Le Problème du Voyageur de Commerce (Traveling Salesman Problem, TSP) possède une formulation élémentaire : étant données n villes, quel chemin doit-on emprunter pour les parcourir
tout en minimisant la longueur totale du trajet ? Il doit rendre régulièrement visite aux clients de
son département
...
Il finit par s’adresser à un informaticien pour
qu’il lui rédige un programme permettant de minimiser ses frais de route
...

Cette première formulation trop vague ne permet guère de reconnaître le vrai problème à
résoudre
...
Une deuxième approche consiste donc à essayer de dégager des informations supplémentaires sur le champ de données en entrée
...

Des frais de logement pour la nuit
...
Si dans une troisième approche l’informaticien demande la raison des
différences de frais, il apprend que l’ordre dans lequel les différentes localités sont visitées joue un
rôle non négligeable, puis, la question est de savoir « s’il y a des clients qu’il a visités plus souvent
que d’autres ? »
...

C’est le représentant de commerce qui spécifie enfin qu’il rend visite exactement une fois par
mois à chaque client de sa région, qu’une tournée de visites a une durée de cinq jours, et qu’il
passe les nuits dans des hôtels à même prix
...
L’informaticien finit par formuler le problème du voyageur de commerce de la ma9

nière suivante :
« Une fois par mois, à partir de son domicile, un représentant de commerce rend visite à sa
clientèle qui est répartie sur N localités différentes (y compris son propre domicile) de sa région
...
C’est ainsi que son trajet
se trouve divisé en exactement N parties différentes et que la totalité des frais de route s’obtient
par addition des frais de route individuels, c
...
des différentes parties
...
Le problème consiste à déterminer le tour dont la somme des frais de
route individuels est minimale
...
»
Par cette formulation de problème on déduit qu’il appartient à la classe des problèmes dits NP,
ce qui signifie qu’il n’existe pas d’algorithme fournissant le chemin optimal en temps polynomial
...


Figure 1
...
5
...
Description
Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème
d’optimisation combinatoire appartenant à la classe des problèmes NP-complets
...
Les objets mis
dans le sac à dos doivent maximiser le profit total, sans dépasser le poids maximum
...
Formulation
Étant donné un ensemble de n objets chacun ayant un certain poidswi et certains profits
(coût)pj , et soit C un réel qui représente la charge (poids, profits, capacité) maximale que l’on
peut emporter dans un sac à dos
...
c M ax
w i xi ≤ C




i=1

xi ∈ {0, 1} ∀i ∈ {1,
...
La contrainte
exprime le fait que les objets sélectionnés doivent tenir dans la capacité C du sac à dos
...

Certaines hypothèses pèsent sur les coefficients wi , pi et C :
pi , wi et C sont des entiers positifs
...

0alors que ceux dont le poids dépasse la capacité du sac peuvent être supprimés
...

i=1

11

Chapitre 2
Optimisation multi-objectif
2
...
La difficulté principale d’un problème multiobjectif est qu’il n’existe pas de définition de la
solution optimale
...
Ce besoin
d’optimisation vient de la nécessité de l’ingénieur de fournir à l’utilisateur un système qui réponde
au mieux aux cahier des charges
...

consommer le minimum d’énergie (coût de fonctionnement)
...

En résumant ces notions mathématique représentant un problème d’optimisation multi-objectif
par la formule suivent :

Figure 2
...


2
...
, xn )
...

A chaque point de l’espace de décision est associé un point de l’espace objectif désignant l’adéquation de la solution associée
...
L’optimisation du vecteur objectif f revient soit :
A minimiser l’ensemble de toutes les fonctions objectifs
...

Minimiser certaines fonction fonction objectif tout en maximisant d’outres
...
2 – representation d’un problème multi-objectif
13

La recherche de la solution optimale pour un POM soulève quelques réflexions par rapport
à la notion même de l’optimalité
...
Les problèmes
multi-objectifs ont en général un ensemble de solutions optimale dont les valeurs des fonctions
sont en fait les meilleurs compromis possible dans l’espace des fonctions objectif
...


2
...
3
...
, M }
...
, M } tel que fm (X (i) ) < fm (X (i) )
...
3 – Exemple de dominance

2
...
2

dominance au sens de pareto

Soit x = (x1 , x2 ,
...
, yn ) deux solutions admissible au problème
multi-objectif, x ∈ X domine y ∈ X si et seulement si ∀i, fi (x) ≤ fi (y) avec au moins un i tel
que fi (x) ≤ fi (y), où i = 1,
...


14

Si la solution x domine la solution y nous notons alors x < y
...

x est dominé par y
...

Remarque 02 :
1
...
, m}

2
...

−
−
x1
x2
x < y si
∀i ∈ {1, 2,
...
, K} : fj (x) < fj (y)
Les solutions qui dominent les autres mais ne se dominent pas entre elles sont appelées solutions optimales au sens de Pareto (ou solutions non dominées)
...


Figure 2
...
4
2
...
1

Loptimalité de Pareto
Optimalité globale au sens de Pareto

−
Un vecteur → est optimal globalement au sens de Pareto (ou optimal au sens de Pareto) s’il
x
−
−
−
n’existe pas de vecteur → tel que → domine le vecteur →
...
4
...

−
une boule de centre x

2
...
3

La surface de compromis

Les solutions obtenues lors du classement basé sur le principe de dominance de Pareto forme
ce que l’on appelle la surface de compromis (ou Pareto Front)
...

− −
g x
h x
On appelle P la surface de compromis
...
5 – Représentation de la surface de compromis

16

Figure 2
...
L’utilisateur n’aura alors pas en sa possession un ensemble de solutions très
utiles
...
Il est alors probable que la solution offrant le « meilleur » compromis
se trouve dans une zone qui ne soit pas représentée par des points solution
...
4
...

les solutions non supportées
Sont plus difficiles à trouver
...
En définissant le critère de dominance dans l’espace des objectifs, on a tendance à
oublier que plusieurs solutions peuvent avoir les mêmes coordonnées
...


17

Figure 2
...


2
...


Point Nadir
Les coordonnés de ce point correspondent aux pires valeurs obtenues par chaque fonction
objective lorsque l’on restreint l’espace des solutions à la surface de compromis
...
8 – Formes les plus courantes de la surface de compromis dans le cas de deux objectifs
...
Le point idéal est utilisé dans beauqoup de méthodes d’optimisation comme point de référence
...

2
...
Généralement, ce point ne correspond pas à une solution de l’espace de décision mais
il est quelques fois utile en tant qu’une référence, par exemple , lors de la normalisation des
valeurs des objectifs
...
A la différence du point idéal qui réprésente les bornes inferieures de chaque objectif dans
l’espace faisable , le point de Nadir correspond à leurs bornes superieures sur la surface de
Pareto et non pas dans tout l’espace faisable
...

4
...
9 – représentation du point idéal et de point « nadir »
...
6 , le problème considéré est un problème de minimisastion
avec deux objectifs
...
Ces deux points sont calculés à partir du Front Pareto
...
le point Nadir) domine (res
...

Bien que ces points ne soient pas forcément compris dans la zone réalisable , ils servent souvent
de pôle d’attraction ( resp
...

Nous avons résolu un problème d’optimisation multiobjectifs, nous allons obtenu une multitude de solutions
...
Pour qu’une
solution soit intéressante, il faut qu’il existe une relation de dominance entre la solution considérée et les autres solutions, dans le sens suivant :

2
...
Dans ce cas il faut utiliser des méthodes capables de trouver l’ensemble
de Pareto tout en se basant sur les contraintes et la définition de problème
...
etc On outre, une deuxième tendance a pour but d’avoir des méthodes non mathématiques et tend vers l’ensemble de solutions dans un temps optimal et d’une manière simple en
se basant sur le principe des heuristiques, cette tendance est « les métaheuristiques », comme les
algorithmes évolutionnaires,
...

Les méthodes d’optimisation multi-objectif s’intéressent aux problèmes essayant d’optimiser simultanément plusieurs objectifs
...
10 –
...
6
...


2
...
2

a posteriori

le décideur choisit une solution parmi les solutions de l’ensemble P O1 fourni par le solveur ;
ainsi, il n’est plus nécessaire de modéliser les préférences du décideur (ce qui peut s’avérer être
très difficile),mais il faut en contre-partie fournir un ensemble de solutions bien réparties, ce qui
peut également être difficile et requérir un temps de calcul important (mais ne nécessite pas la
présence du décideur)

2
...
3

interactive

Il y a coopération progressive entre le décideur et le solveur ; cette approche permet donc de
bien prendre en compte les préférences du décideur, mais nécessite sa présence tout au long du
processus de recherche comme l’illustre la figure

Figure 2
...


22

2
...
4

Approche à base de transformation

Cette approche procède en transformant le problème du cas multi-objectif vers un problème mono-objectif
...

1
...
4
...
Elle consiste à ramener le problème multi-objectif au problème de l’optimisation d’une combinaison linéaire des objectifs initiaux
...

Un POM, comme défini dans 2
...
Cependant, elle ne permet pas de trouver les solutions enfermées dans une concavité (les solutions non supportées)
...
Les poids wi doivent également être choisis en fonction des préférences
associées aux objectifs, ce qui est une tâche délicate
...

La figure représente le principe de la méthode d’agrégation pour transformer un problème multiobjectif on problème mono-objectif
...
12 – La méthode d’agrégation
23

Théorème 1 Si tous les poids wi sont positifs, La solution du problème est une solution
Pareto optimale du problème multi-objectif
...
wk ) tel que x∗ est la solution du problème
...
6
...
2 La méthode ε-contrainte
Dans cette méthode, le problème admet une seule fonction objectif fk à optimiser, avec des
contraintes sur les autres fonctions objectifs
...
, n, j = k
(BM Oi (ε))

x∈X
Où ε = (ε1 ,
...
, εn )
...
, εk−1 − 1, εk+1 ,
...

Les différentes valeurs de εi peuvent être données pour pouvoir générer différentes solutions Pareto
optimales
...
Pour définir les valeurs appropriées pour εi , le vecteur idéal doit être calculé pour
déterminer les bornes inférieures
...
3 illustre, en dimension 2, le cas où un point (ε, f1min ), de la partie non convexe,
est trouvé
...
3 montre aussi comment cette approche procède
...
Ensuite, le processus
d’optimisation trouve le point optimal sur l’objectif restant
...
13 – La méthode ε-contrainte

24

2
...
5

Approche par traitement séparé des objectifs (approche non Pareto)

Cette approche consiste à réaliser la recherche en traitant les différents objectifs séparément
...
Parmi ces approches on peut
citer :
2
...
5
...
Elle a été proposée en 1985 par Schaffer comme une
extension d’un algorithme génétique simple pour la résolution d’un problème multi-objectif
...

L’idée est simple
...
Ainsi k sous-populations vont être créées, chacune d’entre elles contenant les n/k meilleurs individus pour un objectif particulier
...
le processus
se termine par l’application des opérateurs génétiques de modification (croisement et mutation)
...
14 – Schéma de fonctionnement de VEGA
Cette méthode, populaire car facilement implèmentable, a tendance à créer des k sous-populations
dont les meilleurs individus sont spécialisés pour un objectif particulier
...

2
...
5
...
Ensuite, on optimise dans cet ordre les fonctions objectif les unes
25

après les autres
...
, k, les fonctions objectif sont rangées suivant le choix du décideur dans
cet ordre :f1 , f2 , f3 ,
...
On résout le problème suivant :
M in f1 (x)
s
...
c f1 (x) = f1

x∈X
∗
Soit x∗ la meilleure solution trouvée avec f2 = f2 (x∗ , l’expression du problème sera le suivant :
2
2

M in f1 (x)
∗
s
...
La solution
obtenue à la dernière étape sera la solution du problème
...

Cette façon de procéder équivaut à une somme pondérée dans laquelle un poids correspond à la
probabilité que la fonction objectif associée soit sélectionnée
...

La solution fi∗ trouvée pour l’objectif le plus important va influencer l’algorithme et le diriger
vers une zone restreinte de l’espace faisable

2
...
6

Approche Pareto

Cette approche s’appuie directement sur la notion d’optimalité Pareto
...
Le
principal avantage de cette approche est qu’elle soit capable de générer un ensemble de solutions
Pareto appartenant aux parties concaves de la frontière Pareto
...

En effet, il existe deux générations des approches Pareto [11] :
⇒
√ La première génération est caractérisée par l’utilisation :
D’un mécanisme de sélection Pareto basé sur la technique de ranking, utilisant la relation de
dominance pour affecter des rangs aux individus de la population, faisant apparaître la notion de
Front
...

Parmi les approches représentatives de cette génération, on peut citer :
- MOGA (Multi-Objective Genetic Algorithm)
...

Parmi les approches représentatives de cette génération, on peut citer :
- SPEA et SPEA-2 (Strength Pareto Evolutionary Algorithm)
- NSGA-II ( Non dominated Sorting Genetic Algorithm)
- PAES ( Pareto Archived Evolution Strategy)
- PESA et PESA-II (Pareto Envelope-based Selection Algorithm)
- MOMGA et MOMGA-II (Multi-Objective Messy Genetic Algorithm)
- MicroGA pour l’optimisation multi-objectif
2
...
6
...

Goldberg indiquait que la notion de recherche génétique est multi-objectif dans sa nature
...
La formulation du problème comme optimisation d’un critère global n’est souvent pas
évidente
...
En plus, une seule solution est fournie, éliminant
le besoin du décideur à intervenir
...
Plusieurs algorithmes génétiques multi-objectif ont été proposés dans la littérature, on
peut citer [11] :
2
...
6
...
1 La méthode MOGA (Multiple Objective Genetic Algorithm)
Cette méthode est basée sur la dominance au sens de Pareto
...

(t)
Par exemple, si l’on considère un individu xi à la génération t qui est dominé par pi individus,
le rang de l’individu considéré est donné par :
(t)

rang(xi , t) = 1 + pi

A tous les individus non dominés on affecte le rang 1
...

Pour le calcul de l’efficacité, on peut suivre les étapes suivantes :
1
...

2
...
Cette fonction est, le plus souvent linéaire
...
6
...
1
...
La différence principale
intervient dans l’efficacité d’un individu
...
15 – Un exemple de fonction d’efficacité
Dans un premier temps, on affecte à chaque individu un rang de Pareto
...
Chaque catégorie aura une efficacité inversement
proportionnelle à son rang
...
On calcule, pour chaque individu, le compte de ses voisins
Avec K : nombre d’individus de la catégorie
...

2
...
Récemment une nouvelle version améliorée
de NSGA appelée NSGA-II
...
En comparaison avec
NSGA, NSGA-II obtient de meilleurs résultats, ce qui fait de cet algorithme un des plus utilisés
aujourd’hui
...
6
...
1
...

Dans NSGA-II, la population des enfants Q(t) est d’abord créée à partir de la population
des parents P (t)
...
Le nombre total de classes, noté r, dépend

28

Figure 2
...

Quand toute la population est triée, La population suivante P (t + 1) est remplie par les solutions
des sous-ensembles non dominé de R(t) l’un après l’autre en commençant, évidement, par le premier front
...

Q(t) = generate(Pt )
...
Réunir les populations des parents et des enfants Rt = Pt ∪ Q(t) et trier l’ensemble résultant
en sous-ensembles Fi tels que :
Rt = ∪r Fi etF1 < F2 <
...

i=1
3
...

– Le compteur des sous-ensembles non-dominés i = 1
...
Tant que | P(t+1) | + | Fi |< N faire :
- P(t+1) ← P(t+1) ∪ Fi
...

5
...


29

Figure 2
...
C’est donc une phase importante pour
laquelle les auteurs de NSGA-II ont développé une méthode particulière : la distance de crowding

Figure 2
...
Sur la
figure 1
...
Un algorithme de
calcul de la distance de crowding est détaillé
...
Une fois tous
les di calculés, il ne reste plus qu’à les trier par ordre décroissant et à sélectionner les individus
30

possédant la plus grande valeur de crowding

---

Title: memoire
Description: it a goood memoir .

Buy These NotesPreview