Probabilité roulette de casino biaisée.

[gloups13]

Bonsoir tout le monde.
Dans le cadre d'un projet d'étude je suis confronté à un petit problème.
Voilà, j'ai un ensemble de chromosome. Il y a des chromosomes meilleur que d'autres.
Tous les chromosomes sont indépendant entre eux.
Je numérote chaque chromosome de telle sorte que le chromosome numéro 1 soit le meilleur chromosome.
Je veux tirer deux chromosomes , noter leur numéro puis les remettre dans l'ensemble et répéter cette opération.

Soit i<j et Pi, Pj la probabilité de le ième (respectivement le jème) chromosome soit sélectionné.
Je pose Pi<Pj: C'est a dire, la probabilité de tirer un chromosome bon est supérieure à la probabilité de tirer un chromosome mauvais.
Je connaît le nombre de chromosome dans mon ensemble et je connaît la valeur de tous les Pi.

Ma question est la suivante: Quelle est la probabilité de tirer le ième et le jème chromosome.
J'insiste sur un point, l'ordre ne m'intéresse pas. C'est comme si je tirais simultanément deux chromosomes.

Mon but final étant de coder tout ça sur ordinateur pour continuer mon projet.
Est ce que vous pouvez me donner une piste de départ.
J'ai essayé de modéliser les chromosomes par des boules numéroté .9a n'a rien donné. ça a l'air simple comme ça mais dès que je commence à le mettre en équation les problèmes arrivent.
Merci de votre temps.
-----

[gg0]

Bonjour.

L'ordre ne t'intéresse pas, mais comme tu connais des probabilités individuelles, il est plus simple de prendre pour univers C², où C est l'ensemble des chromosomes. L'univers est donc composé des n²-n couples (C_l,C_k) de deux chromosomes différents, et la probabilité de tirer (C_l,C_k) est (*).
Donc la probabilité d'avoir tiré justement les deux chromosomes Pi et Pj, sans ordre, est la probabilité de {(C_i,C_j);(C_j,C_i)} qui vaut


Cordialement.


(*) est la probabilité de tirer C_k, sachant qu'on a déjà tiré C_l auparavant.

[gloups13]

Bonjour,

Merci beaucoup pour votre réponse très claire. Vous avez l'air de maitriser très bien les probabilités.
J'aurai juste deux question:
Une question de dénombrement: Comment avez vous fait pour savoir que l'univers était composé de n²-n couples (Cl,Ck)?
Enfin, question que je me suis toujours posé, comment faites vous pour introduire une formule quand vous postez un message sur ce forum?
Encore une fois merci de votre réponse très claire.

[gg0]

Il y a n fois n couples (n possibilités pour le premier terme, n pour le deuxième), mais il faut enlever le n couples (Pi,Pi) puisqu'on tire des chromosomes différents.
Pour les formules, lire ce fil : http://forums.futura-sciences.com/ma...res-forum.html qui est épinglé au début du forum.

Cordialement.

[A voir en vidéo sur Futura]

[Dlzlogic]

Bonjour Gloups,
Vous avez classé vos chromosomes, je suis d'accord, mais ce classement dépend de votre perception de la qualité "bon ou mauvais". En fait, quelle que soit leur qualité ils sont différents et n'ont ni un précédent ni un suivant.
Si on a N chromosomes, chacun portant un numéro, ou un nom, ou relié à une image, ou a un bruit ou je ne sais quoi d'autre, au moment d'un tirage ils ont chacun exactement la même probabilité d'être tirés, c'est à dire 1/N. Le second, tiré simultanément a la même probabilité d'être tiré, c'est à dire 1/N. Donc la probabilité de deux chromosomes de N° donné est 1/N².
En fait, puisque le même chromosome ne peut pas être tiré 2 fois, la probabilité est 1/N(N-1).

D'autre part, si j'ai bien compris, les deux chromosomes tirés vont produire deux chromosomes fils, ayant chacun une partie des qualités des chromosomes père. J'ai cru comprendre que les fils remplaçaient les pères, mais je n'en suis pas sûr.
Pour ce type d'opération, je vous conseille vivement de vérifier les formules par des simulations. Des opérations simples présentent des écarts de quelques %, dès que ça devient un peu compliqué, c'est la seule vérification possible.

Il y a une bonne image pour se représenter cela : le tir sur cible. Que ce soit à l'arc, au pistolet ou au canon, les conclusions en matière de probabilité sont le mêmes.

[Dlzlogic]

Suite de mon message précédent.
Vos chromosomes ont un poids qui dépend de leur caractéristique "bon ou mauvais", qu'on peut aussi appeler "note".
Vous faites un tirage en appliquant une relation poids -> probabilité de sortie.
La probabilité de tirage du couple C1-C2 est certes intéressante, mais ce n'est pas cela, à mon avis, qui va vous donner le poids que vous devrez attribuer au résultat du tirage.
Les poids se calculent par moyenne pondérés, les probabilités dépendent essentiellement du théorème des probabilités totales.
Une solution serait peut-être d'établir une classe de notes.

[emmane]

Bonjour

En fait, puisque le même chromosome ne peut pas être tiré 2 fois, la probabilité est 1/N(N-1).

cette jolie formule ne fonctionne pas : il suffit de prendre uniquement un ensemble deux chromosomes N=2. La formule 1/N(N-1) donne une proba de 1/2, alors que la seule possibilité est de tirer les deux chromosomes.

En revanche, la formule de gg0 donne une proba de 1, tout à fait conforme à l'évidence, quand on a uniquement deux chromosomes, ils sont obligatoirement tirés au sort.

[gloups13]

Bonsoir tout le monde.
Tout d'abord, merci à gg0 pour son explication sur le dénombrement.

Ensuite, Dlzlogic vous n'avez pas compris ce que je voulais faire.
C'est à cause de moi car je n'ai pas dis ce que représentaient les chromosomes.

A un chromosome j'associe une structure (métallique dans mon cas) Ce chromosome comporte toute l'information de la structure qu'il représente(J'ai codé dans ce chromosome la masse de la structure, etc)
Certaines structures sont meilleures que d'autres( d'un point de vue physique) D'où les bons et mauvais chromosome.
Ensuite, je veux faire se reproduire les meilleurs individus entre eux pour former une génération supérieure à la précédente. Mais comme je prends un modèle qui se rapproche le plus de la nature, je laisse quand même une chance aux mauvais chromosome de se reproduire. Voila. J'espère que c'est plus clair.

IL me fallait la probabilité de sélectionner 2 chromosomes, gg0 a réglé mon problème rapidement.
Bonne soirée.

[gg0]

Gloups13,

tu fais des algorithmes génétiques avec de vrais chromosomes ?

[gloups13]

Non je n'ai pas de vrais chromosomes. Ce que j'appelle chromosome m'est en faite qu'une matrice ligne composée de 1 et de 0.

[gg0]

Mais c'est bien des algorithmes génétiques ?

J'avais vu, quand j'ai regardé ça de près, que le croisement simple (sans privilégier les meilleurs) ne convergeait pas vers la bonne solution quand il n'y en a qu'une. C'était il y a une vingtaine d'année, pour mes collègues chercheurs en optimisation.

Cordialement.

[gloups13]

Oui bien sur, c'est un algorithme génétique pour optimiser la masse d'un pont métallique.
Comme quoi, vous avez encore contribué à l'élaboration d'un algorithme génétique.

Oui, en effet je privilégie les meilleurs individus sans pour autant supprimer les plus mauvais.
Cordialement.

[gg0]

Ce qui correspond bien à ce que j'avais compris à l'époque. Mes collègues se sont orientés vers d'autres horizons (application des méthodes industrielles à la gestion hospitalière), je ne suis pas allé très loin.

Cordialement.

[gloups13]

L'algorithme génétique n'a pas donné satisfaction à vos collègues?
Moi c'est mon premier que je fais alors je ne sais pas trop si ça va bien marcher.
Cordialement.

[Dlzlogic]

Bonsoir gg0,
Jette un coup d'oeil ici : https://fr.wikipedia.org/wiki/Algori...A9n%C3%A9tique et tu comprendras pourquoi la probabilité d'avoir 2 chromosomes donnés n'offre aucun intérêt. La valeur résultant de l'association de deux chromosomes est un résultat lié à l'intérêt des chromosomes sélectionnés et non de leur probabilité d'être sélectionnés. D'autre part à chaque tirage, la probabilité d'être sélectionné pour un chromosome change, puisque la somme des probabilités est 1 et que 2 chromosomes ont changés (ou ont été rajoutés, c'est à préciser).
Bien sûr, on pourra rétorquer que la probabilité d'être sélectionné dépend de leur note. Il me semble que tout le problème de l'algorithme génétique se situe là. C'est le principe et l'intérêt de l'algorithme génétique : "plus un chromosome est bon, plus il a des chances d'être sélectionné". Par contre, la difficulté réside dans le fait d'attribuer à un chromosome la probabilité d'être sélectionné en fonction de sa qualité. A mon avis sûrement pas par une fonction simple de la probabilité d'être le fils de deux chromosomes qui ont été sélectionnés.
C'est un problème intéressant, on ne peut y arriver que si à chaque étape on reste positif.
Petit point technique, à chaque tirage la répartition des probabilités change, ce qui fait que la loi de probabilité change.

[gg0]

En fait, c'était une voie de recherche qui les intéressait parmi pas mal d'autres. Leur orientation était l'optimisation en gestion de production, puis, comme je l'ai dit, ils ont ciblé un thème nouveau, la gestion hospitalière (nombre de salles d'opération, d'anesthésistes, organisation des étuvages des matériels opératoires, même réorganisation des usages du bâtiment tout neuf de l'hôpital de la ville, rentabilité des services, modes d'utilisation d'un synchrotron, ...) qui permettait d'utiliser ces outils dans un cadre tout neuf.
J'ai eu vent de quelques cas où l'utilisation d'algorithmes génétiques fonctionne, sous des formes diverses, les suites de réels semblent plus souples, mais je n'ai plus d'info sur l'état de la recherche de ce domaine depuis 15 ans. Sauf quelques articles de revues généralistes (Science et vie, Pour la science).
Je te souhaite que ça marche bien !