II- 6 Classification des méthodes
d'optimisations :
La complexification croissante des problèmes
d'optimisation, a entraîné le
développement d'une grande quantité de
méthodes de résolution. La globalité de ces techniques
d'optimisation dans les différentes publications, se
divise typiquement en deux grandes classes dont le premier classement les
méthodes déterministes. Et une grande partie de
l'effort de recherche, plus spécifiquement dans les
domaines de la recherche opérationnelle et de
l'Intelligence Artificielle, est consacré depuis une
vingtaine d'années à la deuxième classe
de méthodes d'optimisation : les
métaheuristiques. La classification et illustrée dans la figure
II -5 [13].
Les méthodes
déterministes
Les méthodes
stochastiques
Les méthodes d'optimisations
Les méthodes
heuristiques
Méthodes
Branch bounde
Méthodes
mathématiques
Simplex hook et
rosembrok
Direction
conjuguée
Plus grande
pente
Gradient
conjugué
QuasiNewton
Réseau de
neurones
Les méthodes
évolutionnistes
Mante
carlo
Recuit
simulé
Recherche
taboue
Particule
d'essaim
Plan
d'expérience
Méthodes
D'apprentissage
Algorithme génétique
Stratégie d'évolution
Prog évolutionniste
Evolution différentielle
Figure II-6 : Classification des
méthodes d'optimisations
II- 6. 1 Méthodes déterministes «
locales » :
II-6. 1. 1 Les méthodes de gradient :
Historiquement, les méthodes de gradient sont les plus
anciennes. Elles permettent de résoudre des problèmes non
linéaires et sont basées sur une hypothèse fort : la
connaissance de la dérivée de la fonction objectif en chacun des
points de l'espace. Cette famille de méthodes
procède de la façon suivante :
On choisit un point de départ x0 et
on calcule le gradient ?f (x0 ) en
x0 . Comme le gradient indique la direction de plus grande
augmentation de f , on se déplace d'une
quantité 0 dans le sens opposé au gradient et on
définit le point x1 :
x 1
? f x
( )
0
= -
x (II-16)
0 0 f x
? ( )
0
Cette procédure est répétée et
engendre les points x 0 , x 1 ,...,
xk . Ainsi, pas à pas, la distance entre le point
d'indice k et l'optimum diminue.
? f x
( )
k
x + = -
x ou k
? , > 0
k (II-17)
1 k k k
? f x
( )
k
k est le pas de déplacement à chaque
itération. Si k est fixé, on parle de
méthode de gradient à
pas prédéterminer.
L'inconvénient de cette procédure est que la
convergence est très dépendante du choix du pas de
déplacement. La convergence peut être très lente si le pas
est mal choisi. L'intérêt principal de cette
méthode est de pouvoir se généraliser aux cas de fonctions
non partout différentiables.
Actuellement, la méthode la plus usitée de cette
famille est la méthode de la plus forte pente. Elle permet de se
libérer du choix d'un k mais elle
introduit un critère d'arrêt. Le but de cette
méthode est de minimiser la fonction de :
g ( ) (
= f x k - . ? f x k
( ) ) (II-18)
- Algorithme de la plus forte pente
:
a) Choisie un point de départ x0 et
faire k=0.
b) A l'itération k : d k =
-?f( x k). Recherche k tel que
:
f x
( . ) { ( . ) }
+ d Min f x
= + d pour = 0 x k + 1 = x
k + k . d k .
k k k k k k
c) Si le test d'arrêt est
vérifié alors fin sinon k ? k + 1 et retourner
en b).
L'algorithme de la plus forte pente est à
la base de l'algorithme de Hill-climbing appelé
également algorithme de descente de gradient [14].
| 
