doc/fr/ref_algorithm_ParticleSwarmOptimization.rst

   1 ..
   2    Copyright (C) 2008-2023 EDF R&D
   3
   4    This file is part of SALOME ADAO module.
   5
   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.
  10
  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.
  15
  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
  19
  20    See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21
  22    Author: Jean-Philippe Argaud, jean-philippe.argaud@edf.fr, EDF R&D
  23
  24 .. index:: single: ParticleSwarmOptimization
  25 .. index:: single: Essaim particulaire (Optimisation par)
  26 .. _section_ref_algorithm_ParticleSwarmOptimization:
  27
  28 Algorithme de calcul "*ParticleSwarmOptimization*"
  29 --------------------------------------------------
  30
  31 .. ------------------------------------ ..
  32 .. include:: snippets/Header2Algo01.rst
  33
  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`.
  43
  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.
  50
  51 Il existe diverses variantes de cet algorithme. On propose ici les formulations
  52 stables et robustes suivantes :
  53
  54 .. index::
  55     pair: Variant ; CanonicalPSO
  56     pair: Variant ; OGCR
  57     pair: Variant ; SPSO-2011
  58     pair: Variant ; AIS PSO
  59     pair: Variant ; APSO
  60
  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
  64   particulaires,
  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" ou "SPSO-2011-AIS" (Standard Particle Swarm Optimisation 2011,
  69   voir [ZambranoBigiarini13]_), algorithme de référence 2011 d'essaim
  70   particulaire, robuste, performant et défini comme une référence des
  71   algorithmes d'essaims particulaires. Cet algorithme est parfois appelé
  72   ":math:`\omega`-PSO" ou "Inertia PSO" car il intègre une contribution dite
  73   d'inertie, ou encore appelé "AIS" (pour "Asynchronous Iteration Strategy") ou
  74   "APSO" (pour "Advanced Particle Swarm Optimisation") car il intègre la mise à
  75   jour évolutive des meilleurs éléments, conduisant à une convergence
  76   intrinsèquement améliorée de l'algorithme.
  77 - "SPSO-2011-SIS" (Standard Particle Swarm Optimisation 2011 with Synchronous
  78   Iteration Strategy), très similaire à l'algorithme de référence 2011 et avec
  79   une mise à jour synchrone, appelée "SIS", des particules.
  80 - "SPSO-2011-PSIS" (Standard Particle Swarm Optimisation 2011 with Parallel
  81   Synchronous Iteration Strategy), similaire à l'algorithme "SPSO-2011-SIS"
  82   avec mise à jour synchrone et parallélisation, appelée "PSIS", des
  83   particules.
  84
  85 Voici quelques suggestions pratiques pour une utilisation efficace de ces
  86 algorithmes :
  87
  88 - La variante recommandée de cet algorithme est le "SPSO-2011" même si
  89   l'algorithme "CanonicalPSO" reste par défaut le plus robuste. Dans le cas où
  90   l'évaluation de l'état peut être réalisé en parallèle, on peut utiliser
  91   l'algorithme "SPSO-2011-PSIS" même si sa convergence est parfois un peu moins
  92   performante.
  93 - Le nombre de particules ou d'insectes usuellement recommandé varie entre 40
  94   et 100 selon l'algorithme, à peu près indépendamment de la dimension de
  95   l'espace des états. En général, les meilleurs performances sont obtenues pour
  96   des populations de 70 à 500 particules. Même si la valeur par défaut de ce
  97   paramètre de base provient d'une expérience étendue sur ces algorithmes, il
  98   est recommandé de l'adapter à la difficulté des problèmes traités.
  99 - Le nombre recommandé de générations, lors de l'évolution de la population,
 100   est souvent de l'ordre de 50, mais il peut facilement varier entre 25 et 500.
 101 - Le nombre maximal d'évaluation de la fonction de simulation doit usuellement
 102   être limité entre quelques milliers et quelques dizaines de milliers de fois
 103   la dimension de l'espace des états.
 104 - La fonctionnelle d'erreur décroît usuellement par pallier (donc avec une
 105   progression nulle de la valeur de fonctionnelle à chaque génération lorsque
 106   l'on reste dans le palier), rendant *non recommandé* un arrêt sur critère de
 107   décroissance de la fonction-coût. Il est normalement plus judicieux d'adapter
 108   le nombre d'itérations ou de générations pour accélérer la convergence des
 109   algorithmes.
 110 - Si le problème est contraint, il faut définir les bornes des variables (par
 111   la variable "*Bounds*"). Si le problème est totalement non contraint, il est
 112   indispensable de définir des bornes d'incrément (par la variable
 113   "*BoxBounds*") pour circonscrire la recherche optimale de manière utile. De
 114   manière similaire, si le problème est partiellement contraint, il est
 115   recommandé (mais pas indispensable) de définir des bornes d'incrément. Dans
 116   le cas où ces bornes d'incréments ne sont pas définies, ce sont les bornes
 117   des variables qui seront utilisées comme bornes d'incréments.
 118
 119 Ces conseils sont à utiliser comme des indications expérimentales, et pas comme
 120 des prescriptions, car ils sont à apprécier ou à adapter selon la physique de
 121 chaque problème que l'on traite.
 122
 123 Le décompte du nombre d'évaluations de la fonction à simuler lors de cet
 124 algorithme est déterministe, à savoir le "*nombre d'itérations ou de
 125 générations*" multiplié par le "*nombre d'individus de la population*". Avec
 126 les valeurs par défaut, il faut entre `40x50=2000` et `100*50=5000` évaluations
 127 par défaut. C'est pour cette raison que cet algorithme est usuellement
 128 intéressant lorsque la dimension de l'espace des états est grande, ou que les
 129 non-linéarités de la simulation rendent compliqué, ou invalide, l'évaluation du
 130 gradient de la fonctionnelle par approximation numérique. Mais il est aussi
 131 nécessaire que le calcul de la fonction à simuler ne soit pas trop coûteuse
 132 pour éviter une temps d'optimisation rédhibitoire.
 133
 134 .. ------------------------------------ ..
 135 .. include:: snippets/Header2Algo02.rst
 136
 137 .. include:: snippets/Background.rst
 138
 139 .. include:: snippets/BackgroundError.rst
 140
 141 .. include:: snippets/Observation.rst
 142
 143 .. include:: snippets/ObservationError.rst
 144
 145 .. include:: snippets/ObservationOperator.rst
 146
 147 .. ------------------------------------ ..
 148 .. include:: snippets/Header2Algo03AdOp.rst
 149
 150 .. include:: snippets/BoundsWithNone.rst
 151
 152 .. include:: snippets/BoxBounds.rst
 153
 154 .. include:: snippets/CognitiveAcceleration.rst
 155
 156 .. include:: snippets/InertiaWeight.rst
 157
 158 .. include:: snippets/InitializationPoint.rst
 159
 160 .. include:: snippets/MaximumNumberOfFunctionEvaluations.rst
 161
 162 .. include:: snippets/MaximumNumberOfIterations_50.rst
 163
 164 .. include:: snippets/NumberOfInsects.rst
 165
 166 .. include:: snippets/QualityCriterion.rst
 167
 168 .. include:: snippets/SetSeed.rst
 169
 170 .. include:: snippets/SocialAcceleration.rst
 171
 172 StoreSupplementaryCalculations
 173   .. index:: single: StoreSupplementaryCalculations
 174
 175   *Liste de noms*. Cette liste indique les noms des variables supplémentaires,
 176   qui peuvent être disponibles au cours du déroulement ou à la fin de
 177   l'algorithme, si elles sont initialement demandées par l'utilisateur. Leur
 178   disponibilité implique, potentiellement, des calculs ou du stockage coûteux.
 179   La valeur par défaut est donc une liste vide, aucune de ces variables n'étant
 180   calculée et stockée par défaut (sauf les variables inconditionnelles). Les
 181   noms possibles pour les variables supplémentaires sont dans la liste suivante
 182   (la description détaillée de chaque variable nommée est donnée dans la suite
 183   de cette documentation par algorithme spécifique, dans la sous-partie
 184   "*Informations et variables disponibles à la fin de l'algorithme*") : [
 185   "Analysis",
 186   "BMA",
 187   "CostFunctionJ",
 188   "CostFunctionJb",
 189   "CostFunctionJo",
 190   "CurrentIterationNumber",
 191   "CurrentState",
 192   "Innovation",
 193   "InternalCostFunctionJ",
 194   "InternalCostFunctionJb",
 195   "InternalCostFunctionJo",
 196   "InternalStates",
 197   "OMA",
 198   "OMB",
 199   "SimulatedObservationAtBackground",
 200   "SimulatedObservationAtCurrentState",
 201   "SimulatedObservationAtOptimum",
 202   ].
 203
 204   Exemple :
 205   ``{"StoreSupplementaryCalculations":["CurrentState", "Residu"]}``
 206
 207 .. include:: snippets/SwarmTopology.rst
 208
 209 .. include:: snippets/Variant_PSO.rst
 210
 211 .. include:: snippets/VelocityClampingFactor.rst
 212
 213 .. ------------------------------------ ..
 214 .. include:: snippets/Header2Algo04.rst
 215
 216 .. include:: snippets/Analysis.rst
 217
 218 .. include:: snippets/CostFunctionJ.rst
 219
 220 .. include:: snippets/CostFunctionJb.rst
 221
 222 .. include:: snippets/CostFunctionJo.rst
 223
 224 .. ------------------------------------ ..
 225 .. include:: snippets/Header2Algo05.rst
 226
 227 .. include:: snippets/Analysis.rst
 228
 229 .. include:: snippets/BMA.rst
 230
 231 .. include:: snippets/CostFunctionJ.rst
 232
 233 .. include:: snippets/CostFunctionJb.rst
 234
 235 .. include:: snippets/CostFunctionJo.rst
 236
 237 .. include:: snippets/CurrentIterationNumber.rst
 238
 239 .. include:: snippets/CurrentState.rst
 240
 241 .. include:: snippets/Innovation.rst
 242
 243 .. include:: snippets/InternalCostFunctionJ.rst
 244
 245 .. include:: snippets/InternalCostFunctionJb.rst
 246
 247 .. include:: snippets/InternalCostFunctionJo.rst
 248
 249 .. include:: snippets/InternalStates.rst
 250
 251 .. include:: snippets/OMA.rst
 252
 253 .. include:: snippets/OMB.rst
 254
 255 .. include:: snippets/SimulatedObservationAtBackground.rst
 256
 257 .. include:: snippets/SimulatedObservationAtCurrentState.rst
 258
 259 .. include:: snippets/SimulatedObservationAtOptimum.rst
 260
 261 .. ------------------------------------ ..
 262 .. _section_ref_algorithm_ParticleSwarmOptimization_examples:
 263
 264 .. include:: snippets/Header2Algo09.rst
 265
 266 .. include:: scripts/simple_ParticleSwarmOptimization1.rst
 267
 268 .. literalinclude:: scripts/simple_ParticleSwarmOptimization1.py
 269
 270 .. include:: snippets/Header2Algo10.rst
 271
 272 .. literalinclude:: scripts/simple_ParticleSwarmOptimization1.res
 273     :language: none
 274
 275 .. include:: snippets/Header2Algo11.rst
 276
 277 .. _simple_ParticleSwarmOptimization1:
 278 .. image:: scripts/simple_ParticleSwarmOptimization1.png
 279   :align: center
 280   :width: 90%
 281
 282 .. ------------------------------------ ..
 283 .. include:: snippets/Header2Algo06.rst
 284
 285 - :ref:`section_ref_algorithm_DerivativeFreeOptimization`
 286 - :ref:`section_ref_algorithm_DifferentialEvolution`
 287 - :ref:`section_ref_algorithm_TabuSearch`
 288
 289 .. ------------------------------------ ..
 290 .. include:: snippets/Header2Algo07.rst
 291
 292 - [WikipediaPSO]_
 293 - [ZambranoBigiarini13]_