Variante HTML animée - la version du cours est ici

SIMULATED
ANNEALING

Un algorithme d'optimisation

Une descente de gradient

Le simulated annealing (refroidissement simulé) est un algorithme intuitif qui permet de rechercher et possiblement trouver le minimum global d'une courbe.

On peut aussi, inversement, rechercher le maximum global d'une courbe.

Recherche de minimum dans points

let minimumY = points[0]; let minimumX = 0; for (let x in points) { let y = points[x]; // est-ce que ce point est plus bas ? if (y < minimumY) { minimumY = y; minimumX = x; } }
Quel est donc l'algorithme ? On le rédige ensemble en classe.

D'une boucle for à un pas par tick

L'algorithme classique : tout d'un coup
for (let x in points) { let y = points[x]; if (y < minimumY) { minimumY = y; minimumX = x; } } // fini : la reponse est prete
Dans p5.js : un pas par image
// draw() appelle update() 60x/seconde update() { this.x = this.avancer(); this.y = this.points[this.x]; this.rechercher(); } // un seul tour de boucle par image !
La boucle disparaît : c'est draw() qui la remplace, une itération à la fois.

Où sont passés les morceaux de la boucle ?

Dans la boucle forDans le skieur
let x = 0 (l'initialisation)initialiser(), appelée une seule fois
x++ (l'incrément)avancer() : retourne la prochaine position
le corps if (y < minimumY)rechercher() : juste la comparaison
x < points.length (la condition)un drapeau this.trouve testé dans avancer()
avancer() { // le drapeau remplace la fin de la boucle if (this.trouve) { return this.x; // on ne bouge plus } if (ma condition d'arret) { this.trouve = true; // on leve le drapeau return this.x; } return this.x + this.saut; } rechercher() { if (this.y < this.minY) { // juste la comparaison this.minY = this.y; this.minX = this.x; } }

Recherche de minimum = VERSION COMPLÈTE

Un algorithme systématique de taille N : on vérifie TOUS les POINTS et on retient le vrai minimum.

On trouve le vrai minimum, mais le temps d'exécution est long. Ce n'est pas de l'IA.

0 point visité
Tous les points ont été analysés : c'est le vrai minimum !

VERSION VOISINS : s'arrêter quand ça remonte

On descend en comparant au point voisin, jusqu'à ce que les points voisins remontent.

Dépendant du point de départ, on se retrouve pris dans la première anfractuosité de la courbe.

0 point visité
L'algo pense avoir trouvé le minimum !

VERSION VOISINS : tolérer une petite remontée

Même chose, mais plus tolérant : on continue tant que la remontée ne dépasse pas une certaine distance.

On franchit les petites bosses, mais dépendant du point de départ on reste pris dans un minimum local.

0 point visité
L'algo pense avoir trouvé le minimum !

VERSION HASARD : le hasard seul

Un algorithme semi-systématique, avec du hasard ajouté : on saute partout et on garde le plus petit, jusqu'à ce qu'un certain nombre d'itérations soit effectué.

Dépendant des points générés, on ne se retrouve pas dans le creux du minimum mais dans une pente.

0 point visité
L'algo pense avoir trouvé le minimum !

VERSION HASARD : le refroidissement simulé

Le hasard ajouté est de plus en plus petit : on se concentre sur la recherche alentour des points les plus bas.

Comme on cherche des ressources en forêt après avoir trouvé les premiers indices.

On identifie la zone du minimum global, puis on converge dedans.

0 point visité
L'algo a peut-être trouvé le minimum !

Les 4 stratégies sur la même montagne

COMPLÈTE trouve le vrai minimum, mais visite les 620 points
VOISINS piégée dans la première anfractuosité
HASARD seul explore partout, finit sur une pente
HASARD + refroidissement repère la zone, puis converge dedans

Le lapin saoul

"We can think of SA as the following scenario: a drunk rabbit jumps randomly as she wants to reach the hill top. As she wakes up gradually little by little, she walks steady to the hill top…" - justyyuk (Github)
Le hasard du début, c'est l'ivresse. Le refroidissement, c'est le réveil.

C'EST QUOI LE
REFROIDISSEMENT ?

C'est quand la quantité de hasard utilisée par l'algorithme diminue avec le temps…

Refroidissement simulé = simulated annealing

let rayon = points.length; // la fenetre couvre tout let minimumX = 0; let minimumY = points[minimumX]; while (rayon >= 1) { rayon = rayon * 0.99; // le refroidissement ! // la fenetre suit le meilleur point trouve let x = hasardEntre(minimumX - rayon, minimumX + rayon); if (points[x] < minimumY) { minimumY = points[x]; minimumX = x; } }
Quel est donc l'algorithme ? On le rédige ensemble en classe.

Pourquoi c'est si important ?

  • 🎛️ Le refroidissement simulé permet d'optimiser toutes sortes de variables, et même des combinaisons de variables.
  • 🧊 On peut imaginer une recherche dans un plan 3D pour son minimum. On peut ajouter des dimensions…
  • 💰 Les valeurs à minimiser ou maximiser peuvent être des coûts, des revenus, des distances, des ressources, etc.

Application de la minimisation

🧳 Traveling salesman problem

Un problème pédagogique pour tester les algorithmes d'optimisation : étant donné une liste de villes et les distances entre chaque paire, quel est le plus court chemin qui visite chaque ville une fois et revient au point de départ ?

Démo JS

🍁 Canadian traveller problem

Un problème de plus court chemin qui révèle la carte à mesure de l'exploration : on découvre les routes bloquées seulement en arrivant dessus.

🖼️ Optimisation d'images

Recomposer une image avec un nombre limité de formes, en minimisant l'écart avec l'original.

Démo nayuki Démo levibyte

🧪 Et bien d'autres

Horaires, placement de composants, routage, entraînement de modèles : partout où l'espace des solutions est trop grand pour tout vérifier.

Le projet de vjeux

L'animation de référence

L'animation classique du hill climbing avec simulated annealing : on la regarde ensemble et on observe le hasard qui diminue.

▶ L'animation (Wikipedia) L'article Simulated annealing

Références

katrinaeg.com : simulated annealing codeheir : what is simulated annealing Wikipedia CMU : simulated annealing artint.info La librairie npm helloacm : la librairie en démo ⬇ Le diaporama original (pptx)

Les anciens noms (V0 à V4)

Les versions s'appelaient V0 à V4 les sessions précédentes. Si vous avez commencé avec ces noms-là, voici la correspondance - les deux nomenclatures sont acceptées à la correction.

Ancien nomNouveau nomPoints
V0 : tout vérifierVERSION COMPLÈTE1
V1 : s'arrêter quand ça remonteVERSION VOISINS
(une des deux au choix)		2
V2 : tolérer une petite remontée
V3 : ajouter du hasardVERSION HASARD (hasard seul)1
V4 : le refroidissement simuléVERSION HASARD (complète)2

À VOS MONTAGNES !

L'énoncé du laboratoire : intelligence.projet.autos/labo-gradients