===== GNG =====

Ressources utilisées :
   * http://www.booru.net/download/MasterThesisProj.pdf

==== Algorithme ====

   * Commencer avec deux nœuds relié par un arc d'age 0
   - Générer une entrée
   - Localiser les deux noeuds les plus près de cette entrée
   - Mise à jour de l'erreur locale du noeud gagnant 
   - Bouger le gagnant et ses voisins vers l'entrée 
   - Incrémenter l'age des arcs entre le noeud gagnant et ses voisins
   - Si les deux noeuds (étape 2) sont relié par un arc, passer son age à 0, sinon créer l'arc
   - Supprime un arc s'il atteint un age supérieur au seuil fixé Amax, supprimer le noeud s'il n'est relié à aucun autre noeud
   - Si l'itération est un multiple de λ et que le maximum d'itération n'est pas atteint, insérer un noeud entre le noeud qui a la plus grosse erreur et son voisin qui a la plus grosse erreur. Supprimer les arcs entre les deux noeuds et en ajouter entre eux et le noeud nouvellement insérer. Décroître le taux d'erreur pour chaque noeud.
   - Décroître un peu le taux d'erreur pour tous les noeuds
   - Réitérer les étapes 2 à 9 n fois

==== Equations ====

Mettre à jour le taux d'erreur (étape 3) :

{{:var_erreur.png|}}

Mettre à jour les poids des noeuds (étape 4) : 

{{:maj_vecteurs.png|}}

Poids du noeud à insérer (étape 8) :

{{:gng1.png|}}

Mettre à jour les taux d'erreur après insertion d'un nouveau noeud (étape 8) :

{{:gng2.png|}}

Décroître le taux d'erreur de tous les noeuds (étape 9) :

{{:gng3.png|}}



==== Expérience ====

Comme pour la Self Organizing Map, l'expérience se déroule sur un repère orthonormé sur les intervalles x[0, 100] et y [0, 100].

{{:vide.png|}}

L'expérience commence en plaçant deux noeuds de manière aléatoire sur le terrain. Avec l'algorithme du GNG ils sont censé se dupliquer et occuper l'espace petit à petit.

{{:debutgng.png|}}
==== Résultat ====

Après 5000 itérations j'obtiens le résultat suivant :

{{:fingng.png|}}

En testant le GNG dans les même conditions que la SOM, je m'attendais à avoir un résultat similaire, peut être avec plus de noeuds moins bien organisés.\\
Le résultat obtenu est incorrect, on voit sur l'image que les noeuds sont loin de recouvrir l'espace disponible. Ce qu'on ne voit pas, c'est que l'algorithme à crée plus de 4 noeuds, mais que ceux-ci ce sotn superposés. Il faudrait vérifier plus en détail le fonctionnement des méthodes implémentées et les déboguer si nécessaire.