En algorithmique, le recuit simulé est une méthode empirique (métaheuristique) d'optimisation, inspirée d'un processus, le recuit, utilisé en métallurgie. On alterne dans cette dernière des cycles de refroidissement lent et de réchauffage (recuit) qui ont pour effet de minimiser l'énergie du matériau. Cette méthode est transposée en optimisation pour trouver les extrema d'une fonction. Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983, et indépendamment par V. Černy en 1985. La méthode vient du constat que le refroidissement naturel de certains métaux ne permet pas aux atomes de se placer dans la configuration la plus solide. La configuration la plus stable est atteinte en maîtrisant le refroidissement et en le ralentissant par un apport de chaleur externe, ou bien par une isolation. recuit La description des phénomènes physiques et quantiques liés au processus de recuit s'appuie sur la statistique de Maxwell-Boltzmann. lien=|500x500px Ci-dessus, on donne un exemple de recuit simulé ayant pour but de chercher un maximum. Il n'est pas suffisant d'utiliser un simple algorithme de hill climbing car il y a de nombreux maxima locaux. En refroidissant le matériau lentement, le maximum global peut être trouvé, avec une probabilité assez élevée. Le recuit simulé s'appuie sur l'algorithme de Metropolis-Hastings, qui permet de décrire l'évolution d'un système thermodynamique. Par analogie avec le processus physique, la fonction à minimiser deviendra l'énergie du système. On introduit également un paramètre fictif, la température du système. Partant d'un état donné du système, en le modifiant, on obtient un autre état. Soit celui-ci améliore le critère que l'on cherche à optimiser — on dit alors qu'on a fait baisser l'énergie du système — soit celui-ci le dégrade. Si on accepte un état améliorant le critère, on tend ainsi à chercher l'optimum dans le voisinage de l'état de départ.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (5)
MATH-414: Stochastic simulation
The student who follows this course will get acquainted with computational tools used to analyze systems with uncertainty arising in engineering, physics, chemistry, and economics. Focus will be on s
PHYS-467: Machine learning for physicists
Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practi
CS-450: Algorithms II
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
Afficher plus
Séances de cours associées (35)
Optimisation en ingénierie
Explore les techniques d'optimisation en ingénierie pour résoudre efficacement des problèmes complexes.
Estimateur de Bayes, recuit simulé et EM
Couvre l'estimateur de Bayes, le recuit simulé et la ME pour l'estimation des paramètres.
Maximisation et regroupement des attentes
Couvre l'algorithme de maximisation des attentes et les techniques de regroupement, en mettant l'accent sur l'échantillonnage Gibbs et l'équilibre détaillé.
Afficher plus
Publications associées (150)

Data-driven LPV Disturbance Rejection Control with IQC-based Stability Guarantees for Rate-bounded Scheduling Parameter Variations

Alireza Karimi, Elias Sebastian Klauser

In this paper, the challenge of asymptotically rejecting sinusoidal disturbances with unknown time-varying frequency and bounded rate is explored. A novel data-driven approach for designing linear parameter-varying (LPV) con- troller is introduced, leverag ...
2024

Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets

Daniel Kuhn, Mengmeng Li, Tobias Sutter

We propose a policy gradient algorithm for robust infinite-horizon Markov Decision Processes (MDPs) with non-rectangular uncertainty sets, thereby addressing an open challenge in the robust MDP literature. Indeed, uncertainty sets that display statistical ...
2023

Engineering random spin models with atoms in a high-finesse cavity

Jean-Philippe Brantut

Random spin models play a key role in our understanding of disorder and complex many-body systems. Two all-to-all interacting, disordered models have now been realized using a cavity quantum electrodynamics platform. All-to-all interacting, disordered quan ...
NATURE PORTFOLIO2023
Afficher plus
Concepts associés (26)
Optimisation combinatoire
L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.
Recherche tabou
La recherche tabou est une métaheuristique d'optimisation présentée par Fred W. Glover en 1986. On trouve souvent l'appellation recherche avec tabous en français. Cette méthode est une métaheuristique itérative qualifiée de recherche locale au sens large. L'idée de la recherche tabou consiste, à partir d'une position donnée, à en explorer le voisinage et à choisir la position dans ce voisinage qui minimise la fonction objectif.
Métaheuristique
Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît pas de méthode classique plus efficace. Les métaheuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un optimum global (c'est-à-dire l'extremum global d'une fonction), par échantillonnage d’une fonction objectif.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.