Discussion :

[Revaroa]

Bonjour,

J'ai programmer un algorithme génétique en java, afin de minimiser la fonction fitness f suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
<img src="http://miscws.developpez.com/latex2pngcache.php?latex=U-DlStOo0FSwVYhJSk3PzKsuy00sKcqsqFWIKUtNrg6tVdBViCkuzY2vzrQ1rI2rzqtVqIjPVIgpycxNLYaoCQOqTc1LQejk5QIA" alt="Formule mathématique" title="Formule mathématique" />

Voici mon algo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Population initiale -> N individus (par exemple N=1000)
Evaluation selon fonction fitness
Selection par rang:
    Tri croissant des individus selon leur fitness.
    On Garde les M meilleurs (i.e les premiers de la liste puisque on veut celui qui minimise f)
Croisement:
    On tire au hasard un paire d'individus dans les M meilleurs
    On effectue le croisement, deux nouveaux individus seront créer
    On répète l'opération de croisement selon le taux de croisement (ex: 60% alors sur mille on aura 600 individus issus du croisement)
Mutation:
    On choisi au hasard des individus à muter dans M meilleurs
    On fait les mutations

Génération suivante(taille N) = M meilleurs + individus croiser + mutants
On refait toutes ces opérations jusqu'à trouver l'individu avec un fitness proche de 0

Je voudrais juste votre avis en ce qui concerne les croisements et mutations.

Merci.

[Gophys]

Bonjour,

Tu as très bien décrit les principes de bases d'un algorithme génétique. Maintenant pour les paramètres a faire varier tu as l'embarras du choix:

- le nombre de nouveaux individus a chaque nouvelle génération
- le nombre d'individus gardes a chaque génération
- la probabilité d'utiliser chaque individu (plus son score est proche de ton optimal, plus tu as de chance de l'utiliser pour se reproduire pour la génération future)
- la possibilité ou non qu'un individu puisse se reproduire plusieurs fois (tirage avec ou sans remise)
- la taille du crossing-over (combien de valeurs font être échangées entre les deux individus, ces valeurs doivent elles êtres contiguës ou non?)
- la fréquence de tes mutations (je te conseille de faire tes mutations sur tes enfants et pas sur tes individus de l'ancienne génération, ca te permet de garder tes parents intacts dans le pool génétique a la génération suivante)
- la condition d'arrêt de ton algorithme (soit X générations, soit Y générations pendant lesquelles l'individu le plus optimal est le même)

Je te conseille les paramètres suivants pour un premier essai, a faire varier par la suite en fonction de ton problème:

- X individus a la première génération
- X/2 individus gardes a chaque génération
- X nouveaux individus a la seconde génération (soit un total de 3X/2 individus a partir de la seconde génération)
- probabilité égale d'utiliser chaque individu parent (avec remise puisque tu vas créer plus de nouveaux individus que de parents)
- taille du crossing over tirée sur une loi uniforme allant de 0 a 1.5 (si la taille est supérieure a 1 alors tu crées des individus identiques aux parents)
- nombre de mutations par nouvel individu tirée sur une loi de poisson d'espérance 1% de ton nombre de paramètres (minimum 1 si tu as moins de 1 paramètre)
- utiliser a la fois X générations (même nombre que d'individus pour commencer) et Y générations avec le même individu optimal (une 20aine de générations suffisent en général)


Ensuite a toi de jouer avec les paramètres et d'essayer de bidouiller a ton aise pour essayer d'obtenir quelque chose de plus fin.

[theodorandaipieds]

taille du crossing over tirée sur une loi uniforme allant de 0 a 1.5 (si la taille est supérieure a 1 alors tu crées des individus

Comment générer les nombres aléatoires pour tirer selon une loi uniforme ?
Tu peux aussi générer une meta variante de l algorithme (qui naugmente pas l ordre de l algo) : créer un "échantillonnage" des résultats pour en rétirer le meilleur. Il te suffit pour ça de trouver le moyen de faire varier les racines des générateurs de nombres aléatoires.
Tu fait donc varier tes sources de nombres pour la loi uniforme.

Qu en dis-tu ?

[Gophys]

Pour ce qui est du générateur de nombre aléatoire, je le laisse a l'appréciation de la personne qui va l'implémenter et du langage qu'elle va utiliser. Tant que tu gardes ta graine aléatoire pour être sur de la reproductibilité de tes résultats un simple générateur pseudo-aleatoire fournit avec les bibliothèques standard suffit amplement pour le cas d'un algorithme comme celui-ci.

Quand a ta ta demande sur l'échantillonnage, comme tout algorithme stochastique il est nécessaire de relancer le même algorithme plusieurs fois avec des graines aléatoires différents, afin de ne pas rester coince dans un optimal local qui empêcherai de trouver un optimal général. Ce nombre dépends fortement de la complexité de la fonction a optimiser, en général j'effectue un échantillonnage de l'ordre de 50, mais on peut monter a plusieurs centaines de run de algorithme si jamais la fonction est plus complexe.