Je suis en train de coder un algo génétique et je voudrais savoir quel est le meilleur algo (le plus rapide) pour la sélection proportionelle aléatoire d'un individu dans une population. En gros, chaque individu a une proba d'être sélectionné et je souhaite que l'individu est d'autant plus de chances d'être sélectionné que sa proba est grande.
ex : individu 1 -> 40%, individu 2 -> 10% et individu 3 -> 50%
je veux que ma fonction de sélection me donne le plus souvent l'individu 3 ensuite le 1 et enfin le 2.
 
Comme je vais coder l'algo en php, est-ce qu'il existe une implémentation spécifique à php (utilisant au mieux ses fonctions de base)?
 
perso, je suis parti sur la génération d'un nb et la somme cumulative jusqu'à ce que j'atteigne le nb...

Faire un tirage aleatoire d'un individu dont la proba est I pour I allant de 100 à 1  

c'est ce que je ferais aussi... Si tu as besoin de faire ça plusieurs fois de suite, tu peux précalculer les sommes de pourcentage (par exemple au moment où tu renormalises les pourcentages de tes individus pour que la somme fasse bien 100%)

algorithme de la roulette biaisée (roulette wheel selection) ou encore connue sous la roue de la fortune (faire un joker ou bien tomber sur une lettre n'est pas de même probabilité hein ).

 
la roue de la fortune, c'est justement ce que je veux implémenter. Ma question porte justement sur cette implémentation (quelle est la meilleure manière en php). Pour l'instant, j'en suis resté aux sommes des probas d'un tableau.

 
Ta solution de partir sur les proba cumulées me paraît bonne. (c'est ce que j'utilisais pour me algo de sélection dans les algo génétiques)

ok, donc, a priori, y'a pas mieux...

pas à ma connaissance...et je vois difficilement comment faire plus efficace.

ça dépends. si en PHP, l'allocation mémoire est rapide, et que tu n'as pas de nombre d'élément trop élevé, tu peux stocker dans un tableau tes "personnes" autant de fois que leur pourcentage (40% = 40 lignes)
Ensuite, la recherche dans le tableau peut se faire sans faire de cumul. C'est d'autant avantageux si tu n'as pas un nombre trop élevé d'éléments.
 
evidement, si t'as une popupation e 1000000 personnes, et que chacune à une proba de 80%, faut oublier cette solution

j'ai essayé en créant un tableau via range(1..proba_individu * 100) puis je tire un nombre au hasard compris entre 0 et 99 mais c'est très long...donc pas viable.

allouer un tableau c'est moins bien que de faire des "+" (proba cumulées) et un test (si le nombre aléatoire a été dépassé)

ben ça dépend si le tirage doit se faire plusieurs fois de suite sur une même population ou non. accéder à un tableau via son index sans devoir le lire, ce sera toujours plus rapide que lire ligne par ligne le tableau et faire une batterie de cumuls/tests dans une boucle.
 
ensuite, l'initialisation d'un tel tableau est en effet plus lente, donc le gain n'est visible que si on faire des tirages successifs.

y'a pas photo côté perfs : pour une population de 100 individus et 20 générations, la méthode des cumuls met 0.013s alors qu'avec le tableau, > 4s

4 secondes ??? là y'a clairement un souci avec PHP, je vois pas comment c'est possible que ce soit aussi lent...
tu peux poster ton script de test ???

si tu dois faire plusieurs tirages successifs, tu peux précalculer tes sommes partielles une fois pour toute et chaque tirage s'effectue donc uniquement avec O(n) comparaisons (si n est le nombre d'individus).
 
Donc même dans ce cas là ça reste sans doute beaucoup plus efficace que d'allouer un tableau énorme.

 
le pb, c'est qu'avec des probas faibles, j'étais obligé de faire un tableau de 1000 éléments pour chaque tirage (le tableau changeant à chaque tirage)... Donc allouer un tableau de 1000 éléments (via array_fill()) pour chacun des 100 individus 20 fois, ça prend du temps...

oui, c'est sûr. comme je dis, la solution que j'ai proposé n'est efficace que si tu fais des tirages successifs sur le même tableau. la création d'un tel tableau est en effet très lente.
 
c'est comme si tu veux aller d'un point A à un point B en voiture.
 
tu peux prendre un hammer, et te traîner à 30km/h dans les rocailles, ou construire une route et rouler ensuite à 180km/h en porsche... si tu dois reconstruire la route à chaque trajet, c'est plus lent, mais si tu reprend toujours le même chemin, il est rapidement plus rentable d'un point de vue perfs de contruire la route

 
 
CQFD !    
 
 

j'aime bien les analogies à deux balles, ça se voit tant que ça ?