<jupyter_start><jupyter_text>Recuit simuléCette séance sera divisée en deux parties. La première partie consiste à mettre au point un algorithme de recuit simulé pour trouver le minimum d'une fonction à deux variables *chaotique*. Nous réutiliserons cet algorithme sur un problème où la fonction d'évaluation est sur le modèle « boîte noire ».Limitations techniques:Afin d'avoir accès aux animations matplotlib dans le notebook, nous utiliserons l'option *notebook* (qui crée un widget Matplotlib dans le notebook) en place de *inline* (qui affiche un rendu png du plot). Cependant, il est important de bien cliquer sur l'icône de fermeture des widgets de plot (ce qui génère un png de l'état courant du widget) pour éviter que des graphes se tracent dans les mauvaises fenêtres.-->La deuxième partie de la séance tourne autour d'une implémentation GPU (calcul sur carte graphique) des graphes de Voronoi. L'appel à la fonction d'évaluation n'est pas possible dans un notebook ; il faudra donc écrire le programme dans un fichier séparé. Aussi, la bibliothèque de visualisation GPU `vispy` n'a pas été testée par nos soins sous Windows et l'appel à la fonction d'évaluation sera pénalisé sur les écrans Retina (MacOS). Par conséquent, pour cet exemple, il est conseillé de rester sur les machines (Linux) de l'école !<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
from matplotlib import animation
import numpy as np

def anim_to_html(anim):
    plt.close(anim._fig)
    return anim.to_html5_video()

animation.Animation._repr_html_ = anim_to_html<jupyter_output><empty_output><jupyter_text>Le code suivant génère une fonction à deux variables dont les contours sont dessinés ci-après. Peu importe l'implémentation, concentrons-nous sur le profil du contour.<jupyter_code>%run 01-boulders.py
from mpl_toolkits.mplot3d import Axes3D

fig = plt.figure(figsize=(7, 7))
ax = plt.axes(projection='3d')

ax.axis('off')
ax.view_init(-10, 30)

ax.plot_surface(X, Y, Z, cmap=plt.cm.viridis)

def animate(i):
    ax.view_init(-20, 30 + 4*i)
    return []

animation.FuncAnimation(fig, animate, frames=90, interval=200, blit=True)

fig = plt.figure(figsize=(7, 7))
plt.contour(X, Y, Z, alpha=.5)<jupyter_output><empty_output><jupyter_text>C'est à vous !Codez un recuit simulé, en essayant différents paramètres pour:le profil de température ($T_0$ et profil de décroissance);le mouvement local autour d'une position courante.N.B. : eval_boulders(x,y) renvoie la valeur de la fonction au point (x,y)  À chaque itération, remplissez un tableau 2D `parcours` avec un tableau de quatre variables :```pythonparcours = [] boucle du recuit simuléfor ...:     une itération    parcours.append([x_current, y_current, x_best, y_best])````x_current, y_current` représentent la position d'un point à une itération donnée, et `x_best, y_best` la position du point qui a s'évalue de manière minimale entre l'itération 0 et l'itération courante. Les cellules suivantes créent alors une animation qui représente la convergence de votre algorithme sur les contours tracés ci-dessus.Il peut être pertinent d'afficher un graphe avec l'évolution:- de l'évaluation de chacun des éléments du parcours de votre algorithme de recuit simulé;- de la meilleure évaluation rencontrée jusqu'à l'itération courante.<jupyter_code># %load solutions/01-parcours.py

# à exécuter une fois que vous aurez rempli `parcours`

from stochastic.display import sa_animation

fig = plt.figure(figsize=(7, 7))
ax = fig.add_axes([0,0,1,1], frameon=False, aspect=1)
ax.contour(X, Y, Z, alpha=.5)

sa_animation(fig, ax, parcours)<jupyter_output><empty_output><jupyter_text>Graphes de VoronoiPetit passage par Wikipedia:> Un **diagramme de Voronoi** est un découpage du plan (pavage) en cellules à partir d'un ensemble discret de points appelés « germes ». Chaque cellule enferme un seul germe, et forme l'ensemble des points du plan plus proches de ce germe que de tous les autres. La cellule représente en quelque sorte la « zone d'influence » du germe.Note: Un diagramme de Voronoi est lié à une triangulation de Delaunay par une relation de dualité. (cf. tout plein d'exemples sur le net)La classe `Voronoi` vous est fourni dans la librairie `stochastic` qui accompagne le cours. `nb_points` représente le nombre de germes et `nb_colors` un nombre de couleurs parmi lesquelles effectuer un tirage aléatoire de couleurs pour chacun des germes.Un exemple de programme vous est fourni ici. Le principe d'utilisation est d'hériter de cette classe avant de coder des callbacks. Dans l'exemple ci-dessous, on code les callbacks `on_mouse_move` (qui fait réagir l'affichage à un mouvement de la souris) et `on_mouse_press` (qui fait réagir l'affichage à un clic de souris).La callback `on_mouse_move` capture la position de la souris pour faire bouger un des germes (celui d'indice `self.current`). Un clic de souris incrémente l'indice `self.current`. On peut récupérer la position des germes par le *getter* `self.points` et positionner les germes par le même *setter*. **Attention à bien faire une copie du tableau Numpy (`np.array(self.points)`) avant de la modifier.**Vous pouvez faire bouger la souris pour avoir une intuition du comportement d'un diagramme de Voronoi.<jupyter_code># %load 01-voronoi_mouse.py<jupyter_output><empty_output><jupyter_text>Exercice: L'idée du deuxième exercice est de bouger les germes de sorte à équilibrer la présence de chaque couleur dans l'image résultante.Pour cela, créez une nouvelle classe qui hérite de `stochastic.voronoi.Voronoi` et codez la méthode `on_timer(self, event)` qui sera appelée à chaque pas de temps. Une méthode `self.eval()` vous est fournie: elle est basée sur l'[entropie de Shannon](https://fr.wikipedia.org/wiki/Entropie_de_Shannon). Elle est maximale quand une seule couleur est présente dans l'image et décroît quand chaque couleur devient autant représentée que les autres, pour s'annuler quand chacune des $k$ couleurs occupe exactement $\frac{1}{k}$ de la surface totale de l'image.**Conseils**:- bien réfléchir à la définition d'un mouvement local d'une solution ;- commencer par afficher les valeurs de la fonction d'évaluation pour avoir une appréhension d'un bon profil de température ;- tester avec 2 points et 10 couleurs ;    *On choisit 10 couleurs pour s'assurer d'en avoir deux différentes.*- tester avec 3 points et 2 couleurs ;    *L'idée est d'avoir deux points qui ont la même couleur.*- tester avec 10 points et 3 couleurs.    *L'idée est d'avoir certaines couleurs avec peu de germes et d'autres avec beaucoup de germes représentant.*<jupyter_code># NE CODEZ PAS ICI, OUVREZ UN NOUVEAU FICHIER .py POUR ÉCRIRE VOTRE PROGRAMME<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07238805970149254, 'fraction_numerical': 0.007611940298507463, 'mean_word_length': 5.3456439393939394, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 23, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '196365', 'license': 'MIT', 'n_tokens_mistral': 2258, 'n_tokens_neox': 2231, 'n_words': 889, 'path': 'notebooks/01-simulated_annealing.ipynb', 'repo_name': 'pchtsp/metaheuristics', 'size': '6700'}