[VBA-E] Tirage au sort avec probabilité

**clarisse** · 11/05/2006, 10h52

Tout d'abord, bonjour à tous, je suis nouvelle sur ce forum.

Je travaille actuellement sur un algorithme génétique, et j'ai le problème suivant :

j'ai les deux colonnes suivantes :
- dans la première, une liste de nombre
- dans la deuxième, des probabilités associés à chaque nombre.

J'aimerai générer dans VBA un tirage au sort de nombre de la première colonne, en fonction de leur probabilité associé.

Ou pour ceux qui connaissent les algorithmes génétiques, j'ai envisagé cela pour la selection des individus, peut-être avez vous une meilleure idée...

Merci.

**Catbull** · 11/05/2006, 11h11

Questions :

* la taille de ta population initiale est fixe? Car si tu te bases sur des probabilités pour la générer, sa taille ne sera pas forcément fixe.

* A quoi correspondent les nombres de la première colonne?

Ou pour ceux qui connaissent les algorithmes génétiques, j'ai envisagé cela pour la selection des individus, peut-être avez vous une meilleure idée...

Pour trouver une autre solution, tu devrais nous préciser à quoi correspondent tes individus.

**clarisse** · 11/05/2006, 11h21

la première colonne correspond a la référence des individus.
En fait, après avoir calculé la "fitness" de chaque individus, je leur ai associer des probabilités pour se ramener à une "fitness" comprise entre 0 et 1.

(Sinon, la taille de la population initiale est fixe, les probabilités ne sont pas utilisés pour cela. L'utilisateur pourra fixer cette taille lui meme...)

Ensuite, vient l'étape de la sélection pour la reproduction, je voudrai donc que les individus aient d'autant plus de chances d'être sélectionnés que leur fitness (donc, leur probabilité) est importante.

c'est pour cela que je voudrai générer le tirage aléatoire des individus à sélectionner pour la reproduction, mais ce tirage doit tenir compte de la probabilité...

Mon algorithme à pour but de réaliser des plans de découpe de pièces rectangulaires dans des panneaux, sastisfaisant un carnet de commande.
Un individu est donc constitué de n plans de débit "optimaux", réalisés dans des quantités à spécifier (j'ai utiliser le solveur pour ce calcul..) pour répondre au carnet de commande.

**HPJ** · 11/05/2006, 11h27

Un petit exemple à adapter à ton problème:

i: indice de l'élément du tableau
v(i): valeur de l'élément d'indice i
p(i): probabilité de tirer v(i)

Il faut que la somme des p(i) = 1

i v(i) p(i) cumul des proba
1 2 0,3 0,3
2 4 0,4 0,7
3 7 0,1 0,8
4 1 0,2 1

Puis tu tires un nombre n avec 0 <= n < 1
si 0 <= n < 0,3 -> i = 1
si 0,3 <= n < 0,7 -> i = 2
si 0,7 <= n < 0,8 -> i = 3
si 0,8 <= n < 1 -> i = 4

Je pense que c'est un solution qui fonctionne...

**Catbull** · 11/05/2006, 11h35

Ok, je comprends mieux, je pensais que tu étais dans une logique d'initialisation de population et non de croisement.

Tu souhaites donc croiser plus fréquement les meilleurs individus?

Le nombre de croisement (ou reproduction?) est-il fixe à chaque génération?

**clarisse** · 11/05/2006, 11h37

Oui effectivement je n'y avais pas pensé, ça me parait utilisable dans mon cas.
En plus, c'est simple à mettre en oeuvre

La somme des mes proba est deja égale à 1, c'est pour cela que j'étais passée par les probas...

et merci à tous les deux !
bonne journée.

**chmod777** · 11/05/2006, 12h28

Envoyé par HPJ

Un petit exemple à adapter à ton problème:

i: indice de l'élément du tableau
v(i): valeur de l'élément d'indice i
p(i): probabilité de tirer v(i)

Il faut que la somme des p(i) = 1

i v(i) p(i) cumul des proba
1 2 0,3 0,3
2 4 0,4 0,7
3 7 0,1 0,8
4 1 0,2 1

Puis tu tires un nombre n avec 0 <= n < 1
si 0 <= n < 0,3 -> i = 1
si 0,3 <= n < 0,7 -> i = 2
si 0,7 <= n < 0,8 -> i = 3
si 0,8 <= n < 1 -> i = 4

Je pense que c'est un solution qui fonctionne...

c est vraiment bien pense

**clarisse** · 11/05/2006, 12h49

pour répondre à Catbull, je pensais que l'utilisateur pourrai fixer lui même le taux de croisement avant l'exécution de l'algorithme, il serai donc fixe à chaque génération.

Il me semble que je n'ai pas vu d'algo génétiques ou les taux de croisements sont variables, mais tu as peut etre raison je devrais me documenter la dessus.
Si tu as des infos...