13.15. Algorithme de calcul « TabuSearch »

Description

Cet algorithme réalise une estimation d’état par minimisation d’une fonctionnelle d’écart J sans gradient. C’est une méthode qui n’utilise pas les dérivées de la fonctionnelle d’écart. Elle entre, par exemple, dans la même catégorie que l”Algorithme de calcul « DerivativeFreeOptimization », l”Algorithme de calcul « ParticleSwarmOptimization » ou l”Algorithme de calcul « DifferentialEvolution ».

C’est une méthode d’optimisation permettant la recherche du minimum global d’une fonctionnelle d’erreur J quelconque de type L^1, L^2 ou 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.

Elle fonctionne par exploration aléatoire itérative du voisinage du point courant, pour en choisir l’état qui minimise la fonctionnelle d’écart. Pour éviter de revenir dans un point déjà exploré, le mécanisme de mémoire de l’algorithme permet d’interdire (d’où le nom de tabou) le retour dans les derniers états explorés. Les positions déjà explorées sont conservées dans une liste de longueur finie.

Commandes requises et optionnelles

Les commandes générales requises, disponibles en édition dans l’interface graphique ou textuelle, sont les suivantes :

Background
Vecteur. La variable désigne le vecteur d’ébauche ou d’initialisation, usuellement noté \mathbf{x}^b. Sa valeur est définie comme un objet de type « Vector » ou « VectorSerie ». Sa disponibilité en sortie est conditionnée par le booléen « Stored » associé en entrée.
BackgroundError
Matrice. La variable désigne la matrice de covariance des erreurs d’ébauche, usuellement notée \mathbf{B}. Sa valeur est définie comme un objet de type « Matrix », de type « ScalarSparseMatrix », ou de type « DiagonalSparseMatrix », comme décrit en détail dans la section Conditions requises pour décrire des matrices de covariance. Sa disponibilité en sortie est conditionnée par le booléen « Stored » associé en entrée.
Observation
Liste de vecteurs. La variable désigne le vecteur d’observation utilisé en assimilation de données ou en optimisation, et usuellement noté \mathbf{y}^o. Sa valeur est définie comme un objet de type « Vector » si c’est une unique observation (temporelle ou pas) ou « VectorSerie » si c’est une succession d’observations. Sa disponibilité en sortie est conditionnée par le booléen « Stored » associé en entrée.
ObservationError
Matrice. La variable désigne la matrice de covariance des erreurs a priori d’ébauche, usuellement notée \mathbf{R}. Cette matrice est définie comme un objet de type « Matrix », de type « ScalarSparseMatrix », ou de type « DiagonalSparseMatrix », comme décrit en détail dans la section Conditions requises pour décrire des matrices de covariance. Sa disponibilité en sortie est conditionnée par le booléen « Stored » associé en entrée.
ObservationOperator
Opérateur. La variable désigne l’opérateur d’observation, usuellement noté H, qui transforme les paramètres d’entrée \mathbf{x} en résultats \mathbf{y} qui sont à comparer aux observations \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 Conditions requises pour les fonctions décrivant un opérateur. Si un contrôle U est inclus dans le modèle d’observation, l’opérateur doit être appliqué à une paire (X,U).

Les commandes optionnelles générales, disponibles en édition dans l’interface graphique ou textuelle, sont indiquées dans la Liste des commandes et mots-clés pour un cas d’assimilation de données ou d’optimisation. De plus, les paramètres de la commande « AlgorithmParameters » permettent d’indiquer les options particulières, décrites ci-après, de l’algorithme. On se reportera à la Description des options d’un algorithme par « AlgorithmParameters » pour le bon usage de cette commande.

Les options sont les suivantes :

Bounds

Liste de paires de valeurs réelles. Cette clé permet de définir des paires de bornes supérieure et inférieure pour chaque variable d’état optimisée. Les bornes doivent être données par une liste de liste de paires de bornes inférieure/supérieure pour chaque variable, avec une valeur None chaque fois qu’il n’y a pas de borne. Les bornes peuvent toujours être spécifiées, mais seuls les optimiseurs sous contraintes les prennent en compte.

Exemple : {"Bounds":[[2.,5.],[1.e-2,10.],[-30.,None],[None,None]]}

LengthOfTabuList

Valeur entière. Cette clé indique la longueur de la liste taboue, c’est-à-dire le nombre maximal de perturbations antérieurement réalisées et conservées pour mémoire. Le défaut est 50, et il est recommandé de l’adapter aux besoins pour des problèmes réels.

Exemple : {"LengthOfTabuList":50}

MaximumNumberOfIterations

Valeur entière. Cette clé indique le nombre maximum d’itérations interne 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 : {"MaximumNumberOfIterations":50}

NoiseAddingProbability

Valeur réelle. Cette clé indique la probabilité de perturbation d’une composante de l’état. C’est une valeur obligatoirement comprise entre 0 et 1. La valeur par défaut est 1, et il n’est pas recommandé de la changer.

Exemple : {"NoiseAddingProbability":1.}

NoiseDistribution

Nom prédéfini. Cette clé indique le type de la distribution utilisée pour générer les perturbations d’état. Cette distribution peut être de type « Uniform » ou « Gaussian ». Le défaut est une distribution de type « Uniform », et il est recommandé de l’adapter aux besoins pour des problèmes réels.

Exemple : {"NoiseDistribution":"Uniform"}

NoiseHalfRange

Liste de valeurs réelles. Cette clé indique, uniquement dans le cas d’une distribution de type « Uniform » demandée par le mot-clé « NoiseDistribution », la demi-amplitude des perturbations uniformes centrées d’état pour chaque composante de l’état. Le défaut est une liste vide, cette clé doit donc obligatoirement être renseignée dans le cas d’une distribution « Uniform ». Une manière simple de le faire est de donner une liste de la longueur de l’état recherché et de demi-amplitudes identiques, comme dans l’exemple ci-dessous avec des demi-amplitudes de 3%. Il est conseillé de prendre des demi-amplitudes de quelques pourcents au maximum.

Exemple : {"NoiseHalfRange":<longueur de l'état>*[0.03]}

NumberOfElementaryPerturbations

Valeur entière. Cette clé indique le nombre de perturbations élémentaires qui seront réalisées pour choisir une perturbation complète d’état. Le défaut est de 1, et il est recommandé de l’adapter avec prudence aux besoins pour des problèmes réels, sans choisir un trop grand nombre de perturbations élémentaires.

Exemple : {"NumberOfElementaryPerturbations":1}

QualityCriterion

Nom prédéfini. 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 » <=> « Linf »].

Exemple : {"QualityCriterion":"DA"}

SetSeed

Valeur entière. Cette clé permet de donner un nombre entier pour fixer la graine du générateur aléatoire utilisé dans l’algorithme. Par défaut, la graine est laissée non initialisée, et elle utilise ainsi l’initialisation par défaut de l’ordinateur, qui varie donc à chaque étude. Pour assurer la reproductibilité de résultats impliquant des tirages aléatoires, il est fortement conseiller d’initialiser la graine. Une valeur simple est par exemple 123456789. Il est conseillé de mettre un entier à plus de 6 ou 7 chiffres pour bien initialiser le générateur aléatoire.

Exemple : {"SetSeed":123456789}

StandardDeviation

Liste de valeurs réelles. Cette clé indique, uniquement dans le cas d’une distribution de type « Gaussian » demandée par le mot-clé « NoiseDistribution », l’écart-type des perturbations gaussiennes d’état pour chaque composante de l’état. Le défaut est une liste vide, cette clé doit donc obligatoirement être renseignée dans le cas d’une distribution « Gaussian ». Une manière simple de le faire est de donner une liste de la longueur de l’état recherché avec des écart-types identiques, comme dans l’exemple ci-dessous avec des demi-amplitudes de 5%. Il est conseillé de prendre des écart-types de quelques pourcents au maximum.

Exemple : {"StandardDeviation":<longueur de l'état>*[0.05]}

StoreSupplementaryCalculations

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 », « OMA », « OMB », « SimulatedObservationAtBackground », « SimulatedObservationAtCurrentState », « SimulatedObservationAtOptimum », ].

Exemple : {"StoreSupplementaryCalculations":["BMA", "CurrentState"]}

Informations et variables disponibles à la fin de l’algorithme

En sortie, après exécution de l’algorithme, on dispose d’informations et de variables issues du calcul. La description des Variables et informations disponibles en sortie indique la manière de les obtenir par la méthode nommée get, de la variable « ADD » du post-processing en interface graphique, ou du cas en interface textuelle. 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”Inventaire des informations potentiellement disponibles en sortie.

Sorties permanentes (non conditionnelles)

Les sorties non conditionnelles de l’algorithme sont les suivantes :

Analysis

Liste de vecteurs. Chaque élément de cette variable est un état optimal \mathbf{x}^* en optimisation ou une analyse \mathbf{x}^a en assimilation de données.

Exemple : Xa = ADD.get("Analysis")[-1]

CostFunctionJ

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J choisie.

Exemple : J = ADD.get("CostFunctionJ")[:]

CostFunctionJb

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J^b, c’est-à-dire de la partie écart à l’ébauche. Si cette partie n’existe pas dans la fonctionnelle, sa valeur est nulle.

Exemple : Jb = ADD.get("CostFunctionJb")[:]

CostFunctionJo

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J^o, c’est-à-dire de la partie écart à l’observation.

Exemple : Jo = ADD.get("CostFunctionJo")[:]

Ensemble des sorties à la demande (conditionnelles ou non)

L’ensemble des sorties (conditionnelles ou non) de l’algorithme, classées par ordre alphabétique, est le suivant :

Analysis

Liste de vecteurs. Chaque élément de cette variable est un état optimal \mathbf{x}^* en optimisation ou une analyse \mathbf{x}^a en assimilation de données.

Exemple : Xa = ADD.get("Analysis")[-1]

BMA

Liste de vecteurs. Chaque élément est un vecteur d’écart entre l’ébauche et l’état optimal.

Exemple : bma = ADD.get("BMA")[-1]

CostFunctionJ

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J choisie.

Exemple : J = ADD.get("CostFunctionJ")[:]

CostFunctionJb

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J^b, c’est-à-dire de la partie écart à l’ébauche. Si cette partie n’existe pas dans la fonctionnelle, sa valeur est nulle.

Exemple : Jb = ADD.get("CostFunctionJb")[:]

CostFunctionJo

Liste de valeurs. Chaque élément est une valeur de fonctionnelle d’écart J^o, c’est-à-dire de la partie écart à l’observation.

Exemple : Jo = ADD.get("CostFunctionJo")[:]

CurrentIterationNumber

Liste d’entiers. Chaque élément est l’index d’itération courant au cours du déroulement itératif de l’algorithme utilisé. Il y a une valeur d’index d’itération par pas d’assimilation correspondant à un état observé.

Exemple : i = ADD.get("CurrentIterationNumber")[-1]

CurrentState

Liste de vecteurs. Chaque élément est un vecteur d’état courant utilisé au cours du déroulement itératif de l’algorithme utilisé.

Exemple : Xs = ADD.get("CurrentState")[:]

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.

Exemple : d = ADD.get("Innovation")[-1]

OMA

Liste de vecteurs. Chaque élément est un vecteur d’écart entre l’observation et l’état optimal dans l’espace des observations.

Exemple : oma = ADD.get("OMA")[-1]

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.

Exemple : omb = ADD.get("OMB")[-1]

SimulatedObservationAtBackground

Liste de vecteurs. Chaque élément est un vecteur d’observation simulé par l’opérateur d’observation à partir de l’ébauche \mathbf{x}^b. C’est la prévision à partir de l’ébauche, elle est parfois appellée « Dry ».

Exemple : hxb = ADD.get("SimulatedObservationAtBackground")[-1]

SimulatedObservationAtCurrentState

Liste de vecteurs. Chaque élément est un vecteur d’observation simulé par l’opérateur d’observation à partir de l’état courant, c’est-à-dire dans l’espace des observations.

Exemple : hxs = ADD.get("SimulatedObservationAtCurrentState")[-1]

SimulatedObservationAtOptimum

Liste de vecteurs. Chaque élément est un vecteur d’observation obtenu par l’opérateur d’observation à partir de la simulation d’analyse ou d’état optimal \mathbf{x}^a. C’est l’observation de la prévision à partir de l’analyse ou de l’état optimal, et elle est parfois appellée « Forecast ».

Exemple : hxa = ADD.get("SimulatedObservationAtOptimum")[-1]