Je viens de terminer un projet que je souhaitais réaliser depuis déjà un petit bout de temps : un algorithme génétique de reproduction d’images. J’ai réalisé ce projet en C pour une question de performance et pour continuer de m’entraîner sur ce langage.

Résultat

L’objectif de base du programme est de reproduire une image, en utilisant uniquement des carrés de tailles et de couleurs différentes en se servant d’un algorithme génétique.

Voici typiquement le rendu obtenu au bout de quelques minutes de calculs :

Et ici un exemple un peu plus évolué  :

Je remercie au passage Dettorer pour le prêt de son serveur, il aura fallu au total environ 2h de calcul pour générer les 30.000 générations nécessaires à la création de la Joconde.

Les sources sont disponible sur mon github : https://github.com/Underflow/genetik-draw

Un algorithme génétique

Un algorithme génétique se base sur la théorie de l’évolution de Darwin pour résoudre un problème. Il fonctionne donc sur le même principe fondamental que la sélection naturelle des êtres vivants : « l’individu le plus adapté aura plus de chance de se reproduire ».

Note : Pour faire plaisir à ce connard de Chewie il faudrait plutôt parler de la théorie de Lamarck.

Tous les algorithmes génétiques fonctionnent selon le même principe :

  1. On génère une population d’individus avec un ADN aléatoire
  2. On classe les individus selon leur aptitude à résoudre un problème donné
  3. On génère une nouvelle génération d’individus en effectuant des croisements entre les individus de la dernière génération. Les individus les mieux classés ont une probabilité plus forte d’engendrer une progéniture
  4. On effectue des mutations aléatoires sur les individus (avec une probabilité relativement faible pour ne pas produire de générations de dégénérés)
  5. Retour à l’étape 2.

Pour implémenter un algorithme génétique, il faut d’abord définir le sens de l’ADN des individus. C’est à dire à quoi correspondront les données contenu dans l’ADN. Pour faire le parallèle avec les êtres vivants, dans un organisme l’ADN est transcrit en ARN qui est ensuite traduit en protéine.
De la même façon il faut réaliser une fonction de « traduction ». Dans mon cas, la fonction de traduction transforme l’ADN en une image. L’ADN contient en fait les coordonnées des carrés et leur couleur.

Ensuite, il est nécessaire de déterminer une fonction déterminant le fitness des individus, c’est à dire un score d’adaptation au problème à résoudre. J’ai choisi pour ce projet d’utiliser une bête fonction de comparaison d’image. Elle retourne la somme de la différence des couleurs de chaque pixels entre l’image source et celle de l’individu.

Enfin il faut une fonction de croisement (aka crossover) qui mélangera deux ADN pour brasser les générations. Sur mon programme, le croisement s’effectue gène par gène (ou carré par carré si vous préférez) et non pas octet par octet ce qui n’aurait eu aucun sens (ou toute autre méthode de croisement adaptée à d’autres algorithmes génétiques).

 

Une fois que tout ceci est correctement codé, la magie opère toute seule, et un dessin « correct » arrive très vite à l’écran !

Evolution d’une population

J’aurais pu vous faire un beau graphique, mais j’ai vraiment la flemme. Je vous copie colle le résultat de la sortie console. Le score affiché correspond au pourcentage de ressemblance entre l’image génétique et l’image à reproduire.

Generation : 0 - Best fitness : 69.230701
Generation : 10 - Best fitness : 72.895536
Generation : 20 - Best fitness : 74.464792
Generation : 30 - Best fitness : 75.163049
Generation : 40 - Best fitness : 76.264078
Generation : 50 - Best fitness : 76.895984
Generation : 60 - Best fitness : 77.855822
Generation : 70 - Best fitness : 78.508686
Generation : 80 - Best fitness : 79.311399
Generation : 90 - Best fitness : 79.834519
Generation : 100 - Best fitness : 80.285271
Generation : 110 - Best fitness : 80.652855
Generation : 120 - Best fitness : 81.155114
Generation : 130 - Best fitness : 81.250519
Generation : 140 - Best fitness : 81.679887
Generation : 150 - Best fitness : 81.935676
Generation : 160 - Best fitness : 82.397639
Generation : 170 - Best fitness : 82.737401
Generation : 180 - Best fitness : 83.023686
Generation : 190 - Best fitness : 83.427936
Generation : 200 - Best fitness : 83.569475
Generation : 210 - Best fitness : 83.896074
Generation : 220 - Best fitness : 84.156327
Generation : 230 - Best fitness : 84.421856
Generation : 240 - Best fitness : 84.653619
...
Generation : 280 - Bestfitness : 85.210001
...
Generation : 460 - Bestfitness : 87.734134
...
Generation : 910 - Bestfitness : 90.093073
...
Generation : 1810 - Bestfitness : 91.600760