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

[am_003]

pas de répons??
j'aimerais juste que vs donniez un coup de pouce car je n'arrive vraiment pas à comprendre ce qu'il faut faire !!
merci

[jeanmichB]

RE bonjour,

J'ai donc bien régler le problème de la décroissance de température (avec palier), mais concernant le génération d'un nouveau voisin...je bloque un peu.
(J'ai essayé de générer un voisin totalement aléatoire, et aussi un voisin proche de la solution actuelle, mais ça ne fonctionne pas...).

En simplifié, l'algo donnerait ça pour le moment:

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
19
20
21
22
23
24
25
26
27
28
29
 
 Tant que (Température > Température Finale) faire
 
{ 
Tant que (Répétition > Max Répétition à T constant) faire:
 
{
Choisir Y dans le Voisinage de X   ( ???)
Calculer DF = F(Y) –F(X)
Si DF < 0 alors 				 (ce qui signifie que Y est mieux que X)
 
{ 
X = Y   			
Si F(X) < F(Xbest) alors 
Xbest = X  			
Fmin = F(Xbest) 		
}
 
Sinon  					(Y n’est pas mieux que X)
Tirer p dans [0; 1] 			
Si p <  exp(-DF/T )
X = Y				 (on accepte le voisin moins bon, avec une proba p)
}
 
T = 0,99 T
 
}
 
- Retourner Xbest

MERCI de votre aide, pour ceux qui s'y connaisse

[b_reda31]

pas de répons??
j'aimerais juste que vs donniez un coup de pouce car je n'arrive vraiment pas à comprendre ce qu'il faut faire !!
merci

Vous disposez, d'un ensemble de composants électroniques (blocs) interconnectés entre eux par des fils conducteurs, et d'une certaine configuration représentant l'emplacement initial de chaque composant.

Code :

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

1
2
3
4
5
6
7
8
 
BLOC 1 * * * * * * * BLOC 2
                   *
               *
           *
       *
   *
BLOC 3 * * * * * * * BLOC 4

Comme le cuivre est assez cher nous voulons minimiser la longueur totale des fils conducteurs et cela en modifiant l'emplacement des blocs.
Le coût représente alors la longueur totale des fils conducteurs. Pour la configuration que j'ai donné le coût vaut 4=1+2+1 selon la distance de manhatan.
Cependant si nous permutons les emplacement des blocs 3 et 4 nous atteindrons un meilleurs coût = 1+1+1=3

Code :

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

1
2
3
4
5
6
7
8
9
 
BLOC 1 * * * * * * * BLOC2
                       *          
                       *
                       *
                       *
                       *
                       *  
BLOC 4 * * * * * * * BLOC3

Le problème consiste donc à trouver la meilleure configuration des blocs.
à vous de jouer maintenant

[b_reda31]

RE bonjour,

J'ai donc bien régler le problème de la décroissance de température (avec palier), mais concernant le génération d'un nouveau voisin...je bloque un peu.
(J'ai essayé de générer un voisin totalement aléatoire, et aussi un voisin proche de la solution actuelle, mais ça ne fonctionne pas...).

Comment avez vous procédé exactement?
Qu'entendez vous par "ça ne fonctionne pas"?

Le mécanisme de génération de solution doit être conçu de manière à pouvoir atteindre tout (ou une bonne partie) l'espace de recherche à partir d'une solution initiale.
Un petit exemple :
générer un "pas" entre [-n,+n]
New_solution = Current_Sol + pas.
Vous pouvez ainsi par exemple commencer avec une valeur de n assez grande de manière à circuler librement dans l'espace recherche au début, puis faire décroitre n (en fonction de la température) pour une meilleure précision...

Je vous conseille de faire des essais en modifiant vos paramètres et voir comment se comporte votre algo.

Cependant je rejoins ce qu'a dis Nebulix. La force du recuit simulé est son apptitude à remonter les pente des minimum locaux afin d'atteindre le minimum global. Dans la fonction de Rosenbrock il me semble qu'il y a qu'un seul minimum.

[jeanmichB]

Salut b_reda !

J'ai modifié mon code de manière à générer un pas compris dans l'intervalle [-n,n], avec n qui décroit petit à petit avec la température. Et ça marche cette fois ci donc un très grand merci !
Mon erreur venait du fait justement, que pour générer un point voisin du point actuel, j'utilisais une fonction trouvée sur le net qui était supposé "efficace" ( comme quoi internet... ). Mais cela me donnait des minimums qui n'étaient pas les bons. Bref.

J'ai donc mis le code ci dessous, au cas ou cela puisse servir à quelqu'un, même si je préviens, je suis un pur débutant en matlab, et ce programme n'est certainement pas écrit dans les règles de l'art. Mais il marche (testé avec d'autres fonctions que Rosenbrock).

Les différents paramètres comme la température initiale, la température d'arrêt, le nombre d'itération à T constants ont été ajusté en fonction des tests que j'ai pu faire et de ce que j'ai pu lire (sur le net).

Une dernière question tout de même: peut on considérer, pour ceux qui pratique matlab régulièrement, qu'un 1.3e-006 et équivalent à un 0 ?
Si il y a la moindre remarque, conseil ou autre, je suis preneur...
Et si certains ont des questions et que je peux aider, ce sera avec plaisir.
Et encore merci !

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
x1=-1.2;    %point de départ imposé par mon énoncé: 
y1=1;        %   P=[-1.2,1]
T=70;
RepetitionTfixe=0;  %compteur à zéro
xbest=-1.2;          % la meilleur solution est pour l'instant le pt de départ
ybest=1;
n=4;
 
while(T>0.01)
 
    while(RepetitionTfixe<50)
 
        x2= x1 + ( (rand(1,1)-rand(1,1))*n);     %recherche d'un point voisin
        y2= y1 + ( (rand(1,1)-rand(1,1))*n);
        Delta=Rosenbrock(x2,y2)-Rosenbrock(x1,y1);  %calcul du delta
 
        if Delta<0
            x1=x2;
            y1=y2;
            Gamma=Rosenbrock(xbest,ybest)-Rosenbrock(x1,y1);
            if Gamma>0
                xbest=x1;
                ybest=y1;
            end
 
        else
            p=rand(1,1);    % on tire aléatoirement p entre 0 et 1
            if p< exp(-Delta/T)  % critère de metropolis
                xbest=x2;           % on sauve les valeurs 
                ybest=y2;
 
            end
        end	
        RepetitionTfixe=RepetitionTfixe+1;  
    end
    T=0.99*T;  % une méthode parmi d'autre de "cooling schedule"
    n=0.99*n;   % on diminue l'intervalle de recherche du point voisin
    RepetitionTfixe=0;  % remise à zéro du compteur une fois les 50 répétitions
end
 
xbest
ybest
Rosenbrock(xbest,ybest)

[el-bey2]

je suis debutant en matlab et je veu optimiser la fonctions x1^4-7*x1^2-3*x1-5*x2+11*x1^2*x2^2+ sin(71*x1)+*sin(51*x2); par la méthode de recuit simulé (simulated annealing)ou la méthode tabou.
Quelqu'un a peut m'aidé

[b_reda31]

Bonjour,

je suis debutant en matlab et je veu optimiser la fonctions x1^4-7*x1^2-3*x1-5*x2+11*x1^2*x2^2+ sin(71*x1)+*sin(51*x2); par la méthode de recuit simulé (simulated annealing)ou la méthode tabou.
Quelqu'un a peut m'aidé

JeanmichB a donné l'implémentation matlab de pour l'optimisation de la fonction de Rosenbrock par le recuit simulé. c'est une fonction à deux variables tout comme la votre, vous n'avez qu'à remplacer la fonction de Rosenbrock par la votre et ajuster éventuellement les paramètres. Je ne vois pas ce qu'il faut de plus.

[el-bey2]

salut mais ce algo me donne que xbest et ybest c.a.d le point il ne donne pas le best_fit ou minf

[b_reda31]

salut mais ce algo me donne que xbest et ybest c.a.d le point il ne donne pas le best_fit ou minf

Comme tout algorithme d'optimisation, le recuit simulé tente de retrouver la solution x_best pour laquelle la fonction à optimiser est minimale/maximale:
f(x_best) = Min (f(x)), pour tout x dans l'espace de recherche.(dans un cas idéal).
Que représente alors best_fit et minf ?

[el-bey2]

Comme tout algorithme d'optimisation, le recuit simulé tente de retrouver la solution x_best pour laquelle la fonction à optimiser est minimale/maximale:
f(x_best) = Min (f(x)), pour tout x dans l'espace de recherche.(dans un cas idéal).
Que représente alors best_fit et minf ?

oui ci ça
best_fit=minf=f(x_best)=min(f(x_best)) sont les même.
mais cet algo ne le donne pas !
et aussi je ne comprend pas bien le rôle de fonction rend
je veux la changer avec une autre fonctionva le mémé rôle

[b_reda31]

best_fit=minf=f(x_best)=min(f(x_best)) sont les même.
mais cet algo ne le donne pas !

Ben il suffit tout simplement d'appeler votre fonction en lui fournissant x_best et y_best comme paramètres :

Code :

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

1
2
3
 
best_fit=Rosebrock(x_best,y_best);
% là vous devez remplacer Rosebrock par votre fonction.

et aussi je ne comprend pas bien le rôle de fonction rend
je veux la changer avec une autre fonctionva le mémé rôle

Cette fonction permet la génération d'un nombre aléatoire, utilisez "help rand" sous matlab pour avoir plus d'infos.

[el-bey2]

merci reda
et pour optimiser cette fonction j'ai besoin de ploter cette fonction (les différents représentation de f) dans l'inter val de recherche j'ai utilise tout les commandes- plot3;mesh; surf- mais j'ai n'arive pas a un graphe souhaite
est ce que vous pouvez m'aider a resolu se problèmes

[b_reda31]

Je veux bien vous aider, mais je ne comprend pas vraiment ce qui vous bloque.
Votre question me semble relative à matlab et non à l'algorithmique.
Pour dresser la surface de votre fonction je vous propose ça :

Code :

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

1
2
3
4
 
[x1,x2]=meshgrid(-5:0.1:5);
z=x1.^4-7*x1.^2-3*x1-5*x2 %...il y a une erreur de syntaxe ds votre fonction
surf(x1,y1,z);

Cependant vous aurez sans doute de meilleurs réponses dans le forum Matlab

[el-bey2]

merci reda
je veux juste réécrire le code précédant avec les variable x1,x2 pas x,y et
je n'arrive pas a faire ca.