Optimisation Inspirée par la Nature

Piste rouge Le 9 octobre 2018  - Ecrit par  Carola Doerr Voir les commentaires

Algorithmes “naturels” de recherche d’optimum

De nombreux problèmes de mathématiques et d’informatique appliquées se ramènent à l’optimisation (maximisation ou minimisation) d’une certaine fonction : que ce soit dans la vie quotidienne (recherche de plus court chemin, création d’emploi du temps pour les écoles, affectation des étudiants aux universités et aux matières...), ou encore dans les processus économiques et industriels (conception d’équipement économes en énergie comme ceux des turbines, des voitures ou des éoliennes ; disposition et horaires d’un réseau de transports ; découverte de traitements médicaux appropriés à des maladies complexes ; etc...). La plupart de ces problèmes sont trop complexes pour admettre une solution analytique, c’est à dire que leur trouver une solution optimale est souvent impossible en un temps raisonnable. De plus, ils nécessitent souvent de prendre un grand nombre de décisions simultanées, donc une évaluation exhaustive de toutes les combinaisons possibles n’est pas envisageable : par exemple, planifier ’sport’ pour la classe 1 le lundi matin a une influence sur la disponibilité de la salle de gymnastique et sur les professeurs de sport de toutes les classes de cette école. On voit qu’une tentative de lister toutes les possibilités donnera lieu à une croissance incontrôlable de la complexité. En pratique, ces problèmes sont résolus par des algorithmes dits meta-heuristiques (ou heuristiques) qui recherchent un optimum en privilégiant la simplicité de calcul à l’exactitude de la solution : plutôt que de chercher une solution optimale, on se contente d’une solution satisfaisante ou pour le moins aussi bonne que possible.

Plusieurs heuristiques très populaires s’inspirent de phénomènes naturels, comme les processus physico-chimiques liés au refroidissement des matériaux, le comportement des animaux, ou encore l’évolution des espèces. Les lecteurs fidèles de l’Objet du mois se rappellent certainement de l’aptitude étonnante du physarum à trouver son chemin dans les labyrinthes [Goa17].

Le fonctionnement des méta-heuristiques est itératif (voir la figure 1) : à chaque étape ils génèrent une ou plusieurs solutions possibles, évaluent la qualité de ces points de recherche, et mettent à jour en temps réel la stratégie pour en trouver de nouveaux. Ce processus continue jusqu’à ce qu’un certain critère d’arrêt soit satisfait : ou bien une solution de qualité satisfaisante a été trouvée, ou bien le temps de recherche alloué a été atteint, ou bien aucun progrès significatif n’a eu lieu lors des dernières itérations. Nous allons évoquer dans cet article certains des plus connus de ces algorithmes : recherche locale, recuit simulé, et algorithmes génétiques (également appelés évolutionnistes).

PNG - 57.6 ko
Figure 1 – Schéma d’une heuristique de recherche randomisée pour l’optimisation d’une fonction f : S → R.

Le Problème du Mastermind

Pour illustrer ces idées dans un cadre mathématique raisonnable, nous allons considérer le problème de la résolution du Mastermind. Si ce nom vous est inconnu, sachez qu’il s’agit d’un jeu de plateau qui a eu son heure de gloire dans les années 70 et 80, et qui figure encore en bonne place dans les magasins de jouets de la plupart des pays occidentaux. Il se joue à deux : le premier joueur (le codeur) choisit un code couleur secret, et le deuxième (le décodeur) doit le deviner en utilisant le moins possible de tentatives. Chaque tentative est un code du même type que celui recherché, et à chaque fois le codeur indique un score, qui est le nombre de couleurs se trouvant dans la bonne position. Par exemple si le code choisi par le premier joueur est Bleu-Vert-Rouge-Blanc et que le deuxième joueur propose la combinaison Jaune-Vert-Bleu-Blanc, le score obtenu est 2.
(Dans le jeu original le codeur indique également le nombre de couleurs correctes mais situées en mauvaise position. Par souci de simplicité nous négligerons cet aspect du jeu dans la suite.)

JPEG - 40 ko
Figure 2 – Le Mastermind

Même s’il est sûrement moins connu des mathématiciens que
le Rubik’s Cube, le Mastermind a été mathématiquement étudié
sous divers aspects (voir [DDST16] pour un aperçu de quelques résultats
et problèmes ouverts). Les mathématiciens hongrois Paul Erdős et
Alfréd Rényi [ER63] ont par exemple considéré le cas où il n’y a que
deux couleurs (disons rouge et bleu) et cherché une stratégie optimale pour le décodage. Plus précisément, ils ont analysé le nombre
de tentatives nécessaires en fonction de la longueur du code. De
manière surprenante, ils ont montré que doubler la longueur du
code n’implique pas nécessairement un doublement du nombre de
tentatives et trouvé une stratégie significativement plus efficace :
Grosso modo, l’algorithme inventé par Erdős et Rényi requiert en moyenne environ $\frac{2n}{\log_2 n}$ tentatives pour un code de longueur $n$ [1] ($\log_2$ est le logarithme binaire, c’est à dire le nombre $t$ tel que $2^t = n$, par exemple $ \log_2 1024 = 10$). Il a été démontré que cette stratégie est essentiellement optimale. Inversement, pour le jeu original qui comporte plus de deux couleurs, on ne sait toujours pas quelle est la borne.

Détail 1 : un cas particulier important.

Dans le cas où le nombre de couleurs est égal à la longueur $n$ du code, la meilleure stratégie connue requiert en moyenne $Dn \log_2(log_2 n)$ essais pour une certaine constante $D$, et d’un point de vue théorique on sait qu’il faut en moyenne au moins $Cn$ essais ($C$ une certaine constante) pour résoudre le Mastermind (voir [DDST16] pour plus de détails).

L’algorithme d’Erdős et Rényi est très spécifique au Mastermind, et donc n’est que peu d’utilité pour les autres problèmes d’optimisation, sans parler des problèmes complexes issus de situations réelles. À l’inverse, les heuristiques d’optimisation inspirées par la nature sont peut-être moins efficaces pour résoudre le Mastermind, mais peuvent êtres appliquées dans de nombreuses situations : on peut les qualifier d’heuristiques d’application générale.

Que donnent les heuristiques générales sur le problème du Mastermind ?

Pour comprendre l’efficacité des algorithmes généraux sur le problème du Mastermind, il faut d’abord comprendre pourquoi il s’agit bien d’un problème d’optimisation. Pour simplifier, nous utiliserons encore une fois la version du Mastermind qui n’a que deux couleurs, rouge et bleu. Soit $n$ la longueur du code. Ce nombre est connu du décodeur, qui va donc proposer des solutions de même longueur. Si on assigne la valeur 0 à la couleur rouge et 1 au bleu, le code secret devient une séquence de bits $z = (z_1,...,z_n)$. Les tentatives sont des séquences du même type (voir la figure 3). Pour toute tentative $x = (x_1, . . . , x_n)$ proposée par le décodeur, le codeur calcule le nombre de positions en lesquelles les deux séquences coïncident. Le score s’exprime donc formellement par une fonction $f_z$ qui donne à chaque tentative de code $x$ le score
\[f_z(x) = |\{i ∈ \{1,2,...,n\} | x_i = z_i\}|.\] Trouver le code $z$ revient alors à maximiser la fonction $f_z$, qui est une fonction de $\{0,1\}^n$ dans
$\{0,1,2,...,n\}$. L’unique solution optimale est $z$, qui atteint le score $f_z(z) = n$.

PNG - 15.7 ko
Figure 3 – Exemple pour un Mastermind avec deux couleurs

Exemple 1 : recherche locale randomisée. Notre premier exemple est la plus simple des heuristiques de recherche, la recherche locale randomisée (« RLS » pour randomized local search).
L’algorithme RLS démarre par une séquence $x=(x_1,\ldots,x_n)$ choisie au hasard et demande le score associé à cette
séquence. Puisque pour chaque position la probabilité de trouver la bonne couleur est $1/2$, le score moyen de cette
première tentative est $n\cdot 1/2 =n/2$. Pour optimiser $f_z$, RLS procède par étapes. À chaque étape, il crée un nouveau code $y$ en choisissant une position aléatoire $i \in \{1,2,\ldots,n\}$ et en inversant la couleur (i.e. la valeur
du bit) en cette position. Il demande alors le score de $y$. Dans un deuxième temps, l’algorithme doit décider
avec quelle séquence il souhaite continuer la recherche :
en bon exemple d’ algorithme glouton, RLS choisit celle qui a le score le plus élevé et oublie la solution précédente qui est moins bonne. Remarquer qu’on
a forcément $f_z(x)>f_z(y)$ ou $f_z(y)>f_z(x)$, puisque on a soit $x_i=z_i$, soit $y_i=z_i$.

Il est ici intéressant
d’introduire la distance de Hamming \[H(x,y):=|\{i\in \{1,2,\ldots,n\} \mid x_i \neq y_i \}|,\] qui est le nombre de positions en lesquelles les deux séquences diffèrent.
On voit que la distance de
Hamming entre l’ancien et le nouveau code est 1 : $y$ est voisin de $x$, d’où la qualification d’algorithme
local.

L’analyse du nombre moyen d’étapes nécessitées par RLS pour aboutir à la solution ressemble à un autre problème
classique en informatique, celui du collectionneur de coupons. En termes concrets ce problème étudie
combien de vignettes doit acheter un collectionneur de vignettes
Panini pour remplir l’album de la Coupe du Monde 2018.
On suppose qu’il achète successivement des vignettes choisies aléatoirement un ensemble de
$n$ vignettes (et qu’il ne fait pas d’échanges avec d’autres collectionneurs). Ce problème est très bien compris
et on sait que le nombre moyen de vignettes qu’un collectionneur doit acheter est approximativement
$n\ln(n)+ 0.577 n$, où $\ln(n)=\log_e(n)$ est le logarithme neperien (ou naturel),
c’est à dire le nombre $t$ tel que $n=e^t$ (où $e\approx 2,718$).

Détail 2 : Le problème du collectionneur de coupons.

Pour comprendre cette analogie, numérotons les différentes vignettes de 1 à $n$. Identifions maintenant les vignettes que notre collectionneur possède déjà avec
les positions $i$
où notre meilleure tentative $x=(x_1,\ldots,x_n)$ coïncide avec le code secret $z=(z_1,\ldots,z_n)$. Inverser un bit aléatoire revient à acheter une nouvelle vignette. Si le collectionneur
ne la possède pas déjà, il l’ajoute à sa collection. Ceci correspond à la situation où une position $i$ telle que
$x_i \neq z_i$ a été choisie. Après l’échange du bit $i$, on a $y_i=z_i$, et donc $f_z(y)=f_z(x)+1$. Ainsi le score de $y$
est supérieur à celui de $x$, et donc RLS continue sa recherche avec le code $y$. La différence entre les deux
problèmes est la situation initiale : dans le cas du Mastermind, RLS démarre typiquement avec un score de $n/2$
alors que le collectionneur de vignettes démarre avec un score de 0. Il est amusant d’observer que malgré cette
différence, le nombre moyen d’étapes nécessaires pour chacun des deux problèmes est sensiblement le même. [2] .
Combien de vignettes faut il acheter pour compléter la collection ? Supposons que notre collectionneur possède
$k$ vignettes différentes, où $k$ est compris entre 0 et $n-1$. Il lui reste donc $n-k$ vignettes à collecter.
La probabilité qu’il en obtienne une à son prochain achat est $(n-k)/n$. Donc en moyenne, il lui faut en acheter $n/(n-k)$
pour en ajouter une à sa collection. Puisqu’il a démarré avec 0 vignette, on voit que le nombre moyen de vignettes
qu’il devra acheter est \[\sum_{k=0}^{n-1}{n/(n-k)} = n \sum_{k=1}^{n}{1/k} = n H(n)=O(n \ln n),\] où
$H(n)$ est le $n$-ème nombre harmonique, i.e. $H(n)=\sum_{k=1}^n{\tfrac{1}{k}}$, qui vaut environ
$\ln(n)+0.577$.

Pour un album de 50 vignettes, il faut donc en acheter en moyenne $50\cdot \ln(50) + 0.577\cdot 50 \approx 224$ (car
$\ln(50)\approx 3.91$). Pour l’album Panini de la Coupe du Monde 2018, qui comporte 682 vignettes différentes,
ce nombre s’élève à $682 \cdot \ln(682) + 0.577\cdot 682 \approx 4843$ ! De même, le nombre d’itérations nécessaires à RLS pour trouver un code Mastermind de longueur 682 est d’environ 4843. En comparaison, la stratégie d’Erdős et Rényi ne requiert que 145 étapes
(mais beaucoup plus de puissance de calcul !).

On voit que RLS fait beaucoup moins bien qu’un algorithme taillé sur mesure pour le Mastermind. Une modification
évidente qui améliore considérablement ses performances consiste à ne pas toucher aux bits qui
ont déjà été inversés lors d’une étape précédente. Avec cette idée, même dans dans le pire des cas où toutes les couleurs initiales sont incorrectes, on a besoin d’au plus
682 essais. Ceci est une particularité du problème du Mastermind, qui est séparable au sens où toutes les décisions i.e., quelle couleur mettre à chaque position, peuvent être prises indépendamment. En d’autres termes la qualité d’une décision
donnée ne dépend pas de celle des autres décisions : en effet si l’on choisit $x_i=0$, cela ne contribuera au score
$f_z(x)$ que si $z_i=0$, indépendamment du score du reste du code. La plupart des problèmes issus du monde
réel ne sont malheureusement pas séparables, donc cela peut avoir du sens de revenir sur une
décision prise précédemment.

On peut toujours espérer qu’une heuristique générale puisse résoudre le Mastermind plus efficacement que RLS, nous reviendrons sur ce point un peu plus loin.

D’autres algorithmes de recherche heuristique

On peut s’interroger sur le caractère “inspiré par la nature” du RLS, même s’il entre bien dans le cadre du schéma de la figure 1. Nous allons discuter quelques autres exemples plus clairement d’inspiration naturelle. Remarquons d’abord que le RLS finit toujours par trouver le code secret au Mastermind : en effet

  • une séquence ne peut être remplacée que par une nouvelle séquence strictement plus proche de la solution $z$
  • si $x$ n’est pas la bonne solution, l’algorithme finira toujours par trouver un bit où $x$ et $z$ diffèrent.

Comme on l’a déjà dit, les problèmes d’optimisation réels ne sont pas aussi basiques que le Mastermind. Le principal défi que doivent surmonter les algorithmes de recherche heuristique est de rester coincé près de solutions ayant l’apparence de l’optimalité sans pouvoir s’en échapper. Les points $x$ ayant la propriété que tous leurs voisins sont inférieurs s’appellent des optima locaux. On voit que par principe la présence d’optima locaux peut être fatale au RLS.

On peut mettre en place plusieurs stratégies pour surmonter cette difficulté (voir figure 4) : accepter temporairement de moins bonnes solutions, augmenter le rayon de recherche, ou bien faire une recherche globale.

PNG - 29.2 ko
Figure 4 – Trois stratégies pour échapper à un optimum local
  • accepter de moins bonnes solutions. L’idée est de ne pas être trop gourmand dans la sélection des points de recherche que l’on garde en mémoire. Un algorithme basé sur cette idée ne conserve pas seulement la meilleure solution
    mais peut également décider de continuer sa recherche autour d’une moins bonne solution. Une analogie possible avec la nature est l’observation suivante : il se peut qu’un gène muté soit a priori désavantageux pour un individu mais s’avère bénéfique par la suite, par exemple lors d’une modification de l’environnement.
    Les algorithmes les plus connus utilisant cette idée sont le recuit simulé [KGV83], l’algorithme de Metropolis [MMR+53], et Threshold Accepting [DS90]. [3]

Détail 3 : La sélection moins gourmande.

La sélection des nouvelles solutions dans ce type d’algorithme se fait selon un certain seuil : une nouvelle solution $y$
est préférée à une solution $x$ d’une étape précédente si elle satisfait $f(y)-f(x) \ge T$, où $T$ est un certain seuil négatif. On prend alors en général une décision aléatoirement, et la probabilité d’accepter la nouvelle solution $y$ dépend
de sa qualité. Par exemple pour les algorithmes de type Metropolis, la probabilité de garder la solution $y$ est
$\min\{ 1, \exp(-(f(x)-f(y))/T) \}$. L’analogie de cette formule avec la mécanique statistique n’est pas fortuite, et le paramètre $T$ s’appelle la température de l’algorithme. Pour le recuit simulé, on diminue la température au cours du temps, de sorte que l’algorithme devient de plus en plus glouton. L’idée est qu’il va dans un premier temps explorer largement l’espace de recherche avant de s’affiner et converger vers un optimum.

  • augmenter le rayon de recherche. Lorsque l’on ne peut pas faire de progrès en explorant le voisinage direct, ou lorsqu’on imagine que les optima ne se trouvent pas à proximité, on peut tenter de chercher à plus grande distance. Pour le Mastermind, cela revient à modifier plusieurs couleurs à la fois. Cette idée est utilisée par les algorithmes de recherche à rayon d’action variable. Il faut alors mettre en place une procédure tirant parti des étapes passées pour décider jusqu’à quelle distance on décide de chercher. Une analogie que l’on trouve dans la nature est l’exemple suivant : quand un chat est relâché dans un environnement inconnu, il va chercher sa maison en marchant en cercles de plus en plus grands.
  • algorithmes globaux. Plutôt que de changer de rayon de recherche au cours du temps, une autre idée consiste à conserver pour tout point de l’espace de recherche (qui n’a pas déjà été testé) une probabilité non nulle d’être choisi. Cette probabilité n’est pas uniforme et dépend en général de la distance aux solutions précédentes.
    Une application célèbre de cette idée est la mutation de bits standard qui comme son nom l’indique s’inspire de la mutation des séquences d’ADN où à chaque étape du processus de reproduction un nombre aléatoire de mutations peuvent avoir lieu. On peut alors parler d’algorithmes génétiques. Pour le Mastermind cela consiste à créer une nouvelle séquence en inversant pour chaque position dans la séquence le bit avec probabilité $p$ et en ne l’inversant pas
    avec probabilité
    $1-p$. Si ce taux de mutation est fixé à $p= 1/n$, le nombre moyen de couleurs qui sont changées à chaque
    étape est $np=1$ et l’algorithme se comporte comme RLS (mais avec une aptitude à échapper aux optima locaux en faisant de parfois de grands « sauts »).

Quelle efficacité pour le problème du Mastermind ?

On peut montrer [DDY16],[LW12] que pour le problème du Mastermind, on ne peut pas améliorer significativement les performances en remplaçant l’algorithme RLS par une des méthodes mentionnées ci dessus. Il y a en revanche une autre idée inspirée par la génétique qui est très efficace pour ce problème : la recombinaison (voir Figure 5).

PNG - 20.4 ko
Figure 5 – Deux types de crossover souvent utilisés dans la pratique

Il s’agit ici d’engendrer de nouvelles séquences candidates en combinant plusieurs candidats précédents. La question de l’utilité de la recombinaison dans les algorithmes d’optimisation inspirés par la nature est ancienne et controversée. Pour le Mastermind il a été rigoureusement démontré que certains algorithmes basés sur la recombinaison ont de meilleures performances que tous les algorithmes dérivés de RLS.

Détail 4 : un algorithme de recombinaison avec complexité linéaire.

Un algorithme résolvant le problème du Mastermind avec deux couleurs en temps linéaire, c’est à dire majoré par $Cn$ où $C$ est une
constante (inconnue à ce jour) a été introduit dans [DDE14], [DD18]. En contrepartie, un algorithme basé uniquement sur des mutations randomisées nécessite au moins $Cn\log n$ tentatives pour résoudre le Mastermind à 2 couleurs. Notre algorithme montre donc que même pour des problèmes relativement simples (i.e. sans optima locaux), l’idée de recombinaison apporte des améliorations significatives.

L’algorithme ne garde en mémoire
qu’une tentative précédente $x$. L’itération se fait en deux étapes : une étape de mutation et une étape de recombinaison.
À la première étape, un certain nombre $\lambda$
de nouveaux candidats sont engendrés par mutation standard. On sélectionne le meilleur de cette descendance et on le recombine $\lambda$ fois avec son parent $x$. Parmi cette nouvelle descendance, on ne sélectionnera le meilleur
candidat que si son score est au moins aussi bon que celui de $x$.

Et les maths dans tout ça ?

On l’a vu, une caractéristique commune à tous ces algorithmes est l’intervention des probabilités :
le choix des points stockés dans la mémoire ainsi que la création de nouveaux candidats peut dépendre de décisions aléatoires.
Ainsi la suite des candidats obtenus $\big(x^{(0)},x^{(1)}, \ldots, x^{(t)}\big)$ jusqu’au temps $t$ est une suite de
variables aléatoires
. Bien sûr $x^{(t)}$ dépend fortement de tous les candidats précédents. L’analyse de ces processus est mathématiquement difficile, et on ne peut pas espérer pour le moment une caractérisation
mathématiquement rigoureuse des meilleurs algorithmes heuristiques de recherche.

L’analyse des heuristiques randomisées est pour le moment restreinte à des modèles simplifiés et quelque peu artificiels, qui visent à comprendre les performances typiques de ces heuristiques sur des problèmes réels. En revanche, la vraie force des heuristiques inspirées par la nature est qu’elles peuvent effectivement résoudre de nombreux problèmes qui sont hors d’atteinte de la rigueur mathématique.

Toutefois l’analyse mathématique
de ces algorithmes est utile car elle offre des informations qu’une simple analyse empirique ne saurait fournir
et s’applique souvent à toute une classe de problèmes. Elle permet également
de donner des bornes théoriques à l’efficacité maximale que l’on peut espérer et ainsi savoir si les algorithmes formant
l’état de l’art peuvent encore être améliorés.

Finalement, l’analyse mathématique de ces heuristiques offre un point de vue complémentaire à celui, plus pragmatique, des ingénieurs et de nouvelles idées qui permettent d’améliorer leur efficacité.

Références

[DD16] Benjamin Doerr and Carola Doerr. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica, 75 :529–553, 2016.

[DD18] Benjamin Doerr and Carola Doerr. Optimal static and self-adjusting parameter choices for the (1 + (λ, λ)) genetic algorithm. Algorithmica, 80 :1658–1709, 2018.

[DDE15] Benjamin Doerr, Carola Doerr, and Franziska Ebel. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 567 :87–104, 2015.

[DDST16] Benjamin Doerr, Carola Doerr, Reto Spöhel, and Henning Thomas. Playing Mastermind with many colors. Journal of the ACM, 63 :42 :1–42 :23, 2016.

[DDY16] Benjamin Doerr, Carola Doerr, and Jing Yang. Optimal parameter choices via precise black-box analysis. In Proc. of Genetic and Evolutionary Computation Conference (GECCO’16), pages 1123–1130. ACM, 2016.

[DS90] Gunter Dueck and Tobias Scheuer. Threshold accepting : A general purpose optimi- zation algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90 :161 – 175, 1990.

[ER63] Paul Erdős and Alfréd Rényi. On two problems of information theory. Magyar Tu- dományos Akadémia Matematikai Kutató Intézet Közleményei, 8 :229–243, 1963.

[Goa17] Xavier Goaoc. Calculer sans neurone. Images des Mathématiques, CNRS, 2017.


[KGV83] Scott Kirkpatrick, C. D. Gelatt, and Mario P. Vecchi. Optimization by simulated annealing. Science, 220 :671–680, 1983.


[LW12] Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica, 64 :623–642, 2012.

[MRR+53] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth,
Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21 :1087–1092, 1953.

Post-scriptum :

L’auteur remercie chaudement Romain Dujardin pour avoir suggéré d’écrire cet article, pour ses suggestions d’amélioration et sa traduction. L’auteur tient aussi à remercier Nathan Buskulic pour sa relecture et ses suggestions et les secrétaires de rédaction pour leur aide avec l’éditeur de texte.

La rédaction d’Images des maths, ainsi que l’auteur, remercient également pour leur relecture attentive, les relecteurs suivants : Daniel Massart, janpol3, Claire Wenandy et François Guéritaud.

Article édité par Romain Dujardin

Notes

[1Ce résultat n’est pertinent que quand $n$ est très grand : en bons mathématiciens, Erdős et Rényi ont considéré un Mastermind où la longueur du code tend vers l’infini !

[2Plus précisément la différence est asymptotiquement d’1/2étape ! (cf [DD16].)

[3L’article original introduisant la méthode du recuit simulé a été cité à ce jour (juin 2018) plus de 43500 fois, ce qui atteste vraisemblablement d’une certaine efficacité. La terminologie “recuit simulé” vient d’une analogie avec certains processus de refroidissement utilisés en métallurgie, passant par des périodes successives de réchauffement et de refroidissement permettant un alignement optimal des atomes et par là une meilleure solidité.

Partager cet article

Pour citer cet article :

Carola Doerr — «Optimisation Inspirée par la Nature» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM