III-3.1 Principe Caractéristiques
L'optimisation par essaim de particules
repose sur un ensemble d'individus originellement
disposés de façon aléatoire et homogène, que nous
appèlerons dès lors des particules, qui se déplacent dans
l'hyperespace de recherche et constituent, chacune, une
solution potentielle. Chaque particule dispose d'une
mémoire concernant sa meilleure solution visitée ainsi que la
capacité de communiquer avec les particules constituant son entourage.
A partir de ces informations, la particule va suivre une
tendance faite, d'une part, de sa volonté à
retourner vers sa solution optimale, et d'autre part, de son
mimétisme par rapport aux solutions trouvées dans son
voisinage.
A partir d'optimums locaux
et empiriques, l'ensemble des particules va, normalement,
converger vers la solution optimale globale du problème traité.
Ce modèle présente quelques propriétés
intéressantes, qui en font un bon outil pour de nombreux
problèmes d'optimisation, particulièrement les problèmes
fortement non linéaires, continus ou mixtes (certaines variables
étant réelles et d'autres entières) :
1) Il est facile à programmer, quelques lignes de code
suffisent dans n'importe quel langage évolué.
2) Il est robuste (de mauvais choix de paramètres
dégradent les performances, mais n'empêchent pas d'obtenir une
solution).
Figure III-9 : Schéma de
principe du déplacement d'une particule.
Signalons, de plus, qu'il existe des versions adaptatives qui
évitent même à l'utilisateur la peine de définir les
paramètres (taille de l'essaim, taille des groupes d'informatrices,
coefficients de confiance). L'une de ces méthodes (Tribes) est
décrite en détail dans un des documents
téléchargeables à partir du site du séminaire
OEP'03. Son code source est disponible via le site Particle Swarm Central.
III -3.2 Topologie du voisinage
Le voisinage constitue la structure du réseau social.
Les particules à l'intérieur
d'un voisinage communiquent entre-elles. Différents
voisinages ont été étudiés (Kennedy, 1999) et sont
considérés en fonction des identificateurs des particules et non
des informations topologiques comme les distances euclidiennes dans
l'espace de recherche [15] :
A. Topologie en étoile : chaque
particule est reliée à toutes les autres.
l'optimum du voisinage est l'optimum
global.
B. Topologie en anneau : chaque particule est
reliée à n particules (en général, n =3),
c'est la topologie la plus utilisée.
C. Topologie en rayon : les particules ne
communiquent qu'avec une seule particule centrale
Figure III-10 : (a) anneau (avec n
= 2), (b) rayon, (c) étoile.
Le voisinage géographique auquel nous sommes
amenés à penser en premier lieu n'est pas
nécessairement pertinent car, d'une part, il
s'agirait d'un voisinage trop local, et
d'autre part car la socialisation des particules tend à
rendre tout voisinage social en voisinage géographique. Enfin,
c'est un voisinage très lourd en terme de calculs car
nécessitant de recalculer le voisinage de chaque particule à
chaque itération [29].
| 
