calcul des fitness dans un algorithme génétique
Bonjour à tous,
Je ne sais en fait si je suis sur le bon forum. Merci de me virer si je ne suis pas au bon endroit.
Voila: J'utilise depuis des années des algorithmes génétiques (soit que je code moi-même, soit à partir de libraries dispos en C/C++) pour trouver des solutions optimales dans des espaces d'état assez grands et surtout très stochastiques. Je m'occupe de comportement animal, et la fitness de chaque chromosome de l'algo est le fruit d'un calcul de simulation. C'est un peu comme l'exemple célèbre (et rigolo) de boxcar2d que l'on peut voir ici, pour ceux qui connaissent, avec la stochasticité en plus.
Ca fonctionne bien, je trouve les points optimaux sans trop de problème, au besoin en parallélisant mon code (car les temps de calculs sont rapidement prohibitifs).
Jusque là ok (so far, so good).
Je dois à présent résoudre un problème bien plus compliqué, où il y a compétition entre les individus (pour reprendre l'exemple de boxcar2d cité ci-dessus, ca serait comme si il y avait plus qu'une voiture, disons entre 2 et 5 qui font la course à chaque fois). Du coup, la fitness d'un chromosome dépend de la fitness des chromosomes des compétiteurs, toujours avec stochasticité. Je suis donc confronté au problème, à chaque génération de l'algo, de calculer la fitness de chaque chromosome. Je peux bien par exemple calculer la fitness de chaque chromosome en faisant des tournois. Par exemple, la fitness du chromosome i serait la moyenne de sa fitness en le mettant en compétition avec à chaque fois un autre chromosome, et en balayant tous les chromosomes de la population à la génération donnée sauf le ième. Si la population possède 100 chromosomes, ca serait donc la moyenne sur 99 tournois. Mais si la compétition peut se faire entre 2, 3, 4 où 5 individus, je vais me retrouver avec C(99,2)+C(99,3)+C(99,4)+C(99,5) situations à comparer, et la combinatoire est immense et il me faudrait des siècles de calcul (même sur une machine fortement parallélisée) pour chaque génération. Impossible donc.
Y a t-il parmi vous quelqu'un qui s'y connaisse bien en algo génétique et qui aurait vu des recherches de points optimaux avec cet outil dans une situation de compétition ? Ca m'étonnerait que je sois le seul être humain sur cette planète à devoir résoudre ce genre de problèmes (je pense que les militaires font des choses comme ça, par exemple).
Merci de toute aide sur ce point.
Cordialement,
Eric.
