Sommaire

Optimisation par essaims particulaires

Pour la plupart des métaheuristiques, les résultats sont meilleurs si on lance plusieurs exécutions à partir de solutions initiales différentes. En effet, cela permet de parcourir une plus grande zone de recherche.

Cependant, il est possible de retomber plusieurs fois sur la même solution, et de passer à côté de l’optimum global (ou d’un meilleur optimum local).

L’optimisation par essaims particulaires s’inspire de la biologie. En effet, autant chez les oiseaux que chez les poissons, on peut observer de grands groupes d’animaux se déplaçant ensemble en trois dimensions. Les oiseaux (ou les poissons) ne se rentrent cependant pas dedans : la direction de chacun s’adapte en permanence en fonction de la direction actuelle et de la position des autres. Sa vitesse aussi s’adapte.

Dans cet algorithme, plusieurs solutions potentielles cohabitent dans l’espace de recherche, et chacune se déplace dans une direction donnée. À chaque itération, les solutions vont se déplacer comme une nuée, en allant vers les zones qui semblent les plus intéressantes.

Chaque solution doit connaître sa vélocité actuelle, sous la forme d’un vecteur (ce qui permet d’indiquer la direction du déplacement) et les meilleures positions découvertes jusqu’alors. De plus, toutes les solutions de l’essaim connaissent la meilleure solution actuelle ...