Table des matières PDF

Recherche d'un minimum à une dimension

1. Introduction

Soit une fonction f d'une variable réelle et à valeurs réelles, admettant un minimum dans l'intervalle ]a,b[, par exemple :

from matplotlib.pyplot import *
import numpy
def f(x):
    return x**4+2*x**3-12*x**2-2*x+77.37
a=-5
b=4
x=numpy.linspace(a,b,1000)
y=f(x)
figure()
plot(x,y)
xlabel("x")
ylabel("f(x)")
grid()
            
figAfigA.pdf

Il s'agit de déterminer le minimum de la fonction, appelé aussi minimum absolu, situé à . Cette fonction possède aussi un minimum relatif à .

La recherche d'un minimum consiste à partir d'un point quelconque et à suivre la pente descendante jusqu'à parvenir au minimum. En l'absence d'informations plus précises, le point initial de la recherche est choisi aléatoirement (avec une densité uniforme) sur l'intervalle ]a,b[. Cependant, la recherche d'un minimum en suivant la pente descendante a autant de chances de conduire au minimum relatif qu'au minimum absolu. Il faut donc un algorithme pour isoler un intervalle dans lequel se situe le minimum absolu, avant de faire une recherche plus précise de ce minimum. Nous utiliserons pour cela l'algorithme du recuit simulé.

2. Algorithme du recuit simulé

L'algorithme du recuit simulé est inspiré des méthodes de Monte-Carlo appliquées à la statistique de Boltzmann, et en particulier l'algorithme de Metropolis. Supposons que la fonction f définie ci-dessus représente l'énergie d'un système physique en fonction d'un paramètre x, définissant par exemple la structure cristalline d'un solide. D'après la loi de Boltzmann, la probabilité d'un état d'énergie E pour un système à la température T est :

p0 est une constante et kb la constante de Boltzmann.

Lorsque la température est suffisamment basse, le système se place au voisinage d'un état de minimum de l'énergie, soit le minimum absolu (état stable), plus rarement le minimum relatif (état métastable). Lorsque la température est très élevée, toutes les valeurs de x de l'intervalle sont équiprobables. Si le corps est refroidi lentement, il converge vers son état stable. Un refroidissement rapide peut le conduire dans un état métastable, c'est-à-dire un minimum relatif de l'énergie. Ce phénomène est mis à profit en métallurgie pour obtenir des structures cristallines métastables aux propriétés mécaniques intéressantes. En recuisant un cristal se trouvant dans un état métastable puis en le laissant refroidir lentement on peut l'amener dans son état stable.

L'algorithme du recuit simulé (simulated annealing) consiste en fait à simuler le processus de refroidissement très lent, en partant d'une température assez élevée. On devrait donc plutôt l'appeler algorithme du refroidissement simulé. L'algorithme permet de placer la variable x au voisinage du minimum absolu, mais pas de manière certaine. Avec un bon réglage de la vitesse de décroissance de la température, elle permet d'obtenir le minimum absolu avec une forte probabilité.

Pour notre problème, la loi de Boltzmann s'écrit :

Pour une température T donnée, l'algorithme de Metropolis consiste à générer une suite d'états (ici de valeurs de x) qui converge vers un ensemble d'états obéissant à la loi de probabilité de Boltzmann (ou une autre loi). On commence par une valeur x choisie aléatoirement (avec une densité de probabilité uniforme) dans l'intervalle ]a,b[. La suite d'états est générée par l'algorithme suivant :

Dans une simulation de Metropolis d'un système physique, on fait des calculs statistiques avec la suite des états ainsi générée. Dans l'algorithme du recuit simulé, seule la dernière valeur de x est utilisée. L'itération est répétée un grand nombre de fois avec la même température, puis on recommence avec une température un peu plus faible, en partant de la dernière valeur de x obtenue avec la température précédente. Avec une température finale assez faible, l'état final obtenu est très probablement très proche du minimum absolu.

Cet algorithme nécessite des réglages qui dépendent du problème à résoudre : valeur de Δx, nombre d'itérations à chaque température, températures initiale et finale, loi de décroissance de la température.

3. Recherche du minimum par encadrement itératif

L'algorithme du recuit simulé nous donne une valeur x1 proche du minimum absolu, du moins avec une forte probabilité. Pour rechercher avec précision le minimum, on peut à présent utiliser un algorithme déterministe.

Il faut tout d'abord encadrer le minimum en cherchant x1, x2 et x3 tels que f(x2)<f(x1) et f(x2)<f(x3), ce qui garantit la présence du minimum dans l'intervalle [x1,x3].

Soit un déplacement assez petit (initialement positif). On considère tout d'abord x2=x1+δx puis on échange éventuellement x1 et x2 pour que f(x2)<f(x1) (auquel cas on change le signe de ). En se déplaçant plusieurs fois de δx, on recherche ensuite une valeur x3 telle que f(x3)>f(x2). L'algorithme est illustré sur la figure suivante pour trois cas différents.

encadrement-1.svgFigure pleine page

L'algorithme doit fonctionner quelle que soit la position de x1 par rapport au minimum et quelle que soit la valeur de , à condition que celle-ci soit assez petite (en valeur absolue) pour qu'un déplacement de ne fasse pas sortir de la cuvette où se situe le minimum recherché.

On dispose à présent d'un encadrement du minimum par x1 et x3. On utilise une méthode itérative se répétant tant que |x3-x1|>ε, où ε est une tolérance égale au moins à la racine carrée de la précision des flottants. À chaque itération, une nouvelle valeur x est prise alternativement au milieu de l'intervalle [x1,x2] ou bien au milieu de l'intervalle [x2,x3]. Cette valeur vient remplacer une des trois valeurs (x1,x2,x3) de telle sorte que l'on ait toujours f(x2)<f(x1) et f(x2)<f(x3) afin de maintenir l'encadrement du minimum. Cet algorithme est illustré sur la figure suivante :

encadrement-2.svgFigure pleine page

4. Implémentation

On utilise le module random et la fonction random.random(). Pour ne pas générer toujours la même suite de nombres aléatoires, on initialisera le générateur avec random.seed().

[1] Écrire une fonction recuit_simule(f,a,b) qui effectue le recuit simulé pour la fonction f sur l'intervalle [a,b]. La rempérature pourra être variée de T=100 à T=1, avec une cinquantaine d'étapes comportant chacune un millier d'itérations. On pourra adopter le déplacement Δx=0.1. La fonction renvoie x1, la dernière valeur obtenue. Pour chaque température, faire un affichage de cette température et de la valeur de x finale.

[2] Tester plusieurs fois la fonction pour vérifier qu'elle donne le plus souvent une valeur proche du minimum absolu. Observer comment la valeur de x s'approche progressivement du minimu absolu.

[3] Écrire une fonction encadrement(f,x1,delta_x) qui effectue le premier encadrement du minimum et renvoie (x1,x2,x3).

[4] Écrire une fonction recherche_minimum(f,x1,x2,x3,tol) qui effectue la recherche itérative par encadrement et renvoie le minimum. Tester avec une tolérance 10-4.

[5] Mettre en place un test visant à déterminer la probabilité de trouver le minimum absolu et non pas le minimum relatif. Tester différentes vitesses de refroidissement.

Creative Commons LicenseTextes et figures sont mis à disposition sous contrat Creative Commons.