TOPOLOGIE DE VOISINAGE DANS PSO ÉTUDEE T PERFECTIONNEMENT

TOPOLOGIE DE VOISINAGE DANS PSO ÉTUDEE T PERFECTIONNEMENT

Nous avons expliqué précédemment que PSO est un algorithme inspiré d’un compor tement social, comme celui des individus d’un essaim d’oiseaux ou d’un banc de poissons. Ce comportement a été modélisé par les auteurs de PSO en deux équations(1.3.1)et(1.3.2), déjà détaillées au premier chapitre. À partir de ces équations, nous constatons que le dé placement d’une particule est influencé par trois composantes : la composante d’inertie, la composante cognitive et la composante sociale.

Chacune de ces composantes représente une partie de l’équation (1.3.1). Dans ce chapitre, nous allons nous intéresser à la compo sante sociale (i.e. la troisième partie) de cette équation, où nous utilisons le terme gbest ou lbest, selon la version utilisée. L’équation (1.3.1) montre que les relations entre les particules influencent directement leurs vitesses et donc leurs déplacements. Dans la littérature de PSO, il existe plusieurs versions qui utilisent la notion de voisinage d’une particule et ce de manières différentes.

Certaines se servent de la version globale, c’est-à-dire que chaque particule est connectée à toutes les autres particules de l’essaim (i.e. le voisinage d’une particule est l’ensemble des particules de l’essaim); d’autres utilisent la version locale, où chaque particule n’est connectée qu’à une partie des autres particules de l’essaim (i.e. le voisinage d’une parti cule est un sous-ensemble des particules de l’essaim). Le voisinage d’une particule i peut donc être défini comme le sous-ensemble de particules de l’essaim que i peut interroger afin de récupérer ses informations.

Pour intégrer ces notions dans l’équation (1.3.1), nous avons besoin de définir une structure de voisinage entre les particules, qui forme le ré seau de communication entre elles. Cette structure est appelée « topologie de voisinage ». Les auteurs ont proposé deux types de topologies : les topologies statiques et dynamiques. Chaquetype étant plus performant pour certains problèmes que pour d’autres.

Pour avoir unemeilleureperformancedel’algorithme,ilesttrèsimportantdebiendéfinirlatopologie 70 Topologie de voisinage dans PSO : étude et perfectionnement devoisinage, ainsi quelesmodalitésd’échanged’informationsentreparticules.C’estpour quoi, pour accroître les performances de PSO, nous avons élaboré une nouvelle topologie dynamique, que nous avons nommée Dcluster, qui est une combinaison d’une topologie statique (Four-clusters) [Mend 04] et d’une topologie dynamique (Fitness) [Wang 08].

Dans ce chapitre, nous nous concentrons d’abord sur le concept de voisinage, en étu diant les caractéristiques des échanges d’informations entre les particules. Ensuite, nous procédons à une description détaillée de la topologie proposée (Dcluster). Enfin, nous pré sentons une analyse expérimentale, ainsi qu’une comparaison des performances de Dclus ter à celles d’autres algorithmes utilisant différentes topologies connues dans la littérature de PSO.

Notion de voisinage de PSO

Comme nous l’avons vu dans le chapitre 1, l’algorithme PSO est inspiré du compor tement collectif des essaims lors des études et des simulations informatiques de groupes d’animaux (vols d’oiseaux ou bancs de poissons). Ces études mettent en évidence la capa cité d’un individu à rester à une distance optimale par rapport aux autres dans le même groupe et à suivre un mouvementglobalaffecté par les mouvements locaux de ses voisins. Àpartir de ces simulations, les auteurs ont modélisé le comportement des individus par les équations (1.3.1) et (1.3.2).

Dans la pratique, en utilisant l’équation (1.3.1), un réseau doit être défini afin d’établir des connexions entre les particules et leur permettre d’échan ger des informations entre elles. Ce réseau de communication entre les particules est ap pelé topologie de voisinage. Cette topologie contribue à définir un groupe d’informatrices pour chaque particule, c’est ce que l’on appelle le voisinage d’une particule.

Le voisinage d’une particule peut donc être défini comme le sous-ensemble de particules de l’essaim avec lesquelles celle-ci a une communication directe, i.e. chaque particule peut interroger les particules dans son voisinage (ses informatrices) qui, à leur tour, lui transmettent leurs informations. Dans notre description de PSO dans le chapitre 1, nous avons décrit brièvement la version globale de PSO,danslaquelle toutes les particules ont accès à l’information globale gbest de la population. Toutefois, ce n’est pas le seul choix possible, et il existe des essaims dans lesquels les particules ont accès à des informations locales, ou à des informations à la fois globales et locales