Particules swarm optimisation (PSO)
L’Algorithme d’Optimisation par Essaim des Particules (EOEP) est un algorithme d’IE, proposé par le psychologue James Kennedy et l’ingénieur en électricité Russel Elberhart en 1995. Ces deux chercheurs ont utilisés les études de Craig Reynolds sur le comportement social d’un groupe d’oiseaux, à la fin des années 1987.
La source d’inspiration :
L’AOEP s'est inspirée d’un phénomène sociologique associé au flocage des oiseaux, et très précisément le comportement de recherche de nourriture. Naturellement, les oiseaux volent en groupes nombreux sans collision et faisant usage de leurs efforts pour maintenir une distance optimale entre eux ainsi qu’une interaction locale afin d’atteindre l’objectif commun visé par le groupe.
Le phénomène du flocage est défini clairement dans le scénario suivant : au départ, un groupe d'oiseaux est à la recherche au hasard de nourriture dans une zone. Il y a seulement un morceau de nourriture dans la zone recherchée. Les oiseaux ne savent pas où est la nourriture, mais ils savent à quelle distance se trouvent et les positions de leurs voisins. Alors, une question se pose: Quelle est la meilleure stratégie pour trouver de la nourriture ? Une stratégie efficace celle de suivre l'oiseau qui est le plus proche de la nourriture.
Résumé de l’algorithme :
Généralement, l’AOEP est utilisée pour faire face aux problèmes dans lesquels une meilleure solution peut être représentée comme un point ou une surface dans un espace à N dimensions. Il est basé sur une population de solutions (particules) aléatoirement générer (chaque solution est comme un oiseau). Chaque particule est associée à une vitesse et une position initiale. Au fil du temps, les particules se déplacent à travers l’espace de recherche avec des vitesses ajustées dynamiquement en fonction de leurs performances et en mettant à jour chaque solution pour diriger le processus de recherche. Par conséquence, les particules ont tendance à voler vers la zone de recherche optimale où ils sont évalués en fonction de certains critères de fitness après chaque étape dans le temps et aussi grâce à des règles simples en suivant les particules avec les meilleures solutions (meilleure valeur de fitness) pour pouvoir converger progressivement vers un minimal local.
Le processus général :
L’entrée de l’AOEP est un ensemble de particules. Chaque particule est caractérisée par sa position, sa meilleure position trouvée, la meilleure position trouvée par son voisinage et sa vitesse. Durant le processus de recherche, nous ajustons la position de chaque particule dans l’espace de recherche, en nous basant sur sa meilleure position trouvée (Pbest) et la meilleure position trouvée par son voisinage (gbest). L’architecture générale de l’AOEP est présentée dans la figure suivante :
Chaque étape du fonctionnement de l’AOEP est détaillée par la suite:
Particules initiales:
La génération de N solutions (particules) initial est basée sur la génération aléatoire de la vitesse et la position de chaque particule.
Evaluation :
Cette étape permet d’évaluer la qualité de chaque solution, en évaluant la position de chaque particule afin de détecter la meilleure position parmi les performances de toutes les particules.
Changement de vitesse :
Itérativement, chaque particule change sa vitesse en fonction de sa position courante et la meilleure position de son voisinage. La mise à jour des vitesses des particules est effectuée.
Déplacement :
Le déplacement de chaque particule d’une position à une autre est basé sur sa position courante et sa vitesse de déplacement. La prochaine position de chaque particule est calculée.
Comparaison et mise à jour :
Nous comparons la position courante de chaque particule avec sa meilleure position trouvée dans les étapes précédentes.
Problème 1 : trouver le minimum de la fonction suivante : F(x, y)= (x-3)2+(y-6)2 avec : -100≤x,y≤ 200
Problème 2 : écrire un programme en utilisant le langage de programmation que vous voulez qui permet de minimiser l’équation suivante :
avec:
Problème 3 : adapter le PSO pour un problème de classification.
Problème 4 : Résoudre le problème de voyageur de commerce en utilisant le PSO.
Problème 5 : Combiner l’algorithme PSO avec un algorithme de classification non supervisée comme le k-moyenne, k-médoide, fuzzy-c-means.
Problème : réduction du dimension
Problème IOT :
1- Adapter le PSO pour découvrir les endroits des terroristes ou pour feuiller une piste, découvrir les voleurs à travers des caractéristiques comme les gestes, les vêtements et reconnaissance facial. Pour cela vous devez utiliser des capteurs (équipé d’une caméra de surveillance) qui volent.
2- Adapter le PSO pour le problème du Formation flying est le vol discipliné de deux aéronefs ou plus sous le commandement d'un chef de vol.
3- Trajectory Planning : La planification de trajectoire est parfois appelée planification de mouvement et erronée en tant que planification de trajectoire.