{"id":1933,"date":"2016-02-10T10:01:56","date_gmt":"2016-02-10T09:01:56","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1933"},"modified":"2022-12-03T22:58:54","modified_gmt":"2022-12-03T21:58:54","slug":"recuit-simule","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/annealing-simulates\/","title":{"rendered":"Simulated annealing"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1933\" class=\"elementor elementor-1933\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3ed7051 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3ed7051\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-aa7dd3b\" data-id=\"aa7dd3b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b14a049 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b14a049\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Physical algorithms<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-e0fa98c\" data-id=\"e0fa98c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ee2a618 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ee2a618\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-72f4138\" data-id=\"72f4138\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f1d91ae elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f1d91ae\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Recuit_simul%C3%A9\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6b25a5a5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6b25a5a5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-312860ee\" data-id=\"312860ee\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-653f695e elementor-widget elementor-widget-text-editor\" data-id=\"653f695e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/annealing-simulates\/#Recuit-simule\" >Simulated annealing<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/annealing-simulates\/#Presentation-de-lalgorithme\" >Presentation of the algorithm<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/annealing-simulates\/#Deroulement-de-lalgorithme\" >Sequence of the algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Recuit-simule\"><\/span>Simulated annealing<span class=\"ez-toc-section-end\"><\/span><\/h2><div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Annealing is a metallurgical method making it possible to obtain crystallized solids while avoiding the glass state. Once the metal has melted, the temperature is gradually lowered until it reaches a solid state. To remove all defects, the metal is heated and then cooled, in decreasing temperature steps, until a stable state is reached.<\/div><p style=\"text-align: justify;\">This decreasing step system gave birth to the Metropolis algorithm of 1953 and then to the annealing simulated by IBM in 1983.<\/p><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Presentation-de-lalgorithme\"><\/span>Presentation of the algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">The simulated annealing algorithm, or simulated annealing for English speakers, is therefore the adaptation <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithmic<\/a> of the annealing process.<\/p><div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">The goal is to achieve a stable state of the objective function - a local or global optimum - from a random solution. This state is reached in stages, where the acceptance of a mutation is made according to the &quot;temperature&quot; of the stage.<\/div><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><p>The simulated annealing algorithm successively generates configurations from an initial solution R<sub>0<\/sub> and an initial temperature T<sub>0<\/sub> decreasing with each iteration, until a stable configuration is obtained. The probability of accepting a new configuration is (Metropolis rule):<\/p><ul style=\"text-align: justify;\"><li>1 if the configuration improves the objective function;<\/li><li>exp (diff (E) \/ T) with diff (E) the energy difference and T the temperature; the energy difference is an internal function, depending on the objective function.<\/li><\/ul><\/div><h2 style=\"text-align: justify;\"><span class=\"ez-toc-section\" id=\"Deroulement-de-lalgorithme\"><\/span>Sequence of the algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><p style=\"text-align: justify;\">The annealing algorithm is as follows:<\/p><ol style=\"text-align: justify;\"><li>Take an initial solution R = R<sub>0<\/sub> and an initial temperature T = T<sub>0<\/sub>. The initial state is as for the exact methods, obtained by a <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">heuristic<\/a> (downhill or gluttonous).<\/li><li>Generate a random solution R<sub>(i + 1)<\/sub> in the neighborhood of the current solution:<ol><li>compare R<sub>(i + 1)<\/sub> with R<sub>i<\/sub> according to the Metropolis rule<\/li><li>repeat until a stable solution is found (or after a certain number of iterations)<\/li><\/ol><\/li><li>Decrease the temperature T to a threshold temperature T<sub>min<\/sub>, or have a stable solution.<\/li><\/ol><div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\"><pre> R<sub>0<\/sub>\nT<sub>0<\/sub>\n<b>as long as<\/b> T&gt; T<sub>min<\/sub> <b>and<\/b> E&gt; e<sub>max<\/sub>\n   R<sub>(i + 1)<\/sub> = neighbor (R<sub>i<\/sub>)\n<b>   if<\/b> E (R<sub>(i + 1)<\/sub>) &lt;E (R<sub>i<\/sub>) <b>Where<\/b> random () &lt;P (diff (E) \/ T) <b>so<\/b>\n      accept R<sub>(i + 1)<\/sub>\n   update T\n<b>return<\/b> R<sub>not<\/sub><\/pre><\/div><p style=\"text-align: justify;\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-1988 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/sa.png\" alt=\"Simulated annealing\" width=\"1075\" height=\"579\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/sa.png 1075w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/sa-300x162.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/sa-1024x552.png 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/sa-768x414.png 768w\" sizes=\"(max-width: 1075px) 100vw, 1075px\" \/><\/p><p style=\"text-align: justify;\">Since T is large at the start, many solutions degrading the current solution can be chosen. This makes it possible to escape from a local optimum. The following figure shows the value of the objective function as a function of the parameter vector X. The temperature therefore makes it possible to \u201cskip\u201d less \u201cgood\u201d areas to leave a \u201cvalley\u201d. The balls and signals in the following figure show up to what height the balls can &quot;jump&quot;, that is to say the tolerance of negative variation of the objective function in obtaining a new solution.<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"alignnone wp-image-1979 size-large\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-1024x502.jpeg\" alt=\"Simulated annealing\" width=\"1024\" height=\"502\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-1024x502.jpeg 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-300x147.jpeg 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-768x377.jpeg 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-1536x754.jpeg 1536w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-2048x1005.jpeg 2048w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-1200x589.jpeg 1200w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/image7-1980x972.jpeg 1980w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p><p style=\"text-align: justify;\">If the temperature is low, it is more difficult to escape from a local optimum:<\/p><p style=\"text-align: justify;\"><img decoding=\"async\" class=\"alignnone wp-image-1973 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/img143.png\" alt=\"Simulated annealing\" width=\"551\" height=\"367\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/img143.png 551w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/img143-300x200.png 300w\" sizes=\"(max-width: 551px) 100vw, 551px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Physical algorithms Wiki home page Simulated annealing Annealing is a metallurgical method that allows crystallized solids to be obtained while avoiding the glass state. Once \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":7121,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1933","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1933","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=1933"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1933\/revisions"}],"predecessor-version":[{"id":18379,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1933\/revisions\/18379"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7121"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1933"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}