{"id":1073,"date":"2023-10-24T10:15:36","date_gmt":"2023-10-24T10:15:36","guid":{"rendered":"https:\/\/uneedtalk.com\/config\/tredword\/?page_id=1073"},"modified":"2023-12-01T13:13:28","modified_gmt":"2023-12-01T13:13:28","slug":"5-2-simulated-annealing","status":"publish","type":"page","link":"https:\/\/radi-cal.org\/method\/5-2-simulated-annealing\/","title":{"rendered":"5.2. Simulated annealing"},"content":{"rendered":"<div class=\"row\"  id=\"row-579033535\">\n<div class=\"col medium-6 small-12 large-6\"  ><div class=\"col-inner\"  >\n<h1>5.2. Simulated annealing<\/h1>\n<p>Simulated annealing is a probabilistic optimisation method proposed in 1983 by Kirkpatrick et al. (1983). However, the main idea behind the algorithm dates back significantly longer to a key paper by Nicholas Metropolis in the year 1953 (Metropolis et al., 1953). The combinatorial optimisation method allows finding the minima (or maxima) of functions that depend on a large number of variables. Thermodynamical observations have inspired the method, and an actual annealing process can serve as an illustrative example to explain its principles. It is commonly known that perfectly symmetrical single crystals can be grown from a melt or a saturated solution. While we are used to this fact, it is <\/p>\n<\/div><\/div>\n<div class=\"col medium-6 small-12 large-6\"  ><div class=\"col-inner text-center\"  >\n\t<div class=\"img has-hover x md-x lg-x y md-y lg-y\" id=\"image_715153574\">\n\t\t\t\t\t\t\t\t<div class=\"img-inner dark\" >\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"566\" height=\"565\" src=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a12-7.jpg\" class=\"attachment-large size-large\" alt=\"\" srcset=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a12-7.jpg 566w, https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a12-7-280x280.jpg 280w, https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a12-7-401x400.jpg 401w\" sizes=\"(max-width: 566px) 100vw, 566px\" \/>\t\t\t\t\t\t\n\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\n<style scope=\"scope\">\n\n#image_715153574 {\n  width: 93%;\n}\n<\/style>\n\t<\/div>\n\t\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner\"  >\n<p>actually quite astounding that trillions of molecules or atoms can arrange themselves in a way that their macroscopic arrangement reflects an energetically ideal shape. How is this possible? The answer to this question is the principle behind the simulated annealing optimisation algorithm: Firstly, excess energy determined a temperature measure is provided to the system to allow an efficient reconfiguration of its constituents. These reconfigurations also include transitions to energetically less optimal configurations. Second, the temperature, i.e. the associated excess energy, is slowly reduced, and the probability for less ideal configurations decreases along with it. In order to determine what configurations are possible in such a process, first some funamentals of thermodynamics, or statistical mechanics to be more precise, have to be considered. At thermal equilibrium the probability that a system with N potential states can be found in the state i having energy \ud835\udc38\ud835\udc56 , is described by the Boltzmann distribution:<\/p>\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner text-center\"  >\n\t<div class=\"img has-hover x md-x lg-x y md-y lg-y\" id=\"image_2076973251\">\n\t\t\t\t\t\t\t\t<div class=\"img-inner dark\" >\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"163\" height=\"106\" src=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a13-7.jpg\" class=\"attachment-large size-large\" alt=\"\" \/>\t\t\t\t\t\t\n\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\n<style scope=\"scope\">\n\n#image_2076973251 {\n  width: 17%;\n}\n<\/style>\n\t<\/div>\n\t\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner\"  >\n<p>Metropolis proposes an efficient way to populate these states numerically in his publication (Metropolis et al., 1953). In order to generate configurations matching the Boltzmann distribution, the following strategy is applied:<\/p>\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner text-left\"  >\n\t<div class=\"img has-hover x md-x lg-x y md-y lg-y\" id=\"image_1157640383\">\n\t\t\t\t\t\t\t\t<div class=\"img-inner dark\" style=\"margin:-25px 0px 0px 0px;\">\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"690\" height=\"187\" src=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a14-6.jpg\" class=\"attachment-large size-large\" alt=\"\" \/>\t\t\t\t\t\t\n\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\n<style scope=\"scope\">\n\n#image_1157640383 {\n  width: 68%;\n}\n<\/style>\n\t<\/div>\n\t\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner\"  >\n<p>If the temperature is gradually reduced during this process, the system moves effectively to its ideal state, as the temperature dependence of \ud835\udc5d\ud835\udc56 \ud835\udc5d\ud835\udc57 \u2044 increasingly rules out less ideal states (see Figure 70). However, since at higher temperature levels, less optimal configurations are still accepted, it can be avoided that the optimiser gets trapped in local minima early. If the annealing process were given infinite time, it would reach the optimal solution, i.e. the absolute minimum of the cost function, as it would escape from any local minima again. In its practical application, with limited processing time, it cannot be guaranteed that the ideal state can be identified. However, simulated annealing is able to identify good solutions for such problems very efficiently.<br \/>\nIn its practical implementation, the following four components need to be implemented to perform a simulated annealing optimisation (see, e.g., Ziegel, et al. (2007), Penna (2002)):<\/p>\n<h5>1. Definition of a state<\/h5>\n<p>A concise and unambiguous structure containing all state parameters of the system has to be provided.<\/p>\n<h5>2. Cost function<\/h5>\n<p>A function that is used to evaluate the optimality of a state (its \u201cenergy\u201d). The target of the optimiser is to find the absolute minimum of this function. Often the function is defined in negative values. However, only the difference between two evaluations of the cost function is considered in the algorithm. Therefore, its absolute value is irrelevant.<\/p>\n<h5>3. Alteration algorithm<\/h5>\n<p>An algorithm that is able to generate random new states is necessary. This function has a significant impact on the efficiency of the optimisation. While it is generally possible to create new states independent of the current state, it proved that an algorithm that is able to generate incremental adaptions of the current states is more efficient for most problems. Generally, a combination of both is applied.<\/p>\n<h5>4. Temperature and cooling schedule<\/h5>\n<p>Following the thermodynamic fundamentals, the cooling schedule usually provides a logarithmic temperature decay. However, the actual cooling schedule depends on the cost function and the nature of the optimisation task. In most cases, \u201cphase changes\u201d in the system can be observed. These represent temperature regions where the cost function remains constant to drop sharply afterwards. Since this implies that the system transitions into a path of new configurations, making it harder to access previous states, it is advisable to slow down the cooling at such critical temperature ranges. This can, e.g., effectively be achieved by tracking the average costs with two exponential moving averages of different period lengths. If the deviation of the two measures indicates a sharper decrease, the cooling speed should be reduced, whereas it can be increased if the ratio of the averages indicates little change.<\/p>\n<p>In order to demonstrate how simple the core of the annealing algorithm is, a simple example is provided below. All applications of the algorithm used in this work follow the presented scheme. Only the usually applied additional features to adjust the cooling schedule dynamically are omitted below for reasons of clarity. <\/p>\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner text-center\"  >\n\t<div class=\"img has-hover x md-x lg-x y md-y lg-y\" id=\"image_1291274420\">\n\t\t\t\t\t\t\t\t<div class=\"img-inner dark\" >\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"926\" height=\"471\" src=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a15-5.jpg\" class=\"attachment-large size-large\" alt=\"\" srcset=\"https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a15-5.jpg 926w, https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a15-5-786x400.jpg 786w, https:\/\/radi-cal.org\/method\/wp-content\/uploads\/2023\/10\/a15-5-768x391.jpg 768w\" sizes=\"(max-width: 926px) 100vw, 926px\" \/>\t\t\t\t\t\t\n\t\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t\n<style scope=\"scope\">\n\n#image_1291274420 {\n  width: 85%;\n}\n<\/style>\n\t<\/div>\n\t\n<\/div><\/div>\n<div class=\"col small-12 large-12\"  ><div class=\"col-inner\"  >\n<p>As can be seen, the algorithm described above can be simplified to calculating the difference of both cost functions and using it to determine the probability for a new, energetically less optimal state by calculating the probability exp(-delta\/T) as this is equivalent to the ratio \ud835\udc5d\ud835\udc56 \ud835\udc5d\ud835\udc57 \u2044 .<\/p>\n<\/div><\/div>\n<\/div>\n<style>\n#menu-main li:nth-child(5) .sub-menu{display:block !important;}\n<\/style>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"page-right-sidebar.php","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/pages\/1073"}],"collection":[{"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/comments?post=1073"}],"version-history":[{"count":17,"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/pages\/1073\/revisions"}],"predecessor-version":[{"id":1969,"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/pages\/1073\/revisions\/1969"}],"wp:attachment":[{"href":"https:\/\/radi-cal.org\/method\/wp-json\/wp\/v2\/media?parent=1073"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}