Cette page a été traduite par traduction automatique. Cliquez ici pour voir la dernière version en anglais.

Algorithme d'optimisation par essaim particulaire

Introduction à l'algorithme

particleswarm est basé sur l'algorithme décrit dans Kennedy et Eberhart [1], en utilisant des modifications suggérées dans Mezura-Montes et Coello Coello [2] et dans Pedersen [3].

L'algorithme d'essaim particulaire commence par créer les particules initiales et leur attribuer des vitesses initiales.

Il évalue la fonction objectif à chaque emplacement de particule et détermine la meilleure valeur de fonction (la plus basse) et le meilleur emplacement.

Il choisit de nouvelles vitesses, en fonction de la vitesse actuelle, des meilleurs emplacements individuels des particules et des meilleurs emplacements de leurs voisines.

Il met ensuite à jour de manière itérative les emplacements des particules (le nouvel emplacement est l'ancien plus la vitesse, modifiée pour maintenir les particules dans les limites), les vitesses et les voisins.

Les itérations se poursuivent jusqu'à ce que l'algorithme atteigne un critère d'arrêt.

Voici le détail des étapes.

Initialisation

Par défaut, particleswarm crée des particules de manière aléatoire et uniforme dans les limites. S'il y a une composante non limitée, particleswarm crée des particules avec une distribution uniforme aléatoire de –1000 à 1000. Si vous n'avez qu'une seule limite, particleswarm décale la création pour avoir la limite comme point de terminaison et un intervalle de création de 2000 de large. La particule i a la position x(i), qui est un vecteur de ligne avec des éléments nvars. Contrôlez la durée de l'essaim initial à l'aide de l'option InitialSwarmSpan.

De même, particleswarm crée des vitesses de particules initiales v de manière aléatoire et uniforme dans la plage [-r,r], où r est le vecteur des portées initiales. La plage du composant k est min(ub(k) - lb(k),InitialSwarmSpan(k)).

particleswarm évalue la fonction objectif sur toutes les particules. Il enregistre la position actuelle p(i) de chaque particule i. Dans les itérations suivantes, p(i) sera l'emplacement de la meilleure fonction objectif que la particule i a trouvée. Et b est le meilleur parmi toutes les particules : b = min(fun(p(i))). d est l'emplacement tel que b = fun(d).

particleswarm initialise la taille du voisinage (neighborhood) N à minNeighborhoodSize = max(2,floor(SwarmSize*MinNeighborsFraction)).

particleswarm initialise l'inertie W = max(InertiaRange), ou si InertiaRange est négatif, il définit W = min(InertiaRange).

particleswarm initialise le compteur de décrochage c = 0.

Pour faciliter la notation, définissez les variables y1 = SelfAdjustmentWeight et y2 = SocialAdjustmentWeight, où SelfAdjustmentWeight et SocialAdjustmentWeight sont des options.

Étapes d'itération

L'algorithme met à jour l'essaim comme suit. Pour la particule i, qui est à la position x(i) :

1. Choisissez un sous-ensemble aléatoire S de N particules autres que i.

2. Trouvez fbest(S), la meilleure fonction objectif parmi les voisins, et g(S), la position du voisin avec la meilleure fonction objectif.

3. Pour les vecteurs aléatoires u1 et u2 uniformément (0,1) distribués de longueur nvars, mettez à jour la vitesse

   v = W*v + y1*u1.*(p-x) + y2*u2.*(g-x).

   Cette mise à jour utilise une somme pondérée de :

   • La vitesse précédente v

   • La différence entre la position actuelle et la meilleure position que la particule a vue p-x

   • La différence entre la position actuelle et la meilleure position dans le voisinage (neighborhood) actuel g-x

4. Mettez à jour la position x = x + v.

5. Respectez les limites. Si un composant de x est en dehors d'une limite, définissez-le égal à cette limite. Pour les composants qui viennent d'être définis sur une limite, si la vitesse v de ce composant pointe en dehors de la limite, définissez ce composant de vitesse sur zéro.

6. Évaluer la fonction objectif f = fun(x).

7. Si f < fun(p), alors définissez p = x. Cette étape garantit que p a la meilleure position que la particule ait vue.

8. Les étapes suivantes de l’algorithme s’appliquent aux paramètres de l’essaim entier, et non aux particules individuelles. Considérons le plus petit f = min(f(j)) parmi les particules j dans l’essaim.

   Si f < b, alors définissez b = f et d = x. Cette étape garantit que b a la meilleure fonction objectif dans l’essaim et que d a le meilleur emplacement.

9. Si, à l’étape précédente, la meilleure valeur de fonction a été abaissée, définissez flag = true. Sinon, flag = false. La valeur de flag est utilisée à l’étape suivante.

10. Mettre à jour la valeur du voisinage (neighborhood). Si flag = true :

    1. Spécifiez c = max(0,c-1).

    2. Définissez N comme étant minNeighborhoodSize.

    3. Si c < 2, alors définissez W = 2*W.

    4. Si c > 5, alors définissez W = W/2.

    5. Assurez-vous que W est dans les limites de l'option InertiaRange.

    Si flag = false :

    1. Spécifiez c = c+1.

    2. Spécifiez N = min(N + minNeighborhoodSize,SwarmSize).

Critères d'arrêt

particleswarm itère jusqu'à atteindre un critère d'arrêt.

Option d'arrêt	Arrêt du test	Exit Flag
MaxStallIterations et FunctionTolerance	Le changement relatif de la meilleure valeur de fonction objectif g au cours des MaxStallIterations dernières itérations est inférieur à FunctionTolerance.	1
MaxIterations	Le nombre d'itérations atteint MaxIterations.	0
OutputFcn ou PlotFcn	OutputFcn ou PlotFcn peuvent arrêter les itérations.	-1
ObjectiveLimit	La meilleure valeur de fonction objectif g est inférieure à ObjectiveLimit.	-3
MaxStallTime	La meilleure valeur de fonction objectif g n'a pas changé au cours des MaxStallTime dernières secondes.	-4
MaxTime	Le temps d'exécution de la fonction dépasse MaxTime secondes.	-5

Si particleswarm s'arrête avec l'exit flag 1, il appelle éventuellement une fonction hybride après sa sortie.

Références

[1] Kennedy, J., and R. Eberhart. "Particle Swarm Optimization." Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995, pp. 1942–1945.

[2] Mezura-Montes, E., and C. A. Coello Coello. "Constraint-handling in nature-inspired numerical optimization: Past, present and future." Swarm and Evolutionary Computation. 2011, pp. 173–194.

[3] Pedersen, M. E. "Good Parameters for Particle Swarm Optimization." Luxembourg: Hvass Laboratories, 2010.

Voir aussi

Rubriques

• Qu'est-ce que l'optimisation par essaim particulaire ?
• Optimiser à l'aide d'un essaim particulaire