..
- Copyright (C) 2008-2015 EDF R&D
+ Copyright (C) 2008-2023 EDF R&D
This file is part of SALOME ADAO module.
Author: Jean-Philippe Argaud, jean-philippe.argaud@edf.fr, EDF R&D
.. index:: single: ParticleSwarmOptimization
+.. index:: single: Essaim particulaire (Optimisation par)
.. _section_ref_algorithm_ParticleSwarmOptimization:
Algorithme de calcul "*ParticleSwarmOptimization*"
--------------------------------------------------
-Description
-+++++++++++
-
-Cet algorithme réalise une estimation de l'état d'un système dynamique par un
-essaim particulaire.
-
-C'est une méthode d'optimisation permettant la recherche du minimum global d'une
-fonctionnelle d'erreur :math:`J` quelconque de type :math:`L^1`, :math:`L^2` ou
-:math:`L^{\infty}`, avec ou sans pondérations. La fonctionnelle d'erreur par
-défaut est celle de moindres carrés pondérés augmentés, classiquement utilisée
-en assimilation de données.
-
-Commandes requises et optionnelles
-++++++++++++++++++++++++++++++++++
-
-.. index:: single: Background
-.. index:: single: BackgroundError
-.. index:: single: Observation
-.. index:: single: ObservationError
-.. index:: single: ObservationOperator
-.. index:: single: MaximumNumberOfSteps
-.. index:: single: NumberOfInsects
-.. index:: single: SwarmVelocity
-.. index:: single: GroupRecallRate
-.. index:: single: QualityCriterion
-.. index:: single: BoxBounds
-.. index:: single: SetSeed
-.. index:: single: StoreInternalVariables
-.. index:: single: StoreSupplementaryCalculations
-
-Les commandes requises générales, disponibles dans l'interface en édition, sont
-les suivantes:
-
- Background
- *Commande obligatoire*. Elle définit le vecteur d'ébauche ou
- d'initialisation, noté précédemment :math:`\mathbf{x}^b`. Sa valeur est
- définie comme un objet de type "*Vector*" ou de type "*VectorSerie*".
-
- BackgroundError
- *Commande obligatoire*. Elle définit la matrice de covariance des erreurs
- d'ébauche, notée précédemment :math:`\mathbf{B}`. Sa valeur est définie
- comme un objet de type "*Matrix*", de type "*ScalarSparseMatrix*", ou de
- type "*DiagonalSparseMatrix*".
-
- Observation
- *Commande obligatoire*. Elle définit le vecteur d'observation utilisé en
- assimilation de données ou en optimisation, et noté précédemment
- :math:`\mathbf{y}^o`. Sa valeur est définie comme un objet de type "*Vector*"
- ou de type "*VectorSerie*".
-
- ObservationError
- *Commande obligatoire*. Elle définit la matrice de covariance des erreurs
- d'ébauche, notée précédemment :math:`\mathbf{R}`. Sa valeur est définie
- comme un objet de type "*Matrix*", de type "*ScalarSparseMatrix*", ou de
- type "*DiagonalSparseMatrix*".
-
- ObservationOperator
- *Commande obligatoire*. Elle indique l'opérateur d'observation, noté
- précédemment :math:`H`, qui transforme les paramètres d'entrée
- :math:`\mathbf{x}` en résultats :math:`\mathbf{y}` qui sont à comparer aux
- observations :math:`\mathbf{y}^o`. Sa valeur est définie comme un objet de
- type "*Function*" ou de type "*Matrix*". Dans le cas du type "*Function*",
- différentes formes fonctionnelles peuvent être utilisées, comme décrit dans
- la section :ref:`section_ref_operator_requirements`. Si un contrôle
- :math:`U` est inclus dans le modèle d'observation, l'opérateur doit être
- appliqué à une paire :math:`(X,U)`.
-
-Les commandes optionnelles générales, disponibles dans l'interface en édition,
-sont indiquées dans la :ref:`section_ref_assimilation_keywords`. En particulier,
-la commande optionnelle "*AlgorithmParameters*" permet d'indiquer les options
-particulières, décrites ci-après, de l'algorithme. On se reportera à la
-:ref:`section_ref_options_AlgorithmParameters` pour le bon usage de cette
-commande.
-
-Les options de l'algorithme sont les suivantes:
-
- MaximumNumberOfSteps
- Cette clé indique le nombre maximum d'itérations possibles en optimisation
- itérative. Le défaut est 50, qui est une limite arbitraire. Il est ainsi
- recommandé d'adapter ce paramètre aux besoins pour des problèmes réels.
-
- Exemple : ``{"MaximumNumberOfSteps":100}``
-
- NumberOfInsects
- Cette clé indique le nombre d'insectes ou de particules dans l'essaim. La
- valeur par défaut est 100, qui est une valeur par défaut usuelle pour cet
- algorithme.
-
- Exemple : ``{"NumberOfInsects":100}``
-
- SwarmVelocity
- Cette clé indique la part de la vitesse d'insecte qui est imposée par
- l'essaim. C'est une valeur réelle positive. Le défaut est de 1.
-
- Exemple : ``{"SwarmVelocity":1.}``
-
- GroupRecallRate
- Cette clé indique le taux de rappel vers le meilleur insecte de l'essaim.
- C'est une valeur réelle comprise entre 0 et 1. Le défaut est de 0.5.
-
- Exemple : ``{"GroupRecallRate":0.5}``
-
- QualityCriterion
- Cette clé indique le critère de qualité, qui est minimisé pour trouver
- l'estimation optimale de l'état. Le défaut est le critère usuel de
- l'assimilation de données nommé "DA", qui est le critère de moindres carrés
- pondérés augmentés. Les critères possibles sont dans la liste suivante, dans
- laquelle les noms équivalents sont indiqués par un signe "=" :
- ["AugmentedWeightedLeastSquares"="AWLS"="DA", "WeightedLeastSquares"="WLS",
- "LeastSquares"="LS"="L2", "AbsoluteValue"="L1", "MaximumError"="ME"].
-
- Exemple : ``{"QualityCriterion":"DA"}``
-
- BoxBounds
- Cette clé permet de définir des bornes supérieure et inférieure pour chaque
- incrément de variable d'état optimisée (et non pas chaque variable d'état
- elle-même). Les bornes doivent être données par une liste de liste de paires
- de bornes inférieure/supérieure pour chaque incrément de variable, avec une
- valeur extrême chaque fois qu'il n'y a pas de borne (``None`` n'est pas une
- valeur autorisée lorsqu'il n'y a pas de borne). Cette clé est requise et il
- n'y a pas de valeurs par défaut.
-
- Exemple : ``{"BoxBounds":[[-0.5,0.5],[0.01,2.],[0.,1.e99],[-1.e99,1.e99]]}``
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo01.rst
+
+Cet algorithme réalise une estimation de l'état d'un système par minimisation
+d'une fonctionnelle d'écart :math:`J` en utilisant une méthode évolutionnaire
+d'essaim particulaire. C'est une méthode qui n'utilise pas les dérivées de la
+fonctionnelle d'écart. Elle est basée sur l'évolution d'une population (appelée
+"essaim") d'états (chaque individu étant appelé une "particule" ou un insecte).
+Elle entre dans la même catégorie que les
+:ref:`section_ref_algorithm_DerivativeFreeOptimization`,
+:ref:`section_ref_algorithm_DifferentialEvolution` ou
+:ref:`section_ref_algorithm_TabuSearch`.
+
+C'est une méthode d'optimisation mono-objectif, permettant la recherche du
+minimum global d'une fonctionnelle d'erreur :math:`J` quelconque de type
+:math:`L^1`, :math:`L^2` ou :math:`L^{\infty}`, avec ou sans pondérations,
+comme décrit dans la section pour :ref:`section_theory_optimization`. La
+fonctionnelle d'erreur par défaut est celle de moindres carrés pondérés
+augmentés, classiquement utilisée en assimilation de données.
+
+Il existe diverses variantes de cet algorithme. On propose ici les formulations
+stables et robustes suivantes :
+
+.. index::
+ pair: Variant ; CanonicalPSO
+ pair: Variant ; OGCR
+ pair: Variant ; SPSO-2011
+ pair: Variant ; AIS PSO
+ pair: Variant ; APSO
+
+- "CanonicalPSO" (Canonical Particule Swarm Optimisation, voir
+ [ZambranoBigiarini13]_), algorithme classique dit "canonique" d'essaim
+ particulaire, robuste et définissant une référence des algorithmes d'essaims
+ particulaires,
+- "OGCR" (Simple Particule Swarm Optimisation), algorithme simplifié d'essaim
+ particulaire sans bornes sur les insectes ou les vitesses, déconseillé car
+ peu robuste, mais parfois beaucoup plus rapide,
+- "SPSO-2011" ou "SPSO-2011-AIS" (Standard Particle Swarm Optimisation 2011,
+ voir [ZambranoBigiarini13]_), algorithme de référence 2011 d'essaim
+ particulaire, robuste, performant et défini comme une référence des
+ algorithmes d'essaims particulaires. Cet algorithme est parfois appelé
+ ":math:`\omega`-PSO" ou "Inertia PSO" car il intègre une contribution dite
+ d'inertie, ou encore appelé "AIS" (pour "Asynchronous Iteration Strategy") ou
+ "APSO" (pour "Advanced Particle Swarm Optimisation") car il intègre la mise à
+ jour évolutive des meilleurs éléments, conduisant à une convergence
+ intrinsèquement améliorée de l'algorithme.
+- "SPSO-2011-SIS" (Standard Particle Swarm Optimisation 2011 with Synchronous
+ Iteration Strategy), très similaire à l'algorithme de référence 2011 et avec
+ une mise à jour synchrone, appelée "SIS", des particules.
+- "SPSO-2011-PSIS" (Standard Particle Swarm Optimisation 2011 with Parallel
+ Synchronous Iteration Strategy), similaire à l'algorithme "SPSO-2011-SIS"
+ avec mise à jour synchrone et parallélisation, appelée "PSIS", des
+ particules.
+
+Voici quelques suggestions pratiques pour une utilisation efficace de ces
+algorithmes :
+
+- La variante recommandée de cet algorithme est le "SPSO-2011" même si
+ l'algorithme "CanonicalPSO" reste par défaut le plus robuste. Dans le cas où
+ l'évaluation de l'état peut être réalisé en parallèle, on peut utiliser
+ l'algorithme "SPSO-2011-PSIS" même si sa convergence est parfois un peu moins
+ performante.
+- Le nombre de particules ou d'insectes usuellement recommandé varie entre 40
+ et 100 selon l'algorithme, à peu près indépendamment de la dimension de
+ l'espace des états. En général, les meilleurs performances sont obtenues pour
+ des populations de 70 à 500 particules. Même si la valeur par défaut de ce
+ paramètre de base provient d'une expérience étendue sur ces algorithmes, il
+ est recommandé de l'adapter à la difficulté des problèmes traités.
+- Le nombre recommandé de générations, lors de l'évolution de la population,
+ est souvent de l'ordre de 50, mais il peut facilement varier entre 25 et 500.
+- Le nombre maximal d'évaluation de la fonction de simulation doit usuellement
+ être limité entre quelques milliers et quelques dizaines de milliers de fois
+ la dimension de l'espace des états.
+- La fonctionnelle d'erreur décroît usuellement par pallier (donc avec une
+ progression nulle de la valeur de fonctionnelle à chaque génération lorsque
+ l'on reste dans le palier), rendant *non recommandé* un arrêt sur critère de
+ décroissance de la fonction-coût. Il est normalement plus judicieux d'adapter
+ le nombre d'itérations ou de générations pour accélérer la convergence des
+ algorithmes.
+- Si le problème est contraint, il faut définir les bornes des variables (par
+ la variable "*Bounds*"). Si le problème est totalement non contraint, il est
+ indispensable de définir des bornes d'incrément (par la variable
+ "*BoxBounds*") pour circonscrire la recherche optimale de manière utile. De
+ manière similaire, si le problème est partiellement contraint, il est
+ recommandé (mais pas indispensable) de définir des bornes d'incrément. Dans
+ le cas où ces bornes d'incréments ne sont pas définies, ce sont les bornes
+ des variables qui seront utilisées comme bornes d'incréments.
+
+Ces conseils sont à utiliser comme des indications expérimentales, et pas comme
+des prescriptions, car ils sont à apprécier ou à adapter selon la physique de
+chaque problème que l'on traite.
+
+Le décompte du nombre d'évaluations de la fonction à simuler lors de cet
+algorithme est déterministe, à savoir le "*nombre d'itérations ou de
+générations*" multiplié par le "*nombre d'individus de la population*". Avec
+les valeurs par défaut, il faut entre `40x50=2000` et `100*50=5000` évaluations
+par défaut. C'est pour cette raison que cet algorithme est usuellement
+intéressant lorsque la dimension de l'espace des états est grande, ou que les
+non-linéarités de la simulation rendent compliqué, ou invalide, l'évaluation du
+gradient de la fonctionnelle par approximation numérique. Mais il est aussi
+nécessaire que le calcul de la fonction à simuler ne soit pas trop coûteuse
+pour éviter une temps d'optimisation rédhibitoire.
+
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo02.rst
+
+.. include:: snippets/Background.rst
+
+.. include:: snippets/BackgroundError.rst
+
+.. include:: snippets/Observation.rst
+
+.. include:: snippets/ObservationError.rst
+
+.. include:: snippets/ObservationOperator.rst
+
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo03AdOp.rst
+
+.. include:: snippets/BoundsWithNone.rst
+
+.. include:: snippets/BoxBounds.rst
- SetSeed
- Cette clé permet de donner un nombre entier pour fixer la graine du
- générateur aléatoire utilisé pour générer l'ensemble. Un valeur pratique est
- par exemple 1000. Par défaut, la graine est laissée non initialisée, et elle
- utilise ainsi l'initialisation par défaut de l'ordinateur.
+.. include:: snippets/CognitiveAcceleration.rst
- Exemple : ``{"SetSeed":1000}``
+.. include:: snippets/InertiaWeight.rst
- StoreInternalVariables
- Cette clé booléenne permet de stocker les variables internes par défaut,
- principalement l'état courant lors d'un processus itératif. Attention, cela
- peut être un choix numériquement coûteux dans certains cas de calculs. La
- valeur par défaut est "False".
+.. include:: snippets/InitializationPoint.rst
- Exemple : ``{"StoreInternalVariables":True}``
+.. include:: snippets/MaximumNumberOfFunctionEvaluations.rst
- StoreSupplementaryCalculations
- Cette liste indique les noms des variables supplémentaires qui peuvent être
- disponibles à la fin de l'algorithme. Cela implique potentiellement des
- calculs ou du stockage coûteux. La valeur par défaut est une liste vide,
- aucune de ces variables n'étant calculée et stockée par défaut. Les noms
- possibles sont dans la liste suivante : ["BMA", "OMA", "OMB", "Innovation"].
+.. include:: snippets/MaximumNumberOfIterations_50.rst
- Exemple : ``{"StoreSupplementaryCalculations":["BMA","Innovation"]}``
+.. include:: snippets/NumberOfInsects.rst
-Informations et variables disponibles à la fin de l'algorithme
-++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+.. include:: snippets/QualityCriterion.rst
-En sortie, après exécution de l'algorithme, on dispose d'informations et de
-variables issues du calcul. La description des
-:ref:`section_ref_output_variables` indique la manière de les obtenir par la
-méthode nommée ``get`` de la variable "*ADD*" du post-processing. Les variables
-d'entrée, mises à disposition de l'utilisateur en sortie pour faciliter
-l'écriture des procédures de post-processing, sont décrites dans
-l':ref:`subsection_r_o_v_Inventaire`.
+.. include:: snippets/SetSeed.rst
-Les sorties non conditionnelles de l'algorithme sont les suivantes:
+.. include:: snippets/SocialAcceleration.rst
- Analysis
- *Liste de vecteurs*. Chaque élément est un état optimal :math:`\mathbf{x}*`
- en optimisation ou une analyse :math:`\mathbf{x}^a` en assimilation de
- données.
+StoreSupplementaryCalculations
+ .. index:: single: StoreSupplementaryCalculations
- Exemple : ``Xa = ADD.get("Analysis")[-1]``
+ *Liste de noms*. Cette liste indique les noms des variables supplémentaires,
+ qui peuvent être disponibles au cours du déroulement ou à la fin de
+ l'algorithme, si elles sont initialement demandées par l'utilisateur. Leur
+ disponibilité implique, potentiellement, des calculs ou du stockage coûteux.
+ La valeur par défaut est donc une liste vide, aucune de ces variables n'étant
+ calculée et stockée par défaut (sauf les variables inconditionnelles). Les
+ noms possibles pour les variables supplémentaires sont dans la liste suivante
+ (la description détaillée de chaque variable nommée est donnée dans la suite
+ de cette documentation par algorithme spécifique, dans la sous-partie
+ "*Informations et variables disponibles à la fin de l'algorithme*") : [
+ "Analysis",
+ "BMA",
+ "CostFunctionJ",
+ "CostFunctionJb",
+ "CostFunctionJo",
+ "CurrentIterationNumber",
+ "CurrentState",
+ "Innovation",
+ "InternalCostFunctionJ",
+ "InternalCostFunctionJb",
+ "InternalCostFunctionJo",
+ "InternalStates",
+ "OMA",
+ "OMB",
+ "SimulatedObservationAtBackground",
+ "SimulatedObservationAtCurrentState",
+ "SimulatedObservationAtOptimum",
+ ].
- CostFunctionJ
- *Liste de valeurs*. Chaque élément est une valeur de fonctionnelle d'écart
- :math:`J`.
+ Exemple :
+ ``{"StoreSupplementaryCalculations":["CurrentState", "Residu"]}``
- Exemple : ``J = ADD.get("CostFunctionJ")[:]``
+.. include:: snippets/SwarmTopology.rst
- CostFunctionJb
- *Liste de valeurs*. Chaque élément est une valeur de fonctionnelle d'écart
- :math:`J^b`, c'est-à-dire de la partie écart à l'ébauche.
+.. include:: snippets/Variant_PSO.rst
- Exemple : ``Jb = ADD.get("CostFunctionJb")[:]``
+.. include:: snippets/VelocityClampingFactor.rst
- CostFunctionJo
- *Liste de valeurs*. Chaque élément est une valeur de fonctionnelle d'écart
- :math:`J^o`, c'est-à-dire de la partie écart à l'observation.
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo04.rst
- Exemple : ``Jo = ADD.get("CostFunctionJo")[:]``
+.. include:: snippets/Analysis.rst
-Les sorties conditionnelles de l'algorithme sont les suivantes:
+.. include:: snippets/CostFunctionJ.rst
- BMA
- *Liste de vecteurs*. Chaque élément est un vecteur d'écart entre
- l'ébauche et l'état optimal.
+.. include:: snippets/CostFunctionJb.rst
- Exemple : ``bma = ADD.get("BMA")[-1]``
+.. include:: snippets/CostFunctionJo.rst
- CurrentState
- *Liste de vecteurs*. Chaque élément est un vecteur d'état courant utilisé
- au cours du déroulement de l'algorithme d'optimisation.
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo05.rst
- Exemple : ``Xs = ADD.get("CurrentState")[:]``
+.. include:: snippets/Analysis.rst
- Innovation
- *Liste de vecteurs*. Chaque élément est un vecteur d'innovation, qui est
- en statique l'écart de l'optimum à l'ébauche, et en dynamique l'incrément
- d'évolution.
+.. include:: snippets/BMA.rst
- Exemple : ``d = ADD.get("Innovation")[-1]``
+.. include:: snippets/CostFunctionJ.rst
- OMA
- *Liste de vecteurs*. Chaque élément est un vecteur d'écart entre
- l'observation et l'état optimal dans l'espace des observations.
+.. include:: snippets/CostFunctionJb.rst
- Exemple : ``oma = ADD.get("OMA")[-1]``
+.. include:: snippets/CostFunctionJo.rst
- OMB
- *Liste de vecteurs*. Chaque élément est un vecteur d'écart entre
- l'observation et l'état d'ébauche dans l'espace des observations.
+.. include:: snippets/CurrentIterationNumber.rst
- Exemple : ``omb = ADD.get("OMB")[-1]``
+.. include:: snippets/CurrentState.rst
-Voir aussi
-++++++++++
+.. include:: snippets/Innovation.rst
-Références bibliographiques :
- - [WikipediaPSO]_
+.. include:: snippets/InternalCostFunctionJ.rst
+
+.. include:: snippets/InternalCostFunctionJb.rst
+
+.. include:: snippets/InternalCostFunctionJo.rst
+
+.. include:: snippets/InternalStates.rst
+
+.. include:: snippets/OMA.rst
+
+.. include:: snippets/OMB.rst
+
+.. include:: snippets/SimulatedObservationAtBackground.rst
+
+.. include:: snippets/SimulatedObservationAtCurrentState.rst
+
+.. include:: snippets/SimulatedObservationAtOptimum.rst
+
+.. ------------------------------------ ..
+.. _section_ref_algorithm_ParticleSwarmOptimization_examples:
+
+.. include:: snippets/Header2Algo09.rst
+
+.. include:: scripts/simple_ParticleSwarmOptimization1.rst
+
+.. literalinclude:: scripts/simple_ParticleSwarmOptimization1.py
+
+.. include:: snippets/Header2Algo10.rst
+
+.. literalinclude:: scripts/simple_ParticleSwarmOptimization1.res
+ :language: none
+
+.. include:: snippets/Header2Algo11.rst
+
+.. _simple_ParticleSwarmOptimization1:
+.. image:: scripts/simple_ParticleSwarmOptimization1.png
+ :align: center
+ :width: 90%
+
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo06.rst
+
+- :ref:`section_ref_algorithm_DerivativeFreeOptimization`
+- :ref:`section_ref_algorithm_DifferentialEvolution`
+- :ref:`section_ref_algorithm_TabuSearch`
+
+.. ------------------------------------ ..
+.. include:: snippets/Header2Algo07.rst
+
+- [WikipediaPSO]_
+- [ZambranoBigiarini13]_
