Remerciez-le!

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

Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Te

Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 41 Dr. BEKAKRA Youcef Chapitre IV : Technique d’Optimisation par Essaims de Particules (PSO) IV.2. Définitions de Base : En règle générale, on ne connaît pas toujours de méthode exacte pour trouver la solution d’un problème d’optimisation en recherche opérationnelle. Dans ce cas on peut d’abord tenter de voir si le problème que l’on étudie n’a pas de problème équivalent qui a déjà été résolu. Si l’on n’a toujours pas trouvé de méthode de résolution alors on utilise ce que l’on appelle une heuristique, c’est-à-dire un algorithme qui donne une solution approchée. Ces algorithmes sont assez intuitifs ou simples. On les déduits grâce à des observations et en faisant preuve de bon sens. Leur principe consiste souvent à explorer un certain nombre de solutions et de mémoriser la meilleure. Ils peuvent faire intervenir le hasard: cela permet de balayer un plus grand nombre de solution éventuelle, mais il faut les exécuter plusieurs fois pour tendre au mieux vers la solution optimale. Certaines heuristiques sont classées parmi les métaheuristiques. Ce sont des algorithmes dont le principe peut être réutilisé pour traiter différents problèmes d’optimisation. Ce sont des principes génériques que l’on adapte selon le besoin. La plus utilisé des heuristiques et la plus simple est la descente stochastique. Voici son fonctionnement dans le cas d’un problème de minimisation : on choisit une solution initiale, on sélectionne au hasard un de ses voisins :  Si la valeur de la fonction objectif pour cette nouvelle solution est plus petite alors on prend ce nouveau point comme point de référence et on observe ses voisins.  Sinon on recherche un autre voisin. On s’arrête quand on se rend compte que l’on ne trouve plus de meilleure solution. IV.3 Optimisation par Essaim de Particules (PSO): IV.3.1 Origines : Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 42 Dr. BEKAKRA Youcef L’optimisation par essaim de particules est une méthode née en 1995 aux Etats Unis sous le nom de Particle Swarm Optimization (PSO). Initialement, ses deux concepteurs, Russel Eberhart et James Kennedy, cherchaient à modéliser des interactions sociales entre des « agents » devant atteindre un objectif donné dans un espace de recherche commun, chaque agent ayant une certaine capacité de mémorisation et de traitement de l’information. La règle de base était qu’il ne devait y avoir aucun chef d’orchestre, ni même aucune connaissance par les agents de l’ensemble des informations, seulement des connaissances locales. Un modèle simple fut alors élaboré. IV.3.2 Principe de la Technique PSO : Cette méthode est inspirée du comportement social des animaux évoluant en essaim. L’exemple le plus souvent utilisé est le comportement des nuées d’oiseaux et des bancs de poissons, (Figure IV.1). (a) (b) Figure IV.1 Groupe de : (a) oiseaux, (b) poissons En effet, on peut observer chez ces animaux des dynamiques de déplacement relativement complexes, alors qu’individuellement chaque individu a une intelligence limitée et une connaissance seulement locale de sa situation dans l’essaim. Un individu de l’essaim n’a pour connaissance que la position et la vitesse de ses plus proches voisins. Chaque individu utilise donc, non seulement, sa propre mémoire, mais aussi l’information locale sur ses plus proches voisins pour décider de son propre déplacement. Des règles simples, telles que “aller à la même Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 43 Dr. BEKAKRA Youcef vitesse que les autres”, “se déplacer dans la même direction” ou encore “rester proche de ses voisins” sont des exemples de comportements qui suffisent à maintenir la cohésion de l’essaim, et qui permettent la mise en œuvre de comportements collectifs complexes et adaptatifs. L’ “intelligence globale” de l’essaim est donc la conséquence directe des interactions locales entre les différentes particules de l’essaim. La performance du système entier est supérieure à la somme des performances de ses parties. Kennedy et Eberhart se sont inspirés de ces comportements socio-psychologiques pour créer le PSO. Un essaim de particules, qui sont des solutions potentielles au problème d’optimisation, “survole” l’espace de recherche, en quête de l’optimum global. Le déplacement d’une particule est influencé par les trois composantes suivantes :  Une composante physique : la particule tend à suivre sa direction courante de déplacement ;  Une composante cognitive : la particule tend à se diriger vers le meilleur site par lequel elle est déjà passée ;  Une composante sociale : la particule tend à se fier à l’expérience de ses congénères et, ainsi, à se diriger vers le meilleur site déjà atteint par ses voisins. Dans le cas d’un problème d’optimisation, la qualité d’un site de l’espace de recherche est déterminée par la valeur de la fonction objectif en ce point. La figure IV.2 illustre la stratégie de déplacement d’une particule. Figure IV.2 Déplacement d’une particule Il faut ensuite définir les voisinages et leur structure, il en existe de deux types :  Les voisinages géographiques : les voisins d’une particule sont ses voisines les plus proches. Ce type de voisinage impose l’utilisation d’une distance pour recalculer à chaque itération (ou toutes les k itérations) les voisins de chaque particule. Ci-dessous, la Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 44 Dr. BEKAKRA Youcef figure IV.3 est un exemple où les voisins d’une particule sont les deux particules qui lui sont le plus proche. Figure IV.3 Exemple de voisinage géographique  Les voisinages sociaux : les voisinages sont établis à l’initialisation et ne sont pas modifiés ensuite. Il existe différentes structures de voisinages sociaux, nous allons vous en présenter quelques uns (Figure IV.4). Figure IV.4 Deux cas de voisinage social IV.3.3 Principe de l’Algorithme PSO : On dispose une fonction objectif à optimiser dans un sens ou dans l’autre. Un essaim est un ensemble de particules positionnées dans l’espace de recherche de la fonction objectif. Le principe de l’algorithme consiste à déplacer ces particules dans l’espace de recherche afin de trouver la solution optimale. Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 45 Dr. BEKAKRA Youcef Au départ de l’algorithme, un essaim est réparti au hasard dans l’espace de recherche, chaque particule ayant également une vitesse aléatoire. Ensuite, à chaque pas de temps :  Chaque particule est capable d’évaluer la qualité de sa position et de garder en mémoire sa meilleure performance, c’est-à-dire la meilleure position qu’elle a atteinte jusqu’ici (qui peut en fait être parfois la position courante) et sa qualité (la valeur en cette position de la fonction à optimiser).  Chaque particule est capable d’interroger un certain nombre de ses congénères de son voisinage et d’obtenir de chacune entre elles sa propre meilleure performance.  A chaque pas de temps, chaque particule choisit la meilleure des meilleures performances dont elle à connaissance modifie sa vitesse en fonction de cette information et de ses propres données et se déplace en conséquence. A partir des quelques informations dont elle dispose, une particule doit décider de son prochain mouvement, c’est-à-dire décider de sa nouvelle vitesse. Pour ce faire, elle combine trois informations :  Sa vitesse actuelle.  Sa meilleure position actuelle.  La meilleure performance (vitesse et position) de ses voisines. Le hasard joue un rôle, grâce à une modification aléatoire limitée des coefficients de confiance, ce qui favorise l’exploration de l’espace de recherche. Naturellement, pour pouvoir être programmé, tout ceci est formalisé dans des équations de mouvement. Un point intéressant est que, contrairement à bien d’autres heuristiques qui restent purement expérimentales, il existe une analyse mathématique précisant les conditions de convergence et le choix des paramètres. IV.3.3.1 Formulation Mathématique de l’Algorithme PSO : Dans un espace de recherche de dimension D , la particule i de l’essaim est modélisée par son vecteur position 1 2 3 ( , , ,..., ) i i i i iD X x x x x    et par son vecteur vitesse 1 2 3 ( , , ,..., ) i i i i iD V v v v v   . Cette particule garde en mémoire la meilleure position par laquelle elle est déjà passée, que l’on note 1 2 3 ( , , ,..., ) i best i best i best iD best i best P p p p p   . La meilleure position atteinte par toutes les particules de l’essaim est notée 1 2 3 ( , , ,..., ) best best best best D best G g g g g   . Au temps t , le vecteur vitesse est calculé à partir de l’équation V.1, [Coo 08]. Chapitre IV Technique d’Optimisation par Essaims de Particules (PSO) Cours : Techniques de l’Intelligence Artificielle 46 Dr. BEKAKRA Youcef   1 1 2 2 ( ) . ( 1) . .( ( 1) ( 1)) . .( ( 1)), 1,..., ij ij ij ij best j best ij v t w v t c uploads/Management/ chapitre-4-cours-tia.pdf