Algorithmes d’intelligence en essaim

Algorithmes d’intelligence en essaim

Les algorithmes d’intelligence en essaim sont issus de l’étude du comportement col- lectif de certaines espèces comme les oiseaux, les poissons, les fourmis ou encore les abeilles. Par exemple, les fourmis laissent des traces de phéromones pour indiquer à leurs congénères le chemin vers les points d’eau et de nourriture, les abeilles s’agglu- tinent entre elles durant l’hiver pour se protéger du froid et se répartissent les tâches pour organiser la vie de la ruche, les oiseaux adoptent une formation en V pour mini- miser les pertes aérodynamiques lors des longues migrations et les poissons adoptent une formation en banc serré notamment pour se protéger des prédateurs. La figure 3.16 présente quelques exemples d’intelligence en essaim pour différentes espèces animales. Les algorithmes d’intelligence en essaim se caractérisent par l’utilisation d’une popu- lation d’agents. Ici, la notion d’agent se différencie de celle de solution, puisqu’ici chaque individu de la population a la possibilité de communiquer avec les autres membres de Parmi les méthodes citées précédemment, nous avons fait le choix de mettre en œuvre l’optimisation par essaim particulaire ou particle swarm optimization. Cette technique est régulièrement utilisée dans la littérature scientifique pour solutionner des problèmes d’optimisation dans une vaste gamme de domaines d’application.Initialement, les travaux de Reynolds [97] et Heppner [98] ont permis de mettre en évidence que les animaux au sein d’un groupe en mouvement suivent le mouve- ment global du groupe grâce aux déplacements de leurs voisins tout en conservant un espacement optimal entre les individus.

Dans la nature, il est possible de remarquer que la dynamique de déplacement d’un groupe d’animaux peut être très complexe alors que chaque individu pris individuelle- ment n’a qu’une connaissance limitée de sa position dans l’essaim (figure 3.16). Par la suite, en 1995, Kennedy et Eberhart ont repris ces observations pour en dé- duire une métaheuristique de recherche : l’optimisation par essaims particulaires (OEP) [99]. Ainsi, l’OEP exploite ce concept de déplacement coordonné en intégrant une di- mension sociale et une mémoire de groupe aux particules composant l’essaim afin de mener une recherche efficace. La stratégie globale de l’essaim s’adapte alors selon les expériences vécues par chaque particule de l’essaim pour atteindre l’optimum global de l’espace des solutions.La popularité de cet algorithme s’explique, entre autres choses, par sa relative sim- plicité d’implémentation, le faible nombre de paramètres de réglages pour paramé- trer le déroulement de la recherche, sa capacité à explorer efficacement un espace à n−dimensions, ou encore l’utilisation de règles de recherche simple qui n’utilisent pas de gradient.stocke la meilleure position visitée Pi,best et la valeur de la fonction objectif en ce point. Les particules ont également la capacité de se communiquer entre elles la position de la meilleure solution globale connue de l’essaim Gbest.

Chaque solution de l’essaim est codée de manière analogue à un chromosome, par une liste des temps d’arrêt qui seront effectués successivement par les trains en exploita- tion. Une particule est alors un vecteur d’entiers appartenant à un espace n−dimensions et bornés sur chaque dimension du problème. Ces bornes permettent, lors du proces- sus itératif, de ne pas explorer les solutions qui violent les conditions d’exploitations définies en 3.2.3. L’objectif étant que chacune des positions visitées représentent un scénario de stationnement plausible.Au sein de l’essaim, les particules communiquent entre elles via un réseau social appelé voisinage. Il ne s’agit pas ici de voisinage géométrique mais plutôt d’un voi- sinage topologique. Un voisinage spatial nécessiterait de recalculer à chaque itération le nouveau voisinage géométrique des particules ce qui alourdirait la procédure de re- cherche. D’après [87], le choix de la topologie influence grandement les propriétés de convergence de l’OEP.Principalement trois types de topologie de voisinage existent dans la littérature : le voisinage en rayon où toutes les particules ne communiquent qu’avec une particule centrale ; le voisinage en anneau où chaque particule n’est relié qu’avec un nombre limité d’autres particules, les particules tendent alors à se déplacer vers la meilleure particule de son voisinage ; le voisinage en étoile où toutes les particules sont capables de communiquer entre elles [86]. Ici, le choix a été fait d’une communication totale entre tous les individus de l’es- saim. Ce choix est notamment motivé par le fait que dans notre cas, l’espace des solutions a une dimension assez élevée dimEsol ∈ [101; 103], de sorte qu’il y a peu de probabilités que les particules stagnent dans un optimum local. Cette version de l’algorithme d’OEP où tous les individus de l’essaim communiquent entre eux est ap- pelée version globale, puisque toutes les particules ont connaissance d’un même optimal.