2 Copyright (C) 2008-2023 EDF R&D
4 This file is part of SALOME ADAO module.
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 This library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with this library; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
22 Author: Jean-Philippe Argaud, jean-philippe.argaud@edf.fr, EDF R&D
24 .. index:: single: ParticleSwarmOptimization
25 .. index:: single: Essaim particulaire (Optimisation par)
26 .. _section_ref_algorithm_ParticleSwarmOptimization:
28 Algorithme de calcul "*ParticleSwarmOptimization*"
29 --------------------------------------------------
31 .. ------------------------------------ ..
32 .. include:: snippets/Header2Algo01.rst
34 Cet algorithme réalise une estimation de l'état d'un système par minimisation
35 d'une fonctionnelle d'écart :math:`J` en utilisant une méthode évolutionnaire
36 d'essaim particulaire. C'est une méthode qui n'utilise pas les dérivées de la
37 fonctionnelle d'écart. Elle est basée sur l'évolution d'une population (appelée
38 "essaim") d'états (chaque individu étant appelé une "particule" ou un insecte).
39 Elle entre dans la même catégorie que les
40 :ref:`section_ref_algorithm_DerivativeFreeOptimization`,
41 :ref:`section_ref_algorithm_DifferentialEvolution` ou
42 :ref:`section_ref_algorithm_TabuSearch`.
44 C'est une méthode d'optimisation mono-objectif, permettant la recherche du
45 minimum global d'une fonctionnelle d'erreur :math:`J` quelconque de type
46 :math:`L^1`, :math:`L^2` ou :math:`L^{\infty}`, avec ou sans pondérations,
47 comme décrit dans la section pour :ref:`section_theory_optimization`. La
48 fonctionnelle d'erreur par défaut est celle de moindres carrés pondérés
49 augmentés, classiquement utilisée en assimilation de données.
51 Il existe diverses variantes de cet algorithme. On propose ici les formulations
52 stables et robustes suivantes :
55 pair: Variant ; CanonicalPSO
57 pair: Variant ; SPSO-2011
58 pair: Variant ; AIS PSO
61 - "CanonicalPSO" (Canonical Particule Swarm Optimisation, voir
62 [ZambranoBigiarini13]_), algorithme classique dit "canonique" d'essaim
63 particulaire, robuste et définissant une référence des algorithmes d'essaims
65 - "OGCR" (Simple Particule Swarm Optimisation), algorithme simplifié d'essaim
66 particulaire sans bornes sur les insectes ou les vitesses, déconseillé car
67 peu robuste, mais parfois beaucoup plus rapide,
68 - "SPSO-2011" (Standard Particle Swarm Optimisation 2011, voir
69 [ZambranoBigiarini13]_), algorithme de référence 2011 d'essaim particulaire,
70 robuste, performant et défini comme une référence des algorithmes d'essaims
71 particulaires. Cet algorithme est parfois appelé ":math:`\omega`-PSO" ou
72 "Inertia PSO" car il intègre une contribution dite d'inertie, ou encore
73 appelé "AIS" (pour "Asynchronous Iteration Strategy") ou "APSO" (pour
74 "Advanced Particle Swarm Optimisation") car il intègre la mise à jour
75 évolutive des meilleurs éléments, conduisant à une convergence
76 intrinsèquement améliorée de l'algorithme.
78 Voici quelques suggestions pratiques pour une utilisation efficace de ces
81 - La variante recommandée de cet algorithme est le "SPSO-2011" même si
82 l'algorithme "CanonicalPSO" reste par défaut le plus robuste.
83 - Le nombre de particules ou d'insectes usuellement recommandé varie entre 40
84 et 100 selon l'algorithme, à peu près indépendamment de la dimension de
85 l'espace des états. En général, les meilleurs performances sont obtenues pour
86 des populations de 70 à 500 particules. Même si la valeur par défaut de ce
87 paramètre de base provient d'une expérience étendue sur ces algorithmes, il
88 est recommandé de l'adapter à la difficulté des problèmes traités.
89 - Le nombre recommandé de générations, lors de l'évolution de la population,
90 est souvent de l'ordre de 50, mais il peut facilement varier entre 25 et 500.
91 - Le nombre maximal d'évaluation de la fonction de simulation doit usuellement
92 être limité entre quelques milliers et quelques dizaines de milliers de fois
93 la dimension de l'espace des états.
94 - La fonctionnelle d'erreur décroît usuellement par pallier (donc avec une
95 progression nulle de la valeur de fonctionnelle à chaque génération lorsque
96 l'on reste dans le palier), rendant *non recommandé* un arrêt sur critère de
97 décroissance de la fonction-coût. Il est normalement plus judicieux d'adapter
98 le nombre d'itérations ou de générations pour accélérer la convergence des
100 - Si le problème est contraint, il faut définir les bornes des variables (par
101 la variable "*Bounds*"). Si le problème est totalement non contraint, il est
102 indispensable de définir des bornes d'incrément (par la variable
103 "*BoxBounds*") pour circonscrire la recherche optimale de manière utile. De
104 manière similaire, si le problème est partiellement contraint, il est
105 recommandé (mais pas indispensable) de définir des bornes d'incrément. Dans
106 le cas où ces bornes d'incréments ne sont pas définies, ce sont les bornes
107 des variables qui seront utilisées comme bornes d'incréments.
109 Ces conseils sont à utiliser comme des indications expérimentales, et pas comme
110 des prescriptions, car ils sont à apprécier ou à adapter selon la physique de
111 chaque problème que l'on traite.
113 Le décompte du nombre d'évaluations de la fonction à simuler lors de cet
114 algorithme est déterministe, à savoir le "*nombre d'itérations ou de
115 générations*" multiplié par le "*nombre d'individus de la population*". Avec
116 les valeurs par défaut, il faut entre `40x50=2000` et `100*50=5000` évaluations
117 par défaut. C'est pour cette raison que cet algorithme est usuellement
118 intéressant lorsque la dimension de l'espace des états est grande, ou que les
119 non-linéarités de la simulation rendent compliqué, ou invalide, l'évaluation du
120 gradient de la fonctionnelle par approximation numérique. Mais il est aussi
121 nécessaire que le calcul de la fonction à simuler ne soit pas trop coûteuse
122 pour éviter une temps d'optimisation rédhibitoire.
124 .. ------------------------------------ ..
125 .. include:: snippets/Header2Algo02.rst
127 .. include:: snippets/Background.rst
129 .. include:: snippets/BackgroundError.rst
131 .. include:: snippets/Observation.rst
133 .. include:: snippets/ObservationError.rst
135 .. include:: snippets/ObservationOperator.rst
137 .. ------------------------------------ ..
138 .. include:: snippets/Header2Algo03AdOp.rst
140 .. include:: snippets/BoundsWithNone.rst
142 .. include:: snippets/BoxBounds.rst
144 .. include:: snippets/CognitiveAcceleration.rst
146 .. include:: snippets/InertiaWeight.rst
148 .. include:: snippets/InitializationPoint.rst
150 .. include:: snippets/MaximumNumberOfFunctionEvaluations.rst
152 .. include:: snippets/MaximumNumberOfIterations_50.rst
154 .. include:: snippets/NumberOfInsects.rst
156 .. include:: snippets/QualityCriterion.rst
158 .. include:: snippets/SetSeed.rst
160 .. include:: snippets/SocialAcceleration.rst
162 StoreSupplementaryCalculations
163 .. index:: single: StoreSupplementaryCalculations
165 *Liste de noms*. Cette liste indique les noms des variables supplémentaires,
166 qui peuvent être disponibles au cours du déroulement ou à la fin de
167 l'algorithme, si elles sont initialement demandées par l'utilisateur. Leur
168 disponibilité implique, potentiellement, des calculs ou du stockage coûteux.
169 La valeur par défaut est donc une liste vide, aucune de ces variables n'étant
170 calculée et stockée par défaut (sauf les variables inconditionnelles). Les
171 noms possibles pour les variables supplémentaires sont dans la liste suivante
172 (la description détaillée de chaque variable nommée est donnée dans la suite
173 de cette documentation par algorithme spécifique, dans la sous-partie
174 "*Informations et variables disponibles à la fin de l'algorithme*") : [
180 "CurrentIterationNumber",
183 "InternalCostFunctionJ",
184 "InternalCostFunctionJb",
185 "InternalCostFunctionJo",
189 "SimulatedObservationAtBackground",
190 "SimulatedObservationAtCurrentState",
191 "SimulatedObservationAtOptimum",
195 ``{"StoreSupplementaryCalculations":["CurrentState", "Residu"]}``
197 .. include:: snippets/SwarmTopology.rst
199 .. include:: snippets/Variant_PSO.rst
201 .. include:: snippets/VelocityClampingFactor.rst
203 .. ------------------------------------ ..
204 .. include:: snippets/Header2Algo04.rst
206 .. include:: snippets/Analysis.rst
208 .. include:: snippets/CostFunctionJ.rst
210 .. include:: snippets/CostFunctionJb.rst
212 .. include:: snippets/CostFunctionJo.rst
214 .. ------------------------------------ ..
215 .. include:: snippets/Header2Algo05.rst
217 .. include:: snippets/Analysis.rst
219 .. include:: snippets/BMA.rst
221 .. include:: snippets/CostFunctionJ.rst
223 .. include:: snippets/CostFunctionJb.rst
225 .. include:: snippets/CostFunctionJo.rst
227 .. include:: snippets/CurrentIterationNumber.rst
229 .. include:: snippets/CurrentState.rst
231 .. include:: snippets/Innovation.rst
233 .. include:: snippets/InternalCostFunctionJ.rst
235 .. include:: snippets/InternalCostFunctionJb.rst
237 .. include:: snippets/InternalCostFunctionJo.rst
239 .. include:: snippets/InternalStates.rst
241 .. include:: snippets/OMA.rst
243 .. include:: snippets/OMB.rst
245 .. include:: snippets/SimulatedObservationAtBackground.rst
247 .. include:: snippets/SimulatedObservationAtCurrentState.rst
249 .. include:: snippets/SimulatedObservationAtOptimum.rst
251 .. ------------------------------------ ..
252 .. _section_ref_algorithm_ParticleSwarmOptimization_examples:
254 .. include:: snippets/Header2Algo09.rst
256 .. include:: scripts/simple_ParticleSwarmOptimization1.rst
258 .. literalinclude:: scripts/simple_ParticleSwarmOptimization1.py
260 .. include:: snippets/Header2Algo10.rst
262 .. literalinclude:: scripts/simple_ParticleSwarmOptimization1.res
265 .. include:: snippets/Header2Algo11.rst
267 .. _simple_ParticleSwarmOptimization1:
268 .. image:: scripts/simple_ParticleSwarmOptimization1.png
272 .. ------------------------------------ ..
273 .. include:: snippets/Header2Algo06.rst
275 - :ref:`section_ref_algorithm_DerivativeFreeOptimization`
276 - :ref:`section_ref_algorithm_DifferentialEvolution`
277 - :ref:`section_ref_algorithm_TabuSearch`
279 .. ------------------------------------ ..
280 .. include:: snippets/Header2Algo07.rst
283 - [ZambranoBigiarini13]_