Étape 1 : exploration de l'espace des paramètres par méthode de proches voisins (NA)

La première étape de l'inversion a pour but d'explorer l'espace des paramètres. Elle permet aussi d'avoir accès à un meilleur modèle. La figure 5.2 illustre le principe de l'algorithme itératif (proches voisins) à partir d'un exemple d'inversion pour un espace à deux dimensions.

La fonction de Rosenbrock (ou fonction banane) que l'on cherche à minimiser est souvent utilisée pour tester les algorithmes d'optimisation. Elle a la particularité de posséder une vallée dans laquelle la valeur du coût varie très peu. Le minimum que l'on cherche à retrouver correspond au point de coordonnées [1,1].

À la première itération, $Ns_1$ modèles sont tirés de manière aléatoire et pour chacun d'entre eux, la fonction coût est calculée. L'espace des paramètres est ensuite divisé en cellules de Voronoï, puis ces cellules sont triées selon les valeurs croissantes de la fonction coût.

**Figure 5.2 :** Exemple de minimisation d'une fonction par proches voisins. On cherche le minimum de la fonction banane montrée à la première figure ($\min_{banane}=[1,1]$). Les bornes utilisées sont $(x,y)\in[-2,2]$, $Ns_1 = 25$ et $Ns_2 = 10$. Pour l'itération $n$, tous les points tirés aux itérations $<n$ sont marqués en noir, les cellules contenant les meilleurs modèles sont surlignées en rouge, et les points tirés dans ces meilleures cellules sont marqués en rouge.

À l'itération $n+1$, les $Ns_2$ cellules associées aux $Ns_2$ meilleurs modèles sont sélectionnées, c'est à dire celles pour lesquelles la fonction coût est la plus faible, puis un nouveau modèle est tiré de manière aléatoire dans chacune de ces cellules. De nouveau, les fonctions coût sont calculées pour ces nouveaux modèles, puis l'espace des paramètres est de nouveau fragmenté en cellules de Voronoï en prenant en compte les nouveaux modèles calculés.

À chaque itération, les nouveaux modèles sont tirés dans les cellules ayant un coût faible. Dès lors, au fur et à mesure des itérations, les modèles tirés convergent vers le modèle correspondant au minimum de la fonction coût. La taille (ou surface dans notre exemple) des cellules de voronoï nouvellement créées diminue avec le nombre d'itérations, et l'espace des paramètres est d'autant mieux sous-échantillonné que la procédure se rapproche du minimum de la fonction $\chi^2$.

L'exploration de l'espace des paramètres par méthode de proches voisins a été implémenté en langage Matlab par [Fukushima et al.(2005)]. Nous présentons un guide d'utilisation d'une version très modifiée de cette procédure dans la partie II (fonction nasearch_moi) ainsi que différentes variantes de la recherche par proches voisins.

kunos 2014-07-01