Passions d’un développeur indépendant

Un nouveau blog sur Wefrag le blog de DraK.

Bonjour à tous,

Nous allons parler ici d’algorithme génétique et de réseau de neurones, si ces concepts ne vous sont pas familiers, 2 articles sont à votre disposition pour palier ce problème : Algorithme génétique et Réseau de neurones.

Introduction Forex

Gérant les cotations des devises, ce marché fait 5000 milliards de dollars d’échanges chaque jour.

Les banques, les états et autres fonds d’investissement se battent dessus en permanence par traders et robots interposés.

Les robots traders sont autorisés, et même encouragés par certains professionnels du milieu.

L’accession au Forex pour les particuliers a été facilitée en 2000, ce qui a amené pas mal de chair fraîche pour tout ce beau monde.

90% des traders particuliers sont perdants, il faut les venger !

Notre stratégie ? C’est simple :

*Retire le cigare de sa bouche* T’achète quand c’est bas, tu vends quand c’est haut, pigé !?

Mais pourquoi j’écris ces conneries ? xD

Mise en pratique

Structure du réseau de neurones

La structure du réseau neuronal est assez classique, il y a 2 neurones :

  • 1 neurone pour ouvrir un trade
  • 1 neurone pour fermer le trade en cours

Les entrées correspondent aux informations fournies par le marché :

  • La tendance du marché (le cours monte ou baisse)
  • La force de la tendance
  • Le volume des transactions du marché
  • Le rapport de force entre les acheteurs et les vendeurs
  • Etc…

Le réseau de neurones est appelé 2 fois de suite, une fois pour prendre une décision d’achat, et une autre pour prendre une décision de vente.

Les informations du marché sont prémâchées 2 fois (achat et vente) par le code pour pouvoir être envoyées dans le réseau.

Voici 2 tableaux récapitulant les décisions prises en fonction de la réponse des neurones :

Tableau des décision pour un achat

Tableau des décisions pour un achat

Tableau des décisions pour la vente

Tableau des décisions pour la vente

Algorithme génétique

L’algorithme génétique paramètre le réseau de neurones, c’est donc lui qui fait l’apprentissage.

Contrairement à l’algorithme avec les voitures, nous ne cherchons pas un idéal pour terminer l’apprentissage. Nous ferons 1000 générations quelque soit le résultat.

Chaque génération se verra composée d’une population de 50 individus (ADN).

Ce qui nous fera 50000 ADN testés, soit autant de robots différents.

Évidemment, 95% de ces robots seront complètement nazes, mais on s’en fout !

Comme d’habitude, la sélection des meilleurs, la reproduction et les mutations seront de la partie !

Fonction d’évaluation

Les robots sont chargés dans une plateforme de trading qui simuler les trades sur 1 année de cours passé.

Le programme qui supervise l’apprentissage récupère les résultats de tous les trades passés sur l’historique et calcule des statistiques dessus.

Le score d’un ADN est basé sur les informations suivantes :

  • Nombre de trades
  • Rendement mensuel
  • Efficacité (ratio <total des gains> / <total des pertes>)
  • Plus grosse chute de capital sur le compte

Résultat en vidéo

YouTube Preview Image

Il est donc possible de faire un robot de trading avec un algorithme génétique et un réseau neuronal, même basique.

Bon week-end à tous :)

Snatcrisee posté sur Steam Greenlight

Mercredi 6 juillet 2016 à 2:15

Bonjour à tous les nofragés !

C’est avec grand plaisir que je vous présente mon jeu indé !

Présentation

Le jeu s’appelle Snatcrisee, ça veut rien dire de spécial, c’est juste un anagramme de “résistance”, de “cartésiens” et aussi de “scénariste”…
C’est un jeu de plateforme shooter 2D avec un coté rogue-like.
Il y a un mode mode multijoueur distant et on joue en coop pour tenter de finir le jeu (c’est très dur en mode expert).

Le but du jeu est d’augmenter sa puissance en même temps que la progression dans les niveaux. Pour cela, il faut ramasser les objets qui donnent des bonus aux statistiques de votre personnage (bonus de résistance, vitesse d’attaque, double projectiles, etc…).

Développement

Je me suis lancé dans ce projet en Février 2014. J’ai, depuis, quitté mon emploi pour devenir auto-entrepreneur et essayer de vivre de ce projet.
C’est pour l’instant très loin d’être gagné (aucune vente par mon site perso), et mon dernier espoir repose sur la fameuse plateforme de Gaben Le Magnifique.

Un ami me fait les musiques (dont celle dans la vidéo, c’est la musique des boss), j’ai fait tout le reste (code et graphismes). Evidemment, on voit tout de suite que je ne suis pas graphiste ! Mais bon, c’est suffisant pour que ça soit agréable à jouer.

Le jeu est suffisamment avancé pour être vendu (il est possible de s’amuser pendant des heures, même si ça manque un peu de contenu au bout d’un moment, je vais ajouter encore beaucoup de choses).

Greenlight

J’ai enfin terminé la vidéo du trailer et je viens de soumettre le jeu sur Steam Greenlight.

YouTube Preview Image

Voici le lien de la page Greenlight

J’aimerai connaître vos impressions sur le jeu et au passage, je serai reconnaissant si vous votiez un petit coup :D

Dans un avenir inconnu, je posterai un article pour expliquer comment j’ai réalisé les explosions du jeu à partir du bruit de Perlin (fallait bien que je trouve un truc, je ne sais pas dessiner les explosions …).

Merci et bonne semaine à vous ;)

Bonjour à tous,

Si vous n’avez pas vu le 1er article, vous risquez de ne pas tout saisir.

Aujourd’hui, nous allons voir une application des algorithmes génétiques qui permet d’obtenir une IA de voiture sur un circuit en 2D. Pour ce faire, nous allons intégrer un réseau de neurones à notre algorithme.

Introduction baclée très rapide aux réseaux de neurones

Neurone

Un neurone a plusieurs entrées (autant que voulu) et une seule sortie. Les valeurs des entrées passent dans une fonction mathématique et le résultat donne la valeur de sortie du neurone. Cette fonction est paramétrable pour chaque neurone.

Généralement, cette fonction est une somme des entrées E pondérée par des poids P et à laquelle on soustrait un seuil S. Le résultat étant borné entre 0 et 1 par une fonction F.

Ce qui nous donne en formule : pour n entrées : F(E1 * P1 + … + En * Pn - S)

Nous choisissons d’utiliser cette fonction, les paramètres de chaque neurone seront donc tous les poids P ainsi que le seuil S.

Fonctionnement d'un neurone

Réseau de neurones

La version la plus simple consiste à faire des couches de neurones, en sachant que chaque couche reçoit en entrée de ses neurones les sorties des neurones de la couche précédente.

De plus, les neurones de la 1ère couche vont recevoir en entrée les informations concernant notre problème. Les neurones de la dernière couche nous donneront le résultat en sortie.

Fonctionnement d'un réseau de neurones

Exemple #2 : Voiture de course 2D

Voiture et neurones

La voiture possède 4 capteurs de route positionnés sur les roues permettant au programme d’éliminer la voiture si 2 de ses roues sont en dehors du circuit. Elle possède également 8 capteurs lasers qui donnent la distance avant la sortie de chaussée. Pour contrôler la voiture, nous disposons de 2 commandes : le moteur et le volant.

Capteurs de la voiture

Du coup, nous allons utiliser une seule couche de 2 neurones, un neurone pour contrôler le moteur (accélérer, freiner, voire marche arrière) et un autre pour contrôler le volant.

Chacun de nos 2 neurones va recevoir 9 valeurs en entrée : la vitesse actuelle de la voiture, car il y a de l’inertie dans la commande du moteur (accélération), et les 8 capteurs lasers.

Et là, vous vous posez une question : où est passé l’algorithme génétique ?

Algorithme génétique

L’ADN de l’algorithme génétique va correspondre dans notre cas au paramétrage du réseau de neurones.

L’ADN de chaque voiture sera donc une liste de 20 nombres réels ((9 poids + 1 seuil) * 2 neurones).

Nous allons ensuite voir la fonction d’évaluation !

Ce sera un championnat composé de 4 circuits différents. Chaque circuit est complété en faisant un seul tour.

Si la voiture sort du circuit (2 roues dehors), nous lui donnerons un nombre de points équivalant au pourcentage du circuit complété (exemple : 50 points pour 50% du circuit). Si la voiture boucle le circuit, nous lui donnerons 200 points + un bonus en fonction du temps (exemple : 100 points pour 30 secondes, 300 points pour 10 secondes, etc…). Pour ne pas attendre indéfiniment, nous imposons un temps maximum pour chaque circuit. Toutes les voitures encore sur le circuit à la fin du temps imparti seront considérées comme sortant de la piste.

Pour évaluer les individus à chaque génération, les 4 circuits se succéderont, le score d’une voiture sera la somme de ses scores sur les 4 circuits.

Les principes de l’algorithme génétique sont toujours présents : l’évaluation, la sélection, la reproduction et la mutation seront utilisées.

Le résultat est une IA qui apprend à conduire la voiture grâce aux capteurs. L’IA est encouragée à boucler le circuit rapidement, mais la sortie de route reste très punitive (elle passe de 300/400 points à moins de 100…). L’IA n’apprend pas le circuit, elle n’a d’ailleurs aucune mémoire de suite de virage ou quoi que ce soit. Elle apprend simplement à négocier les virages. Ou plutôt, elle apprend à négocier les combinaisons de valeurs que ses capteurs lui donnent.

Une fois que l’on a obtenu une IA qui gère bien les 4 circuits, nous arrêtons l’algorithme et nous sauvegardons l’ADN de notre champion pour pouvoir l’utiliser plus tard.

Mais nous n’en avons pas fini avec elle, nous allons lui soumettre un test particulier… Notre IA va devoir compléter un 5ème circuit inconnu et du 1er coup ! Plus besoin d’algorithme génétique, plus d’évolution possible ! Il nous suffit de charger notre ADN dans le réseau de neurones et de poser la voiture sur le nouveau circuit.

Va-t-elle réussir le test ?

Résultat

Vidéo de l’apprentissage au fil des générations + Bonus test sur le 5ème circuit :

YouTube Preview Image

Et voilà ! Nous venons de prouver qu’il est possible de conduire une voiture avec seulement 2 neurones :D

Nous avons obtenu une IA qui est capable de finir des circuits simples avec des virages assez serrés, mais elle sera surement perdue si elle rencontre une situation jamais vue (croisement de route, virage encore plus serré, route plus étroite, grande étendue, etc…).

Il est donc possible de créer une IA pour son propre jeu relativement facilement. Il suffit de créer quelques capteurs d’environnement (position de l’ennemi le plus proche, distance avant le prochain mur en face, etc…). De plus, si vous codez l’algorithme génétique et le réseau de neurones de manière générique, vous pouvez l’utiliser facilement partout.

Bonne fin de semaine à vous :)

Algorithme Génétique : Introduction et Exemple #1

Vendredi 13 novembre 2015 à 19:21

Bonjour à tous !

Nous allons voir ensemble brièvement comment les algorithmes génétiques fonctionnent et quelles peuvent être leurs utilisations.
L’objectif de cet article n’est pas de montrer comment coder, développer ou mettre en place un algorithme génétique, il y a des tutoriels pour cela. Notre objectif ici est de vulgariser le principe afin de comprendre les possibilités qu’il offre.

Introduction

L’algorithme génétique est un algorithme qui permet de trouver des solutions à un problème donné. Il est basé en partie sur l’aléatoire et ne trouve que rarement la solution parfaite, mais s’approche plutôt d’une des solutions. Ce qui fait de lui un algorithme de recherche locale.

Le principe est inspiré de la génétique et de la théorie de l’évolution, ce qui lui vaut son nom.

Avantages

  • Il permet de trouver des compromis dans des problèmes complexes
  • Il permet de créer des IA pour contrôler des entités dans un jeu (un robot, une voiture, un monstre, etc…)

Inconvénients

  • Il faut beaucoup de temps pour obtenir un résultat correct dans la plupart des cas, il n’est donc pas fait pour être exécuter en temps réel dans un jeu mais exécuter pendant le développement du jeu (à moins de faire un jeu basé sur l’évolution évidemment)
  • Il ne fait bien souvent que se rapprocher d’une solution sans l’atteindre
  • Il faut passer du temps dans le paramétrage pour trouver le juste milieu entre diversité génétique et performance des ADN, et cela en fonction du type de problème, de la taille des ADN, etc…
  • Il est totalement dépassé par les algorithmes de recherche d’un chemin parmi des nœuds (A*, Dijkstra, etc…)
  • Le procédé étant basé en partie sur l’aléatoire, les résultats et le temps pour y parvenir sont différents à chaque exécution

Principe

L’algorithme génétique gère une population d’individus (le nombre est au choix) qui se renouvèle à chaque génération. Chaque individu a son ADN.

Un ADN est une liste d’informations qui constitue une possible solution que le développeur va tester dans son problème.

La structure d’information, le nombre et le type des informations est au choix du développeur, voici une liste non exhaustive :

  • Chaîne de caractères : “HHGBGGHD”
  • Une liste d’entier entre 1 et 8 : 13556482
  • Une formule mathématique : “(1+x)*2″
  • Une liste de paramètres pour une IA (taux d’agressivité, taux de fuite, etc…)
  • Les paramètres d’un réseau de neurone (article à venir)

Ces informations représentent pour le développeur quelque chose de précis :

On peut imaginer par exemple que la chaîne de caractère “HHGBGGHD” est en fait une série de touches à appuyer à la suite avec H = Haut, B = Bas, G = Gauche, D = Droite dans un jeu où le héros doit esquiver des monstres.

Revenons à notre population, à chaque génération, tous les individus vont voir leurs ADN évaluer par une fonction d’évaluation que le développeur aura créée. A la suite de cette évaluation, l’individu obtiendra un score qui définira combien sa “solution” est bonne dans ce problème. Ce score peut être le temps de survie du héros, ou bien le nombre de monstre qu’il a tué, ou encore la distance parcourue sur un terrain. En gros ce score doit refléter combien le développeur est satisfait de cet ADN.

Une fois l’évaluation terminée, on procède à une sélection des X% meilleurs individus (en fonction du score), et on leur permet de se reproduire entre eux, on supprime tous les anciens individus pour les remplacer par la génération suivante (les enfants).

Pour créer un enfant à partir des 2 parents, on lui donne une partie (la taille est aléatoire) de l’ADN d’un parent, et ce qu’il reste vient de l’autre parent, ça donne un tout nouvel ADN (à moins que les 2 parents aient le même ADN mais là on ferait dans le consanguin xD).

L’enfant donné a ensuite une chance de muter, c’est-à-dire voir une partie de son ADN changer aléatoirement, en général un ou plusieurs gènes. Dans notre cas, un gène serait par exemple un caractère de la chaîne de caractère “HHGBGGHD”.

Exemple de reproduction :

Parent A : “HHHHDDDD”

Parent B : “GGGBBBGG”

Enfant avant mutation : “HHGBBBGG”

Enfant après mutation “HHGBDBGG”

Dans cet exemple, les ADN font tous 8 gènes, mais il est possible de faire reproduire des ADN de tailles différentes.

Une fois la nouvelle génération conçue, on est partis pour un nouveau tour d’évaluation. Ce procédé est répétable à l’infini, on ne s’arrête que lorsque l’on a une solution que l’on juge convenable. Au fil des générations, les ADN devrait se rapprocher de la solution. Si je dis “devrait”, c’est parce qu’il est possible de perdre des bons ADN si le paramétrage n’est pas correct (trop de mutation ou trop de diversité génétique). Le nombre de générations à faire avant d’avoir un résultat satisfaisant dépend du problème initial et de la chance, et ça peut monter à 100, 1.000, 10.000 ou même 100.000 générations !

Notons que les ADN de la 1ère génération sont totalement aléatoires et donc chaotiques (bien qu’il soit possible de reprendre des ADN sauvegardés afin de les améliorer).

Exemple #1 : Dessiner une image avec des ellipses

On prend une image qui va nous servir de modèle pour dessiner (je me suis limité à 400px de large).

En définissant l’ADN comme étant 5000 gènes, chacun contient des informations pour dessiner une ellipse (position horizontale, position verticale, largeur, hauteur, couleur).

Les positions horizontales et verticales sont comprises entre 0 et la taille de l’image. La largeur et la hauteur de l’ellipse sont comprises entre 3 et 16 pixels. Les couleurs possibles sont limitées à la palette de couleur de l’image modèle. Sans ces conditions préalables, il serait trop compliqué d’obtenir un résultat correct.

Exemple d’un ADN : (30, 55, 12, 7, #FF0000), (201, 138, 9, 16, #AB3765), … 5000 fois

Notre fonction d’évaluation crée une image toute noire aux dimensions du modèle, puis dessine les 5000 ellipses de l’ADN. La fonction compare alors chaque pixel de l’image résultante avec le pixel correspondant sur l’image modèle et donne un pourcentage global de similarité entre les 2 images. Ce pourcentage sera alors le score de l’individu.

Lors du procédé, j’ai généré une capture d’écran du meilleur individu toutes les 10 générations, et j’ai laissé tourner ça 2 heures (avec 1 processeur à 100%) pour obtenir finalement cette vidéo :

YouTube Preview Image

Il est mimi le gros chat ! Bon, l’image restera toujours grossière avec seulement 5000 ellipses quand on sait que l’image originale est composée de 131600 pixels et de 29303 couleurs différentes ! Mais la ressemblance est flagrante quand on s’éloigne de l’écran, non ?

Ce qui est pratique, c’est que ça fonctionne pour toutes les images, il suffit juste de remplacer l’image modèle pour obtenir une nouvelle vidéo :

YouTube Preview Image

Ha ! La flemme légendaire des développeurs…

Le prochain exemple sera un peu plus intéressant qu’une bouillie de pixels dégueulasse…