Upload
benkhada-hamane
View
3.362
Download
3
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
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
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
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.
2
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.
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.
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.
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]
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.
8
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]
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
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.
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.
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]
:
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]
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.
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.
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.
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
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);
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]);
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;
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)
{
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;
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;
}
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