Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

I.INTRODUCTION Depuis que l’ordinateur existe, l’homme n’a cessé de le perfecti

I.INTRODUCTION Depuis que l’ordinateur existe, l’homme n’a cessé de le perfectionner pour qu’il soit le plus rapide et le plus performant, mais rien de cela ne serait possible sans la partie logiciel qui vient s’implanté sur ce support. Le logiciel de par son histoire a lui aussi fait un bon gigantesque récemment et encore plus ces dernières années. A l’aire ou les logiciels les plus rapide du marché ne peuvent plus résoudre certains problèmes (de part leur complexité), l’homme s’inspire de plus en plus de la nature qui l’entoure pour mettre en place des algorithmes simulant le comportement des animaux, leurs actions ou réactions vis-à-vis d’un problème et même les méthodes qu’ils utilisent pour y faire face ! Même si ces méthodes sont sujette à de nombreuses controverses de part leur non-exactitude, ils permettent de trouver facilement et rapidement la solution la plus approchée du l’optimale si ce dernier existe, et reste un moyen très efficace pour traitement de problèmes complexes pouvant prendre des années de calculs sans résultats. Dans ce sujet, nous allons faire la connaissance avec une de ces méthodes, celle-ci est dite « optimisation par essaims de particule » dont l’idée directrice est la simulation du comportement collectif des oiseaux à l’intérieur d’une nuée. « Lorsque le soc de la charrue pénètre le sol pour la première fois en automne le champ est vide de tout goéland et quelques minutes après une nuée accompagne le tracteur. Au début du labour un oiseau découvre la source de nourriture et très rapidement un autre arrive et ainsi de suite. Que s’est-il passer ? C’est ce que nous allons comprendre dans ce sujet … » II.UN PEU D’HISTOIRE L'optimisation par Essaim de particule (OEP) ou bien (PSO Particle swarm optimization), a été inventée par Russel Eberhart (ingénieur en électricité) et James Kennedy (socio-psychologue) en 1995. Au départ J. Kennedy et R. Eberhart cherchaient à simuler la capacité des oiseaux à voler de façon synchrone et leur aptitude à changer brusquement de direction tout en restant en une formation optimale. Le modèle qu’ils ont proposé à ensuite été étendu en un algorithme simple et efficace d’optimisation. III.DEFINITIONS III.1.Optimisation Par Essaims de Particule : L'optimisation1 par Essaim de particule (OEP) ou bien (PSO Particle swarm optimization) est une technique utilisée pour explorer l'espace de recherche d'un problème quelconque pour trouver l'ensemble des paramètres qui maximise/minimise un objectif particulier. Cet objectif est atteint en suivant un algorithme dédié que l’on verra par la suite. III.2.Notion de voisinage : Le voisinage constitue la structure du réseau social. Les particules à l’intérieur d’un voisinage communiquent entre-elles. En général, pour une nuée d’oiseaux, le voisinage suit trois types de topologies :  T opologie en étoile (Figure1 (a)) : le réseau social est complet, donc une communication complète et une attirance vers la meilleure particule.  T opologie en anneau (Figure1 (b)) : chaque particule communique avec n voisines immédiates. Chaque particule tend à se déplacer vers la meilleure dans son voisinage local.  T opologie en rayon (Figure1 (c)) : une particule "centrale" est connectée à toutes les autres. Seule cette particule centrale ajuste sa position vers la meilleure, si cela provoque une amélioration l’information est propagée aux autres. Figure 1 : différents types de topologie pour un essaim de particules. 1 : L'optimisation est le mécanisme par lequel on trouve la valeur maximale ou minimale d'une fonction. Ce mécanisme est utilisé dans plusieurs domaines tels que: la physique, chimie, l'économie, et l’informatique…etc. où le but est de maximiser l'efficacité, la productivité et d'autre mesures. IV.L’ALGORITHME PSO Chaque particule représente une solution potentielle dans l’espace de recherche. La nouvelle position d’une particule est déterminée en fonction de sa propre valeur et celle de ses voisines. Soit ⃗ xi(t ) la position de la particule Pi au temps t, sa position est modifiée en ajoutant une vitesse ⃗ vi(t ) à sa position courante : ⃗ xi(t )=⃗ xi(t−1)+⃗ vi(t) La vitesse de chaque particule est mise à jour suivant l'équation suivante: v i(t+1)=ωv i(t )+c1r 1[x pi(t)−xi(t)]+c2r 2[g(t)−xi(t )] vi(t) est la vitesse de particule i à l'instant t et xi(t) est la position de particule i à l'instant t, les paramètres w, c1, et c2 (0 ≤ w ≤ 1.2, 0 ≤ c1 ≤ 2, et 0 ≤ c2 ≤ 2) sont des coefficients constants fixés par l'utilisateur, r 1 et r2 sont des nombres aléatoires tirés à chaque itération, g(t) est la meilleure solution trouvée jusqu'à l'instant t et xp i(t) est la meilleure solution trouvée par le particule i. C’est le vecteur vitesse qui dirige le processus de recherche et reflète la "sociabilité" des particules. Les variables et paramètres de l’algorithme : N nombre de particules ⃗ xi(t ) Position de la particule Pi ⃗ vi vitesse de la particule Pi pbesti Meilleure fitness obtenue pour la particule Pi ⃗ x pbesti Position de la particule Pi pour la meilleure fitness ⃗ xgbest i Position de la particule ayant la meilleure fitness de toutes ρ1,ρ2 valeurs aléatoires positives Initialisations : Initialiser aléatoirement la population. Traitement : Répéter Pour i de 1 à N faire Si F(⃗ xi)> pbesti ¿ ) Alors pbesti←F(⃗ xi) ⃗ x pbesti ← ⃗ xi Fin Si Si F(⃗ xi)>gbesti ¿ ) Alors gbesti←F(⃗ xi) ⃗ xgbest i← ⃗ xi Fin Si Fin Pour Pour i de 1 à N faire ⃗ x pbesti−¿ ⃗ vi←⃗ vi+ ρ1¿ ⃗ xgbesti−¿ ⃗ xi¿+ ρ2¿ ⃗ xi¿ ⃗ xi←⃗ xi+⃗ vi Fin Pour Jusqu’à ce que (le processus converge) La variation de la vitesse est proportionnelle à l’éloignement d’une solution par rapport à la solution globale. Les variables aléatoires ρ1et ρ2 peuvent être définies de la façon suivante : { ρ1=r1c1 ρ2=r2c2 r1 et r2 suivent une loi uniforme sur [0..1] et c1 et c2 sont constantes et représentent une accélération positive, avec c1+c2<¿ 4. Le critère de convergence peut être un nombre fixe d’itérations, suivant la fitness ou bien la variation lorsqu’elle tend vers 0. On remarque qu’il y a Six paramètres qui rentrent en ligne de compte : 1. La dimension du problème. 2. Le nombre de particules. 3. Les valeurs des coefficients ρ . 4. La taille du voisinage. 5. La vitesse maximale. 6. L’inertie. La vitesse peut être limitée par une vitesse maximale V max et une vitesse minimale V min pour éviter que les particules se déplacent trop rapidement ou trop lentement d’une région à une autre dans l’espace de recherche. Un facteur d’inertie Φ peut être appliqué à la vitesse Pour contrôler l’influence de celle-ci. V.APPLICATION DE L’ALGORITHME PSO Nous allons dans ce titre appliquer la notion des essaims de particules dans un problème de maximisation, on va essayer de trouver le maximum global d’une fonction en appliquant la théorie des PSO. L’implémentation de ce projet à été réaliser à l’aide du logiciel DELPHI7 qui utilise comme langage de programmation le pascal orienté objet. La fonction en question s’écrit de la forme : exp −x−sin ⁡ (10x) La courbe décrite par cette fonction est représentée dans la figure qui suit (Figure 2) Figure 2 : Représentation de la courbe : exp −x(1+sin ⁡ (10 x)) . Pour commencer, nous allons générer une population de particules réparties aléatoirement sur le graphe. La courbe représente la fonction sous 20 points, et nous choisissant de prendre une population de 5 particules pour cette expérience. Comme paramètres, r1 et r2 qui suivent une loi uniforme sur [0..1], et on a pris la valeur de 2 pour c1 et c2 (accélération positive maximale) Le paramètre qui influx sur la vitesse est très important, celui-ci noté Φ et qui représente le facteur d’inertie comme dit précédemment a été fixé à 0.8 après plusieurs essais expérimentales. La figure 3 montre la génération de la population et sa position sur le graphe. Figure 3 : Représentation de la population de particules. On remarque dès le début que la population se rapproche instinctivement vers la solution optimale globale comme montré dans la figure 4. Figure 4 : Représentation de la population de particules à l’itération 5. Plus on avance dans le nombre d’itérations plus les particules se rapprochent de l’optimale, et dès qu’une des particules l’a atteint les autres ne tardent pas a la suivre pour enfin la rejoindre dans l’optimum globale à la position 3 avec la valeur 1.03781… vers l’itération 180 comme montré dans la figure 5. Figure 5 : Résultat de la l’algorithme PSO. VI.AUTRE DOMAINES D’APPLICATIONS Dans ce projet, nous avons vu l’utilisation des PSO dans la recherche d’un optimum pour une fonction donné, mais cet algorithme qui est lui-même tiré de la notion qu’utilise les nuée d’oiseaux pour se déplacer s’étend encore bien loin. Citons quelques uns :  La restauration d’image qui est converti en un problème d’optimisation et qui, dans ce cas, présente une fonction coût et qui doit être optimisée. La solution qui donne la valeur optimale constitue l’image désirée.  Recherche de minimas dans les émissions de champs magnétique.  Le principe de la uploads/Litterature/ optimisation-par-essaims-de-particule.pdf