essaim particulaire PSO

  • View
    5.042

  • Download
    7

Embed Size (px)

DESCRIPTION

Lapplication de la mthode dessaim particulaire;Optimisation par lessaim particulaire;Introduction sur optimisation par l'essaim particulaire;Origines;Des cription Informelle;Principales caractristiques;Pour en savoir plus sur loptimisation par essaim particulaire;Nombre de particules;Topologie du voisinage;Coefficients de confiance; Vitesse maximale et coefficient de constriction;Facteur dinertie;Initialisation de lessaim;Critres darrt;Lorganigramme de principe de la mthode dessaims particulaires;Exemple dapplication de PSO en langage C;

Transcript

Rpublique Algrienne Dmocratique et Populaire Ecole Normale Suprieurs dEnseignement Technique -ORANDpartement de Gnie Electrique

Magister 1ereOption : Analyse et Commande des Machines Electrique

Module : Techniques doptimisation

Optimisation par la mthode des essaims particulaires Dune fonction trigonomtrique

Mr BOUZID Allal El Moubarek

allalbouzid@live.frSous la direction de : Mr. ABDELMALEKAnne universitaire 2008-2009

SommaireIntroduction Chapitre I Gnralits 03 03 04 04 05 05 05 01

I-1 Informatique bio-inspire I-2 Intelligence collective : conditions dmergence I-3 Intelligence collective et insectes sociaux I-4 Trois rgles locales I-4-1 Sparation I-4-2 Alignement I-4-3 Cohsion Chapitre II PSO

II-1 Loptimisation par les essaims particulaires II-2 Principe de la PSO II-3 tat et comportement dune particule II-4 Information utilise par une particule pour dterminer sa prochaine position II-4-2 Trois types de comportement pondrer II-5 Points essentiels

08 08 09 09 10 12

Chapitre III Formalisation et simulation II.1 Configuration de la mthode II-1-1 Nombre de particules II-1-2 Topologie du voisinage II-1-3 Coefficients de confiance II-1-4 Vitesse maximale et coefficient de constriction II-1-5 Facteur dinertie II-1-6 Initialisation de lessaim II-1-7 Critres darrt III-2. Lorganigramme de principe de la mthode des essaims particulaires III-3 Variantes III-3. Lexemple de la fonction appliqu dans ce programme Conclusion Conclusion gnrale Bibliographie 13 13 13 14 14 14 15 15 16 17 17 19 21 22

Introduction Gnrale

1

Introduction

IntroductionDans le but de crer des systmes autonomes, robustes et volutifs, une nouvelle forme d'ingnierie trouve son inspiration dans les systmes naturels complexes. Par exemple, pour concevoir des systmes scuriss contre les intrusions, il est possible d'imaginer de nouveaux mcanismes inspirs des dfenses immunitaires. Elles doivent tre penses comme des entits auto organises, adaptatives et distribues. L'optimisation des essaims particulaires (PSO) a t l'origine conue et prsente par Eberhart et Kennedy 1995. La PSO est un algorithme de recherche bas sur la population bas sur la simulation du comportement social des oiseaux, des abeilles ou d'une cole des poissons. Cet algorithme prvoit l'origine pour simuler graphiquement la chorgraphie gracieuse et imprvisible des gens d'oiseau. Chaque individu dans l'essaim est reprsent par un vecteur dans l'espace de recherche multidimensionnel. Ce vecteur a galement un vecteur assign qui dtermine le prochain mouvement de la particule et s'appelle le vecteur de vitesse. Sur notre monographie prsent par suite on va sintresser a dfinir loptimisation par les essaims particulaires et bien comprendre comment fonctionne cette mthode en sinspirent pour cela des animaux et leurs comportement puis on va finir par donn un exemple dune fonction trigonomtrique.

Chapitre IGnralits

-3-

CHAPITRE I I-1 Informatique bio-inspire

Gnralits

La bio-inspiration est un changement de paradigme qui amne les ingnieurs s'inspirer de la nature pour dvelopper de nouveaux systmes artificiels. Concerne: Vgtaux. Animaux. Champignons, bactries, virus, . Gnre des applications: Aronautique, Matriaux composites, Intelligence (vie) artificielle, Nanotechnologies, I-2 Intelligence collective : conditions dmergence Une information locale et limite: Chaque individu ne possde qu'une connaissance partielle de lenvironnement. Il n'a pas conscience de la totalit des lments qui influencent le groupe. Un ensemble de rgles simples: Chaque individu obit un ensemble restreint de rgles simples par rapport au comportement du systme global.

Les interactions sont multiples: Chaque individu est en relation avec seulement un ou plusieurs autres individus du groupe. La structure mergente est utile la collectivit Les individus trouvent un bnfice collaborer et leur performance est meilleure que s'ils avaient t seuls.

Le cas des oiseaux migrateurs Les oiseaux migrateurs doivent parcourir de trs longues distances, dans des conditions parfois difficiles Optimiser leur dplacement en termes d'nergie dpense Les oies sauvages adoptent des formations en V o chaque oiseau prend l'aspiration de son prdcesseur o permet d'tendre la distance de vol de prs de 70%

-4-

CHAPITRE I

Gnralits

Le prix payer : o Un individu seul vole en moyenne 24% plus vite qu'une vole o Donc il y a une perte en vitesse

I-3 Intelligence collective et insectes sociaux: L'intelligence collective s'observe : Insectes sociaux (fourmis, termites et abeilles). Animaux se dplaant en formation (oiseaux migrateurs, bancs de poissons)

Points communs qui caractrisent l'intelligence collective : Les individus sont grgaires car ils obtiennent un avantage substantiel chasser, se dplacer ou vivre en groupe. Interagissent de manire locale par le moyen de signaux (grognement, phromones, attitudes). L'individu seul rpond instinctivement certains changements de comportement. La coordination du groupe est implicite. Elle se fait au travers de rgles comportementales trs simples au niveau individuel.

-

-

I-4 Trois rgles locales Comprendre ces phnomnes et la coordination des mouvements (parfois trs brusques) de ces populations. Chaque individus se dplace selon sa propre perception de l'environnement avec des rgles simples : Rgle de sparation. Rgle d'alignement (mimtisme). Rgle de cohsion.

-5-

CHAPITRE I I-4-1 Sparation : Ne pas heurter ses voisins en s'loignant des proches proches.

Gnralit Gnralits

Figure I : Sparation des individus I-1 I-4-2 Alignement : Se dplacer dans la mme direction que l'ensemble en moyennant les vitesses et les directions.

I-4-3 Cohsion : Se maintenir dans le groupe en se dplaant vers le centre peru de la formation

-6-

CHAPITRE I

Gnralits

Ces trois rgles de bases, permettent l'attraction et la rpulsion de chacun des individus et permet la stabilit de l'ensemble.

Plus de nouvelles rgles qui sont: Atteindre un but (perchoir, arbre, nourriture, ) En PSO chaque entit est une solution et le but global est de se rapprocher de la meilleure

Chapitre IILoptimisation par essaims particulaires

-8-

CHAPITRE II

Optimisation par les essaims particulaires

II-1 Loptimisation par les essaims particulaires Optimisation par essaims particulaires (PSO) est relativement un nouvel algorithme de l'rudition computation, en premier a introduit par James Kennedy et Russell Eberhart en 1995. Il porte quelque ressemblance computation volutionnaire. L'objectif de PSO est trouver l'optimum global de quelque multidimensionnel (habituellement non linaire) fonction. L'algorithme a prouv efficace dans rsoudre beaucoup de problmes. Dans PSO, la recherche travers l'espace du problme peut tre pense de comme le vol d'un essaim de particules (points dans l'espace). L'objectif est avoir les particules converger sur l'optimum de la fonction, beaucoup comme un troupeau d'oiseaux converge sur quelque destination. Les particules sont distribues initialement alatoirement travers le problme espacez et donn une vlocit initiale. Chaque particule se tient au courant de son emplacement et aptitude (la valeur de la fonction qui est optimise), aussi bien que la meilleure place (et aptitude correspondante) il a rencontr si loin dans son vol. Avec le temps, la vlocit de chaque particule est ajuste afin qu'il dplace stochastique vers sa propre meilleure place et la meilleure place a trouv par une autre particule dans son voisinage. Le voisinage d'une particule est le sous-ensemble de particules dans l'essaim avec lequel il a la communication directe. Ce rseau de rapports entre toutes les particules est connu comme la sociomtrie, ou topologie de l'essaim. II-2 Principe de la PSO Elle a des agents avec des capacits de perception, mmorisation et calcul limites. Elle est dynamique induite par des interactions locales. Observation de comportements globaux mergents . Une population dagents (ici particules). Coopration plutt que Comptition. Efficace sur un espace de recherche continu. Dynamiques dfinis sur un espace temps discret.

-9-

CHAPITRE II La PSO est efficace dans des domaines varis : Rgulation de systmes lectriques. Conception d'ailes d'avions. Analyse d'images. II-3 tat et comportement dune particule

Optimisation par les essaims particulaires

Modle social simplifi: Mime le comportement dune nue doiseaux (ou banc de poissons). Bas sur les rgles qui permettent de soudain changement de direction, dispersion, regroupement, etc. tat (instantan) dune particule: position (reprsente une solution du problme). vitesse (direction pour un futur dplacement). Comportement : o Se dplacer dans lespace de recherche. o dans le but de se positionner sur des solutions optimales.

II-4 Information utilise par une particule pour dterminer sa prochaine position: Sa vitesse actuelle. Sa meilleure performance. La meilleure performance de ses voisines. Do trois types de comportement goste : suivre sa propre voie. conservateur : revenir en arrire. panurgien : suivre aveuglement le meilleur de tous. III-4-1 Compromis entre les trois types de comportement. Un dplacement est finalement une combinaison. Pondre des trois types de mouvement ; pris en compte de : ltat instantan : position & vitesse (mmoire propre court terme). performance personnelle (mmoire propre long terme). performance des voisins (mmoire partage). Compromis psycho-social, entre confiance en soi et influence de ses relations sociales

- 10 -

CHAPITRE II

Optimisation par les essaims particulaires

II-4-2 Trois types de comportement pondrer:

Figure II-1 Schma de