Optimisation d'une fonction par recuit simulé

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

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:

---

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

---

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:

---

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
• ...

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

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

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

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

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:

---

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 :)

Citation:

---

Envoyé par am_003

pas de répons??:oops:
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:

---

1 2 3 4 5 6 7 8

BLOC 1 * * * * * * * BLOC 2 * * * * * BLOC 3 * * * * * * * BLOC 4

---

Comme le cuivre est assez cher :aie: 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:

---

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 ;)

Citation:

---

Envoyé par 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...).

---

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.

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 :D 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:

---

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)

---

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é

Bonjour,

Citation:

---

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.

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

Citation:

---

Envoyé par 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

---

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 ?

Citation:

---

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

Citation:

---

Envoyé par el-bey2

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:

---

1 2 3

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

---

Citation:

---

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.

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

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:

---

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

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.

Bonjour,
j'ai un projet à réaliser en utilisant l'algorithme de recuit simulé, je suis alors bloqué dans la partie du choix aléatoire de Y, j'ai vu dans le code proposé par @jeanmich, qu'il a fait la soustraction de (rand(1,1)-rand(1,1))*n) de X. je souhaite savoir pourquoi il a fait soustraction et pas l'addition? et qu'est ce que apporte cette combinaison aléatoire (rand(1,1)-rand(1,1))*n), pourquoi ne pas utiliser tout simplement Y=X-rand(1,1)?
merci de votre aide

Citation:

---

Envoyé par hananeeee

Bonjour,
j'ai un projet à réaliser en utilisant l'algorithme de recuit simulé, je suis alors bloqué dans la partie du choix aléatoire de Y, j'ai vu dans le code proposé par @jeanmich, qu'il a fait la soustraction de (rand(1,1)-rand(1,1))*n) de X. je souhaite savoir pourquoi il a fait soustraction et pas l'addition? et qu'est ce que apporte cette combinaison aléatoire (rand(1,1)-rand(1,1))*n), pourquoi ne pas utiliser tout simplement Y=X-rand(1,1)?
merci de votre aide

---

Bonjour,
avant tout il faut savoir que rand(1,1) est une fonction matlab qui génère un scalaire aléatoirement compris entre 0 et 1.

ceci dit, il faut aussi savoir que durant l'optimisation, la valeur d'une solution peut aussi bien augmenter que diminuer au fur et à mesure des itérations.

Citation:

---

pourquoi ne pas utiliser tout simplement Y=X-rand(1,1)?

---

Dans ce cas, la valeur de la variable va uniquement diminuer il n'y aura jamais une augmentation.
(Attention à ne pas confondre entre les variables : dans l'exemple de Jeanmich, il s'agit de minimiser une fonction à deux variables X et Y, ici vous confondez ces deux variables).

La technique utilisée dans le code de l'exemple (x2= x1 + ( (rand(1,1)-rand(1,1))*n); ) permet justement de faire évoluer la valeur dans les deux sens ; car rand(1,1)-rand(1,1)) est compris entre -1 et +2.

Voici une autre solution plus équitable :

x2=x1-(rand(1,1)-0.5) ;
qui est aussi équivalent à
x2=x1+(rand(1,1)-0.5) ;