Séance Séminaire

Séminaire de Probabilités et Statistique

Convergence en loi de l?algorithme d?optimisation par essaim de particules (PSO)

L'algorithme PSO (Particle Swarm Optimization) est une méta-heuristique stochastique d'optimisation introduite au milieu des années 90, faisant partie de la famille des algorithmes évolutionnistes. PSO est basé sur un comportement "social" de particules parcourant un domaine à la recherche d?un minimum de la fonction de coût. L'allure des trajectoires et le mouvement des particules ont donné leur nom à la méthode. L?algorithme PSO est apprécié pour l?absence de calcul de gradient et pour son accommodation aux espaces de recherche de grande dimension. Toutefois, sa convergence n'est pas assurée. Dans cet exposé, nous nous plaçons dans le cas où PSO converge. Notre objectif est de donner des intervalles de confiance pour le point de convergence de l'algorithme. Nous sommes amenés à considérer deux situations : un cas où les particules oscillent entre un minimum local et le minimum global ; et un second cas où un unique minimum global ou local est détecté, entraînant une convergence à vitesse exponentielle. Nous établissons des théorèmes centraux limites pour chaque particule dans ces deux contextes, l'asymptotique étant liée au nombre d'itérations. Nous obtenons aussi des inégalités de concentration pour tout l'essaim de particules à itération fixée. Les résultats théoriques sont étayés par des simulations.