CHAPITRE II. METHODES D'OPTIMISATION
- Croisement : l'individu xi,t est
mélangé avec le mutant, produisant ainsi le vecteur test
ui,t+1 suivant cette formule : ui,t+1 = EDj=1 .uji,t.
Où :
ui,t+1 =
r(j) E [0, 1] : la jeme évaluation d'une
distribution aléatoire uniforme
CR :la constante de croisement.
rn(i) E {1, 2, ... , D} : un indice aléatoire assurant
que ui,t+1 obtient au moins un élément de vi,t+1.
- Selection : un individu est
sélectionné si l'individu test ui,t+1 permet une
amélioration de la fonction objectif par rapport à
xi,t. un individu sélectionné participe à la
prochaine génération, dans le cas contraire, il est uniquement
retenu pour servir de parent lors de la prochaine génération.
Algorithm : DIFFERENTIAL_ EVOLUTION
1 :Generer (P0) selon une distribution uniforme
2 : for t = 0 to T do
//T générations
3 : for i = 0 to N do
// N individus
4 : choisirAléatoire (xr1,t, xr2,t, xr3,t)
5 : creeMutant(vi,t, xi,t,xr1,t, xr2,t, xr3,t) //
mutation
6 : creeIndividuTest(ui,t, vi,t, xi,t) //croisement
7 : if f(ui,t) < f(xi,t)
then
8 : xi,t+1 <-- ui,t // selection
9 : else xi,t+1 <-- xi,t
10 : end for
11 : end for
II.2.8 Discussion
En général, l'efficacité des
méthodes de recherche locale simples est très peu satisfaisante.
D'abord, par définition, la recherche s'arrête au premier minimum
local rencontré, c'est là leur principal défaut.
Le recuit simulé présente l'avantage d'offrir
des solutions de bonne qualité, tout en restant simple à
programmer et à paramétrer. Il offre autant de souplesse d'emploi
que l'algorithme de recherche local classique. Aarts, Korst et
Laarhoven (1997) ont démontré que, sous
certaines conditions de décroissance de la température,
l'algorithme du recuit simulé converge en probabilité vers un
optimum global lorsque le nombre d'itérations tend vers l'infini.
La méthode Tabou est une méthode de recherche
locale, et la structure de son algorithme de base est assez proche de celle du
recuit simulé, avec l'avantage, d'avoir un paramétrage
Simplifié. En revanche, la méthode Tabou exige une gestion de la
mémoire de plus en plus lourde à mesure que l'on voudra raffiner
le procédé en mettant en place des stratégies de
mémorisation complexe.
Les algorithmes génétiques sont coûteux en
temps de calcul, puisqu'ils manipulent plusieurs
I vij,t+1 si (r(j) < CR ou j = rn(i))
xij,t si (r(j) > CR et j =6 rn(i))
14
15
| 
