III-4 Formalisation et programmation
La PSO peut facilement être formalisée et
programmée. L'espace de recherche est de dimension D.
La position courante d'une particule dans cet espace à
l'instant t est donnée par un vecteur Pd (
t) , à D
composantes, donc. Sa vitesse courante est Vd (
t) . La meilleure position trouvée jusqu'ici
par cette
particule est donnée par un vecteur Pdb (
t) . Enfin, la meilleure de celles trouvées par les
informatrices de
la particule est indiquée par un vecteur Pdg (
t) . Avec ces notations, les équations de mouvement
d'une particule sont, pour chaque dimension d [30]
V ( t ) V ( t - 1 ) .r ( P
= + C - P t
( 1) ) .r ( P
- + C - P t
( 1) )
-
d d 1 1 db d 2 2 dg d
Pd ( t ) = Pd( t
-1) + Vd (t)
Vd ( t) : Est la vitesse d'une
particule.
Pd ( t) : Est le déplacement d'une
particule.
r1 , r 2 : Sont des nombres aléatoires
compris dans l'intervalle [0,1]. C1 , C
2: Sont des constantes positives où C1 +
C2 = 2
III-4.1 Initialisation de l'essaim et Nombre de
particules
La position des particules ainsi que leur vitesse initiale
doivent être initialisés aléatoirement. Cependant, en ce
qui concerne la position des particules, il est préférable
d'utiliser un générateur de séquence de
SOBOL qui est plus pertinent dans la disposition homogène des particules
dans un espace de dimension n. La quantité de particules allouées
à la résolution du problème dépend essentiellement
de deux paramètres :
· La taille de l'espace de recherche
· Le rapport entre les capacités de calcul de la
machine et le temps maximum de recherche.
Il n'y a pas de règle pour
déterminer ce paramètre, faire de nombreux essais permet de se
doter de l'expérience nécessaire à
l'appréhension de ce paramètre.
III-4.2 Coefficient de constriction
Afin d'éviter que les particules ne se
déplacent trop rapidement dans l'espace de recherche,
passant éventuellement à côté de
l'optimum, il peut être nécessaire de fixer une
vitesse maximale (notée V max) pour améliorer la convergence de
l'algorithme. Cependant, on peut s'en passer
si on utilise un coefficient de constriction k et qui permet de resserrer
l'hyperespace de recherche. L'équation
de la vitesse devient alors :
|
1
k = -
1 +
( C r C r
. + . )
1 1 2 2
|
|
( C r C r
+ ) (
2
. . - 4 .
C r C r
+ . )
1 1 2 2 1 1 2 2
|
|
2
|
V t
( ) ( ( ) (
= K . V t - 1 + C .r P - P t
( 1) .r P
- +
) (
C - P t
( 1) )
- )
d d 1 1 db d 2 2 dg d
Les études de SHI et
EBERHART indiquent que l'utilisation
d'un coefficient de constriction donne
généralement un meilleur taux de convergence sans avoir à
fixer de vitesse maximale. Cependant, dans certains cas, le coefficient de
constriction seul ne permet pas la convergence vers la solution optimale pour
un nombre d'itérations donné. Pour
résoudre ce problème, il peut être intéressant de
fixer Vd max = pdmax en plus du coefficient de constriction,
ce qui, selon les études de SHI et
EBERHART, permet d'améliorer les
performances globales de l'algorithme.
| 
