Optimisation de la topologie de l’OEP via la méthode des colonies de fourmis

Session : PPP-4 / Placement, Partionnement, Packing
Vendredi 12 février 10:30 - 11:50 Salle : CI2-22
Ahmed Nasreddine Benaichouche, Hamouche Oulhadj et Patrick Siarry

L’optimisation par essaim particulaire (OEP) (Particle Swarm Optimization (PSO), en anglais) est une métaheuristique d’optimisation proposée pour la première fois par J. Kennedy et R. Eberhart en 1995, s’inspirant des modélisations statistiques qui permettent de simuler les déplacements de volées d’oiseaux et de bancs de poissons. Dans l’algorithme d’essaim particulaire, la recherche s’effectue par une population d’individus appelés particules. Chaque particule survolant l’espace de recherche, en quête de l’optimum global, est considérée comme solution potentielle du problème. Afin de définir sa direction de vol, une particule se base sur deux types d’informations : une information tirée de sa propre expérience et une information tirée de l’expérience de l’essaim. Les particules de l’essaim communiquent entre elles via un ensemble de liens, qui contrôlent l’échange d’informations, définissant ainsi ce que l’on appelle la "topologie de l’essaim". Dans la littérature, il existe deux approches définissant la topologie de l’essaim : l’approche statique et l’approche dynamique. Dans l’approche statique, la topologie est fixée préalablement et la communication entre les particules se fait de la même manière tout au long du processus de recherche. Les topologies les plus connues pour cette approche sont : la topologie en étoile, la topologie en anneau et la topologie en rayon. Dans l’approche dynamique, la topologie de l’essaim change au cours du processus de recherche. Pour cette approche, la méthode la plus connue et utilisée dans l’OEP standard 2011 est la topologie en étoile stochastique. Dans cette méthode, à chaque itération où la solution globale n’est pas améliorée, le graphe de communication entre les particules change de telle sorte que chaque particule informe aléatoirement K (souvent K = 3) autres particules. Notre méthode est basée sur cette deuxième approche. Néanmoins, au lieu de changer la topologie de manière complètement aléatoire, nous avons essayé d’introduire un brin d’intelligence, afin que la nouvelle topologie permette d’améliorer la fitness de chaque particule, en se basant sur le principe des colonies de fourmis.

Mots clés : Métaheuristiques d’optimisation, optimisation par essaim particulaire, colonies de fourmis, topologie