Algorithme génétique : représentation des différents éléments

Bonjour,

Dans le cadre d'un projet d'étude, je développe une ia pour un jeux type wargame (figurine).

J'ai développé une ia basée sur la recherche de la meilleure possibilité selon des poids dans un arbre à n niveaux.

Après cette étape, je dois faire apprendre mon ia afin de l'optimiser. J'utilise ainsi les algorithmes génétiques.
N'ayant pas de connaissance précises en algorithme génétique, je me suis renseigné sur le principe sur le web.
Cependant, j'ai du mal à me représenter concrètement les différents aspects de l'algo : les gènes, les chromosomes, les individus, la population.

Ce n'est pas vraiment un jeu au tour par tour, mais je pense que pour simplifier l'explication on peu le résumé comme cela.
En réalité c'est un jeu basé sur "l'initiative" : je joueur possède l'initiative tant qu'il ne rate pas une action. Lorsqu'il rate une action, l'initiative va à l'autre joueur et ainsi de suite (si quelqu'un connait ce type de jeu :)).

J'ai 3 actions :
- bouger : d'un élément de terrain à l'autre, selon ce qu'on voit dans notre champ de vision
- tirer : sur une cible qu'on voit évidemment
- rallier : si une unité est "blessée"

Ainsi j'aimerai avoir votre avis sur ce qu'est le gène, le chromosome, l'individu et la population dans le déroulement du jeu.
Selon moi l'individu correspond à une partie, et la population à un ensemble de parties.
Cependant, pour ce qui est des gènes et des chromosomes, j'avoue ne pas réussir à savoir à quoi ils correspondent par rapport à mes actions.

Merci de votre aide :)

Bonjour,
je pense qu'il faudrait tout d'abord déterminer un ensemble de paramètres (correspondant aux gènes) qui déterminerait le comportement d'un joueur. Un individu correspondrait alors à un comportement de joueur possible, et la population à un ensemble de comportement possible.
Cela dépend beaucoup des règles du jeu, mais les paramètres pourraient être :
- probabilité de tirer selon la distance d'un ennemi
- nombre d'alliés minimum à proximité pour attaquer une cible...

Exactement, les gènes vont correspondre à ces comportements, mais ensuite il faudra créer une fonction de mélange acceptable.

Ok je comprends mieux. Je ne l'avais pas vu comme cela.

En effet, dans mon algo de décision, j'utilise des "poids" sur différents aspects (vue de la cible, présence alliée, rapprochement de la cible, etc).

Pour créer la population de départ, je vais donc me faire plusieurs individus avec des poids qui différent.
Par contre, étant donné que je dois avoir une dizaine de poids, cela va me faire beaucoup de monde ! :?

Quel est le meilleur compromis pour le nombre de génération (pour commencer j'entends) ? Parce qu'il va falloir que je fasse jouer mes individus entre eux, et ca va prendre du temps ! lol
Ainsi, j'aimerai bien tester par exemple sur 1 journée (24h) dans un premier temps et ensuite, en fonction des résultats obtenus, essayer de faire tourner plus longtemps (1 semaine pourquoi pas).
Mais peut-être que ce n'est pas comme cela qu'il faille raisonner dans l'apprentissage. :?

Merci en tout cas pour ces informations ! ;)

Il faut y aller à tâton, il n'y a pas de règle fixe, le plus important est que ta fonction de mélange soit efficace et génère des enfants corrects et valides, naturellement ta fonction de calcul du coût doit aussi l'être.

Si les paramètres sont trop nombreux pour pouvoir commencer avec un échantillon suffisament diversifié, je pense qu'on peut compenser par une probabilité de mutation plus grande, mais comme le dit Miles, il faut y aller à taton.
Selon les cas, la convergence du processus vers une "bonne" solution peut nécéssiter de nombreuses itérations (cela dépend du nombre de paramètres, de l'efficacité de la sélection et du croisement...). Attention donc si tu laisses une journée entière pour une itération, tu risques de ne pas t'en sortir...

Bonjour a tous ;)

Vous n'avez pas parlez des techniques de sélection,
il me semble.

Il y a plusieurs type de sélection :
- Les 'X' Meilleurs sont pris pour la prochaine génération.
(= "Technique de l'élitisme" ou X est un nombre)
- Ceux qui ont un meilleur fitness (= résultat recherché), ont plus de chances d'être pris pour la prochaine génération, sans pour autant être sûr d'y être (= Technique de la loterie).

Attention cependant au choix de ces techniques.

L'élitisme seul pose le problème de se retrouvé dans un maximum LOCAL et non GLOBAL des possibilités.
(il faut voir la fonction de fitness appliquées à tes données (ici des commandes, des actions possibles par tes persos), comme une fonction ayant la possibilité de forme sinusoïdale.)
La loterie peut se rapprocher d'un max locale et en trouvé un autre max locale meilleur que le premier au bout d'un certain temps, cependant il faudra plus de temps pour trouver le max locale de chaque intervalle de faible voisinnage.

La solution vient en générale en prenant un peu des deux techniques.

Sur une population de 50 individus, je prends les 10 meilleurs de la génration actuelle (élitisme) + 10 au hazard, avec ceux qui ont plus de fitness ont plus de chances d'être repris (loterie) + 30 qui seront des mutations/copies des 20 premiers. (ceci n'est qu'un exemple biensûr) :mouarf:

il peut aussi etre interressant de reflechir avant pour borner au maximum tes parametres... cela t'evitera de traiter des cas absurdes..

ATTENTION : comme dans la vraie vie, selectionner mecaniquement les meilleurs individus favorise l'appauvirssement genetique et mene a des individus dégénrés (ie : qui font stagner l'evolution).

le mieux est d'utiliser le principe de la roulette truqué : chaque individu a un score d'autant meilleur qu'il obtient de bons resultats, et a ensuite une proba d'etre selectionné pour le "mariage" d'autant plus grande qu'il a un bon score...

attention quand meme, lalgo genetique peut ne pas donner de si bons resultats.. ca marche bien quand tu as un critere objectif et absolu pour juger de la qualité d'un individu. si tu ne les juges que les uns par rapport aux autres, tu peux te retrouver avec que des individus "debiles", mais certains moins debiles que d'autres...

Je suis d'accord, il est important de savoir que l'algo génétique permet de se rapprocher d'une solution.
Atteindre la solution est autre chose.
Comme l'algorithme génétique utilise le hazard, il faut savoir
qu'il faut un certain temps et non un temps certain pour avoir une solution approchée.

L'éllitisme quand a lui est bien pour trouver le meilleur des 'débiles' :mouarf: (cela dépend aussi de ta fonction de sélection), la loterie te permet de trouver des 'débiles' plus loin...

Je serai un peu moins négatif tout de même, l'essentiel est de bien comprendre on problème afin de mieux cibler tes gènes, ce qui te donnera des solutions plus 'acceptables' et surtout cohérente (pas débiles). Pour cela tu doit avoir un problème assez fermé (donc limité à un nombre de solutions fini).

Deux exemples :
Tu cherches une fonction pour une série de données.
Tu dois trouver cos(x) et tu as mis des outils (puissance, mutiplication, addition, soustraction) qui te permettent de trouver des formules de la forme y = an*x^n + ... + a0*x^0 => toutes tes solutions seront approchées et fausses (ou 'débiles' selon)

Tu cherches à trouver toutes les solutions du morpion à partir d'une partie déjà commencée.
Tu as un nombre de parties assez limité (9!) et même moins car ici ce serait n! avec n < 9.

Cela dépend du problème et du nombre de possibilité qu'il aura pour s'auto-résoudre.