Coverage for src/ensae_teaching_cs/special/tsp_kohonen.py: 97%
203 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief `Réseaux de Kohonen <https://fr.wikipedia.org/wiki/Carte_auto_adaptative>`_
5pour résoudre le
6problème du `voyageur de commerce <https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce>`_.
7"""
8import os
9import random
10import math
11import functools
12from pyquickhelper.loghelper import fLOG
13from ..helpers.pygame_helper import wait_event, empty_main_loop
16def construit_ville(n, x=1000, y=700):
17 """
18 Tire aléatoirement *n* villes dans un carré ``x * y``,
19 on choisit ces villes de sorte qu'elles ne soient pas trop proches.
20 """
21 # deux villes ne pourront pas être plus proches que mind
22 mind = math.sqrt(x * x + y * y) / (n * 0.75)
23 # liste vide
24 lt = []
25 while n > 0:
26 # on tire aléatoirement les coordonnées d'une ville
27 xx = x * random.random()
28 yy = y * random.random()
29 # on vérifie qu'elle n'est pas trop proche d'aucune autre ville
30 ajout = True
31 for t in lt:
32 d1 = t[0] - xx
33 d2 = t[1] - yy
34 d = math.sqrt(d1 * d1 + d2 * d2)
35 if d < mind:
36 ajout = False # ville trop proche
37 # si la ville n'est pas trop proche des autres, on l'ajoute à la liste
38 if ajout:
39 lt.append((xx, yy))
40 n -= 1 # une ville en moins à choisir
41 return lt
44def construit_liste_neurones(villes, nb=0):
45 """
46 Place les neurones sur l'écran,
47 il y a autant de neurones que de villes,
48 le paramètre villes est la liste des villes.
49 """
50 if nb == 0:
51 nb = len(villes)
53 # coordonnées maximale
54 maxx, maxy = 0, 0
55 for v in villes:
56 if v[0] > maxx:
57 maxx = v[0]
58 if v[1] > maxy:
59 maxy = v[1]
61 maxx /= 2
62 maxy /= 2
64 if nb > 1:
65 # dispose les neurones en ellipse
66 n = []
67 for i in range(0, nb):
68 x = maxx + maxx * math.cos(math.pi * 2 * float(i) / nb) / 4
69 y = maxy + maxy * math.sin(math.pi * 2 * float(i) / nb) / 4
70 n.append((x, y))
71 return n
72 else:
73 n = [(maxx, maxy)]
74 return n
77def distance_euclidienne_carree(p1, p2):
78 """
79 Calcule la distance euclidienne entre deux points.
80 """
81 x = p1[0] - p2[0]
82 y = p1[1] - p2[1]
83 return x * x + y * y
86def ajoute_vecteur(v, n):
87 """
88 Ajoute deux vecteurs entre eux.
89 """
90 return (v[0] + n[0], v[1] + n[1])
93def soustrait_vecteur(v, n):
94 """
95 Soustrait deux vecteurs.
96 """
97 return (v[0] - n[0], v[1] - n[1])
100def multiplie_vecteur(v, f):
101 """
102 Multiplie un vecteur par un scalaire.
103 """
104 return (v[0] * f, v[1] * f)
107def poids_attirance(p, dist):
108 """
109 Calcule le poids d'attraction d'une neurone vers une ville.
110 """
111 d = p[0] * p[0] + p[1] * p[1]
112 d = math.sqrt(d)
113 d = dist / (d + dist)
114 return d
117def vecteur_norme(p):
118 """
119 Calcul la norme d'un vecteur.
120 """
121 return math.sqrt(p[0] * p[0] + p[1] * p[1])
124def deplace_neurone(n, villes, neurones, dist_w, forces, compte):
125 """
126 Déplace le neurone de plus proche de la ville *n*,
127 déplace ses voisins.
129 @param villes liste des villes
130 @param neurones liste des neurones
131 @param dist distance d'attirance
132 @param forces force de déplacement des voisins du neurones
133 @param compte incrémente compte [n] où n est l'indice du neurone choisi
134 @return indice du neurone le plus proche
135 """
136 # recherche du neurone le plus proche
137 v = villes[n]
138 proche = 0
139 dist = distance_euclidienne_carree(v, neurones[0])
140 for i in range(1, len(neurones)):
141 d = distance_euclidienne_carree(v, neurones[i])
142 if d < dist:
143 dist = d
144 proche = i
146 # vecteur de déplacement
147 i = proche
148 compte[i] += 1
149 n = neurones[i]
150 vec = soustrait_vecteur(v, n)
151 poids = poids_attirance(vec, dist_w)
152 vec = multiplie_vecteur(vec, poids)
153 n = ajoute_vecteur(n, vec)
154 neurones[i] = n
156 # déplacement des voisins
157 for k in range(0, len(forces)):
158 i1 = (i + k + 1) % len(neurones)
159 i2 = (i - k - 1 + len(neurones)) % len(neurones)
160 n1 = neurones[i1]
161 n2 = neurones[i2]
163 vec = soustrait_vecteur(n, n1)
164 poids = poids_attirance(vec, dist_w)
165 vec = multiplie_vecteur(vec, poids)
166 vec = multiplie_vecteur(vec, forces[k])
167 n1 = ajoute_vecteur(n1, vec)
169 vec = soustrait_vecteur(n, n2)
170 poids = poids_attirance(vec, dist_w)
171 vec = multiplie_vecteur(vec, poids)
172 vec = multiplie_vecteur(vec, forces[k])
173 n2 = ajoute_vecteur(n2, vec)
175 neurones[i1] = n1
176 neurones[i2] = n2
178 return proche
181def iteration(villes, neurones, dist, forces, compte_v, compte_n):
182 """
183 Choisit une ville aléatoirement et attire le neurones le plus proche,
184 choisit cette ville parmi les villes les moins fréquemment choisies.
186 @param villes liste des villes
187 @param neurones liste des neurones
188 @param dist distance d'attirance
189 @param forces force de déplacement des voisins du neurones
190 @param compte_v incrémente compte_v [n] où n est l'indice de la ville choisie
191 @param compte_n incrémente compte_n [n] où n est l'indice du neurone choisi
192 @return indices de la ville et du neurone le plus proche
193 """
194 m = min(compte_v)
195 ind = [i for i in range(0, len(villes)) if compte_v[i] == m]
196 n = random.randint(0, len(ind) - 1)
197 n = ind[n]
198 compte_v[n] += 1
199 return n, deplace_neurone(n, villes, neurones, dist, forces, compte_n)
202def modifie_structure(neurones, compte, nb_sel):
203 """
204 Modifie la structure des neurones, supprime les neurones jamais
205 déplacés, et ajoute des neurones lorsque certains sont trop sollicités.
206 """
207 def cmp_add(i, j):
208 return -1 if i[0] < j[0] else (1 if i[0] > j[0] else 0)
210 if nb_sel > 0:
211 # supprime les neurones les moins sollicités
212 sup = [i for i in range(0, len(neurones)) if compte[i] == 0]
213 if len(sup) > 0:
214 sup.sort()
215 sup.reverse()
216 for i in sup:
217 del compte[i]
218 del neurones[i]
220 # on ajoute un neurone lorsque max (compte) >= 2 * min (compte)
221 add = []
222 for i in range(0, len(compte)):
223 if compte[i] > nb_sel:
224 d1 = math.sqrt(distance_euclidienne_carree(neurones[i],
225 neurones[(i + 1) % len(neurones)]))
226 d2 = math.sqrt(distance_euclidienne_carree(neurones[i],
227 neurones[(i - 1 + len(neurones)) % len(neurones)]))
228 if d1 > d2:
229 d1 = d2
230 p = neurones[i]
231 p = (p[0] + random.randint(0, int(d1 / 2)),
232 p[1] + random.randint(0, int(d1 / 2)))
233 add.append((i, p, 0))
235 add = list(sorted(add, key=functools.cmp_to_key(cmp_add)))
236 add.reverse()
237 for a in add:
238 neurones.insert(a[0], a[1])
239 compte.insert(a[0], a[2])
241 # on remet les compteurs à zéros
242 for i in range(0, len(compte)):
243 compte[i] = 0
246def moyenne_proximite(villes):
247 """
248 Retourne la distance moyenne entre deux villes les plus proches.
249 """
250 c = 0
251 m = 0
252 for v in villes:
253 mn = 100000000
254 for vv in villes:
255 if v == vv:
256 continue
257 d = distance_euclidienne_carree(v, vv)
258 if d < mn:
259 mn = d
260 c += 1
261 m += math.sqrt(mn)
262 m /= float(c)
263 return m
266def display_neurone(neurones, screen, bn, pygame):
267 """
268 Dessine les neurones à l'écran.
269 """
270 color = 0, 0, 255
271 color2 = 0, 255, 0
272 for n in neurones:
273 pygame.draw.circle(screen, color, (int(n[0]), int(n[1])), 5)
274 v = neurones[bn]
275 pygame.draw.circle(screen, color2, (int(v[0]), int(v[1])), 5)
276 if len(neurones) > 1:
277 pygame.draw.lines(screen, color, True, neurones, 2)
280def display_ville(villes, screen, bv, pygame):
281 """
282 Dessine les villes à l'écran.
283 """
284 color = 255, 0, 0
285 color2 = 0, 255, 0
286 for v in villes:
287 pygame.draw.circle(screen, color, (int(v[0]), int(v[1])), 5)
288 v = villes[bv]
289 pygame.draw.circle(screen, color2, (int(v[0]), int(v[1])), 5)
292def pygame_simulation(pygame, folder=None, size=(800, 500), nb=200,
293 tour=2, dist_ratio=4, fs=(1.5, 1, 0.75, 0.5, 0.25),
294 max_iter=12000, alpha=0.99, beta=0.90,
295 first_click=False, flags=0, fLOG=fLOG):
296 """
297 @param pygame module pygame
298 @param first_click attend la pression d'un clic de souris avant de commencer
299 @param folder répertoire où stocker les images de la simulation
300 @param size taille de l'écran
301 @param delay delay between two tries
302 @param flags see `pygame.display.set_mode <https://www.pygame.org/docs/ref/display.html#pygame.display.set_mode>`_
303 @param fLOG logging function
304 @param fs paramètres
305 @param max_iter nombre d'itérations maximum
306 @param alpha paramètre alpha
307 @param beta paramètre beta
308 @param dist_ratio ratio distance
309 @param tour nombre de tours
310 @param nb nombre de points
312 La simulation ressemble à ceci :
314 .. raw:: html
316 <video autoplay="" controls="" loop="" height="125">
317 <source src="http://www.xavierdupre.fr/enseignement/complements/tsp_kohonen.mp4" type="video/mp4" />
318 </video>
320 Pour lancer la simulation::
322 from ensae_teaching_cs.special.tsp_kohonen import pygame_simulation
323 import pygame
324 pygame_simulation(pygame)
326 Voir :ref:`l-puzzle_girafe`.
327 """
328 pygame.init()
329 size = x, y = size[0], size[1]
330 white = 255, 255, 255
331 screen = pygame.display.set_mode(size, flags)
332 villes = construit_ville(nb, x, y)
333 neurones = construit_liste_neurones(villes, 3)
334 compte_n = [0 for i in neurones]
335 compte_v = [0 for i in villes]
336 maj = tour * len(villes)
337 dist = moyenne_proximite(villes) * dist_ratio
339 if first_click:
340 wait_event(pygame)
341 images = [] if folder is not None else None
343 iter = 0
344 while iter < max_iter:
345 iter += 1
347 if iter % 1000 == 0:
348 fLOG("iter", iter)
350 if iter % maj == 0:
351 modifie_structure(neurones, compte_n, tour)
352 dist *= alpha
353 f2 = tuple(w * beta for w in fs)
354 fs = f2
356 bv, bn = iteration(villes, neurones, dist, fs, compte_v, compte_n)
358 screen.fill(white)
359 display_ville(villes, screen, bv, pygame)
360 display_neurone(neurones, screen, bn, pygame)
361 empty_main_loop(pygame)
362 pygame.display.flip()
364 if images is not None and iter % 10 == 0:
365 images.append(screen.copy())
367 if first_click:
368 wait_event(pygame)
370 if folder is not None:
371 fLOG("saving images")
372 for it, screen in enumerate(images):
373 if it % 10 == 0:
374 fLOG("saving image:", it, "/", len(images))
375 image = os.path.join(folder, "image_%04d.png" % it)
376 pygame.image.save(screen, image)