IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Optimisation d'une fonction par recuit simulé


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 5
    Par défaut 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

  2. #2
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 5
    Par défaut Optimisation d'une fonction par recuit simulé
    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

  3. #3
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    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
    • ...

  4. #4
    Membre très actif
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Par défaut
    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

  5. #5
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 5
    Par défaut
    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

  6. #6
    Membre averti
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 15
    Par défaut même principe...
    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

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 15
    Par défaut
    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

  8. #8
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 5
    Par défaut
    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

  9. #9
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    Citation Envoyé par am_003 Voir le message
    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

  10. #10
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    Citation Envoyé par jeanmichB Voir le message
    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.

  11. #11
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 5
    Par défaut
    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)

  12. #12
    Membre confirmé
    Inscrit en
    Octobre 2010
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 61
    Par défaut
    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é

  13. #13
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    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.

  14. #14
    Membre confirmé
    Inscrit en
    Octobre 2010
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 61
    Par défaut
    salut mais ce algo me donne que xbest et ybest c.a.d le point il ne donne pas le best_fit ou minf

  15. #15
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    Citation Envoyé par el-bey2 Voir le message
    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 ?

  16. #16
    Membre confirmé
    Inscrit en
    Octobre 2010
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 61
    Par défaut
    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

  17. #17
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    Citation Envoyé par el-bey2 Voir le message
    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.

  18. #18
    Membre confirmé
    Inscrit en
    Octobre 2010
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 61
    Par défaut
    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

  19. #19
    Membre émérite Avatar de b_reda31
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2007
    Messages
    899
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Algérie

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 899
    Par défaut
    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

  20. #20
    Membre confirmé
    Inscrit en
    Octobre 2010
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2010
    Messages : 61
    Par défaut
    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.

Discussions similaires

  1. optimisation par recuit simulé
    Par el-bey2 dans le forum Mathématiques
    Réponses: 10
    Dernier message: 04/02/2011, 21h20
  2. Réponses: 5
    Dernier message: 29/09/2006, 17h17
  3. Réponses: 6
    Dernier message: 12/05/2006, 15h20
  4. Réponses: 8
    Dernier message: 10/03/2006, 17h28
  5. creation d'une fonction par l'utilisateur
    Par michelk dans le forum VB 6 et antérieur
    Réponses: 16
    Dernier message: 15/03/2005, 09h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo