Probabilités et simulation

Bonsoir
Je suis en train de travailler sur un algorithme de type génétique pour la résolution du problème du voyageur de commerce et un "grave" probleme se présente à moi : simuler une loi de probabilité "non usuelle".
Je connais bien le theorème fondamental de la simulation, mais j'avoue ouvertement que les probabilités ne sont pas ma tasse de thé...

La loi en question est $$p_k(r,s)=\left\{ \begin{array}{r l} \frac{[\tau(r,s)].[\eta(r,s)]^\beta}{\sum_{u\not\in M_k}[\tau(r,s)].[\eta(r,s)]^\beta} & \text{si }s\not\in M_k \\ & \\ 0 & \text{sinon },\end{array}\right.

$$ où $M_k$ est évidemment un ensemble connu et où $\tau(r,s)$ et $\eta(r,s)$ sont des réels constants. $p_k(r,s)$ représente la probabilité que l'agent $k$ se déplace de la ville $r$ vers la ville $s$.

Quelqu'un aurait-il une idée pour simuler ceci a l'aide d'une formule contenant une variable de loi uniforme ?
Il faudra que je regarde dans le "Probabilités pour l'ingénieur" de Boileau mais je ne suis pas vraiment sur d'y trouver une réponse à mon problème.

Merci à qui voudra bien m'aider !
Hoeg

Réponses

  • La même chose avec la fameuse case...


    Bonsoir,


    Je suis en train de travailler sur un algorithme de type génétique pour la résolution du problème du voyageur de commerce et un "grave" probleme se présente à moi : simuler une loi de probabilité "non usuelle".
    Je connais bien le theorème fondamental de la simulation, mais j'avoue ouvertement que les probabilités ne sont pas ma tasse de thé...

    La loi en question est $$p_k(r,s)=\left\{ \begin{tabular}{l l} $\frac{[\tau(r,s)].[\eta(r,s)]^\beta}{\sum_{u\not\in M_k}[\tau(r,s)].[\eta(r,s)]^\beta}$ & si $s\not\in M_k$ \\ & \\ $0$ & sinon \end{tabular}\right.$$

    où $M_k$ est évidemment un ensemble connu et où $\tau(r,s)$ et $\eta(r,s)$ sont des réels constants. $p_k(r,s)$ représente la probabilité que l'agent $k$ se déplace de la ville $r$ vers la ville $s$.

    Quelqu'un aurait-il une idée pour simuler ceci a l'aide d'une formule contenant une variable de loi uniforme ?
    Il faudra que je regarde dans le "Probabilités pour l'ingénieur" de Boileau mais je ne suis pas vraiment sur d'y trouver une réponse à mon problème.

    Merci à qui voudra bien m'aider !

    Hoeg
  • Bonjour,

    sans trop regarder en détail votre expression, je pencherais plutôt pour l'utilisation d'algortihmes basés sur les chaînes de Markov. Faites une recherche sur l'échantillonneur de Gibbs ou l'algorithme de Métropolis pour une recherche en français, sinon en anglais : MCMC (Markov Chains Monte Carlo).

    Amicalement,
  • Bonjour,

    merci pour votre réponse, je vais regarder ca. Mais l'algorithme de Metropolis est celui qu'on appelle egalement recuit simule il me semble, or ce n'est pas tout a fait pareil (enfin je crois)...mais peut etre trouverai-je une idée avec.
    Merci !
  • Bonjour,

    il me semble avoir répondu beaucoup trop vite, sans avoir lu votre post en fait ...
    Pourriez-vous indiquer de manière exacte ce que vous voulez simuler ? Merci

    Amicalement,
  • J'ai vaguement bossé sur les algorithmes génétiques (assez pour voir que le paradigme :algorithmes génétiques binaires; que le paradigme converge, mais pas vers la meilleure solution !). L'intervention d'une probabilité me surprend : Est-ce un algorithme génétique probabiliste ?
  • Re,

    en fait, il s'agit d'une meta-heuristique assez recente (milieu des années 90) qui simule le comportement des fourmis. Les fourmis ont naturellement tendance a suivre un chemin qui contient un fort taux de phéromone (substance chimique que les fourmis déposent elles-meme le ong de leur parcours et qui leur permet en quelque sorte de communiquer).

    Donc on place des fourmis sur un probleme du voyageur de commerce et on les fait "tourner" sur le circuit ou chaque fourmis dépose des phéromones. Une fourmi aura tendance a aller vers la ville dont le trajet contient le plus de phéromones...mais pour augmenter l'efficacité de l'algorithme, il se peut qu'une fourmi prenne une destination autre que celle contenant le plus de phéromones (et donc qui a été préférée par ses prédécesseuses). C'est ici qu'intervient la loi de probabilité : (j'avais fait une faute de frappe donc je la remets)

    $$p_k(r,s)=\left\{ \begin{tabular}{l l} $\frac{[\tau(r,s)].[\eta(r,s)]^\beta}{\sum_{u\not\in M_k}[\tau(r,u)].[\eta(r,u)]^\beta}$ & si $s\not\in M_k$ \\ & \\ $0$ & sinon \end{tabular}\right.$$

    On biaise l'exploration en choisissant une loi de probabilité qui fera qu'une fourmi aura tendance a preferer une ville proche avec un fort taux de phéromones.

    Dans la loi, $k$ représente l'indice d'une fourmi, $r$ la ville dans laquelle la fourmi se trouve et $s$ une direction possible (i.e. une ville dans laquelle la fourmi ne s'est pas rendue donc qui n'est pas dans $M_k$ "mémoire" de la fourmi).
    $\tau(r,u)$ est la quantité de phéromones déposées le long du trajet de la ville $r$ vers la ville $u$
    $\eta(r,u)$ est la distance séparant la ville $r$ et la ville $u$
    et enfin, $\beta$ est un paramètre réel.

    Voila pour la présentation (je joins une traduction partielle de l'article original pour ceux que ca interesserait). Mais apres un peu de repos, je suis en train de me dire que la simulation est simple et qu'il suffit de calculer chaque probabilité et d'associer un domaine de [0;1] puis de générer un pseudo aléatoire dans [0;1]....enfin une simulation classique de loi discrete quelconque il me semble. A toujours vouloir chercher des choses compliquées...

    Hoeg
  • Bon j'ai fait un peu n'importe quoi, désolé.

    Gérard, auriez-vous par hasard aussi étudié l'algorithme de Lin Kernighan parce que j'ai trouvé relativement peu de documentation claire (une description en pseudo langage de la methode serait la bienvenue mais je n'en ai trouvé qu'une qui me pose des petits soucis...) la dessus et ca m'aurait intéressé.

    En tout cas, merci a vous deux.




    Re,

    en fait, il s'agit d'une meta-heuristique assez recente (milieu des années 90) qui simule le comportement des fourmis. Les fourmis ont naturellement tendance a suivre un chemin qui contient un fort taux de phéromone (substance chimique que les fourmis déposent elles-meme le ong de leur parcours et qui leur permet en quelque sorte de communiquer).

    Donc on place des fourmis sur un probleme du voyageur de commerce et on les fait "tourner" sur le circuit ou chaque fourmis dépose des phéromones. Une fourmi aura tendance a aller vers la ville dont le trajet contient le plus de phéromones...mais pour augmenter l'efficacité de l'algorithme, il se peut qu'une fourmi prenne une destination autre que celle contenant le plus de phéromones (et donc qui a été préférée par ses prédécesseuses). C'est ici qu'intervient la loi de probabilité : (j'avais fait une faute de frappe donc je la remets)

    $$p_k(r,s)=\left\{ \begin{tabular}{l l} $\frac{[\tau(r,s)].[\eta(r,s)]^\beta}{\sum_{u\not\in M_k}[\tau(r,u)].[\eta(r,u)]^\beta}$ & si $s\not\in M_k$ \\ & \\ $0$ & sinon \end{tabular}\right.$$

    On biaise l'exploration en choisissant une loi de probabilité qui fera qu'une fourmi aura tendance a preferer une ville proche avec un fort taux de phéromones.

    Dans la loi, $k$ représente l'indice d'une fourmi, $r$ la ville dans laquelle la fourmi se trouve et $s$ une direction possible (i.e. une ville dans laquelle la fourmi ne s'est pas rendue donc qui n'est pas dans $M_k$ "mémoire" de la fourmi).
    $\tau(r,u)$ est la quantité de phéromones déposées le long du trajet de la ville $r$ vers la ville $u$
    $\eta(r,u)$ est la distance séparant la ville $r$ et la ville $u$
    et enfin, $\beta$ est un paramètre réel.

    Voila pour la présentation (je joins une traduction partielle de l'article original pour ceux que ca interesserait). Mais apres un peu de repos, je suis en train de me dire que la simulation est simple et qu'il suffit de calculer chaque probabilité et d'associer un domaine de [0;1] puis de générer un pseudo aléatoire dans [0;1]....enfin une simulation classique de loi discrete quelconque il me semble. A toujours vouloir chercher des choses compliquées...

    Hoeg
  • Effectivement, la situation est par nature discrète. Merci pour l'article, je ne connaissais pas cette méthode.Ni l'algorithme de Lin Kernighan , à moins qu'il ait un autre nom.

    A propos de la méthode : Il doit y avoir un problème à régler (au moins au début) : Il n'y a aucune raison pour que les chemins soient marqués (de phéromones), donc il faut ajouter à la loi de S (cf article) un choix au hasard. Ou bien marquer au départ les chemins. De même, le choix de s nécessite un choix au hasard pour les chemins marqués au même maximum (Le fait de choisir par un ordre d'énumération introduit un biais).

    Bon travail !
  • Vous avez entierement raison, il faut des le depart intialiser les taux de pheromones de chaque chemin avec une certaine valeur (on a choisi le parametre $\tau$). Je pense pas que cela est un réel impact sur le déroulement de la methode, du moment que le taux est le meme sur chaque chemin...et puis peut etre y a-t-il naturellement dans l'air certaines substances chimiques comparables aux pheromones des fourmis !

    Par contre il est vrai que rien n'est stipulé dans le cas ou on a le choix entre deux villes à une meme distance. J'y avais reflechi pour la methode du plus proche voisin car cela me paraissait vraiment problematique de choisir selon l'indexation. Par contre ici je dois avouer que j'ai n'ai pas repensé au probleme pour les fourmis...

    Ce qui m'etonne dans l'execution de l'algorithme, c'est le "chaos" de la solution renvoyee au fil des tours. Il me semble que dans les algos de type génétique, la solution s'améliore visiblement au fil des tours. Or ici on a souvent une progression puis une valeur tres médiocre et ainsi de suite. Je n'ai pourtant pas l'impression que mon implémentation soit differente de la présentation de la methode.

    Si par ailleurs ca interesse quelqu'un , je peux mettre mes sources C.

    Et pour Lin-Kernighan je ne crois pas qu'elle ait un autre nom. C'est une méthode entièrement déterministe qui est en fait un $k$-opt ou on détermine $k$ dans l'algorithme ! C'est une méthode très efficace decrite par (evidemment) Lin et Kernighan et qui est basee sur leur algoritme de bi-partition de graphe. Il me semble qu'elle donne "a $95\%$ de chances" la meilleure solution !!

    L'article complet est disponible sur la page de M. Kernighan : \lien{http://cm.bell-labs.com/cm/cs/who/bwk/tsp/index.html}

    Voila !
    Encore merci !

    Hoeg
  • Votre remarque me fait penser à ce qui se passe dans les algorithmes génétiques binaires. Là, la solution est de conserver les meilleures solutions (mélangées à d'autres). La méthode des fourmis semble ne pas conserver les meilleures solutions, mais, comme dans le recuit simulé, la diminution momentanée n'est elle pas le moyen de passer les maximas locaux pour trouver d'autres maximas ?
Connectez-vous ou Inscrivez-vous pour répondre.