Discussion :

[jeanmichB]

Bonjour,

Mon problème est le suivant:
Je souhaite optimiser la fonction de rosenbrock (f(x,y)=100 (x²-y)²+(1-x)²) à partir de la méthode du recuit simulé (simulated annealing). J'ai pour consigne de reprendre un bon code sur le net plutôt que de faire mon propre code (en effet, à ce stade du cours nous n'avons que peu de connaissance en matlab).
Après de longues recherches sur le net, j'ai trouvé un code qui semble tenir la route (voir ci dessous). Mais je ne vois vraiment pas comment l'adapter pour l'optimisation de la fonction qui m'intéresse.
Quelqu'un a t-il quelques connaissances en la matière ?

merci de votre aide

Code de simulé recuit trouvé:

http://www.mathworks.com/matlabcentr...ling-algorithm

[jeanmichB]

Dans l'idée, un algo de ce genre là est-il exploitable pour rosenbrock ?
Et si oui, que faire de ce paramètre température, qui est tout de même la base du simulated annealing ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Initialization(Current_solution,Temperature)
Calculation of the Current_Cost
LOOP
New_State
Calculation of the new_Cost
IF D(Current_cost - New_Cost) £ 0 THEN
Current_State= New_State
ELSE
IF 
Exp( (Current_cost-New_cost)/ Temperature) > Random (0,1)
THEN
-- Accept
Current_State = New_State
ELSE
-- Reject
Decrease the temperature
EXIT When STOP_CRITERION
END LOOP

[b_reda31]

En gros le principe du recuit simulé consiste à générer successivement des solutions à partir d'une solution initiale x0 et d'une température initiale t0 qui diminuera tout au long du processus jusqu'à atteindre une température finale.
Dans votre cas, le "coût" représente la fonction f que vous voulez mimimiser. Une solution est représentée par un couple (x,y) (fonction à deux paramètres)
Si le coût d'une solution générée est meilleure que la solution actuelle, on l'accepte. Dans le cas inverse (f(New_Solution)>f(Current_Solution)), on peut se permettre d'accepter la nouvelle solution seulement si la température est assez élevée et que la nouvelle solution n'est pas trop mauvaise (par rapport à la solution actuelle).En d'autres termes ceci revient à dire que la nouvelle solution est accepté selon une certaine probabilité p qui est :

• Proportionnelle à T
• Inversement proportionnelle à la variation du coût df = f(New_Solution)-f(Current_Solution)

p est généralement exprimé par la fonction de probabilité : p = exp(-df/T) (regle de metropolis)Ici on peut remarquer que plus T est élevé plus p s'approche du 1,et lorsque T tend vers 0, p aussi...(l'inverse par rapport à df)
En tout, ça donnerait quelque chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Current_Solution=x0
T = T0
nb_iter=0
Tant Que (T>Tfinale) et (Nbitération<nb_max) 
  New_Solution = Generate_NewSolution(Current_Solution)
    Si f(New_Solution)<f(Current_Solution) Alors    
        Current_Solution=New_Solution
    Sinon 
        df= f(New_Solution)-f(Current_Solution)
        p=exp(-df/T)
            Si (p>Random(0.1)) Alors 
                Current_Solution=NewSolution     
            fsi
    fsi
T=Decrease(T)
nb_iter = nb_iter+1
FinTq

Ceci est un algorithme générique du recuit simulé. Il faudra donc que vous l'adaptiez à votre problème :

• Définir un mécanisme de génération de nouvelles solutions (Generate_NewSolution)
• Définir la manière dont décroît la Température (Decrease(T))
• Ajout éventuel d'une boucle imbriquée pour répéter le processus n fois à température constante
• ...

[Nebulix]

La methode de recuit simulé est utile pour trouver le "meilleur" minimum d'une fonction qui en a plusieurs, ce qui n'est pas le cas de la fonction de Rosenbrock, pour laquelle il existe desx algos plus simples

[jeanmichB]

OK merci bien pour vos réponses !

@Nebulix: Je suis parfaitement d'accord avec toi, mais mon sujet est d'optimiser la fonction donnée avec le recuit simulé. On ne me laisse pas vraiment le choix

@b_reda31: Merci pour ton aide, je vais creuser un peu du côté des pistes que tu m'as données (comment faire décroitre la température et comment générer de nouvelles solutions). Même si maintenant ma principale difficulté va être de mettre tout ça en language matlab

Merci encore

[am_003]

Bonjour,
j'ai bcp apprécié les explication données sur la méthode de recuit simulé.en effet, j'ai un projet de TP à faire sur le même principe sauf qu'il est appliqué dans un autre problème.
J'aimerais le réaliser sous Matlab, mais je n'ai pas bien assimiler le problème,
c'est pour cela j'aimerais bien si vous pouvez m'aider svp à mieux comprendre le but de ce projet.(TP abordé sans cours et TD)
Je joins dans le lien ci-dessous, la copie du TP (N.B. seulement la 1ère partie est demandée)
http://i52.tinypic.com/161l1dd.jpg
http://i54.tinypic.com/352el2x.jpg
Merci d'avance