module special.tsp_kohonen#

Short summary#

module ensae_teaching_cs.special.tsp_kohonen

Réseaux de Kohonen pour résoudre le problème du voyageur de commerce.

source on GitHub

Functions#

function

truncated documentation

ajoute_vecteur

Ajoute deux vecteurs entre eux.

construit_liste_neurones

Place les neurones sur l’écran, il y a autant de neurones que de villes, le paramètre villes est la liste des villes. …

construit_ville

Tire aléatoirement n villes dans un carré x * y, on choisit ces villes de sorte qu’elles ne soient pas trop proches. …

deplace_neurone

Déplace le neurone de plus proche de la ville n, déplace ses voisins.

display_neurone

Dessine les neurones à l’écran.

display_ville

Dessine les villes à l’écran.

distance_euclidienne_carree

Calcule la distance euclidienne entre deux points.

iteration

Choisit une ville aléatoirement et attire le neurones le plus proche, choisit cette ville parmi les villes les moins …

modifie_structure

Modifie la structure des neurones, supprime les neurones jamais déplacés, et ajoute des neurones lorsque certains sont …

moyenne_proximite

Retourne la distance moyenne entre deux villes les plus proches.

multiplie_vecteur

Multiplie un vecteur par un scalaire.

poids_attirance

Calcule le poids d’attraction d’une neurone vers une ville.

pygame_simulation

soustrait_vecteur

Soustrait deux vecteurs.

vecteur_norme

Calcul la norme d’un vecteur.

Documentation#

Réseaux de Kohonen pour résoudre le problème du voyageur de commerce.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.ajoute_vecteur(v, n)#

Ajoute deux vecteurs entre eux.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.construit_liste_neurones(villes, nb=0)#

Place les neurones sur l’écran, il y a autant de neurones que de villes, le paramètre villes est la liste des villes.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.construit_ville(n, x=1000, y=700)#

Tire aléatoirement n villes dans un carré x * y, on choisit ces villes de sorte qu’elles ne soient pas trop proches.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.deplace_neurone(n, villes, neurones, dist_w, forces, compte)#

Déplace le neurone de plus proche de la ville n, déplace ses voisins.

Paramètres:
  • villes – liste des villes

  • neurones – liste des neurones

  • dist – distance d’attirance

  • forces – force de déplacement des voisins du neurones

  • compte – incrémente compte [n] où n est l’indice du neurone choisi

Renvoie:

indice du neurone le plus proche

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.display_neurone(neurones, screen, bn, pygame)#

Dessine les neurones à l’écran.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.display_ville(villes, screen, bv, pygame)#

Dessine les villes à l’écran.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.distance_euclidienne_carree(p1, p2)#

Calcule la distance euclidienne entre deux points.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.iteration(villes, neurones, dist, forces, compte_v, compte_n)#

Choisit une ville aléatoirement et attire le neurones le plus proche, choisit cette ville parmi les villes les moins fréquemment choisies.

Paramètres:
  • villes – liste des villes

  • neurones – liste des neurones

  • dist – distance d’attirance

  • forces – force de déplacement des voisins du neurones

  • compte_v – incrémente compte_v [n] où n est l’indice de la ville choisie

  • compte_n – incrémente compte_n [n] où n est l’indice du neurone choisi

Renvoie:

indices de la ville et du neurone le plus proche

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.modifie_structure(neurones, compte, nb_sel)#

Modifie la structure des neurones, supprime les neurones jamais déplacés, et ajoute des neurones lorsque certains sont trop sollicités.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.moyenne_proximite(villes)#

Retourne la distance moyenne entre deux villes les plus proches.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.multiplie_vecteur(v, f)#

Multiplie un vecteur par un scalaire.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.poids_attirance(p, dist)#

Calcule le poids d’attraction d’une neurone vers une ville.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.pygame_simulation(pygame, folder=None, size=(800, 500), nb=200, tour=2, dist_ratio=4, fs=(1.5, 1, 0.75, 0.5, 0.25), max_iter=12000, alpha=0.99, beta=0.9, first_click=False, flags=0, fLOG=<function fLOG>)#
Paramètres:
  • pygame – module pygame

  • first_click – attend la pression d’un clic de souris avant de commencer

  • folder – répertoire où stocker les images de la simulation

  • size – taille de l’écran

  • delay – delay between two tries

  • flags – see pygame.display.set_mode

  • fLOG – logging function

  • fs – paramètres

  • max_iter – nombre d’itérations maximum

  • alpha – paramètre alpha

  • beta – paramètre beta

  • dist_ratio – ratio distance

  • tour – nombre de tours

  • nb – nombre de points

La simulation ressemble à ceci :

Pour lancer la simulation:

from ensae_teaching_cs.special.tsp_kohonen import pygame_simulation
import pygame
pygame_simulation(pygame)

Voir Résolution d’un puzzle.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.soustrait_vecteur(v, n)#

Soustrait deux vecteurs.

source on GitHub

ensae_teaching_cs.special.tsp_kohonen.vecteur_norme(p)#

Calcul la norme d’un vecteur.

source on GitHub