27
République Algérienne Démocratique et Populaire ECOLE NORMALE SUPERIEURE D’ENSEIGNEMENT TECHNIQUE - ORAN - DÉPARTEMENT DU GÉNIE ELECTRIQUE MAGISTER 1 ERE ANNEE OPTION ANALYSE ET COMMANDE DES MACHINES ELECTRIQUES MODULE TECHNIQUE D’OPTIMISATION Sous la direction de : Mr .ABDELMALEK. Réalisé par : Mr. HAMANE Bekhada. Promotion 2008-2009 L’application de la méthode d’essaim particulaire

L’application de la méthode d’essaim particulaire

Embed Size (px)

DESCRIPTION

L’application de la méthode d’essaim particulaire;Optimisation par l’essaim particulaire;Introduction sur optimisation par l'essaim particulaire;Origines;Description Informelle;Principales caractéristiques;Pour en savoir plus sur l’optimisation par essaim particulaire;Nombre de particules;Topologie du voisinage;Coefficients de confiance; Vitesse maximale et coefficient de constriction;Facteur d’inertie;Initialisation de l’essaim;Critères d’arrêt;L’organigramme de principe de la méthode d’essaims particulaires;Exemple d’application de PSO en langage C;Exemple 1 : Recherche du champ minimum entre deux stations;Exemple 2 : Recherche le point minimum d’une fonction.

Citation preview

Page 1: L’application de la  méthode d’essaim particulaire

République Algérienne Démocratique et Populaire

ECOLE NORMALE SUPERIEURE D’ENSEIGNEMENT TECHNIQUE

- ORAN -

DÉPARTEMENT DU GÉNIE ELECTRIQUE

MAGISTER 1ERE ANNEE

OPTION

ANALYSE ET COMMANDE DES MACHINES ELECTRIQUES

MODULE TECHNIQUE D’OPTIMISATION

Sous la direction de : Mr .ABDELMALEK.

Réalisé par : Mr. HAMANE Bekhada.

Promotion 2008-2009

L’application de la méthoded’essaim particulaire

Page 2: L’application de la  méthode d’essaim particulaire

Sommaire

Introduction générale 01

Chapitre I : Optimisation par l’essaim particulaire

I.1. Introduction sur optimisation par l'essaim particulaireI.2.OriginesI.3.Description InformelleI.4. Principales caractéristiquesI.5. Pour en savoir plus sur l’optimisation par essaim particulaire

0404040607

Chapitre II : Application de la méthode d’essaim particulaire en C

II.1. ApplicationsII.2. Configuration de la méthodeII.2.1. Nombre de particulesII.2.2. Topologie du voisinageII.2.3. Coefficients de confianceII.2.4. Vitesse maximale et coefficient de constrictionII.2.5. Facteur d’inertieII.2.6. Initialisation de l’essaimII.2.7. Critères d’arrêtII.3. L’organigramme de principe de la méthode d’essaims particulairesII.4 .Exemple d’application de PSO en langage CII.4.1. Exemple 1 : Recherche du champ minimum entre deux stationsII.4.2. Exemple 2 : Recherche le point minimum d’une fonction

09101010101111121213141416

Conclusion généraleL’annexe : Code source en C d’une version simple de PSORéférence Biographique

171825

Page 3: L’application de la  méthode d’essaim particulaire

Introduction Générale :

1

L’apparition des algorithmes évolutionnistes à fait l’effet d’une bombe dans les domaines de la

résolution de problèmes complexes, et spécialement dans l’optimisation de fonction avec

contraintes.

Pour cela nous présentons une métaheuristique apparue dernièrement : la méthode d’optimisation

par l’essaim particulaire (OEP).

L'OEP est une technique encore peu connue en France, fondée sur la notion de coopération entre

des agents (Les particules) qui peuvent être vus comme des « animaux » aux capacités assez

limitées.

L'échange d'information entre eux fait que, globalement, ils arrivent néanmoins à résoudre des

problèmes difficiles, comme c'est le cas, par exemple, chez les abeilles vivant en essaim

(exploitation de sources de nourriture, construction de rayons, etc.).

Après une présentation succincte des origines, le travail propose une description informelle de

l’OEP, puis en dégage les principales caractéristiques. Simple à comprendre, à programmer et à

utiliser, la PSO se révèle particulièrement efficace pour les problèmes d'optimisation non

linéaire.

La monographie se termine par configuration et une application de la méthode d’essaim

particulaire en programmation en C.

Page 4: L’application de la  méthode d’essaim particulaire

2

Page 5: L’application de la  méthode d’essaim particulaire

Chapitre I Optimisation par l’essaim particulaire

3

I.1.Introduction sur Optimisation par l’essaim particulaire: [1] [2] [3] [4]

Optimisation de l'essaim de la particule (PSO) est un relativement nouvel algorithme de

l'érudition computation, en premier a introduit par James Kennedy et Russell Eberhart en 1995.

Elle porte quelque ressemblance à computation évolutionnaire.

L'objectif de PSO est trouver l'optimum global de quelque multidimensionnel (habituellement

non linéaire) fonction.

L'algorithme a prouvé efficace dans résoudre beaucoup de problèmes.

Dans PSO, la recherche à travers l'espace du problème peut être pensée 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 de comme un troupeau d'oiseaux converge sur quelque

destination. Les particules sont distribuées initialement aléatoirement à travers le problème

espacez et donné une vélocité initiale.

Chaque particule se tient au courant de son emplacement et aptitude (la valeur de la fonction qui

est optimisée), aussi bien que la meilleure place (et aptitude correspondante) il a rencontré si loin

dans son vol.

Avec le temps, la vélocité de chaque particule est ajustée afin qu'il déplace 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 réseau de rapports entre toutes les particules est connu comme la

sociométrie, ou topologie de l'essaim.

L'algorithme arrête quand quelque critère a rencontré quand PSO est appliqué aux problèmes

vécus, les évaluations de la fonction elles-mêmes sont la partie la plus chère de l'algorithme.

Par conséquent, quand comparer deux variations PSO, c'est utile s’ils les deux ont utilisé le

même nombre d'évaluations de la fonction.

Dans les expériences qui suivent, l'essaim est distribué un certain nombre d'évaluations de la

fonction et termine quand ce nombre est atteint.

Page 6: L’application de la  méthode d’essaim particulaire

Chapitre I Optimisation par l’essaim particulaire

4

I.2.Origines : [1] [2] [3] [4]

L’optimisation par essaim particulaire (OEP) est une méthode née en 1995 aux états unis sous le

nom de L'optimisation de l'essaim de la particule (PSO).

Initialement, ses deux concepteurs, Russel Eberhard James Kennedy, cherchaient à modéliser

des interactions sociales entre des «agents » devant atteindre un objectif donne dans un espace

de recherche commun, chaque agent ayant une certaine capacité de mémorisation et de

traitement de l’information.

La règle des bases étant 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.

Des les premières simulations, le comportement collectif de ces agents évoquait celui d’un

essaim d’être vivants convergeant parfois en plusieurs sous- essaims vers des sites intéressants.

Ce compétemment se retrouve dans bien d’autre modèle, explicitement inspires des systèmes

naturels. Ici, la métaphore la plus pertinente est probablement celle de l’essaim d’abeilles,

particulièrement du fait qu’une abeille ayant trouve un site prometteur sait en informer certaines

de ces consœurs et que celle-ci vent tenir comte de cette information pour leur prochain

déplacement.

Le fonctionnement de l’OEP fait qu’elle peut être rangée dans les méthodes itératives ‘on

approche peut à peut de la solution) et stochastique. Sous ce terme un peu technique, on

retrouve un comportement qui aussi vieux que la vie elle- même : améliorer sa situation en ce

déplaçant partiellement au hasard et partiellement.

I.3. Description Informelle : [1] [2] [3] [4]

La version historique peut facilement être décrite en ce plaçant du point de vue d’une particule.

Au départ de l’algorithme, un essaim est reparti au hasard dirigé dans l’espace de rechercher,

chaque particule ayant également une vitesse aléatoire.

Page 7: L’application de la  méthode d’essaim particulaire

Chapitre I Optimisation par l’essaim particulaire

5

Ensuit, à chaque pas de temps :

Chaque particule est capable d’évaluer la qualité de sa 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 (ses

informatrices, dont elle- même) et d’obtenir de chacune d’entre elles sa propre

meilleure performance (et la qualité afférente).

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 ces propres données et se déplace en conséquence.

Le premier point se comprend facilement, mais les deux autres nécessitent quelques précisions.

Les informatrices sont définies une fois pour toutes de la manière suivante (figure I.1).

Figure I.1. Le cercle virtuel pour un essaim de sept particules. [1] [2] [3] [4]

Le groupe d’information de taille trois de la particule 1 est composé des particules 1, 2 et 7.

Une fois la meilleure informatrice détectée, la modification de la vitesse est une simple

combinaison linéaire de trois tendances.

Page 8: L’application de la  méthode d’essaim particulaire

Chapitre I

A l’aide de coefficients de confiance

La tendance «aventureuse

La tendance «conservatrice

trouvée.

La tendance « panurgisme»,

I.4.Principales caractéristiques

Cette méthode présente quelques

nombreux problèmes d’optimisation,

continus ou mixtes (certaines variables

Elle est facile à programmer, quelque lignes de code suffisant dans n’emporte quel

langage évalue.

Elle est robuste (de

n’empêche pas d’obtenir une solution).

Figure I.2.Schéma de principe du déplacement d’une particule.

Optimisation par

6

A l’aide de coefficients de confiance :

a tendance «aventureuse», consistant à continuer selon la vitesse actuelle

La tendance «conservatrice », ramenant plus ou moins vers la meilleure position

panurgisme», orientant approximativement vers la meilleure informatrice.

Principales caractéristiques : [1] [2] [3] [4]

quelques propriétés intéressantes, qui on fait

d’optimisation, particulièrement les problèmes fortement non

continus ou mixtes (certaines variables étant réelles et d’autres entières) :

est facile à programmer, quelque lignes de code suffisant dans n’emporte quel

est robuste (de mauvais choix de paramètres dégrades les performances, mais

pas d’obtenir une solution).

Figure I.2.Schéma de principe du déplacement d’une particule.

Optimisation par l’essaim particulaire

actuelle.

vers la meilleure position déjà

vers la meilleure informatrice.

un bon outil pour de

fortement non linéaire,

est facile à programmer, quelque lignes de code suffisant dans n’emporte quel

dégrades les performances, mais

Figure I.2.Schéma de principe du déplacement d’une particule. [5]

Page 9: L’application de la  méthode d’essaim particulaire

Chapitre I Optimisation par l’essaim particulaire

7

Pour réaliser son prochain mouvement, chaque particule combine trois tendances : suivre sa

vitesse propre, revenir vers sa meilleure performance, aller vers la meilleure performance de ses

informatrices.

I.5.Pour en savoir plus sur l’optimisation par essaim particulaire : [1] [2] [3] [4]

A ce jour, environ 250 articles sur le sujet ont été publiés, mais très peu en français. Un excellent

point d’entrée est le site Particle Swarm Central, avec une bibliographie très complète, des liens

vers des documents et des programmes à télécharger, ainsi qu’une liste de chercheurs travaillant

dans ce domaine.

Le livre Swarm Intelligence, écrit par les deux concepteurs de la méthode, y consacre quelques

chapitres et donne des aperçus plus généraux sur les questions d’intelligence collective.

Page 10: L’application de la  méthode d’essaim particulaire

8

Page 11: L’application de la  méthode d’essaim particulaire

Chapitre II Application de la méthode d’essaim particulaire en C

9

II.1. Applications : [6]

Un essaim de particule est caractérisé par :

a) le nombre de particules de l’essaim (nb).

b) la vitesse maximale d’une particule (vmax).

c) la topologie et la taille du voisinage d’une particule qui définissent son réseau social.

d) l’inertie d’une particule(Y).

e) les coefficients de confiance 1 et ,2 qui pondèrent le comportement conservateur (la

tendance à retourner vers la meilleure solution visitée) et le panurgisme (la tendance à suivre le

voisinage).

Une particule est caractérisée, à l’instant t, par

sa position dans l’espace de recherche ଓ(ݐ)ሬሬሬሬሬሬሬሬሬሬ.

sa vitesse : ଓ(ݐ)ሬሬሬሬሬሬሬሬሬሬ .

la position de la meilleure solution par laquelle elle est passée : ଓሬሬሬሬሬሬሬሬሬሬሬሬሬሬሬሬݐݏ .

la position de la meilleure solution connue de son voisinage : ݒ ଓሬሬሬሬሬሬሬሬሬሬሬሬሬሬሬሬݐݏ .

la valeur de fitness de sa meilleure solution : pbesti .

la valeur de fitness de la meilleure solution connu du voisinage :vbesti .

Algorithme 1 : Version simplifié sans voisinage : [6]

Page 12: L’application de la  méthode d’essaim particulaire

Chapitre II

II.2. Configuration de la méthode

II.2.1. Nombre de particules

La quantité de particules allouées à la résolution du problème dépend essentiellement de deux

paramètres :

La taille de l’espace de recherche et le rapport entre les capacités de calcul de la machine et le

temps maximum de recherche.

Il n’y a pas de règle pour déterminer ce paramètre, faire de nombreux essais permet de se doter

de l’expérience nécessaire à l’a

II.2.2. Topologie du voisinage

La topologie du voisinage défini avec qui chacune des particules va pouvoir communiquer.

Il existe de nombreuses combinaisons dont les suivantes sont les plus utilisées :

a) topologie en étoile : chaque particule est reliée à toutes les autres. L’optimum du voisinage est

l’optimum global.

b) topologie en anneau : chaque particule est reliée à n particules (en général, n = 3) c’est la

topologie la plus utilisée.

c) topologie en rayon : les particules ne communiquent qu’avec une seule particule centrale.

FIGURE.II. 1

II.2.3. Coefficients de confiance

Les variables de confiance pondèrent les tendances de la particule à vouloir suivre son

conservation ou son panurgisme. Les variables aléatoires p

suivante :

Chapitre II Application de la méthode d’essaim particulaire

10

.2. Configuration de la méthode : [6]

:

La quantité de particules allouées à la résolution du problème dépend essentiellement de deux

La taille de l’espace de recherche et le rapport entre les capacités de calcul de la machine et le

temps maximum de recherche.

Il n’y a pas de règle pour déterminer ce paramètre, faire de nombreux essais permet de se doter

de l’expérience nécessaire à l’appréhension de ce paramètre.

.2.2. Topologie du voisinage :

La topologie du voisinage défini avec qui chacune des particules va pouvoir communiquer.

Il existe de nombreuses combinaisons dont les suivantes sont les plus utilisées :

étoile : chaque particule est reliée à toutes les autres. L’optimum du voisinage est

b) topologie en anneau : chaque particule est reliée à n particules (en général, n = 3) c’est la

particules ne communiquent qu’avec une seule particule centrale.

. 1 – (a) anneau (avec n = 2), (b) rayon, (c) étoile.

.2.3. Coefficients de confiance :

Les variables de confiance pondèrent les tendances de la particule à vouloir suivre son

conservation ou son panurgisme. Les variables aléatoires p1 et p2 peuvent être définis de la façon

essaim particulaire en C

La quantité de particules allouées à la résolution du problème dépend essentiellement de deux

La taille de l’espace de recherche et le rapport entre les capacités de calcul de la machine et le

Il n’y a pas de règle pour déterminer ce paramètre, faire de nombreux essais permet de se doter

La topologie du voisinage défini avec qui chacune des particules va pouvoir communiquer.

Il existe de nombreuses combinaisons dont les suivantes sont les plus utilisées :

étoile : chaque particule est reliée à toutes les autres. L’optimum du voisinage est

b) topologie en anneau : chaque particule est reliée à n particules (en général, n = 3) c’est la

particules ne communiquent qu’avec une seule particule centrale.

(a) anneau (avec n = 2), (b) rayon, (c) étoile. [6]

Les variables de confiance pondèrent les tendances de la particule à vouloir suivre son instinct de

peuvent être définis de la façon

Page 13: L’application de la  méthode d’essaim particulaire

Chapitre II Application de la méthode d’essaim particulaire en C

11

Où r1 et r2 suivent une loi uniforme sur [0..1] et c1 et c2 sont des constantes positives

déterminées de façon empirique et suivant la relation c1 + c2 <= 4.

II.2.4. Vitesse maximale et coefficient de constriction :

Afin d’éviter que les particules ne se déplacent pas trop rapidement dans l’espace de recherche,

passant éventuellement à côté de l’optimum, il peut être nécessaire de fixer une vitesse maximale

(Vmax) pour améliorer la convergence de l’algorithme.

Cependant, on peut s’en passer si on utilise un coefficient de constriction k ; et qui permet de

resserrer l’hyper-espace de recherche.

L’équation de la vitesse devient alors :

Les études de SHI et EBERHART indiquent que l’utilisation d’un coefficient de constriction

donne généralement un meilleur taux de convergence sans avoir à fixer de vitesse maximale.

Cependant, dans certains cas, le coefficient de constriction seul ne permet pas la convergence

vers la solution optimale pour un nombre d’itérations donné.

En plus du coefficient de constriction, ce qui, permet d’améliorer les performances globales de

l’algorithme.

II.2.5. Facteur d’inertie :

Le facteur d’inertie Y introduit par SHI et EBERHART permet de définir la capacité

d’exploration de chaque particule en vue d’améliorer la converge de la méthode.

Une grande valeur de Y (>1) est synonyme d’une grande amplitude de mouvement et

donc, in fine, d’exploration globale.

Une faible valeur de Y (<1) est synonyme de faible amplitude de mouvement et donc,

d’exploration locale.

Page 14: L’application de la  méthode d’essaim particulaire

Chapitre II Application de la méthode d’essaim particulaire en C

12

Fixer ce facteur, revient donc à trouver un compromis entre l’exploration locale et l’exploration

globale.

Le calcul de la vitesse est alors défini par :

La taille du facteur d’inertie influence directement la taille de l’hyper-espace exploré et aucune

valeur de Y ne peut garantir la convergence vers la solution optimale.

Les études menées par SHI et EBERHART indiquent une meilleure convergence pour :

II.2.6. Initialisation de l’essaim :

La position des particules ainsi que leur vitesse initiale doivent être initialisés aléatoirement

selon une loi uniforme sur [0..1].

II.2.7. Critères d’arrêt :

La convergence vers la solution optimale globale n’est pas garantie dans tous les cas de figure

même si les expériences dénotent la grande performance de la méthode.

De ce fait, il est fortement conseillé de doté l’algorithme d’une porte de sortie en définissant un

nombre maximum d’itération.

L’algorithme doit alors s’exécuter tant que l’un des critères de convergence suivant n’a pas été

atteint :

– un nombre maximum d’itération a été atteint.

– la variation de la vitesse est proche de 0.

– le fitness de la solution est suffisant.

Page 15: L’application de la  méthode d’essaim particulaire

Chapitre II

Algorithme 2 : Version simplifié avec voisinage

II.3. L’organigramme de principe de la

Schéma de principe de l’algorithme est donné par l’organigramme

Chapitre II Application de la méthode d’essaim particulaire

13

: Version simplifié avec voisinage : [6]

. L’organigramme de principe de la méthode des essaims particulaire

e l’algorithme est donné par l’organigramme suivant :

essaim particulaire en C

aires : [5]

:

Page 16: L’application de la  méthode d’essaim particulaire

Chapitre II

Pour programmer cette méthode, on a plusieurs compilateurs qui peuvent programmer la

méthode des essaims particulaires

(Voir l’annexe : code source en C d’une version simple d’OEP).

II.4 .Exemple d’application de PSO en langage C :

II.4.1. Exemple 1 : Recherche du champ minimum entre deux stations

Voici un exemple très simplifié s’inspirant d’un problème réel. On considère deux stations A et

B, émettrices d’un champ électromagnétique sinusoïdal décroissant avec la distance. On cherche

le point entre ces deux stations où le champ total reçu à un inst

1.4 donne une idée des champs en tout point entre les deux stations, distantes de 2,7 km. En

posant x comme étant la distance à la station A, on a les équations suivantes :

Champ_A =e-x (1+sin (10x))

Champ_B =e-2.7-x (1+sin (10

On cherche le point x où la somme champ_A+champ_B est minimale. On remarquera que la

longueur d’onde commune n’étant pas en rapport simple avec la distance entre les stations, la

détermination analytique n’est pas évidente.

Figure II.2

Chapitre II Application de la méthode d’essaim particulaire

14

Pour programmer cette méthode, on a plusieurs compilateurs qui peuvent programmer la

aires, et pour cela nous avons programmé en C.

(Voir l’annexe : code source en C d’une version simple d’OEP).

Exemple d’application de PSO en langage C :

Recherche du champ minimum entre deux stations

Voici un exemple très simplifié s’inspirant d’un problème réel. On considère deux stations A et

B, émettrices d’un champ électromagnétique sinusoïdal décroissant avec la distance. On cherche

le point entre ces deux stations où le champ total reçu à un instant donné est minimum. La figure

1.4 donne une idée des champs en tout point entre les deux stations, distantes de 2,7 km. En

comme étant la distance à la station A, on a les équations suivantes :

2.7-x))

où la somme champ_A+champ_B est minimale. On remarquera que la

longueur d’onde commune n’étant pas en rapport simple avec la distance entre les stations, la

détermination analytique n’est pas évidente.

II.2. Les stations A et B et leurs sommation. [

essaim particulaire en C

Pour programmer cette méthode, on a plusieurs compilateurs qui peuvent programmer la

la nous avons programmé en C.

: [1] [2] [3] [4]

Voici un exemple très simplifié s’inspirant d’un problème réel. On considère deux stations A et

B, émettrices d’un champ électromagnétique sinusoïdal décroissant avec la distance. On cherche

ant donné est minimum. La figure

1.4 donne une idée des champs en tout point entre les deux stations, distantes de 2,7 km. En

comme étant la distance à la station A, on a les équations suivantes :

où la somme champ_A+champ_B est minimale. On remarquera que la

longueur d’onde commune n’étant pas en rapport simple avec la distance entre les stations, la

[1] [2] [3] [4]

Page 17: L’application de la  méthode d’essaim particulaire

Chapitre II Application de la méthode d’essaim particulaire en C

15

À un instant donné, les valeurs des champs reçus se répartissent selon des sinusoïdes amorties.

La distance entre les stations (ici 2,7 km) n’étant pas en rapport simple avec la longueur d’onde,

le point où le champ total est minimum n’est pas facilement calculable.

De plus, les méthodes classiques (gradients, par exemple) échouent du fait de l’existence de

multiples minimums locaux. Par contre, il est très facile d’ajouter la fonction à minimiser au

programme PSO donné en annexe.

Pour minimiser la fonction champ_A+champ_B, il faut initialiser les paramètres suivants :

Coefficient de confiance en la tendance actuelle : c1=0.738.

Coefficient de confiance maximale en les informatrices : cmax=1.51.

Dimension de l'espace de recherche : D=1.

Précision souhaitée double : eps=0.00001.

Nombre maximum d'évaluations de la fonction : eval_max =190 et eval_max =200005.

Nombre moyen d'évaluations double : eval_moyen=0.

Numéro de la fonction à minimiser : fonction=5.

Nombre de liens d'information : k=3.

Taille de l'essaim : N =20.

Intervalle pour l'espace de recherche : xmin=0, xmax=2.7.

Après l’exécution de programme nous avons eu les résultats suivants :

On fait un premier essai à 190 évaluations, on trouve

x = 0,455594 et, un champ total de 0,067355.

C’est déjà une très bonne approximation du minimum global.

Une solution un peu meilleure peut être obtenue avec plus d’itérations, mais le gain est très

minime.

Par exemple, on fait un deuxième essai à 20005 évaluations, on va trouver x = 0,455356 et un

champ total de 0,067353.

On peut dire que l’augmentation de nombre maximum d'évaluations de la fonction a donné plus

de précision pour trouver le minimum de champ total.

Page 18: L’application de la  méthode d’essaim particulaire

Chapitre II Application de la méthode d’essaim particulaire en C

16

II.4.2. Exemple 2 : Recherche le point minimum d’une fonction :(Pris en cour)

Voici la fonction F(x) :

F(x) = x 3 - 9 * x 2 +24 * x – 12

Il est très facile de trouver le point minimum de la fonction F(x) par l’application de

programme de la PSO pour cette fonction. (Voir l’annexe)

Et pour cela, il faut initialiser les paramètres suivants :

Coefficient de confiance en la tendance actuelle : c1=0.738.

Coefficient de confiance maximale en les informatrices : cmax=1.51.

Dimension de l'espace de recherche : D=1.

Précision souhaitée double : eps=0.00001.

Nombre maximum d'évaluations de la fonction : eval_max =150 et eval_max =20000.

Nombre moyen d'évaluations double : eval_moyen=0.

Numéro de la fonction à minimiser : fonction=6.

Nombre de liens d'information : k=3.

Taille de l'essaim : N =20.

Intervalle pour l'espace de recherche : xmin=2, xmax=10.

Après l’exécution de programme nous avons eu les résultats suivants :

Pour ce la on fait deux essais :

Essai 1 : Pour un nombre maximum d'évaluations de la fonction est égale à 150.

On trouve X * = 4.002377 et F(X *)= 4.000017.

Essai 2 : Pour un nombre maximum d'évaluations de la fonction est égale à 20000.

On trouve X * = 4.000000 et F(X *)= 4.000000.

Donc on peut dire que les résultats obtenu par la PSO confirment bien la précision et la

simplicité de cette méthode.

Il faut bien choisir l’intervalle de rechercher pour ne pas diverger vers une autre solution

fausse.

Si on compare entre les deux essais, on peut dire que l’augmentation de nombre

maximum d'évaluations de la fonction a donné plus de précision par rapport à l’essai 1.

Page 19: L’application de la  méthode d’essaim particulaire

Conclusion générale

17

Au terme de ce travail, on peut dire que :

Les résultats obtenus par PSO sont très satisfaisants, elles confirment bien

sa validité et son efficacité.

Elle a une simplicité d’implémentation sur un calculateur.

C’est un outil d’optimisation très puissant.

L’amélioration de la qualité des solutions ne peut être garantie en

augmentant le nombre d’itération.

L’OEP et d'autres algorithmes de recherche stochastiques ont deux inconvénients

principaux :

le premier est que l'essaim peut prématurément converger.

le deuxième est que les approches stochastiques ont un problème de

dépendance.

Tout changement d’un de leurs paramètres peut avoir un effet sur le

fonctionnement de l’algorithme tout comme sur la solution obtenue.

Plusieurs variantes de l’OEP ont été développées pour remédier à ces

inconvénients.

Comme perspectives futures nous pouvons envisager de concevoir un outil

supplémentaire pour remédier au problème d’optimum local. Cet outil peut être

hybridé avec la PSO pour avoir un outil d’optimisation encore plus puissant et

plus efficace.

Page 20: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

18

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#define D_max 100 // Dimension maximale de l'espace de recherche

struct position {int taille;double x[D_max]; double f;}; // Position d'une particule et saperformance

struct vecteur {int taille;double v[D_max];}; // Vitesse d'une particule

// Sous-programmes//

double alea(double a,double b); // Nombre pseudo-aléatoire entre a et b

double ma_fonction (struct position x, int fonction); // Fonctions à minimiser

// Variables globales//

int nb_eval; // Nombre total d'évaluations

//================PROGRAMME PRINCIPAL=====================//

int main(int argc, char *argv[])

{

double c1,cmax; // Coefficients de confiance

int D; // Dimension de l'espace de recherche

int d; // Numéro de la dimension courante

double eps; // Précision souhaitée

int eval_max; // Nombre max d'évaluations de la fonction

double eval_moyen; // Nombre moyen d'évaluations

double fmin; // Objectif à atteindre

int fonction; // Numéro de la fonction à minimiser

int g; // Numéro de la meilleure informatrice

int k;

struct position P[D_max]; // Positions

struct position P_m[D_max]; // Meilleures positions trouvées

struct position meilleure; // Toute meilleure position trouvée

int K; // Taille des groupes d'informatrices

Page 21: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

19

double min_f;

int N; // Taille de l'essaim

int n; // Numéro de la particule courante

int n_exec,n_exec_max; // Pour exécutions multiples

int rang;

int signe;

struct vecteur V[D_max]; // Vitesses

double xmin,xmax; // Intervalle pour l'espace de recherche

// Paramètres de réglage//

c1=0.738; // Confiance en la tendance actuelle

cmax=1.51; // Confiance maximale en les informatrices

N=20; // Taille de l’essaim (comme un test d’arrêt)

K=3; // Nombre de liens d'information

// Problème à traiter//

fonction=5 ; // La fonction choisi

xmin=0; xmax=2.7; // Intervalle pour l'espace de recherche

D=1; // Espace de recherche

eps=0.00001; // Précision souhaitée

fmin=0; // Valeur minimale à atteindre, à la précision

eval_max=20005; // Nombre maximum d'évaluations (comme un test d'arret )

n_exec_max=1; // Nombre d'exécutions

n_exec=0;

eval_moyen=0;

// Initialisations des positions et vitesses//

init:

for (n=0;n<N;n++)

{ P[n].taille=D;

for (d=0;d<D;d++)

P[n].x[d]=alea(xmin,xmax);

Page 22: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

20

V[n].taille=D;

for (d=0;d<D;d++) V[n].v[d]=alea ((xmin-xmax)/2, (xmax-xmin)/2) ;}

// Evaluations initiales//

nb_eval=0;

for (n=0;n<N;n++)

{

P[n].f=ma_fonction(P[n],fonction); // Evaluation de la position

P_m[n]=P[n]; // Meilleure position = position initiale

}

//Mémorisation du meilleur résultat atteint jusqu'ici//

meilleure=P_m[0];

for (n=0;n<N;n++) if (P_m[n].f<meilleure.f) meilleure=P_m[n];

boucle: // Itérations

for (n=0;n<N;n++) // Pour chaque particule

{

// Meilleure informatrice dans le i-groupe circulaire de taille K//

g=n;

min_f=P_m[n].f;

signe=1;

k=1;

autre_informatrice:

rang=n+signe*k;

if (rang>N-1) rang=rang-N+1;

if (rang<0) rang=rang+N-1;

if (P_m[rang].f<min_f) {g=rang;min_f=P_m[rang].f;}

if (k<K) {signe=-signe;k=k+1; goto autre_informatrice; }

// Calcul de la nouvelle vitesse//

for (d=0;d<D;d++) V[n].v[d]=c1*V[n].v[d]+alea(0,cmax)*(P_m[n].x[d]-P[n].x[d])+alea(0,cmax)*(P_m[g].x[d]-P[n].x[d]);

Page 23: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

21

// Déplacement//

for (d=0;d<D;d++) P[n].x[d]=P[n].x[d]+V[n].v[d];

// Confinement d'intervalle//

for (d=0;d<D;d++)

{

if (P[n].x[d]<xmin) {P[n].x[d]=xmin;V[n].v[d]=0;} // ou bien V[n].v[d]=-0.5* V[n].v[d]

if (P[n].x[d]>xmax) {P[n].x[d]=xmax;V[n].v[d]=0;} // ou bien V[n].v[d]=-0.5*V[n].v[d]

}

// Evaluation de la nouvelle position//

P[n].f=ma_fonction(P[n],fonction);

// Mise à jour de la meilleure position//

if (P[n].f<P_m[n].f) P_m[n]=P[n];

// Mémorisation du meilleur résultat atteint jusqu'ici//

if (P_m[n].f<meilleure.f) meilleure=P_m[n];

}

// Test de fin//

if (fabs(meilleure.f-fmin)>eps && nb_eval<eval_max) goto boucle;

// Affichage du meilleur résultat trouvé vitesse et position //

printf("\n\n\n Eval= %i. Meilleure position (valeur %f ):" ,nb_eval,meilleure.f);

for (d=0;d<D;d++) printf("%f\t",meilleure.x[d]);

// Boucle d'itération //

n_exec=n_exec+1;

eval_moyen=eval_moyen+nb_eval;

if (n_exec<=n_exec_max) goto init;

// Calcul valeur de la itesse moyenne//

eval_moyen=eval_moyen/n_exec;

Page 24: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

22

// Affichage de la valeur moyenne de vitesse //

printf("\n\n\n Eval moyen = %f \n\n",eval_moyen);

system("PAUSE");

}

//====================== ALEA==================//

double alea(double a,double b)

{

// Délivre un nombre pseudo-aléatoire entre a et b selon une distribution simulant l'uniforme//

double r;

// Normalement, RAND_MAX = 32767 = 2^15-1

r=(double)rand()/RAND_MAX; // r dans [0..1]

r=a+r*(b-a);

return r;

}

//================MA_FONCTION===============//

double ma_fonction(struct position x, int fonction)

{

// Evalue la valeur de la fonction à minimiser à la position x//

// AJOUTEZ VOTRE PROPRE FONCTION//

int D,d;

double f,p,xd;

nb_eval=nb_eval+1;

D=x.taille;

switch (fonction)

{

Page 25: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

23

case 1: // Sphère//

f=0;

for(d=0;d<D;d++)

f=f+x.x[d]*x.x[d];

break;

case 2:

// Pour test du confinement. Utiliser un xmin >=0//

f=0;

for(d=0;d<D;d++)

f=f+sqrt(x.x[d]);

break;

case 3:

// Alpine. Min 0 en (0,0 ...0)//

f=0;

for( d=0;d<D;d++)

{

f=f+sqrt(fabs(x.x[d]*sin(x.x[d])));

} break;

case 4:

// Rosenbrock, fonction Banane. Min 0 en (1, ...1)//

f=0;

for (d=0;d<D-1;d++)

{

xd=1-x.x[d];

f=f+xd*xd;

xd= x.x[d]*x.x[d]-x.x[d+1];

f=f+100*xd*xd; }

break;

Page 26: L’application de la  méthode d’essaim particulaire

L’annexe : Code source en C d’une version simple de PSO

24

case 5:

// Chercher minimum champ entre le Champ_A =e-x (1+sin (10x))//

// et le Champ_B =e- 2.7-x (1+sin (10 2.7-x ))//

f=0;

for(d=0;d<D;d++)

{

f=f+(exp(-x.x[d])*(1+sin(10*x.x[d]))+exp(-(fabs(2.7-x.x[d])))*(1+sin(10*(fabs(2.7-x.x[d])))));

}

break;

case 6:

//fonction de cour//

// F(x) = x 3 - 9 * x 2 +24 * x – 12//

f=0;

for(d=0;d<D;d++)

{

f=f+(x.x[d]*x.x[d]*x.x[d]-9*x.x[d]*x.x[d]+24*x.x[d]-12);

}

break;

}

return f;

}

Page 27: L’application de la  méthode d’essaim particulaire

Référence Bibliographique

25

[1] : Berthiau G., Siarry P.

« Etat de l’art des méthodes d’optimisation globale », RAIRO Operations Research,

Vol. 35, N°3, p. 329365,2001.

[2] : Bonabeau E., Dorigo M., Theraulaz G.,

« Swarm Intelligence: from natural to artificial systems ». Oxford University Press, 1999.

[3] : Clerc M., Kennedy J.,

« The Particle Swarm. Explosion, stability, and convergence in a multidimensional complex

space », IEEE Transactions on Evolutionary Computation, Vol. 6, p. 5873, 2002.

[4] : Maurice Clerc et Patrick Siarry

« Une nouvelle métaheuristique pour l’optimisation difficile »: la méthode des essaims

particulaires ‘’

[5] : Equivalents dynamiques des réseaux de puissance : comparaison de méthodes évolutionnaires.

Par D. Craciun.

[6] : Optimisation par essaim de particules par Guillaume CALAS

Sites Internet :

[7] : Méthode des essaims particulaires :

http://www.particleswarm.net/Séminaire OEP’2003

http://www.particleswarm.net/oep_2003/

http://www.particleswarm.info/

[8] : Groupe de travail sur les métaheuristiques :

http://www.lifl.fr/~talbi/META

[9] : Livre récent sur les métaheuristiques :

http://www.eyrolles.com/php.informatique/Ouvrages/ouvragem.php3?ouv_ean13

=9782212113686