De la Théorie à la Pratique
Pour mettre en oeuvre la théorie que vous venez d’apprendre, jetons un œil à un problème simple:
Etant donnés les nombres de 0 à 9 et les opérateurs numériques +, -, * et /, trouver une séquence qui représentera une valeur cible. Les opérateurs seront insérés en séquence, et ce de gauche à droite.
Donc, partant du nombre 23, la séquence 6+5*4/2+1 peut être une solution possible.
Si 75.5 est le nombre à rechercher, alors 5/2+9*7-5 est une solution viable.
S’il vous plait avant de continuer, soyez certains de comprendre le problème. Je sais que c’est tiré par les cheveux mais j’ai pris cet exemple pour sa simplicité.
Tout d’abord, nous devons encoder la solution en tant que chaine de bits…un chromosome. Comment fait-on cela ? Et bien, on commence par représenter tous les différents signes disponibles pour trouver la solution : de 0 à 9 et +, -, * et /.
Ce qui représentera un gène. Chaque chromosome sera fait à partir de plusieurs gènes.
Quatre bits sont nécessaires pour représenter tous les signes :
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
+: 1010
-: 1011
*: 1100
/: 1101
La suite ci-dessus montre tous les gènes nécessaires pour résoudre le problème de tout à l’heure. Les gènes 1110 & 1111 ne seront pas utilisés et l’algorithme les ignorera s’il les rencontre.
Donc maintenant vous pouvez voir que la solution précédente pour la valeur 23, ' 6+5*4/2+1' peut être représentée par neufs gènes comme :
0110 1010 0101 1100 0100 1101 0010 1010 0001
6 + 5 * 4 / 2 + 1
Ces gènes sont assemblés pour former le chromosome:
011010100101110001001101001010100001
Quelques mots sur le décodage
Etant donné que l’algorithme fait des choix aléatoires, il arrive souvent que l’on se retrouve avec des chaînes de bits de ce type :
0010001010101110101101110010
et en les décodant on trouve :
0010 0010 1010 1110 1011 0111 0010
2 2 + n/a - 7 2
Ce qui ne représente rien dans le cas de notre problème ! Par conséquent, lors du décodage l’algorithme ignorera chaque gène non conforme à la forme attendue, comme Nombre->opérande->nombre->opérande, et ainsi de suite.
En définissant cette règle, l’exemple précédent devient :
2 + 7
Cette partie peut être la plus difficile dans la mise en place de l’algorithme. Cela dépend de la nature du problème à résoudre, mais généralement on donne la plus grande valeur d’aptitude au chromosome qui tend à résoudre le problème.
Par rapport au simple projet que je décrit ici, une valeur d’aptitude peut être assignée qui sera inversement parallèle à la différence entre la solution et la valeur du chromosome décodé.
En continuant sur l’exemple du projet précèdent avec 42 comme valeur recherchée, le chromosome résultant serait :
011010100101110001001101001010100001
avec une aptitude de 1/(42-23) ou 1/19.
Il peut arriver qu’une solution débouche sur une division par zéro, comme avec1/(42-42).Néanmoins, ce n’est pas un problème, puisque nous avons trouvé ce que l’on cherchait…..une solution ! . Par conséquent, on peut tester ce résultat car l’algorithme s’arrêtera en fonction.
Tout d’abord veuillez relire ce tutorial
Si maintenant vous pensez qu’avez suffisamment compris comment l’on résout ce problème, je vous recommanderai d’essayer de coder l’algorithme génétique vous-même. Il n’y a pas de meilleure méthode d’apprentissage. Mais si toutefois, vous n’y parvenez pas, j’ai préparé un source simple que vous pouvez trouver ici.
Essayez de jouer avec le taux de mutation, de croisement, la taille du chromosome, etc.. .afin de comprendre l’influence de chacun de ces paramètres sur l’algorithme.
Le code doit être suffisamment documenté pour vous permettre de comprendre ce qu’il se passe. Dans le cas contraire, faites-le moi savoir par email et je tenterais d’améliorer les commentaires
Note : le code à télécharger analysera un chromosome binaire avec les valeurs évoquées précédemment et tentera de trouver une solution qui utilisera tous les symboles valides qu’il aura rencontré. Par conséquent, si l’on cherche à trouver
42 , + 6 * 7 / 2 ne donnera pas un résultat valide même si les quatre premiers symboles ("+ 6 * 7") représentent une solution viable.
(Le code Delphi soumis par Asbjørn est ICI ainsi que la version Java de Tim Roberts téléchargeable ICI )
Quelques mots avant de conclure
J’espère que ce tutorial vous a aidé à avoir les bases des algorithmes génétiques.
Veuillez noter que seules quelques bases ont été abordées ici. Si les algorithmes génétiques vous ont intéressés, alors il y encore pas mal de connaissances à explorer. Par exemple, il existe d’autres techniques de sélection, de croisement et d’autres opérateurs de mutation à essayer et encore plein de trucs ésotériques comme le partage d’aptitude (fitness sharing) et des espèces avec lesquelles s’amuser. Toutes ces techniques, ou même certaines d’entre-elles, amélioreront considérablement la performance de vos algorithmes génétiques.
Un truc à essayer
Si vous avez trouvé comment coder l’algorithme génétique du tutorial par vous-même, essayez donc un problème plus difficile :
Étant donné une aire remplie de disques ne se chevauchant pas et qui sont dispersés le long de sa surface, comme indiqué sur la capture 1,
Capture 1
Utilisez les algorithmes génétiques pour trouver un disque ayant le plus grand rayon et qui peut se placer parmis les autres disques sans les chevaucher, voir capture 2
Capture 2
Comme vous l’avez certainement déjà compris, j’ai déjà écrit le code qui résout ce problème, donc si vous êtes coincé, vous le trouverez ICI (mais vous pouvez tenter de le trouver vous-mêmes, n’est ce pas ;o) )
Pour ceux qui n’ont pas de compilateur, voici les exécutables.