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 

14 

15 

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 

42 

43 

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) 

52 

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] 

60 

61 maxx /= 2 

62 maxy /= 2 

63 

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 

75 

76 

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 

84 

85 

86def ajoute_vecteur(v, n): 

87 """ 

88 Ajoute deux vecteurs entre eux. 

89 """ 

90 return (v[0] + n[0], v[1] + n[1]) 

91 

92 

93def soustrait_vecteur(v, n): 

94 """ 

95 Soustrait deux vecteurs. 

96 """ 

97 return (v[0] - n[0], v[1] - n[1]) 

98 

99 

100def multiplie_vecteur(v, f): 

101 """ 

102 Multiplie un vecteur par un scalaire. 

103 """ 

104 return (v[0] * f, v[1] * f) 

105 

106 

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 

115 

116 

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]) 

122 

123 

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. 

128 

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 

145 

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 

155 

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] 

162 

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) 

168 

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) 

174 

175 neurones[i1] = n1 

176 neurones[i2] = n2 

177 

178 return proche 

179 

180 

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. 

185 

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) 

200 

201 

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) 

209 

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] 

219 

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)) 

234 

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]) 

240 

241 # on remet les compteurs à zéros 

242 for i in range(0, len(compte)): 

243 compte[i] = 0 

244 

245 

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 

264 

265 

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) 

278 

279 

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) 

290 

291 

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 

311 

312 La simulation ressemble à ceci : 

313 

314 .. raw:: html 

315 

316 <video autoplay="" controls="" loop="" height="125"> 

317 <source src="http://www.xavierdupre.fr/enseignement/complements/tsp_kohonen.mp4" type="video/mp4" /> 

318 </video> 

319 

320 Pour lancer la simulation:: 

321 

322 from ensae_teaching_cs.special.tsp_kohonen import pygame_simulation 

323 import pygame 

324 pygame_simulation(pygame) 

325 

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 

338 

339 if first_click: 

340 wait_event(pygame) 

341 images = [] if folder is not None else None 

342 

343 iter = 0 

344 while iter < max_iter: 

345 iter += 1 

346 

347 if iter % 1000 == 0: 

348 fLOG("iter", iter) 

349 

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 

355 

356 bv, bn = iteration(villes, neurones, dist, fs, compte_v, compte_n) 

357 

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() 

363 

364 if images is not None and iter % 10 == 0: 

365 images.append(screen.copy()) 

366 

367 if first_click: 

368 wait_event(pygame) 

369 

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)