Optimisation

FT UMBB

M. AIT CHIKH
 Si vous voyez qu’il y des fautes ou vous avez des questions, merci de me contacter
sur l’adresse email suivante : [Link]@[Link]

1
Contents

1 Chapitre I: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Formulation du problème d’optimisation . . . . . . . . . . . . . . . . . . 3
1.2 Classification selon la nature du problème . . . . . . . . . . . . . . . . . 4
1.3 Classification selon la nature des méthodes de résolution . . . . . . . . . 5
2 Chapitre II: Optimisation et Programmation linéaire . . . . . . . . . . . . . . . 8
2.1 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Exemple d’un problème de production . . . . . . . . . . . . . . 12
2.2 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Forme de programmation linéaire . . . . . . . . . . . . . . . . 14
2.2.2 Transformation minimisation-maximisation . . . . . . . . . . . 15
2.2.3 Condition d’utilisation de la méthode de simplexe . . . . . . . . 15
2.2.4 Étapes de la méthode de simplexe . . . . . . . . . . . . . . . . 16
2.2.5 Variable d’écart . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.6 Variables de base et variables hors base . . . . . . . . . . . . . . 16
2.2.7 Exemple de résolution d’un problème d’optimisation avec simplexe 17
2.3 Méthode du simplexe à deux phases . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Phases I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Chapitre III: Optimisation non linéaire . . . . . . . . . . . . . . . . . . . . . . . 20
3.1 Optimisation non linéaire sans contrainte . . . . . . . . . . . . . . . . . . 20
3.1.1 Condition d’optimalité . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2 fonction convexe et concave . . . . . . . . . . . . . . . . . . . 21
3.1.3 Test de convexité et de concavité . . . . . . . . . . . . . . . . 22
3.1.4 Méthode de gradient : . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.5 Méthode de gradient conjugué : . . . . . . . . . . . . . . . . . . 26
3.1.6 Méthode de Newton Raphson : . . . . . . . . . . . . . . . . . . 28
3.1.7 Méthode quasi-Newton : . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Optimisation non linéaire avec contrainte . . . . . . . . . . . . . . . . . . 33
3.2.1 Contrainte d’égalité . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Contraintes d’inégalité . . . . . . . . . . . . . . . . . . . . . . 37
4 Chapitre IV Méthodes globales (Stochastique) . . . . . . . . . . . . . . . . . . . 41
4.1 Heuristique et méta-heuristique . . . . . . . . . . . . . . . . . . . . . . . 42

2
 4.2 Méta-heuristiques: aperçu historique . . . . . . . . . . . . . . . . . . . . 42
4.3 Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1 Sélection: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4 Optimisation par essaim particulaire . . . . . . . . . . . . . . . . . . . . 49
4.5 Traitement des contraintes pour les méthodes globales . . . . . . . . . . 51

1 Chapitre I: Introduction
Depuis toujours, l’homme cherche à atteindre l’optimum lors de la résolution de problèmes.
En d’autres termes, on vise à obtenir des solutions à profit maximal. L’optimisation est un
domaine qui relève des mathématiques qui s’occupe de la recherche de solutions en minimisant
ou maximisant une ou plusieurs fonctions, appelées fonction objectif, avec le plus souvent, la
prise en compte de limitations ou contraintes diverses. Pour résoudre ce type de problème,
nous disposons de nombreuses méthodes d’optimisation de différentes natures.

1.1 Formulation du problème d’optimisation

L’optimisation est un domaine de recherche de la bonne décision selon un objectif fixé. D’un
point de vue mathématique, c’est la minimisation, ou la maximisation d’une fonction f appelée
fonction objectif. Cette fonction dépend directement ou indirectement (cas de problèmes com-
plexes d’ingénierie) de variables de décision x = [x1 , x2 , . . . ..], et qui varient dans un intervalle
[ximin , ximax ] appelé espace de recherche. Ce dernier peut être limité par des contraintes ou
limitations, exprimées sous forme d’inégalité ou d’égalité, ou bien des deux en même temps.
Ces contraintes partagent le domaine de définition et se répartissent en domaine faisable, où
les solutions sont admissibles, et en domaine non faisable, qui contient des solutions rejetées.
Le problème d’optimisation peut être alors formulé comme suit:

min/max f (X)
avec gj (X) ≤ 0, j = 1, 2, .......J,
hk (X) = 0 k = 1, 2, .......K
X = [x1 , x2 , .......xn ], min(X) ≤ X ≤ max(X)
ou dans le cas d’un problème multi objectif Généralement, un problème d’optimisation multi-
objectif est formulé comme suit :

min fi (X), i = 1, 2, .......M

avec gj (X) ≤ 0, j = 1, 2, ......., J,
hk (X) = 0 k = 1, 2, ...............K,
X = [x1 , x2 , .....xn ], min(X) ≤ X ≤ max(X),

3
Où M est le nombre total de fonctions objectif fi (x), sachant que : M ≥ 2 , gj (x) et hk (x) sont
des contraintes d’inégalité et d’égalité à respecter, dont le nombre total est J et K respective-
ment.

1.2 Classification selon la nature du problème

Comme la classification des méthodes d’optimisation, les problèmes ou les modèles d’optimisation
peuvent être classés selon différentes aspects:

(a) Problèmes continus, discontinus et mixtes: Le problème d’optimisation est continu lorsque
les variables de décision traitées sont de type réel. A l’inverse, si les variables de décision
sont de type entier, le problème est dit discret ou discontinu. Le problème est dit mixte,
si ce sont des variables réelles et entières ou discrètes qui sont traitées conjointement.
Le problème discret ou mixte souvent plus difficile à le résoudre efficacement, les méta-
heuristiques, par exemple basées sur la recherche en voisinage d’une solution donnée
dont le domaine est réel, cette opération devient inefficace pour les variables entières, en
outre, le problème continu reste important pour résoudre un problème mixte, plusieurs
algorithmes qui génère les paramètres discrets ou entiers utilisent des séquences des sous-
problèmes continus.

(b) Problème déterministe ou stochastique et robuste: L’optimisation déterministe consiste à

résoudre le problème, dont l’espace de variation ou de recherche est connu avec précision.
Tandis qu’en pratique, cette précision ne peut pas être assurée à cause de l’erreur de
mesure, raison principale pour laquelle l’optimisation stochastique ou robuste traite le
problème sous incertitudes, c.-à-d. la solution peut varier aléatoirement dans cet espace
de recherche, étendu à une sous-plage d’incertitudes complémentaire. En effet, le but
de ce type de problème d’optimisation est de trouver la solution robuste, c’est à dire la
solution la moindre impactées par les incertitudes.

(c) Problème mono-objectif ou multi-objectif: La fonction objectif dans l’optimisation est une
fonction mathématique à maximiser ou minimiser selon la formulation du problème, en
respectant dans la plupart des cas certaines conditions et des contraintes ou limitations.
Cette fonction objectif peut être unique, c’est le cas d’un problème d’optimisation mono-
objectif, ou bien multiple et contradictoire, c’est le cas d’un problème d’optimisation
multi-objectif. Dans ce dernier cas, nous noterons que parfois on utilise une seule fonction
objectif qui gouverne deux ou plusieurs objectifs pondérés les uns par rapports aux autres.
La décision du choix des objectifs prépondérants est alors prise au début de calcul. Cette
prépondérance, caractérisée par des coefficients de pondération peut être modifiée, en
fonction de l’importance du problème physique traité. Par contre, la résolution de même
problème avec un front de Pareto permis de visualiser et prendre une décision en basant
sur l’ensemble de solutions.

4
 (d) Problème avec ou sans contraintes: Une autre caractérisation du problème d’optimisation
est liée à l’existence ou non de contraintes, qui sont généralement des inéquations et/ou des
équations, qu’il faut les respecter au cours du processus d’optimisation. Ces contraintes
limitent l’espace de recherche, comprenant un domaine des solutions faisables où toutes
les contraintes sont respectées sans aucune violation, et un domaine des solutions non
faisables, où une violation de contrainte au moins est présente.

(e) Problème statique ou dynamique: L’optimisation dynamique est caractérisée par la prise
en compte du facteur temps dans la fonction objectif, pendant que cette dernière dépend
seulement de variables de décision dans le cas de l’optimisation statique.

(f) Problème linéaire ou non linéaire: Le problème est non linéaire si la fonction objectif ou
au moins l’une des contraintes est non linéaire sinon, le problème est considéré comme
linéaire.

1.3 Classification selon la nature des méthodes de résolution

La complexité croissante et la diversité des problèmes d’optimisation dans différents domaines
(économie, ingénierie, médicale, etc. . . . ) ont été à l’origine du développement de nombreuses
méthodes de résolutions, que nous pourrons classer en trois grandes familles:

I. Les méthodes déterministes exactes, appelées aussi méthodes mathématiques ou analy-

tiques. Elles sont basées sur une algorithmique procédurale rigoureuse, où les chemins
des variables de décision et les fonctions sont reproductibles, c.-à-d., le même point de
départ suivra toujours le même chemin d’évaluation.

II. Les méthodes stochastiques, qui se divisent elles-mêmes en deux grandes catégories: les
méthodes heuristiques spécifiques et les méthodes méta-heuristiques, dont les algorithmes
sont caractérisés par leur comportement aléatoire, c.-à-d. le chemin de chaque variable
n’est pas reproductible. Les méthodes méta-heuristiques recouvrent les algorithmes à base
de solution unique, tels que la recherche de tabou, le recuit simulé, recherche de voisinage
variable, etc. . . , les algorithmes à base de population où plusieurs solutions sont possibles.
Cers derniers algorithmes eux-mêmes sont répartis selon la nature de type d’inspiration,
en deux groupes principaux:
1- Les algorithmes bio-inspirés, tels que:
a) Les algorithmes génétiques, qui sont les premiers sets les plus connus algorithmes du
genre ; ils sont basés sur l’abstraction de l’évolution Darwinienne et la sélection naturelle
des systèmes biologiques (croisement mutation et sélection), et sont représentés dans des
opérateurs mathématiques.
b) Les algorithmes à base de l’intelligence d’essaim qui incluent l’algorithme d’optimisation
par essaim particulaire (PSO), basé sur le comportement de certains oiseaux ou poissons
lors du déplacement ou d’immigration en essaim, la recherche de coucou, inspiré par le

5
 parasitisme de certain type de l’oiseau coucou, les colonies d’abeilles s’inspirant du com-
portement des abeilles mellifères lors de la recherche de leur nourriture.
2- Les algorithmes socio-inspirés, à l’instar de l’algorithme TLBO (Teaching Leraning
Based Optimisation), qui s’inspire de l’effet de l’influence d’un enseignant sur le niveau
des élèves dans une classe. Il existe d’autres sources d’inspiration algorithmique, tel que
l’algorithme de recherche d’harmonie, basé sur l’improvisation du ton des instruments
d’un musicien, produisant une harmonie agréable.

III. Les méthodes hybrides, qui combinent les méthodes déterministes et les méthodes stochas-
tiques, à l’exemple de l’algorithme Hill-Climbing, couplé avec un algorithme stochastique
pour choisir aléatoirement des solutions initiales.

En fait, cette classification présentée dans l’organigramme 1 n’est pas unique, car les aspects
de classification sont fort nombreux. Ce tableau résume les algorithmes d’optimisation les plus
communément utilisés.

6
 Méthode d’optimisation

Exacte Approximée Hybride

(analytique) ou (stochastique)
déterministe

Séparation et Escalade de colline avec

évaluation réinitialisation aléatoire
Heuristique Méta-
Programmation Spécifique heuristique
dynamique

A*

A base de solution A base de

unique population

La recherche de tabou

Le recuit simulé Socio-inspiré Bio-inspiré

Autre source
d’inspiration (music....)

VNS

TLBO Les
Recherche algorithmes
d’harmonie génétiques

Colonies de fourmis
Les algorithmes à
base d’intelligence
par essaim
Colonies d’abeilles

L’optimisation par
essaim de particules

La recherche de coucou

Figure 1 – Classification des méthodes d’optimisation

7
2 Chapitre II: Optimisation et Programmation linéaire
2.1 Méthode graphique
Un problème d’optimisation linéaire est formulé comme suit :
n
X
optimiser Z = ci xi = c1 x1 + c2 x2 + c3 x3 + .......cn xn
i=1

Sous contraintes:
 
Xm 
 ≤ 

gj (x) = aij xi ≥ bj
 
i=1
=
 

j = 1, 2, 3, ...J
xi ≥ 0

Avec ai j,ci et bj sont des constants connues, xi ≥ 0 est appelée aussi contrainte de non-
négativité de variables de décision. La méthode graphique consiste à résoudre un problème
d’optimisation linéaire graphiquement dont le nombre de variables ne dépasse pas 2, on trace
les contraintes sur un repère afin de définir la région des solutions faisable. La construction
des isolines (Contours) de la fonction objectif, parfois appelée fonction cout nous permet de
connaitre la direction de sa maximisation et minimisation. Les isolines sont des lignes dont la
fonction objectif ne varie pas, pour ce faire, il suffit de donner une valeur à Z= Cst puis tracer
Pn
la droite ci xi = Cst
i=1
Exemple d’application : Maximiser la fonction Z en considérant certaines contraintes posées:

max Z = 4x1 + 5x2

s .c :
2x1 + 1x2 ≤ 8
1x1 + 2x2 ≤ 7
x2 ≤ 3
x1 , x2 ≥ 0

On trace les lignes des contraintes en suit en désigne la région faisable.

8
 Figure 2 – Solution optimale unique

( ) ( ) ( )
2x1 + 1x2 = 8 1x1 + 2x2 = 7 x2 = 3
A(0, 8) B(4, 0) C (0, 27 ) D (7, 0) E(0, 3) F (x ∈ R, 3)
Puisque la direction de maximisation de Z est définie, on conclut que la solution optimale
évidemment située sur les bornes (frontière) de la région faisable (en gris), mais la question
qui se pose c’est que les frontières contiennent une infinité des solutions, comment faire pour
localiser la solution optimale ? On prend 2 points d’intersection des lignes de contraintes,
c’est clair que la variation de Z sur cette ligne entre les 2 points est linéaire et monotone
(augmentation ou diminution) ou constante, par conséquent, donc la solution optimale réside
sur l’un des points de l’intersection. Dans notre exemple on a 3 points S1, S2 et S3, pourquoi
pas le E ? , parce que c’est très clair que Z(S1) ≥ Z(E).
Pour trouver les coordonnées des points d’intersection, on résout un système d’équations linéaire
qui contient les équations (des contraintes) des deux lignes d’intersection.

  

 x1 = 1  x1 = 3
  x1 = 4

S1 x2 = 3 S2 x2 = 2 S3 x2 = 0
  
Z(S1) = 4 ∗ 1 + 5 ∗ 3 = 19 Z(S2) = 4 ∗ 3 + 5 ∗ 2 = 22 Z(S3) = 4 ∗ 4 + 5 ∗ 0 = 16
  

Z(S2) > Z(S3) > Z(S1) donc la solution optimale est x1 = 3, x2 = 2 avec un Z=22.
Ce type de solution est appelé solution (un problème avec une solution optimale unique). Il
existe 3 d’autres cas possibles :

9
[Link] Cas d’infinité de solutions :

max Z = x1 + x 2
s .c
2x1 + 2x2 ≤ 8
x1 , x2 ≥ 0

Figure 3 – Infinité de solutions

A(0, 4) B(4, 0)

La valeur de la fonction objectif dans A et B est la même, c.à.d, il n’y pas de variation sur
toute la droite construite entre A et B ( 2x1 + 2x2 = 8), autrement dit, le problème possède
une infinité de solutions entre A et B. La forme de la solution optimale dans ce cas est comme
suit :
! ! !
x1 0 4
=λ + (1 − λ)
x2 4 0
0≤λ≤1

x1 = 0 ∗ λ + (1 − λ)4
x2 = 4 ∗ λ + (1 − λ)0
En faisant varier λ entre 0 et 1 on obtient toutes les solutions optimales.

10
[Link] Cas de solution optimale tend vers l’infini :

max Z = x1 + x2
s .c :
8x1 + 4x2 ≥ 40
x1 + 5x2 ≥ 10
x1 , x2 ≥ 0

Figure 4 – Solution optimale infinie

Dans ce cas, on constate que la région de la solution faisable suivant la direction de max Z
n’est pas bornée. Mais dans un cas réel, l’optimum de Z ça sera le point qui contient le max
de x1 etx2 (noter bien que le choix dépend du signe des coefficients dans Z).

[Link] Cas d’inexistence d’une solution : Il reste un dernier cas possible, celui pour
lequel il n’existe pas de solutions réalisables Exemple :

max Z = x1 + 2x2
s .c :
x1 + x2 ≤ 2
x1 − x2 ≥ 3
x1 , x2 ≥ 0

11
 Figure 5 – Solution optimale infinie

La figure ne présente aucune région réalisable c.à.d, il n’existe pas un point qui satisfait
simultanément les deux contraintes. Le problème ne possède donc aucune solution.
En résumé, il existe quatre types de solutions à un problème de programmation linéaire :
1. solution optimale unique ;
2. infinité de solutions optimales ;
3. solution optimale infinie ;
4. aucune solution.

2.1.1 Exemple d’un problème de production

 Une entreprise fabrique des chaises et des tables à l’aide de deux machines A et B. Chaque
produit passe obligatoirement par les deux machines. Pour produire une chaise, il faut 2 heures
de machine A et 1 heure de machine B. Pour produire une table, il faut 1 heure de machine
A et 2 heures de machine B. L’entreprise réalise un bénéfice de 3$ sur chaque chaise et de 4$
sur chaque table. Les deux machines A et B sont disponibles 12 heures par jour au maximum.
Le problème consiste à savoir combien de chaises et de tables il faut fabriquer par jour pour
maximiser le bénéfice. (Dodge et al., 2004) .
Pour transformer ce problème en formulation mathématique, faut poser trois questions nécessaires,
c’est quoi les variables de décision ? quelle est la forme de la fonction objectif, quelle sont les
contraintes posé pour ce problème ?
 Le problème consiste à savoir combien de chaises et de tables  donc c’est clair que les
variables de décision sont la table et la chaise. On pose x1 =table, x2 =chaise.
L’objectif c’est de maximiser le bénéfice, L’entreprise réalise un bénéfice de 3$ sur chaque

12
chaise et de 4$ sur chaque table  et Le problème consiste à savoir combien de chaises et de
tables il faut fabriquer par jour pour maximiser le bénéfice, donc la fonction objectif s’écrit
comme suit: max z = 4x1 + 3x2 .
Les contraintes correspondantes à ce problème,  Pour produire une chaise, il faut 2 heures de
machine A et 1 heure de machine B. Pour produire une table, il faut 1 heure de machine A et 2
heures de machine B , donc, la machine A fonctionne 1 heure pour une table et 2 hures pour
une chaise, et elle ne dépasse pas les 12h par jour Les deux machines A et B sont disponibles
12 heures par jour au maximum, donc 1x1 + 2x2 ≤ 12
La machine B fonctionne 2h pour une table et 1h pour une chaise, et elle ne dépasse pas les
12h par jour, donc 2x1 + 1x2 ≤ 12
En résumé, le problème s’écrit sous la forme :

max z = 4x1 + 3x2

sous contraintes
1x1 + 2x2 ≤ 12
2x1 + 1x2 ≤ 12
x1 , x2 ≥ 0

Figure 6 – Problème de production

La solution optimale est l’intersection des bornes des contraintes, càd, B, C ou bien S1,

  
 x1 = 0
  x1 = 4
  x1 = 6

C x2 = 6 S1 x2 = 4 B x2 = 0
  
Z(C) = 4 ∗ 0 + 3 ∗ 6 = 18 Z(S1 ) = 4 ∗ 4 + 3 ∗ 4 = 28 Z(B) = 4 ∗ 6 + 3 ∗ 0 = 24
  

Z(S1 ) > Z(B) > Z(C) donc la solution optimale est x1=4, x2=4 avec un Z=28

13
2.2 Méthode du simplexe
2.2.1 Forme de programmation linéaire

La methode du simplexe s’agit d’une méthode algébrique itérative qui permet de trouver la
solution exacte d’un problème de programmation linéaire en un nombre fini d’étapes. Dans la
programmation linéaire le problème d’optimisation peut se présenter sous différentes Formes.
En voici la terminologie :

[Link] Forme canonique Si la fonction objectif doit être maximisée et si toutes les con-
traintes sont des inéquations du type ≤, on dit que le programme linéaire se présente sous ça
forme canonique de la manière suivante :

M aximiser Z = cx
S.C : Ax ≤ b
x≥0
m
P
Premier cas Si la kème Contrainte est de la forme : aik xi ≥bk en la multipliant par (-1)
i=1
on obtient :
m
X
−aik xi ≤ − bk
i=1
m
P
Second cas Si la kème contrainte est de la forme aik xi =bk on peut transformer cette
i=1
équation en deux inéquations :
m
P
aik xi ≤bk
i=1
Pm
aik xi ≥bk
i=1

Il suffit alors de multiplier la deuxième inéquation par (-1) pour obtenir :

m
P
aik xi ≤ bk
i=1
Pm
−aik xi ≤ −bk
i=1

Application : transformes des contraintes sous forme canonique.

x1 − 2x2 + x3 ≤ 5
3x1 + 2x2 − x3 ≥ 2
x1 + x2 + x3 = 7
La première contrainte est déjà sous forme canonique. La deuxième doit être multipliée par
(-1) :

−3x1 − 2x2 + x3 ≤ −2

14
 Finalement, pour la troisième contrainte, on pose :

x1 + x2 + x3 ≤ 7
x1 + x2 + x3 ≥ 7
La contrainte x1 + x2 + x3 ≥ 7 doit être multipliée par (-1). Sous forme canonique, les trois
contraintes transformées s’écrivent :

x1 − 2x2 + x3 ≤ 5
−3x1 − 2x2 + x3 ≤ −2
x1 + x2 + x3 ≤ 7
−x1 − x2 − x3 ≤ −7

[Link] Forme standard Un problème de programmation linéaire se présente sous sa

forme standard si toutes les contraintes sont des équations. La fonction objectif doit également
être maximisée. Sous forme matricielle, la forme standard s’écrit :

M aximiser Z = cx
S.C : Ax = b
x≥0

2.2.2 Transformation minimisation-maximisation

Tout problème de minimisation peut être transformé en un problème équivalent de maximisation

(l’inverse est vrai). En effet, le problème :

M inimiserZ = cx ⇔ M aximiser (−Z) = −cx

La raison pour laquelle ces deux formulations sont équivalentes est simple : la solution qui
permet d’obtenir la plus petite valeur de z fournit également la plus grande valeur de (-z) La
seule différence réside dans le signe de la valeur de la fonction objectif. La valeur minimale
de z s’obtient en prenant l’opposé de la valeur maximale de (-Z). Soit la fonction objectif à
minimiser :
M inimiser Z = 3x1 − 2x2 + 5x3

La formulation équivalente en terme de maximisation est :

M aximiser (−Z) = −3x1 + 2x2 − 5x3

2.2.3 Condition d’utilisation de la méthode de simplexe

Nombre de variables supérieur ou égale à 2. Toute contraintes est écrite sous forme d’inégalité.
et le coté droit est toujours positif. Toutes les variables sont positives.

15
2.2.4 Étapes de la méthode de simplexe

1. Écrire le problème sous la forme standard en rendant les inéquations sous forme d’égalité
en ajoutant une variable supplémentaire appelée la variable d’écart.

2. Trouver les variables de base et les variables hors base.

3. Construire le tableau initial qui contient les variables les contraintes et la fonction objectif.

4. Trouver la variable entrante.

5. Trouver la variable sortante.

6. Déduire le pivot et résoudre un système d’équations linéaire.

7. Vérifier la condition d’optimalité de la solution obtenue.

2.2.5 Variable d’écart

Avant de commencer d’utiliser l’algorithme de simplexe le problème d’optimisation linéaire doit

être transformé en un programme équivalant , où toutes les contraintes sont des équations et
toutes les variables sont positives.
Contraintes de type (≤) : Pour chaque contrainte i de ce type, on rajoute une variable d’écart
ei , tel que ei est une variable positive ou nulle.
Par exemple: x1 + 2x2 ≤ 3 devient x1 + 2x2 + e1 = 3 , e1 ≥ 0.
Contraintes de type (≥): Pour chaque contrainte i de ce type, on retranche une variable
d’excédent e2 , tel que e2 est une variable positive ou nulle.
Par exemple: x1 + 2x2 ≥ 3 devient x1 + 2x2 − e2 = 3, e2 ≥ 0.

2.2.6 Variables de base et variables hors base

Considérons un système d’équations à n variables et m équations où n ≤ m. Une solution de

base pour ce système est obtenue de la manière suivante:

1. On pose n − m variables égales à 0. Ces variables sont appelées variables hors base
(V.H.B.).

2. On résout le système pour les m variables restantes. Ces variables sont appelées les
variables de base (V.B.)

3. Le vecteur de variables obtenu est appelé solution de base (il contient les variables de
base et les variables hors base)

16
Une solution de base est admissible si toutes les variables de la solution de base sont ≥ 0.
Toute solution de base de problème d’optimisation linéaire pour laquelle toutes les variables
sont non négatives, est appelée solution de base admissible. Cette solution de base admissible
correspond à un point extrême.

2.2.7 Exemple de résolution d’un problème d’optimisation avec simplexe

max z = 10x1 + 8x2

sous contraintes:

2x1 + 4x2 ≤ 36
4x1 + 2x2 ≤ 48
x1 , x1 ≥ 0

Forme standard

max z = 10x1 + 8x2 + 0e1 + 0e2

sous contraintes:

2x1 + 4x2 + e1 = 36
4x1 + 2x2 + e2 = 48
x1 , x1 ≥ 0

Table 1 – Tableau initial, ou table 0

[Link] Tableau initial

n
X
zj = (Coefficients j dans z de [Link] ∗ Coefficientsj dans les contrainte)
j=1

La variable entrante est située dans la colonne qui contient la valeur maximale de (cj-zj) dans
le cas de maximisation de z, et la valeur minimale dans le cas de minimisation de z. Dans notre
exemple c’est x1.

17
NB : dans le cas d’égalité des coefficients, choisissez une seule variable arbitraire-
ment.
La variable sortante (c.à.d. qui sort de la base) est la variable qui a la valeur minimale (que se
soit pour max de z ou min de z) RHS/ coefficients de la colonne de la variable entrante.
Dans notre cas 36/2=18 pour e1 et 48/4=12 pour e2, donc e2 est la variable sortante.

Table 2 – Tableau illustratif avant de passer à la 1ere itération

La mise à jour des lignes de variable de base est basée sur le pivot, ce dernier est l’intersection
de la colonne de la variable entrante et la ligne de la variable sortante. Dans notre exemple
c’est 4.
La ligne de la variable entrante est égale à la ligne de la variable sortante divisée par le pivot.

[4 2 0 1 48]/4 = [1 1/2 0 1/4 12]

La mise à jour des lignes que restes se fait de façon d’avoir des zéros dans les coefficients de la
colonne de pivot, −2 ∗ [1 1/2 0 1/4 12] + [2 4 1 0 36] = [0 3 − 1/2 12].

Table 3 – Tableau d’itération 1

Après ce tableau (itération), la question qui se pose est : est ce que la solution obtenue est
optimale ou non ? Dans ce cas, faut vérifier le critère d’arrêt de l’algorithme.
cj − zj ≤ 0 pour z max
cj − zj ≥ 0 pour z min
Remarque :
M ax (z) ⇔ M in (−z) etM in (z) ⇔ M ax (−z)

D’après le tableau 6 toutes les valeurs de cj − zj ≤ 0 sauf 3, donc on doit continuer le calcul
de la même manière. La variable entrante c’est x2 la variable sortante est e1.

18
 Table 4 – Tableau d’itération 1

A cette étape le critère d’arrêt est vérifié c.à.d. toute cj − zj ≤ 0.

x1 = 10
x2 = 4
Z = 132
Application: Résoudre le problème de production précédent en utilisant la méthode de
simplexe.

2.3 Méthode du simplexe à deux phases

min z = x1 + x2
s.c 2x1 + x2 ≥ 4
x1 + 7x2 ≥ 7
x1 , x2 ≥ 0
Forme standard:

min z = x1 + x2 + 0e1 + 0e2 + M a1 + M a2

s.c 2x1 + x2 − e1 + a1 = 4
x1 + 7x2 − e2 + a2 = 7
x1 , x2 , e1 , e2 , a2 , a1 ≥ 0
a sont appelées les variables artificielles

2.3.1 Phases I

Dans la phase 1 on cherche à minimiser z=a1+a2 pour éliminer les variables artificialises.

Table 5 – Tableau initial de la phase I

19
 Après quelques itérations en se basant sur la méthode de simplexe classique on obtient :

Table 6 – Tableau final de la phase I

Si la variable artificielle sort de la base ne sera pas présentable sur le tableau de simplexe Si
a1 ou/et a2 apparaı̂t toujours sur la solution de base, le problème original n’a pas de solution.

2.3.2 Phase II

Dans la phase 2, on prend le dernier tableau de la phase 1 comme tableau initiale, et on continue
les procédures avec la méthode de simplexe classique.

Table 7 – Tableau initiale/final de la phase II

cj − zj ≥ 0donc critère d’arrêt est vérifié. x1=21/13 , x2=10/13 , z=31/13

3 Chapitre III: Optimisation non linéaire

Un problème d’optimisation dit non linéaire si au moins l’une de ses fonctions (objectifs e/ou
contraintes) sont pas linéaires.

3.1 Optimisation non linéaire sans contrainte

Il existe deux critères pour déterminer si un point donné et un extrémum (mine au max : le
premier critère est basé sur la variation la dérivée première si le signe de la dérivée première
positive puis négative quand x croit alors la fonction passe par un maximum. (La fonction doit
être continue et deux fois dérivable).

20
 Si le signe de la dérivée est négatif puis devient positif quand x croit alors la fonction, passe
par un minimum. Le second critère fait appel à la dérivée seconde de la fonction. La deuxième
dérivée de f est la dérivée de la première dérivée de f. Elle mesure le taux de variation (crois-
sance ou décroissance) de la première dérivée.

0
Si f (x) > 0 la pente de la tangentef (x) croit et change le signe quand x croit en passant
par x∗ minimum on parle ici de la fonction convexe.
0
Si f (x) < 0 , f (x) décroit et change le signe quand x croit en passant par x* (max) . On
parle ici de la fonction concave.

3.1.1 Condition d’optimalité

Pour une fonction à plusieurs variables, la condition nécessaire de l’existence d’un point critique
( min,max ou point selle) est le gradient égal à 0, ∇f (x) = 0 .La condition suffisante fait appel
à l’étudede la matrice Hessienne à ce point
 critique (viendra par la suite).
∂2f ∂2f ∂2f
2 ∂x1 ∂x2
..... ∂x1 ∂xn
 ∂x2 1 2

 ∂f ∂ f ∂2f
 ∂x2 ∂x1 ∂x22 ..... 
∂x2 ∂xn 
 
H(x) = 
 . . . . 

 

 . . . . 


 . . . . 

∂2f ∂2f ∂2f
∂xn ∂x1 ∂xn ∂x2
..... ∂xn ∂xn

3.1.2 fonction convexe et concave

Soit a et b : deux points dans Rn , le segment de droite joignant ses deux points.

Figure 7 – Fonction Convexe et Concave

[{x ∈ Rn |∃λ ∈ [0, 1]tel que x = a+λ(b − a) = λb + (1 − λ)a}

f (λb + (1 − λ)a) ≤ λf (b)+(1 − λ)f (a)
f esttrictement convexe ⇔ f (λb + (1 − λ)a) < λf (b)+(1 − λ)f (a) avec λ ∈]0, 1[

21
3.1.3 Test de convexité et de concavité

Parfois c’est difficile de vérifier les conditions citées ci-dessous, afin de pouvoir déterminer si la
fonction est convexe ou concave. Pour cela, on passe à d’autres critères.
Supposons f est une fonction deux fois dérivable d’une seule variable, alors F est convexe si
2
et seulement si ∀ x ∈ / R, ∂∂xf2 ≥ 0
2
F est strictement convexe si et seulement si ∀ x ∈ / R, ∂∂xf2 > 0
2
F est concave si et seulement si ∀ x ∈ / R, ∂∂xf2 ≤ 0
2
F est strictement concave si et seulement si ∀ x ∈ / R, ∂∂xf2 < 0

convexe Convexe Strict. concave Concave Strict Point selle On ne peut pas conclure )
∂2f
∂x2
≥0 >0 ≤0 <0 - -
∂2f
∂y 2
≥0 >0 ≤0 <0 - -
 2
∂2f ∂2f ∂2f
.
∂x2 ∂y 2
− ∂x∂y ≥0 >0 ≥0 >0 <0 0

Table 8 – Test de convexité pour une fonction à deux variables

On ne peut pas conclure c.à.d, dans le cas d’un extremumunique

Resultat: si f est strictement convexe sur Ω et Ω est un ensemble convexe. Alors la
solution optimale (en supposant qu’elle existe) doit être unique.
si f est convexe sur Ω et Ω est un ensemble convexe. Alors la solution optimale (en supposant
qu’elle existe) n’est pas unique.

Figure 8 – Domaine Convexe et Non Convexe

22
 Figure 9 – Min, max,point selle

∂2f ∂2f ∂2f

∂2f ∂2f ∂x21 ∂x1 ∂x2 ∂x1 ∂x3
∂2f ∂x21 ∂x1 ∂x2 ∂2f ∂2f ∂2f
[Link] Fonction à trois variables ∆1 = ∂x21
∆2 = ∂2f ∂2f
∆3 = ∂x2 ∂x1 ∂x22 ∂x2 ∂x3
∂x2 ∂x1 ∂x22 ∂2f ∂2f ∂2f
∂x3 ∂x2 ∂x3 ∂x2 ∂x23
∆i est appelé le déterminant de la matrice mineure principale (orthogonale ) de taille i x i

convexe Convexe Strict. concave Concave Strict

∆1 ≥0 >0 ≤0 <0
∆2 ≥0 >0 ≤0 <0
∆3 ≥0 >0 ≥0 >0

Table 9 – Test de convexité pour une fonction à trois variables

∆2 : point selle.

Autre: on n’en peut pas conclure

Il existe un autre critère qui est basé sur les valeurs propres de la matrice Hessienne.
det(H − λIn ) = 0 Avec In est la matrice d’identité de nxn.

23
 Donc cette méthode consiste à résoudre d’une équation d’ordre n dont la variable est la
valeur propre de H c.à.d. λ,
Si λi ≥ 0 la matrice H est définie semi-positive, la fonction f est convexe (min n’est pas
unique).
Si λi > 0 la matrice H est définie positive, la fonction f est strictement convexe (min unique).
Si λi ≤ 0 la matrice H est définie semi-négative, la fonction f est concave (max n’est pas unique).
Si λi < 0 la matrice H est définie négative, la fonction f est strictement concave (max unique).

Si certains λi > 0 et les autres λi < 0 : f ni convexe ni concave, c.à.d. ni min ni max, donc
le point critique est un point selle.
Autre (aucun cas cité ci-dessus n’est vrai), on ne peut pas conclure, voir d’autre méthode.
Exemple d’application :
Soit la fonction z = f (x, y) = x2 + y 2 , continue et deux fois dérivable. Le point cri-
tique (extrême) s’obtient ne résolvant le système d’équations donné par [∇f (x) = 0 (condition
nécessaire)
" # " # " #
∂f ∂f
∂x 0 ∂x
=0
∂f
= ⇔ ∂f
∂y 0 ∂y
=0
∂f
∂x
= 2x = 0 ⇒ x = 0
∂f
∂y
= 2y = 0 ⇒ y = 0
Ce point critique p(0,0) soit un min ou un max ou un point selle, on passe à la condition
suffisante" 2 # " #
∂ f ∂2f
2 = 2 = 0 2 0 2 0 2
H = ∂x
∂2f
∂x∂y
∂2f
= [∆ = = 2 ∗ 2 − 0 ∗ 0 = 4 > et ∂∂xf2 > 0
∂y∂x
= 0 ∂y2 = 2 0 2 0 2
Donc p(0,0) est un min unique.
Exemple 2 : Trouver les points critiques de la fonction (continue et dérivable) suivante :
f (x, y) = 4x2 − xy + y 2 − x3

24
 f (x, y) = 4x2 − xy + y 2 − x3
x=0 et y=0 , x=5/2 et y=5/4, " donc on a 2#point critique p1 ( 0,0 ), p2 ( 5/2, 5/4 )
8 − 6x −1
La matrice Hesseienne H =
−1 2
Pour p1 " #
8 −1
H=
−1 2

∆ = 15 > 0
∂2f
∂x2
=8>0
il s’agit d’un min
" #
−7 −1
Pour p2 H = , donc il s’agit d’un point selle (ni min ni max) ∆ = −15 < 0
−1 2
donc il s’agit d’un point selle (ni min ni max)

Exemple ou la fonction n’est pas strictement convexe mais elle est convexe
f (x, y) = x2 + y 2 + 2xy

f (x, y) = x2 + y 2 + 2xy = (x + y)2

Toute solution x=-y est un min, donc le point 0,0 un min mais n’est pas unique, car le
point 1,-1 aussi est un min ou f est toujours nulle, Si on applique la règle de défermant on a
∆ = 2 ∗ 2 − 2 ∗ 2 = 0 donc on ne peut pas conclure, mais si on applique la méthode de valeur
propre
" #
2 2
H=
2 2
" # " #! " #
2 2 1 0 2−λ 2
det −λ = det = (2 − λ)2 − 4 = 0
2 2 0 1 2 2−λ
λ1 = 0
2 − λ = −2 ou2 − λ = 2, Donc la fonction dans ce cas est convexe car la matrice
λ2 = 4
Hessienne est semi définie positive ou tout point min n’est pas unique.

La solution analytique basée sur la condition nécessaire n’est toujours garantie, les méthodes
numériques interviennent dans ce cas afin de trouver des solutions approximatives

3.1.4 Méthode de gradient :

L’idée de l’algorithme consiste à déplacer un point x en suivant son gradient (pente) à fin
d’obtenir un max (méthode de gradient ascendant) ou min (méthode de gradient descendant)
d’une fonction donnée, c’est le point extrême où la 1ere dérivée est nulle.

25
 Figure 10 – Principe de gradient

[Link] Gradient descendant xt+1 = xt − f 0 (xt )

ou bien dans ça forme générale:
xt+1 = xt − αf 0 (xt )
Avec α est un coefficient d’accélération (taux d’apprentissage), il permet de contrôler la
convergence de la solution lors de déplacement vers la solution optimale. Il peut être fixé ou
variable en fonction des itérations, pour cela, on peut trouver différentes formule de α dans la
littérature.

[Link] Gradient ascendant

xt+1 = xt + αf 0 (xt )

[Link] Multivariables exemple de l’algorithme descendant

xt+1 = xt − α∇f (xt )

c-à-d
     
∂f
x1 x1 ∂x1
     ∂f 

 x2 


 x2 


 ∂x2


∂f
 x3   x3  
∂x3

=  − α
     
  

 . 


 . 

 .




 . 


 . 

 .



∂f
xn t+1
xn t ∂xn t

3.1.5 Méthode de gradient conjugué :

On considère le problème quadratique suivant : f (x) = 21 xT Q x − cT x , x ∈ Rn

" #" # " #
1 Q11 Q12 x1 x1
f (x) = [x1 x2 ] − [c1 c2 ]
2 Q21 Q22 x2 x2
Avec Q symétrique et définie positive.

26
 généralement, les méthodes basés sur le gradient s’écrit comme suit: xk+1 = xk + αk dk αk est
le pas ,dk est la direction.
Étant donnée Q une matrice définie positive de n x n (symétrique), non nulle, les directions
d0 , d1 , . . . . . . .dk sont appelées Q-conjuguée si dTi Qdj = 0pour i 6= j

αk = arg min(f (xk + αdk ))

φk (α) = f (xk + αdk )
= 21 (xk + αdk )T Q (xk + αdk ) − cT (xk + αdk )
= α2 ( 12 dTk Qdk ) + α(xTk Q − cT )dk + f (xk )
1 T
(d Qdk )α2 + (∇T fk dk )α + f (xk )
2 k

dφk −∇T fk dk
= 0 ⇒ αk =
dα dTk Qdk
Dans une itération de la méthode à pas optimale.

∇ T f k dk
xk+1 = xk − dk
dTk Qdk

dTk+1 Qdk = 0

D’autre part :

dφk
= ∇f (xk+1 )dk = 0
dα
On pose: dk+1 = −∇f (xk+1 )βk dk
[−∇f (xk+1 )βk dk ]T Qdk = 0

T −∇T f (xk+1 )Qdk

−∇ f (xk+1 )Qdk + βk dTk Qdk = 0 ⇒ βk =
dTk Qdk
Algorithme de gradient conjugué

Initialisation de x0 , k=0, d0 = −∇f (x0 ),ε

Tant que Erreur > ε
Tf d
Calculer αk = −∇ dT
k k
k Qdk
xk+1 = xk + αk dk
T
Calculer βk = −∇ fdT(xQd k+1 )Qdk
k
k
[dk+1 = −∇f (xk+1 )βk dk
Erreur = |xk+1 − xk |
K =k+1
Fin tant que
x∗ = xk

27
 Figure 11 – Principe de gradient conjugué

3.1.6 Méthode de Newton Raphson :

La méthode de Newton Raphson consiste à chercher un zéro d’une fonction donnée, on donne
un point de départ xt et on estime xt+1 en basant sur la dérivée (la pente) de f (x) à xt . Selon
le développent de Taylor au premier ordre, toute fonction s’écrit comme suit :

f (x) ' f (x0 ) + f 0 (x0 )(x − x0 ) (1)

Donc, on cherche une solution x qui donne f (x) = 0

f (x0 )
0 = f (x0 ) + f 0 (x0 )(x − x0 ) ⇔ x = x0 − (2)
f 0 (x0 )

On généralise :
f (xt )
xt+1 = xt − (3)
f 0 (xt )

Figure 12 – Illustration géométrique de méthode de Newton

28
 Dans le cas de l’optimisation (trouvant max ou min), on ne cherche pas à trouver un 0 de
f (x) mais plutôt un 0 de f 0 (x) , pour cela, la formule de méthode Newton devient :

f 0 (xt )
xt+1 = xt − (4)
f 00 (xt )

[Link] Démonstration : On suppose qu’on a f (xt ), on peut estimer f (xt + ∆x) à laide
de développement de Taylor de 2eme ordre:

1
f (xt + ∆x) = f (xt ) + f 0 (xt )(∆x) + f 00 (xt )(∆x)2 (5)
2

On pose: a = f (x0 ) , b = f 0 (xt ) , c = f 00 (xt )

∂f (xt + ∆x)
f 0 (xt + ∆x) = b + c∆x = (6)
∂∆x
−b f 0 (xt )
f 0 (x0 + ∆x) = 0 à ∆x
c b + c∆x
c = 0 ∆x
c =
c
et x = xt + ∆x c = xt −
c , xt + ∆x
f 00 (xt )

f 0 (xt )
xt+1 = xt − (7)
f 00 (xt )

Donc il est claire que, pour cette méthode, la fonction f doit être dérivable à un point donnée
jusqu’à n ≥ 2.

[Link] Algorithme : t :=0

erreur :=inf
Tolerance :=1.0e-04
Tant que erreur>Tolerence


 t := t + 1
 x := x − f 0 (xt−1 )


t t−1 f 00 (xt−1 )
f aire


 erreur := |xt − xt−1 |
 x∗ := x

t
∗
Retourne x

[Link] Exemple d’application : Trouver un extrême local de la fonction suivante en

appliquant la méthode de Newton : f (x) = (1 − x)2 + ex , avec x0 = 0.5
f 0 (x) = 2x − 2 + ex
f 00 (x) = 2 + ex

29
 t x f f0 f 00 erreur
1 0.500000000000000 1.89872127070013 0.648721270700128 3.64872127070013 Inf
2 0.322205857183591 1.83957376442695 0.0245805787579061 3.38016886439072 0.17779414281640
3 0.314933859912432 1.83948430117770 3.64047080840813e-05 3.37016868488322 0.0072719972711590
4 0.314923057869126 1.83948430098108 7.99382782190605e-11 3.37015388434169 1.0802043306446e-05
5 0.314923057845406 1.83948430098108 0 3.37015388430919 2.3719470831906e-11
6 0.314923057845406 1.83948430098108 0 3.37015388430919 0

Table 10 – Résultats

la solution est x5 , et f (x5 ) est un min car f 00 (x) > 0

[Link] Cas de problème multivariable

xt+1 = xt − Hf −1 (xt )∇f (xt )

avec ∇f (xt ) est le vecteur Jacobien vecteur :

∂f ∂f ∂f T
∇f (x) = [ , , ...... ]
∂x1 ∂x2 ∂xn

∂ 2f
Hfj,j (x) =
∂xi ∂xj
 
∂2f ∂2f ∂2f
∂x1 ∂x1 ∂x1 ∂x2
...... ∂x1 ∂xj
∂2f ∂2f ∂2f
 

 ∂x2 ∂x1 ∂x2 ∂x2
...... ∂x2 ∂xj


. . . .
 
 
 
Hf (x) = 
 . . . . 

. . . .
 
 
 

 . . . . 

∂2f ∂2f ∂2f
∂xi ∂x1 ∂xi ∂x2
..... ∂xi ∂xj

1
A−1 = comt H
det H
exemple de matrice A 3*3  
a11 a12 a13
H =  a21 a22 a23 
 

a31 a32 a33

30
 a22 a23 a21 a23 a21 a22
+ − +
a32 a33 a31 a33 a31 a32

a12 a13 a11 a13 a11 a12

com A = − + −
a32 a33 a31 a33 a31 a32

a12 a13 a11 a13 a11 a12

+ − +
a22 a23 a21 a23 a21 a22
" #
a b
A=
c d" #
d −b
com (A) =
−c a

det(H − λIn ) = 0

A càd (Hf (x)) est positive si toutes les valeur propre λ sont > 0
A càd (Hf (x)) est négative si toutes les valeur propre λ sont < 0

3.1.7 Méthode quasi-Newton :

Parfois il est difficile de trouver l’inverse de la matrice Hessienne surtout dans le cas où on a
grand nombre des variables, le coût de calcul devient important.
Pour cela la méthode Quasi Newton consiste à remplacer la matrice Hessienne inversée par
une matrice approximée.

xk+1 = xk − H −1 (xk )∇f (xk )

H inversible ⇔ |H| =
6 0

dk = −H −1 (xk )∇f (xk )

On pose :dk = −SK ∇f (xk ) avec Sk est une approximation de H −1 , elle est symétrique, définie
positive et facile à calculer.

[Link] Équation de la sécante ou quasi Newton Soit f deux fois différentiable, d’après
le développement de séries de Tylor :

31
 ∇f (x) = ∇f (xk ) + H(xk )(x − xk ) + O(||x − xk ||)
∇f (xk+1 ) ≈ ∇f (xk ) + H(xk )(xk+1 − xk )
qk = ∇f (xk+1 ) − ∇f (xk )
pk = xk+1 − xk
H −1 (xk )qk = pk
Sk qk = pk ...... (1)
H −1 (xk ) ≈ Sk
Sk+1 qk = pk
On cherche Sk solution de l’équation (1) avec méthode quasi Newton de rang 1.
On pose :Sk+1 = Sk + Ck

Ck = ak uk uTk

avec uk (n, 1) xuTk (1, n) = matricede(nxn) et a est un scalaire réel.

h i
b1 b2 b3
   
a1 a1b1 a1b2 a1b3
 a2   a2b1 a2b2 a2b3 
   

a3 a3b1 a3b2 a3b3

(Sk + ak uk uTk )qk = pk

Sk qk + ak uk uTk qk = pk
pk − Sk qk = ak uk uTk qk
On prend

pk − Sk qk = uk
ak uTk qk = 1

ak (pk − Sk qk )T qk = 1

1
ak = (pk −Sk qk )T qk
T
Ck = ak uk uTk = (pk −S k qk ) (pk −Sk qk )
T
(pk −Sk qk ) qk
T
Sk+1 = Sk + (pk −S k qk ) (pk −Sk qk )
(pk −Sk qk )T qk

Algorithme de la méthode Quasi-Newton Initialisation de x0 , S0 = In (matrice

symétrique et définie positive) , k = 0, ε Tant que Erreur ¿ ε Calculer dk = −Sk ∇fk xk
αk = arg min(f (xk + αdk ), α > 0
xk+1 = xk + αk dk Calculer pk = αk dk , qk = ∇f (xk+1 ) − ∇f (xk )
T
Sk+1 = Sk + (pk −S k qk ) (pk −Sk qk )
(pk −Sk qk )T qk
Erreur = |xk+1 − xk | K = k + 1;
Fin tant que

32
x∗ = xk
Initialisation de x0 , k=0, d0 = −∇f (x0 ),ε
Tant que Erreur > ε
Tf d
Calculer αk = −∇ dT
k k
k Qdk
xk+1 = xk + αk dk
T
Calculer βk = −∇ fdT(xQdk+1 )Qdk
k
k

[dk+1 = −∇f (xk+1 )βk dk

Erreur = |xk+1 − xk |

K =k+1

Fin tant que

x∗ = xk

3.2 Optimisation non linéaire avec contrainte

3.2.1 Contrainte d’égalité
optimiser f (x)
s.c hj (x) = 0
Avec f convexe (ou concave) dans un domaine convexe.
On considère x∗ est une solution optimale dont la condition d’optimalité est comme suit :
∇f (x∗ ) + λT ∇h(x∗ ) = 0 On décompose le vecteur des variables x en deux sous ensembles,
S variable solution, et D variable de décision,
 


 s1 


 
 



 s2 



 


 x 1 





 . 



   



 x 2







 . 


 ( )

 x3   
  sm  S
x= = =


 . 




 d1 

 D
   
 . 

  
 
 d2 



   
 x     .


n 





 



 . 



 
 dn−m 

D’âpres les séries de Taylor :

n
∂f (x∗ )
f (x) = f (x∗ )+ (xi −x∗i ) Le second ordre est négligeable devant le petit déplacement
P
∂xi
i=1
(une approximation linéaire est suffisante)

33
 n
∂f (x∗ )
f (x) = f (x∗ ) + − x∗i ) + O(2)
P
∂xi
(xi
i=1
f (x) ≈ f (x∗ ) + ∇ f (x∗ )∆x∗
T

f (x) ≈ f (x∗ ) + ∇TS f (x∗ )∆s∗ + ∇Td f (x∗ )∆d∗

idem pour la fonction h(x) .
n
∂hj (x∗ )
hj (x) = hj (x∗ ) + − x∗i ) + O(2)
P
∂xi
(xi
i=1
hj (x) ≈ hj (x∗ ) + ∇hTj (x∗ )∆x∗
hj (x) ≈ hj (x∗ ) + ∇S hTj (x∗ )∆s∗ + ∇d hTj (x∗ )∆d∗

Puisque h(x)faut être nulle pour n’importe xdonc [h(x∗ ) = 0

⇒ ∇S hTj (x∗ )∆s∗ + ∇d hTj (x∗ )∆d∗ = 0
∆s∗ = −[∇S hTj (x∗ )]−1 ∇d hTj (x∗ )∆d∗

∇S f T (x∗ )∆s∗ + ∇d f T (x∗ )∆d∗ = 0 (condition necessaire)

T ∗ T ∗ −1 T ∗ ∗ T ∗ ∗
−∇
n S f (x )[∇S hj (x )] ∇d hj (x )∆d + ∇d f (xo)∆d = 0
−1
−∇S f T (x∗ )[∇S hTj (x∗ )] ∇d hTj (x∗ ) + ∇d f T (x∗ ) ∆d∗ = 0
−∇S f T (x∗ )[∇S hTj (x∗ )]−1 ∇d hTj (x∗ ) + ∇d f T (x∗ ) = 0
λ∇d hTj (x∗ ) + ∇d f T (x∗ ) = 0
λ = −∇s f T (x∗ )[∇S hTj (x∗ )]−1
λ∇s hTj (x∗ ) + ∇s f T (x∗ ) = 0
(
λ∇d hTj (x∗ ) + ∇d f T (x∗ ) = 0
T ∗ T ∗
⇔ +λ∇x hT (x∗ ) + ∇x f T (x∗ ) = 0
λ∇s hj (x ) + ∇s f (x ) = 0
m
X
∇f (x) = λj ∇hj
j=1

λ est appeler le multiplicateur de Lagrange

m
X
L(x, λ) = f (x) + λj hj
j=1

L est appelé la fonction de Lagrange ou Lagrangien

[Link] Interprétation géométrique: Le vecteur gradient pointe dans la direction où la

fonction croı̂t le plus rapidement, et son module est égal au taux de croissance dans cette direc-
tion. Géométriquement, le point optimal ne peut être qu’un point de tangente entre la fonction
objectif et la contrainte. Dans ce point les gradients de la fonction objectif et la contrainte sont
parallèles (de même sens au sens inverse) .

34
 Figure 13 – Multiplicateur de Lagrange

Les lignes de courants (isolignes) possède les( x y) qui donnent la même valeur de la fonction
f, donc entre deux ligne de courant on une graduation de f ( descendant ou ascendant) .
∇f (x)//∇h(x) ⇔ ∇f (x) = λ∇h(x) ou bien ∇f (x) = −λ∇g(x)
Le signe de λ n’est pas important dans le cas d’une contrainte d’égalité, par contre il est
considéré pour les contraintes d’inégalité (Voire la section prochaine).

Exemple:

min f (x) = 6x21 + 5x22

s.c x1 + 5x2 = 7
Solution:

h(x) = x1 + 5x2 − 7 = 0

" #
∂f
= 12x1
∂x1
∇f (x) = ∂f
= 10x2
∂x2
" #
∂g
= 1
∇h(x) = ∂x∂g
1

∂x2
=5
" # " # " # " #
12x1 λ 12x1 − λ 0
∇f (x) = λ∇h(x) ⇔ = ⇔ =
10x2 5λ 10x2 − 5λ 0
Sans oublierx1 + 5x2 − 7 = 0 , donc on a un système de 3 variables (x1, x2 et λ) et 3
équations

35
 12x1 − λ = 0.......(1)
10x2 − 5λ = 0......(2)
x1 + 5x2 − 7 = 0.......(3)
(1) ⇔ 60x1 − 5λ = 0.......(4)
(2) − (4) ⇔ x2 − 6x1 = 0 ⇔ x2 = 6x1
On remplace x2 dans l’équation (3)

7 42
" 1 ) − 7 = 0 ⇔ 31x1 = #7 ⇔ x1 = 31 ,x2 = 31
x1 + 5(6x
fx1 x1 = 12 fx1 x2 = 0
H=
fx2 x1 = 0 fx2 x2 = 10
|H| = 12 ∗ 10 − 0 ∗ 0 = 120 > 0
Et fx1 x1 = 12 > 0 donc le point (7/31, 42/31) est un min

2eme méthode:
[L(x, λ) = f (x) + λh = 6x21 + 5x22 + λ(x1 + 5x2 − 7)

L(x, λ) = f (x) + λh = 6x21 + 5x22 + λ(x1 + 5x2 − 7)

∂L
Lx1 = ∂x 1
= 12x1 + λ = 0
∂L
Lx2 = ∂x2 = 10x2 + 5λ = 0
Lλ = ∂L
∂λ
= x1 + 5x2 − 7 = 0
3 inconnues s et 3 variables, solution est la même (x1=7/31, x2=42/31)

Exemple 2
min z = x21 + x22 + x23
s.c x1 + x2 + 3x3 = 2
5x1 + 2x2 + x3 = 5

∇f (x) = λ1 ∇h1 (x) + λ2 ∇h2 (x)

      
2x1 1 5  2x1 − λ1 − 5λ2 = 0....(1)

 2x2  = λ1  1  + λ2  2  ⇔ 2x2 − λ1 − 2λ2 = 0.....(2)
     

2x3 3 1 2x3 − 3λ1 − λ2 = 0......(3)


λ1 +5λ2
(1) ⇔ x1 = 2
λ1 +2λ2
(2) ⇔ x2 = 2
3λ1 +λ2
(3) ⇔ x3 = 2

x1 + x2 + 3x3 − 2 = 0
5x1 + 2x2 + x3 − 5 = 0

λ1 + 5λ2 λ1 + 2λ2 3λ1 + λ2

+ + 3( ) − 2 = 0 ⇔ 11λ1 + 10λ2 − 4 = 0
2 2 2

36
    
λ1 + 5λ2 λ1 + 2λ2 3λ1 + λ2
5 +2 +( ) − 5 = 0 ⇔ λ1 + 3λ2 − 1 = 0
2 2 2
2 7 37 16 13
λ1 = 23
; λ2 = 23
et x1 = 46
, x2 = 46
, x3 = 46

 
2 0 0
H= 0 2 0 
 

0 0 2
|H| = 8 > 0 et fx1x1 = 2 > 0,fx2x2 = 2 > 0,fx3x3 = 2 > 0 donc le point critique x1 x2 x3 est
un min.

3.2.2 Contraintes d’inégalité

minf (x)
[Link] (x) ≤ 0

Figure 14 – Contrainte d’inegalité

On décompose la contrainte d’inégalité en deux conditions g(x)=0 et g(x) ¡0 Dans la 1ere

la contrainte est active (la multiplier de Lagrange apparait), mais dans la 2eme est inactive((la
multiplier de Lagrange est nulle, il n’a aucun rôle) ), on considère que x* est un point minimum
de f(x) , et qui respecte la contrainte de g(x). Pour un petit déplacement, le développement en
série de Tylor en négligeant le second ordre s’écrire comment suit:

df (x∗ )
f (x) = f (x∗ ) + (x − x∗ ) + O(2)
dx
∗
Donc dfdx (x )
∆x∗ ≥ 0
df (x∗ )
dx
∆x∗ ≤ 0 pour max (f(x))).

dg(x∗ )
Idem pour g(x) g(x) = g(x∗ ) + dx
(x − x∗ ) + O(2)

37
 dg(x∗ ) ∗
Donc dx
∆x∗ ≤ 0, dg(x
dx
)
∆x∗ ≥ 0pour max (f(x))).

m
P
Pour la forme de lagrangien L(x, µ) = f (x) + µj gj on a
j=1
m
X m
X
∇f (x) = − µj ∇gj ⇔ ∇f (x)∆x∗ = − µj ∇gj ∆x∗
j=1 j=1

Min f(x) Max f(x)

g(x) ≤ 0 µ≥0 µ≤0
g(x) ≥ 0 µ≤0 µ≥0

Table 11 – Signe de multiplicateur de Lagrange dans les cas possibles

Pour la forme de lagrangien.

m
X
L(x, µ) = f (x) − µj gj
j=1

m
X m
X
∇f (x) = µj ∇gj ⇔ ∇f (x)∆x∗ = µj ∇gj ∆x∗
j=1 j=1

Min f(x) Max f(x)

g(x) ≤ 0 µ≤0 µ≥0
g(x) ≥ 0 µ≥0 µ≤0

Table 12 – Signe de multiplicateur de Lagrange dans les cas possibles

Condition d’optimialité de Karush- Kuhn-Tucker ( KKT)

 m
∗
µj ∇gj (x∗ ) = 0
P


 ∇f (x ) +
) 
 j=1
min f (x) 
µj gj (x∗ ) = 0
⇒
sc gj (x) ≤ 0 

 µj ≥ 0


j = 1, 2, 3, ....m


Exemple :

min f (x, y) = 4x2 + 10y 2

s.c x2 + y 2 ≤ 4

min L(x, y, µ) = 4x2 + 10y 2 + µ( x2 + y 2 − 4)

Lx = 8x + 2µx = 0
Ly = 20y + 2µy = 0

38
 cas µ = 0 et g(x) < 0
8x = 0 ⇒ x = 0
20y = 0 ⇒ y = 0
f (0, 0) = 0

cas µ 6= 0 et g(x) = 0
Lx y = 8xy + 2yµx = 0
Ly x = 20yx + 2µyx = 0
Ly x − Lx y = 0 ⇒ 20yx(− 8xy = 0 ⇒ 12yx = 0 ⇒ xy = 0
y = −2 ⇒ µ = −10 < 0 rejetée
x = 0 ⇔ y2 − 4 = 0 ⇔
( y = 2 ⇒ µ = −10 < 0 rejetée
x = −2 ⇒ µ = −4 < 0 (rejetée)
y = 0 ⇔ x2 − 4 = 0 ⇔
x = 2 ⇒ µ = −4 < 0 rejetée
Donc la solution optimale est x=0, y=0 et f(0,0)=0

Exemple 2:

max z = 10x1 + 10x1 − x21 − x22

s.c x1 + x1 ≤ 8.......(1)
−x1 + x2 ≤ 5......(2)
L = 10x1 + 10x1 − x21 − x22 + µ1 (x1 + x1 − 8) + µ2 ( −x1 + x2 − 5)
Lx1 = 10 − 2x1 + µ1 − µ2 = 0
Lx2 = 10 − 2x2 + µ1 + µ2 = 0
µ1 (x1 + x1 − 8) = 0 etµ2 ( −x1 + x2 − 5) = 0
µ1 ≤ 0 etµ2 ≤ 0

g1 (x) = x1 + x1 − 8
g2 (x) = −x1 + x2 − 5
cas (1) (µ1 = 0 , g1 < 0 )et(µ2 = 0, g2 < 0 )
d’après (1) et (2)
10 − 2x1 = 0 ⇒ x1 = 5
g1 (5, 5) > 0 rejetée.
10 − 2x2 = 0 ⇒ x3 = 5
cas (2) (µ1 = 0 , g1 < 0 )et(µ2 6= 0, g2 = 0 )
10 − 2x1 − µ2 = 0  
10 − 2x2 + µ2 = 0 resoudre

−x1 + x2 − 5 = 0


x1 = 2.5, x2 = 7.5,
g1 (2.5, 7.5) > 0 rejetée.
cas (3) (µ1 6= 0 , g1 = 0 )et(µ2 = 0, g2 < 0 )

39
 
10 − 2x1 + µ1 = 0  
10 − 2x2 + µ1 = 0 resoudre

x1 + x2 − 8 = 0


x1 = 4, x2 = 4,
g1 (4, 4) = 0 (satisf ait)
g2 (4, 4) = −5 < 0 (satisf ait)
cas (4) (µ1 6= 0 , g1 = )0 )et(µ2 6= 0, g2 = 0 )
−x1 + x2 − 5 = 0
resoudre
x1 + x2 − 8 = 0
x1 = 1.5, x2 = 6.5
en remplaçant x1 et )
x2 dans (1) et (2)
7 + µ1 − µ2 = 0
resoudre
−3 + µ1 + µ2 = 0
µ1 = −2, µ2 = 5 rejetee
La solution finale est x1=4, x2=4, z=48
Exemple 3: problème mixte

min f (x, y) = 4x21 + 2x22

s.c 2x1 + 4x2 ≤ 15
3x1 + x2 = 8

40
 min f (x, y) = 4x21 + 2x22
s.c 2x1 + 4x2 ≤ 15
3x1 + x2 = 8
min L(x, y, λ, µ) = 4x21 + 2x22 + λ( 3x1 + x2 − 8) + µ(2x1 + 4x2 − 15)
µg(x) = µ(2x1 + 4x2 − 15) = 0
µ≥0
Lx = 8x1 + 3λ + 2µ = 0
Ly = 4x2 + λ + 4µ = 0
µ = 0 , g(x) < 0
Lx = 8x1 + 3λ = 0
Ly = 4x2 + λ = 0 ⇒ 12x2 + 3λ = 0
3Ly − Lx = 12x2 − 8x1 = 0 ⇔ 3x2 − 2x1 = 0
3x1 + x2 − 8 = 0
x1 = 3x22 , 3( 3x22 ) + x2 − 8 = 0
9x2 + 2x2 = −16 ⇒ x2 = 16 11
x1 = 48
22
= 24
11
2x1 + 4x2 ≈ 10.12 < 15 (acceptable)

µ 6= 0 , g(x) = 0
2x1 + 4x2 − 15 = 0........(1)
3x1 + x2 − 8 = 0 ⇒ 12x1 + 4x2 − 32 = 0 ......(2)
(2) − (1) ⇔ 10x1 − 32 + 15 = 0
10x1 = 17 ⇔ x1 = 1710
17
on a x2 = 8 − 3x1 = 8 − 3 10 = 29
10
3Ly − Lx = 6x2 − 4x1 + 5µ = 0
106 + 50µ = 0 ⇒ µ = −106 50
< 0 rejetée
Donc, la solution optimale est x1=24/11, x2=16/11 et f(x1, x2)= 2816/121=23.27272.

4 Chapitre IV Méthodes globales (Stochastique)

Les méthodes d’optimisation proposées sont de type itératif, où les variables sont modifiées à
chaque itération à partir d’une population (ensemble de solutions proposées) générée aléatoirement.
Contrairement aux méthodes d’optimisation exacte, les méthodes méta-heuristiques sont basées
sur l’aspect de la population, qui est constituée par l’ensemble des individus, et s’exprime comme
suit :

Xi = [xi,1 , xi,2 , xi,3 , ......, xi,D ]

1≤i≤n

41
  
x1,1 x1,2 .......... xi,D
x2,1 x2,2 .......... xi,D
 
 
 

 . . . . 

. . . .
 
 
 
P opulation = 
 . . . . 

. . . .
 
 
 

 . . . . 

. . . .
 
 
xn,1 xn,2 .......... xn,D

4.1 Heuristique et méta-heuristique

L’heuristique, ce sont des règles générales, des données de connaissance, une stratégie, une
simplification ou une autre sorte de dispositif qui limitent résolument la recherche de solutions
dans de grands espaces de problèmes utiles, ne garantissant pas de solutions optimales, voir de
solution du tout, mais offrant le plus souvent d’assez bonnes solutions ([? ], [? ]). Les méta-
heuristiques sont des méthodes stochastiques itératives pouvant regrouper plusieurs heuristiques
pour résoudre un problème d’optimisation complexe en offrant des solutions de haute qualité
ou optimale [? ].

4.2 Méta-heuristiques: aperçu historique

Depuis les premières époques de l’histoire humaine, l’homme a utilisé une approche heuris-
tique ou méta-heuristique, pour résoudre ses problèmes. Le moment ‘’Eureka” d’Archimède en
était en fait un triomphe heuristique. Jour après jour, avec l’augmentation de la complexité
des problèmes, les méthodes méta-heuristiques ont justifié leur utilité. [Link] [? ] a été
probablement le premier à avoir utilisé un algorithme heuristique pour déchiffrer le code d’une
machine énigme allemande durant la seconde guerre mondiale. Après ce succès, Turing est
devenu un membre du laboratoire national de physique au Royaume-Uni. Il a présenté le
dessin d’un moteur de calcul automatique en 1948, décrivant les grandes lignes de son idée
innovative de la machine intelligence par apprentissage, basée sur les réseaux de neurones et les
algorithmes évolutionnaires. Les plus grandes et importantes périodes de développement des
méthodes méta-heuristiques, notamment les algorithmes génétiques, se situent entre 1960 et
1970. Durant cette période, John Holland [? ] et ses collègues à l’université de Michigan, ont
développé les opérateurs des algorithmes génétiques, inspirés par le théorème de la sélection
naturelle de Darwin. 1975 a été l’année de la consécration de John Holland, qui a publié les
résultats de recherche. Dans la même année, De Jong [? ] a publié le potentiel et la puissance
des algorithmes génétiques, appliqué sur une large gamme de types de fonction objectif.
Les années 80 et 90 ont été marquées par le développement de plusieurs méthodes méta-
heuristiques inspirées par la nature ou par des phénomènes divers. En 1983, S. Kirkpatrick
et al. [? ] ont développé la méthode d’optimisation du recuit simulé, inspirée du processus de

42
refroidissement dans la métallurgie, où on cherche à atteindre un état d’énergie minimale qui
correspond à la structure des métaux la plus stable. En 1986, [Link] [? ] ont utilisé pour
la première fois la mémoire dans les méta-heuristiques, avec la méthode de recherche tabou;
cette dernière est basée sur la recherche dans le voisinage d’une solution (position) donnée, à
condition d’interdire de revenir sur les positions déjà explorées. [Link] en 1992 [? ] a finalisé
sa thèse de doctorat en proposant une approche d’optimisation innovante, dont la méthode de
base a été inspirée par la nature. Il a notamment développé l’algorithme de colonie de fourmis,
basée sur l’intelligence de l’essaim sociale des fourmis, qui utilisent la phéromone comme mes-
sager chimique, afin de trouver le chemin optimal entre leur colonie et une source de nourriture.
L’algorithme d’optimisation par essaim particulaire (PSO), basé sur le comportement social des
essaimes lors de leur déplacement, peut être considéré comme le plus célèbre algorithme après
les algorithmes génétiques, développé en 1995 par J. Kennedy et [Link] [? ]. En 1997 R.
Stornet et K. Price [? ] ont développé l’algorithme de l’évolution différentielle, considéré comme
une avancée inespérée par rapport aux algorithmes génétiques et aux stratégies évolutionnistes,
notamment en termes d’efficacité pour l’optimisation de problèmes mixtes. Cette approche
permet de créer une nouvelle solution par la combinaison des solutions existantes, selon des
formulations simplifiées.
Les débuts du 21ème siècle a vu un développent technologique fulgurant, qui a entrainé de
fortes exigences dans le domaine de l’optimisation. De nombreuses nouvelles méthodes socio-et
bio-inspirées ont été alors développées pour répondre à la demande. Nous évoquerons dans ce
qui suit les méthodes les plus communément utilisées : la méthode de recherche d’harmonie
(Z.W. Geem et al. [? ]), l’algorithme d’essaim d’abeilles (S. Nakrani and [Link](2004)
[? ]), les colonies artificielles d’abeille (ABC) (D. Karaboga(2005)[? ]), algorithme de fire-
fly (FA),([Link] et al(2008) [? ]). En 2009, [Link] et S. Deb ont proposé un nouvel
algorithme d’optimisation baptisé ”recherche de coucou”, qui est basé sur le parasitisme de
certains oiseaux de coucou. Cet algorithme a prouvé son efficacité par rapport à la plupart
des algorithmes d’optimisation de même nature. En 2011, une autre source d’inspiration basée
sur l’apprentissage, a été exploitée pour le développement de l’algorithme de TLBO (Teach-
ing Lerning Based Optimisation) ( [Link] et al [? ]); cet algorithme innovant a également
démontré son efficacité dans l’optimisation de nombreux problèmes du design de machines, avec
prise en compte de contraintes diverses.

4.3 Algorithmes génétiques

Les algorithmes génétiques font partie de la famille des algorithmes évolutionnaires basés sur
le théorème d’évolution et de la sélection naturelle de Darwin, développés par Jon Holland
(1960) [? ]; ce dernier simule mathématiquement les operateurs de croisement et de mutation,
ainsi que la sélection. La méthode d’optimisation par AG a été publiée en 1975 [? ], par Jo
Holland, qui a utilisé le codage binaire, où le chromosome représente un individu (ensemble de
variables), et un gène présente une variable formée d’une chaine de 0 et 1. Dans cette présente
contribution, nous nous intéresserons au codage réel, en raison de sa rapidité et de sa flexibilité

43
(Michalewiz(1992) [? ]).

4.3.1 Sélection:

Cet opérateur, appelé aussi reproduction, assure le rôle principal de dupliquer les meilleures
solutions, et d’éliminer les mauvaises solutions au sein d’une population, en gardant la même
taille de cette dernière. Plusieurs méthodes de sélection existent, dont les quatre plus fréquents
sont:

(a) Sélection par tournois: La sélection par tournoi binomial est l’opérateur choisi pour notre
présente étude. Deux individus x1 et x2 (ou trois, dans le cas d’une sélection trinomiale)
sont tirées aléatoirement, et celui ayant la bonne valeur de la fonction objectif ou fitness,
sera maintenu dans la prochaine génération, pendant que son binôme sera rejeté. On écrit
donc:

si(f (xt1 ) < f (xt2 ))

xt+1 = xt1
si non
xt+1 = xt2

Figure 15 – Sélection par tournoi

(b) Sélection par élitisme: Au cours des opérations de croisement et mutation, il existe
un risque que les meilleurs individus ou chromosomes soient perdus. Afin d’éviter ce
problème, on utilise l’élitisme qui consiste à copier une ou plusieurs meilleures solutions
dans la population de la prochaine génération.

(c) Sélection par roulette: Dans ce type de sélection, on considère une roulette constituée par
des probabilités de sélection d’individus selon leur fitness pour qu’il soit sélectionné dans
la prochaine génération. La probabilité de sélection du iéme individu peut être calculée
comme suit:

Fi
pi = N
(8)
P
Fj
j=1

44
 N
X
Pi = pj (9)
j=1

Figure 16 – Sélection par roulette

Solution i (individu) Fitness Fi pi Pi

1 15 0.15 0.15
2 25 0.25 0.40
3 05 0.05 0.45
4 45 0.45 0.90
5 10 0.1 01.00

Table 13 – Exemple de sélection par roulette

Par la suite, la probabilité cumulative de chaque individuest calculée en additionnant

les probabilités individuelles précédentes jusqu’au dernier individu de la population qui
a une probabilité cumulée égale à 1 (Eq(9)). Ensuite, un nombre aléatoire entre 0 et 1
est généré (c’est l’équivalent pour faire tourner la roue); par conséquent, l’individu est
sélectionné si ce nombre aléatoire se situe dans leur zone de probabilité dans la roulette.

(d) Sélection par rang: Dans l’opération précédente, la chance de sélectionner des individus
devient possible qu’à une grande probabilité, ce qui provoque une stagnation d’évolution.
La sélection par rang peut régler ce problème. La probabilité étant basée sur le rang,
la population est triée selon leur fitness du mauvais individu qui aura le rang 1 jusqu’au
meilleur individu qui est classé au dernier rang ; ensuite, la probabilité de sélection est
calculée à partir de la position du rang divisé par la somme des rangs. Le tableau 14
montre bien la différence entre les deux types de sélection précédents. On note que
l’inconvénient commun de ces deux méthodes réside dans les mauvaises solutions qui
peuvent être toutes choisies pour la prochaine génération.

45
 Solution i (individu) Fitness Fi Rang pi Pi
1 15 3 0.2 0.2
2 25 4 0.26 0.4667
3 05 1 0.066 0.5333
4 45 5 0.33 0.8667
5 10 2 0.13 1.00
Total 100 15

Table 14 – Exemple de sélection par rang

4.3.2 Croisement

Le rôle de la sélection étant juste de reproduire les meilleures solutions, et ne pas en créer de
nouvelles, le croisement est par contre une opération génétique qui consiste à créer un nouveau
chromosome, appelé enfant, à partir de deux chromosomes parents croisés et tirés aléatoirement.
Il existe plusieurs formes qui expriment cet opérateur selon le type de codage employé.

(a) Codage binaire: Dans ce type de codage, l’individu (solution) qui est considéré génétiquement
comme un chromosome, est représenté par une chaı̂ne binaire constituée par une suite de
bits (formée de 0 et 1).

(a) Exemple de codage binaire d’un individu à (b) Schéma illustratif d’un croisement d’individus
trois variables de décision à une seule variable

Figure 17 – Croisement des chromosomes

Pour évaluer les individus, il faut les décoder, c. à.d passer de la forme binaire à la forme
décimale. La formule pour les chiffres entiers s’écrit comme suit :
n
X
x= a 2n−i (10)
i=1

Sachant que n est la longueur de la chaı̂ne binaire de la variable, pour les nombres réels,
la formule est donnée par:
n  
X
n−i xmax − xmin
x = xmin + a2 (11)
i=1
2n − 1

Avec xmin et xmax : les valeurs des deux bornes de l’intervalle de variation de x. On note
que certains types de croisement sont basés sur plusieurs points de coupage.

46
 (b) Codage réel: Il est connu que le nombre de bits choisi doit être suffisant pour représenter
tout l’intervalle de la variable de décision. On utilise la condition 2n > s pour vérifier la
représentation du nombre dans le cas du nombre entier positif, et s indique un nombre
entier lui-même. Dans le cas des variables réelles, s indique le nombre de variables qui
peuvent être représentées par la chaı̂ne binaire. Dans ce cas-là, on parle de la précision, qui
est l’un des points de faibles du codage binaire. Par exemple, pour représenter un individu
contenant une seule variable dans le domaine [-300, 300], il faut une chaı̂ne d’une longueur
de 30 pour une précision de 10−6 , et pour 100 variables de décision, le problème a besoin
d’une chaı̂ne binaire de 3000, et cela demande de la mémoire et du temps de calcul assez
substantiels. Le codage réel peut régler cet inconvénient, où l’individu est représenté par
les propres valeurs réelles de leur variable de décision. Dans le cadre de notre contribution,
nous employons un type de croisement, appelé croisement intermédiaire [? ], qui permet
de créer deux enfants à partir de deux parents. Ce croisement est contrôlé par un ”ratio”
:
xt+1
1 = xt1 + rand × ratio × (xt2 − xt1 )
(12)
xt+1
2 = x t
2 − rand × ratio × (x t
2 − x t
1 )
où rand est un nombre aléatoire entre [0, 1], et ratio est un ratio constant entre [0 ,1],
pouvant être supérieur à 1, s’il y a un problème de convergence prématurée, le ratio sera
égale à 1.2. Il existe d’autre type de croisement pour le codage réel appelé “Simulated
Binary Crossover (SBX)” ([? ], [? ]), ce type est exprimé comme suit:

xt+1
1 = 21 [(1 + β)xt1 + (1 − β)xt2 ]
(13)
xt+1
2 = 12 [(1 − β)xt1 + (1 + β)xt2 ]

avec: (
1
(2 rand) ηc +1 si rand≤0.5
β= 1 (14)
2 rand
( 2(1−rand) ) ηc +1 si non

ηc l’indice de distribution de croisement, il détermine l’écart entre les enfants et leurs

parents. Les plus grandes valeurs de ηc sont plus susceptibles de produire des solutions
proches de parent, tandis que les plus petites valeurs de mènent à une recherche plus
diversifiée.

4.3.3 Mutation

L’opération de mutation consiste à remplacer aléatoirement un individu par un autre selon une
certaine probabilité P m. Biologiquement, la probabilité de mutation ne dépasse pas les 1 %,
mais dans les algorithmes génétiques, la mutation augmente la diversité de la population afin
d’améliorer la recherche locale et/ou éviter les points d’optimum local ; donc la probabilité de
cette importante opération peuvent être élevée jusqu’à 10 %. Certains auteurs ont choisis une
P m = 1/l, avec l : nombre de variables de décision [? ].

(a) Codage binaire: Dans le codage binaire, la mutation est simple, un bit ai ∈ {1, 0} choisi
aléatoirement est remplacé par un complémentaire a∗i = 1 − ai .

47
 Figure 18 – Schéma illustratif d’une mutation simple

(b) Codage réel: Une mutation gaussienne [? ] a été préférée avec une probabilité de P m =
0.1 ; cette méthode ajoute une distribution normale aléatoire randn pour chaque variable,
telles que:
xt+1 t
id = xi + S  × randn × (xd max − xd min ) (15)
S = scale × 1−shrink×(t+1)
tmax

Sachant que scale est un paramètre qui détermine une déviation standard du nombre
aléatoire généré, sa valeur est entre [0 ,1]([? ]), shrink est un nombre entre [0.5, 1.0].
Dans notre cas, nous prenons scale = 0.1 et shrink = 0.5. mutation polynomiale peut
être utilisée pour un codage réel en utilisant les expressions suivantes:

xt+1
id = xtid + (xd max − xd min )δd
1
(2u) ηm +1 si u<0.5 (16)
δ= 1
1−(2(1−u)) ηm +1 si u≥0.5

ηm l’indice de distribution de mutation.

L’organigramme (19) ci-dessous explicite le fonctionnement des algorithmes génétiques clas-

siques.

48
 Figure 19 – Organigramme des algorithmes génétiques, version réelle

4.4 Optimisation par essaim particulaire

L’algorithme d’optimisation par essaim particulaire ou (particle swarm optimisation (pso)), a
été développé par [Link] and [Link] en 1995 ([? ]). Cet algorithme est basé sur
la simulation du comportement d’un essaim d’oiseaux ou de poissons; une particule ou un
individu représente un oiseau qui est analogiquement un ensemble de variables(position) dans
un problème d’optimisation. Lorsque l’individu se déplace d’une position à l’autre, il est affecté
par trois facteurs principaux:
-L’attirance vers le chef de groupe (gbest).
-L’attirance vers la meilleure position par laquelle il est passé (pbest).
-Rester dans la même position actuelle.

49
Ceci est noté par:

(t+1) (t) (t) (t) (t)

Vid = w × Vidt + C1 × rand × (pbestid − xid ) + C2 × rand × (gbestid − xid )
(t+1) (t) (t+1) (17)
xid = xid + Vid

Sachant que le pbest est la meilleure position passée par l’individu, gbest, ou global best, est la
meilleure position (individu) de toutes les positions dans toutes les générations, la vitesse des
variables de décision est Vidt , C2 = C1 = 2.0, sont des taux d’apprentissage cognitif et taux
d’apprentissage social respectivement, w est le facteur de l’inertie, qui peut être fixé à 0.5, ou
varié de 0.9 jusqu’à 0.4 pendant la phase d’itérations. La méthode de décrémentation linéaire
d’inertie d’optimisation par essaim particulaire (linearly decreasing weight particle swarm op-
timization (LDW-PSO) proposé par [Link] and [Link] [? ] est alors :

tmax − t
w(t) = wmin + ( ) × (wmax − wmin ) (18)
tmax

Où wmin et wmax sont les valeurs minimales et maximales du facteur d’inertie.

50
 (a) Algorithm de PSO (b) Le déplacement de l’individu par PSO

Figure 20 – Principe de PSO

L’organigramme 20a et la figure 20b décrivent le fonctionnement d’un algorithme PSO

standard.

4.5 Traitement des contraintes pour les méthodes globales

Dans la littérature [? ], [? ], [? ], pour les méthodes globales, la méthode de pénalité est la
plus utilisée, mais sa difficulté réside dans le choix du coefficient de pénalité le plus rentable
(convenable ou efficace), selon le problème posé. Les contraintes de variable (les espaces de
recherche) sont traitées différemment, telles qu’elles n’aient aucune influence sur la fitness (sans
pénaliser la fonction objectif), mais doivent être respectées pendant l’évolution de la population.

51
Les deux autres types sont traités par la technique de la fonction de pénalité statique ([Link]
et al [? ]). Cette technique consiste à pénaliser la solution qui est située dans la région non
faisable, avec une constante de pénalité satisfaisant le problème d’optimisation. On écrit :
m
P
Fitness =f+ Ci δi
i=1
(19)
(
δi = 1, si la contrainte est violée
Avec
δi = 0, si la contrainte est respectée

par exemple, on a une contrainte g(x) ≤ 0, pour un ensemble de x donnant un g(x) > 0 , δ = 1;
C est un constant de pénalité choisi par l’utilisateur. Les fonctions de pénalité peuvent porter
à la fois sur l’égalité et l’inégalité des contraintes, et l’approche normale consiste à transformer
une égalité en une inégalité de la forme :

|hj (x)| − ε < 0

où ε est la tolérance autorisée (une très petite valeur).

D’autre formule qui est fréquemment utilisée, c’est la pénalité dynamique [? ]

f itness = f (x) + (C ∗ t)α ∗SVC(β,x)

où C, α et β sont des constantes définies par l’utilisateur (par exemple C = 0.5, α= 1 ou 2, et
β = 1 ou 2), t indique la génération càd l’itération. SVC(β,x) est définie comme:

n p
X X
SVC(β,x) = Diβ (x) + Dj (x)
i=1 j=1

avec:
(
0 , gi (x) ≤ 0
Di (x) = 1≤i≤n
( |gi (x)| sinon

0 − ε ≤ hj (x) ≤ ε
Dj (x) = 1≤j≤p
|hj (x)| sinon
Références

DANTZIG, G. B. 1966. Applications et prolongements de la programmation linéaire:” Lin-

ear programming and extensions”, par George B. Dantzig,... Traduit et adapté par E. Elio
Ventura, Dunod.

DODGE, Y., GONANO-WEBER, S. & RENFER, J.-P. 2004. Optimisation appliquée Springer
Science & Business Media.

52
53