IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Intelligence artificielle Discussion :

calcul des fitness dans un algorithme génétique


Sujet :

Intelligence artificielle

  1. #1
    Membre régulier
    Homme Profil pro
    chercheur
    Inscrit en
    Décembre 2012
    Messages
    195
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Décembre 2012
    Messages : 195
    Points : 84
    Points
    84
    Par défaut 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.

  2. #2
    Membre éclairé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    426
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Puy de Dôme (Auvergne)

    Informations forums :
    Inscription : Octobre 2008
    Messages : 426
    Points : 827
    Points
    827
    Par défaut
    Salut Eric,

    Le livre A field guide to genetic programming pourrait t'intéresser... (Tu peux charger le pdf gratuitement ou acheter la version papier)

    Il en a été question dans ce post, sur ce forum, l'an dernier. Tu en trouvera également une critique ici. Je trouve ce livre extrêmement passionnant. Le chapitre 10: Fast and Distributed Genetic Programm (et plus particulièrement la partie 10.1 Reducing Fitness Evaluations/Increasing their Effectiveness), t'intéressera probablement.

    Bonne lecture.

  3. #3
    Membre régulier
    Homme Profil pro
    chercheur
    Inscrit en
    Décembre 2012
    Messages
    195
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Décembre 2012
    Messages : 195
    Points : 84
    Points
    84
    Par défaut
    Citation Envoyé par bertry Voir le message
    Salut Eric,

    Le livre A field guide to genetic programming pourrait t'intéresser... (Tu peux charger le pdf gratuitement ou acheter la version papier)

    Il en a été question dans ce post, sur ce forum, l'an dernier. Tu en trouvera également une critique ici. Je trouve ce livre extrêmement passionnant. Le chapitre 10: Fast and Distributed Genetic Programm (et plus particulièrement la partie 10.1 Reducing Fitness Evaluations/Increasing their Effectiveness), t'intéressera probablement.

    Bonne lecture.
    Merci pour la référence. J'en ai d'autres du même type. J'ai regardé ça, et ai lu la partie 10.1. Aucune information dans ceci qui me permette de résoudre la problème que je pose ici, je le crains. J'ai déjà parallélisé mes codes, mais la dimensionnalité du problème que je dois résoudre à présent est trop élevée et ce problème doit être abordé différemment. Encore une fois, je ne souhaite pas "réinventé la roue". Je suis convaincu que les économistes (par exemple) sont confrontés à ce genre de problème de compétition, et je cherche donc une expertise que je n'ai pas.

    Merci en tout cas !

    D'autres idées ?

    Cordialement, Eric.

Discussions similaires

  1. l'utilisation des shémas dans l'algorithme génétique
    Par mayouta dans le forum Intelligence artificielle
    Réponses: 0
    Dernier message: 19/02/2009, 02h40
  2. Calcul des prédicats dans prolog
    Par nschoe dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 01/11/2008, 01h56
  3. Calculer des moyennes dans les requêtes
    Par said2n dans le forum Requêtes et SQL.
    Réponses: 7
    Dernier message: 02/07/2008, 14h12
  4. Calcul des unités dans un entier 32bits
    Par hack-77 dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 04/08/2006, 15h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo