763
个编辑
更改
跳到导航
跳到搜索
第16行：
第16行： − + − + − The [[thermodynamic state|state]] of some [[physical system]]s, and the function ''E''(''s'') to be minimized, is analogous to the [[internal energy]] of the system in that state. The goal is to bring the system, from an arbitrary ''initial state'', to a state with the minimum possible energy.+ − − The state of some physical systems, and the function E(s) to be minimized, is analogous to the internal energy of the system in that state. The goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy. − − 一些物理系统的状态以及最小化函数E(S)可以看作该状态下系统的内部能量。本算法的目的是让任意初始状态的系统经过变化得到能量最小状态。 − − − − − − hill climb algorithm, as there are many local maxima. By cooling the temperature slowly the global maximum is found.|500px]] − − 模拟退火寻求最大值。这里的目的是达到最高点；但是由于存在许多局部最大值，仅使用简单的爬坡算法是不够的。通过缓慢冷却温度，可以找到全局最大值。 − + − − At each step, the simulated annealing heuristic considers some neighboring state ''s*'' of the current state ''s'', and [[probabilistic]]ally decides between moving the system to state ''s*'' or staying in-state ''s''. These probabilities ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted. − − At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in-state s. These probabilities ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted. − − 在每个步骤中，模拟退火这种启发式算法都会考虑当前状态s的某个相邻状态<math>s*</math>，并概率性地决定系统的下一个状态是移至状态<math>s*</math>还是保持状态<math>s</math>。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。 − + − − Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the [[travelling salesman problem]] each state is typically defined as a [[permutation]] of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem). − − Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the travelling salesman problem each state is typically defined as a permutation of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem). − − − 解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守改变给定状态而产生的新状态。例如在旅行商问题中，每个地点通常被定义为要访问的城市的排列，通过反转任意两个邻近城市顺序产生邻居的排列集合，不同的移动方式将产生不同的近邻城市集。这种明确界定的改变各地以产生邻近城市集合的方式被称为“移动”。这些移动最后通常会让状态的更改迭代量降到最低，尝试通过迭代改善解决方案的组成部分（例如旅行商问题中的城市联系）来逐步改善解决方案。 − − − − Simple [[heuristic]]s like [[hill climbing]], which move by finding better neighbour after better neighbour and stop when they have reached a solution which has no neighbours that are better solutions, cannot guarantee to lead to any of the existing better solutions{{snd}} their outcome may easily be just a [[local optimum]], while the actual best solution would be a [[global optimum]] that could be different. [[Metaheuristic]]s use the neighbours of a solution as a way to explore the solutions space, and although they prefer better neighbours, they also accept worse neighbours in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time. − − Simple heuristics like hill climbing, which move by finding better neighbour after better neighbour and stop when they have reached a solution which has no neighbours that are better solutions, cannot guarantee to lead to any of the existing better solutions their outcome may easily be just a local optimum, while the actual best solution would be a global optimum that could be different. Metaheuristics use the neighbours of a solution as a way to explore the solutions space, and although they prefer better neighbours, they also accept worse neighbours in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time. 第63行：
第32行： − === 接受概率 Acceptance probabilities === − − The probability of making the [[state transition|transition]] from the current state <math>s</math> to a candidate new state <math>s'</math> is specified by an ''acceptance probability function'' <math>P(e, e', T)</math>, that depends on the energies <math>e = E(s)</math> and <math>e' = E(s')</math> of the two states, and on a global time-varying parameter <math>T</math> called the ''temperature''. States with a smaller energy are better than those with a greater energy. The probability function <math>P</math> must be positive even when <math>e'</math> is greater than <math>e</math>. This feature prevents the method from becoming stuck at a local minimum that is worse than the global one. − − The probability of making the transition from the current state <math>s</math> to a candidate new state <math>s'</math> is specified by an acceptance probability function <math>P(e, e', T)</math>, that depends on the energies <math>e = E(s)</math> and <math>e' = E(s')</math> of the two states, and on a global time-varying parameter <math>T</math> called the temperature. States with a smaller energy are better than those with a greater energy. The probability function <math>P</math> must be positive even when <math>e'</math> is greater than <math>e</math>. This feature prevents the method from becoming stuck at a local minimum that is worse than the global one. + − − − When <math>T</math> tends to zero, the probability <math>P(e, e', T)</math> must tend to zero if <math>e' > e</math> and to a positive value otherwise. For sufficiently small values of <math>T</math>, the system will then increasingly favor moves that go "downhill" (i.e., to lower energy values), and avoid those that go "uphill." With <math>T=0</math> the procedure reduces to the [[greedy algorithm]], which makes only the downhill transitions. − − When <math>T</math> tends to zero, the probability <math>P(e, e', T)</math> must tend to zero if <math>e' > e</math> and to a positive value otherwise. For sufficiently small values of <math>T</math>, the system will then increasingly favor moves that go "downhill" (i.e., to lower energy values), and avoid those that go "uphill." With <math>T=0</math> the procedure reduces to the greedy algorithm, which makes only the downhill transitions. − − − In the original description of simulated annealing, the probability <math>P(e, e', T)</math> was equal to 1 when <math>e' < e</math>—i.e., the procedure always moved downhill when it found a way to do so, irrespective of the temperature. Many descriptions and implementations of simulated annealing still take this condition as part of the method's definition. However, this condition is not essential for the method to work. − − In the original description of simulated annealing, the probability <math>P(e, e', T)</math> was equal to 1 when <math>e' < e</math>—i.e., the procedure always moved downhill when it found a way to do so, irrespective of the temperature. Many descriptions and implementations of simulated annealing still take this condition as part of the method's definition. However, this condition is not essential for the method to work. − − − The <math>P</math> function is usually chosen so that the probability of accepting a move decreases when the difference − − The <math>P</math> function is usually chosen so that the probability of accepting a move decreases when the difference − <math>e'-e</math> increases—that is, small uphill moves are more likely than large ones. However, this requirement is not strictly necessary, provided that the above requirements are met. − − <math>e'-e</math> increases—that is, small uphill moves are more likely than large ones. However, this requirement is not strictly necessary, provided that the above requirements are met. + − Given these properties, the temperature <math>T</math> plays a crucial role in controlling the evolution of the state <math>s</math> of the system with regard to its sensitivity to the variations of system energies. To be precise, for a large <math>T</math>, the evolution of <math>s</math> is sensitive to coarser energy variations, while it is sensitive to finer energy variations when <math>T</math> is small. − Given these properties, the temperature <math>T</math> plays a crucial role in controlling the evolution of the state <math>s</math> of the system with regard to its sensitivity to the variations of system energies. To be precise, for a large <math>T</math>, the evolution of <math>s</math> is sensitive to coarser energy variations, while it is sensitive to finer energy variations when <math>T</math> is small.+ − − 考虑到这些性质，因为温度<math>T</math>对系统能量变化很敏感，所以它在控制系统状态<math>s</math>的演化方面起着至关重要的作用。准确地说，对于一个庞大的<math>T</math>来说，<math>s</math>的变化对比粗略的能量变化更为敏感，当<math>T</math>很小时，它对精细能量变化更为敏感。 − − 第190行：
第133行： − The name and inspiration of the algorithm demand an interesting feature related to the temperature variation to be embedded in the operational characteristics of the algorithm. This necessitates a gradual reduction of the temperature as the simulation proceeds. The algorithm starts initially with <math>T</math> set to a high value (or infinity), and then it is decreased at each step following some ''annealing schedule''—which may be specified by the user, but must end with <math>T=0</math> towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the [[steepest descent]] heuristic. − − The name and inspiration of the algorithm demand an interesting feature related to the temperature variation to be embedded in the operational characteristics of the algorithm. This necessitates a gradual reduction of the temperature as the simulation proceeds. The algorithm starts initially with <math>T</math> set to a high value (or infinity), and then it is decreased at each step following some annealing schedule—which may be specified by the user, but must end with <math>T=0</math> towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the steepest descent heuristic. 第202行：
第142行： − 对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近1。然而，因为确保取得大概率成功所需的时间通常超过完全搜索解决方案空间所需的时间，所以这一理论结果并不是特别有用，+
→概述Overview
可以通过求解密度函数的动力学方程<ref name=":0">{{cite journal |pages=519–524 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases |journal=Sov.Phys. Crystallography |year=1979 |volume=24 |issue=5 }}</ref><ref name=":1">{{cite journal |pages=742–754 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=The Thermodynamic Approach to the Structure Analysis of Crystals |issue=A37 |journal=Acta Crystallographica |volume=37 |year=1981 |doi=10.1107/S0567739481001630|bibcode=1981AcCrA..37..742K }}</ref> 或采用随机抽样方法进行模拟仿真。<ref name=":2">{{cite journal |jstor=1690046 |pages=671–680 |last1=Kirkpatrick |first1=S. |last2=Gelatt Jr |first2=C. D. |last3=Vecchi |first3=M. P. |title=Optimization by Simulated Annealing |volume=220 |issue=4598 |journal=Science |year=1983 |pmid=17813860 |doi=10.1126/science.220.4598.671|bibcode=1983Sci...220..671K |citeseerx=10.1.1.123.7607 }}</ref><ref>{{cite journal |doi=10.1007/BF00940812 |title=Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm |year=1985 |last1=Černý |first1=V. |journal=Journal of Optimization Theory and Applications |volume=45 |pages=41–51}}</ref> 这种方法是对[[Metropolis-Hastings算法]]（一种用于生成热力学系统的样本状态的[[Monte Carlo方法]]）的一种改进，该算法在1953年由N. Metropolis等人提出。<ref>{{cite journal |doi=10.1063/1.1699114 |title=Equation of State Calculations by Fast Computing Machines |year=1953 |last1=Metropolis |first1=Nicholas |last2=Rosenbluth |first2=Arianna W. |last3=Rosenbluth |first3=Marshall N. |last4=Teller |first4=Augusta H. |last5=Teller |first5=Edward |journal=The Journal of Chemical Physics |volume=21 |issue=6 |pages=1087|bibcode=1953JChPh..21.1087M }}</ref>
可以通过求解密度函数的动力学方程<ref name=":0">{{cite journal |pages=519–524 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases |journal=Sov.Phys. Crystallography |year=1979 |volume=24 |issue=5 }}</ref><ref name=":1">{{cite journal |pages=742–754 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=The Thermodynamic Approach to the Structure Analysis of Crystals |issue=A37 |journal=Acta Crystallographica |volume=37 |year=1981 |doi=10.1107/S0567739481001630|bibcode=1981AcCrA..37..742K }}</ref> 或采用随机抽样方法进行模拟仿真。<ref name=":2">{{cite journal |jstor=1690046 |pages=671–680 |last1=Kirkpatrick |first1=S. |last2=Gelatt Jr |first2=C. D. |last3=Vecchi |first3=M. P. |title=Optimization by Simulated Annealing |volume=220 |issue=4598 |journal=Science |year=1983 |pmid=17813860 |doi=10.1126/science.220.4598.671|bibcode=1983Sci...220..671K |citeseerx=10.1.1.123.7607 }}</ref><ref>{{cite journal |doi=10.1007/BF00940812 |title=Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm |year=1985 |last1=Černý |first1=V. |journal=Journal of Optimization Theory and Applications |volume=45 |pages=41–51}}</ref> 这种方法是对[[Metropolis-Hastings算法]]（一种用于生成热力学系统的样本状态的[[Monte Carlo方法]]）的一种改进，该算法在1953年由N. Metropolis等人提出。<ref>{{cite journal |doi=10.1063/1.1699114 |title=Equation of State Calculations by Fast Computing Machines |year=1953 |last1=Metropolis |first1=Nicholas |last2=Rosenbluth |first2=Arianna W. |last3=Rosenbluth |first3=Marshall N. |last4=Teller |first4=Augusta H. |last5=Teller |first5=Edward |journal=The Journal of Chemical Physics |volume=21 |issue=6 |pages=1087|bibcode=1953JChPh..21.1087M }}</ref>
==概述Overview==
==概述==
一些物理系统的状态以及最小化函数<math>E(S)</math>可以看作该状态下系统的内部能量。本算法的目的是让任意初始状态的系统经过变化得到能量最小状态。
[[File:Hill Climbing with Simulated Annealing.gif|center|thumb|模拟退火寻求最大值。这里的目的是达到最高点；但是由于存在许多局部最大值，仅使用简单的[[爬坡算法 hill climb algorithm]]是不够的。通过缓慢冷却温度，可以找到全局最大值。|500px]]
[[File:Hill Climbing with Simulated Annealing.gif|center|thumb|Simulated annealing searching for a maximum. The objective here is to get to the highest point; however, it is not enough to use a simple [[hill climbing|hill climb algorithm]], as there are many [[Hill climbing algorithm#Local maxima|local maxima]]. By cooling the temperature slowly the global maximum is found.|500px]]
=== 基本迭代The basic iteration ===
=== 基本迭代The basic iteration ===
在每个步骤中，模拟退火这种启发式算法都会考虑当前状态<math>s</math>的某个相邻状态<math>s*</math>，并概率性地决定系统的下一个状态是移至状态<math>s*</math>还是保持状态<math>s</math>。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。
=== 城市的邻居 The neighbours of a state ===
=== 城市的邻居 The neighbours of a state ===
解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守改变给定状态而产生的新状态。例如在[[旅行商问题]]中，每个地点通常被定义为要访问的城市的排列，通过反转任意两个邻近城市顺序产生邻居的排列集合，不同的移动方式将产生不同的近邻城市集。这种明确界定的改变各地以产生邻近城市集合的方式被称为“移动”。这些移动最后通常会让状态的更改迭代量降到最低，尝试通过迭代改善解决方案的组成部分（例如旅行商问题中的城市联系）来逐步改善解决方案。
===接受概率===
从当前状态<math>s</math>到候选状态 <math>s'</math>的转变概率是由接受概率密度函数<math>P(e,e',T)</math>确定的，这取决于两个状态的能量<math>e = E(s)</math> ，<math>e' = E(s')</math>，以及称为温度的全局时变参数<math>T</math>。能量较小的状态比能量较大的状态好。概率密度函数<math>P</math>必须是正值，即使<math>e'</math>大于<math>e</math>，这个特性可以防止陷入比全局最小值糟糕的局部最小值。
从当前状态<math>s</math>到候选状态 <math>s'</math>的转变概率是由接受概率密度函数<math>P(e,e',T)</math>确定的，这取决于两个状态的能量<math>e = E(s)</math> ，<math>e' = E(s')</math>，以及称为温度的全局时变参数<math>T</math>。能量较小的状态比能量较大的状态好。概率密度函数<math>P</math>必须是正值，即使<math>e'</math>大于<math>e</math>，这个特性可以防止陷入比全局最小值糟糕的局部最小值。
当<math>T</math>趋于零时，如果<math>e' > e</math>，概率<math>P(e, e', T)</math>必须趋于零，反之趋于正值。对于足够小的<math>T</math>值，系统会越来越倾向于走“下坡路”(即降低能量值) ，而避免走“上坡路”。使用<math>T=0</math>的过程，只有下坡过渡，简化为贪婪算法。
当<math>T</math>趋于零时，如果<math>e' > e</math>，概率<math>P(e, e', T)</math>必须趋于零，反之趋于正值。对于足够小的<math>T</math>值，系统会越来越倾向于走“下坡路”(即降低能量值) ，而避免走“上坡路”。使用<math>T=0</math>的过程，只有下坡过渡，简化为贪婪算法。
在模拟退火的原始描述中，当<math>e' < e</math>时，概率<math>P(e, e', T)</math>等于1。即无论温度如何，程序总会找到一种方法，找到“下坡路”。许多模拟退火的描述和实现仍然把这个条件作为方法定义的一部分。然而这个条件并不是这个方法工作的必要条件。
在模拟退火的原始描述中，当<math>e' < e</math>时，概率<math>P(e, e', T)</math>等于1。即无论温度如何，程序总会找到一种方法，找到“下坡路”。许多模拟退火的描述和实现仍然把这个条件作为方法定义的一部分。然而这个条件并不是这个方法工作的必要条件。
The <math>P</math>函数的选择通常是为了降低接受移动的概率。
The <math>P</math>函数的选择通常是为了降低接受移动的概率。
<math>e'-e</math>增加意味着小的上坡动作比大的动作更有可能发生。如果符合上述要求，这一要求并非绝对必要。
<math>e'-e</math>增加意味着小的上坡动作比大的动作更有可能发生。如果符合上述要求，这一要求并非绝对必要。
考虑到这些性质，因为温度<math>T</math>对系统能量变化很敏感，所以它在控制系统状态<math>s</math>的演化方面起着至关重要的作用。准确地说，对于一个庞大的<math>T</math>来说，<math>s</math>的变化对比粗略的能量变化更为敏感，当<math>T</math>很小时，它对精细能量变化更为敏感。
=== 退火时间表 ===
=== 退火时间表The annealing schedule ===
{{multiple image
{{multiple image
}}
}}
算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。
算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。
For any given finite problem, the probability that the simulated annealing algorithm terminates with a global optimal solution approaches 1 as the annealing schedule is extended. This theoretical result, however, is not particularly helpful, since the time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.
For any given finite problem, the probability that the simulated annealing algorithm terminates with a global optimal solution approaches 1 as the annealing schedule is extended. This theoretical result, however, is not particularly helpful, since the time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.
对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近1。<ref>{{cite journal |doi=10.1109/34.295910 |title=Simulated annealing: A proof of convergence |year=1994 |last1=Granville |first1=V. |last2=Krivanek |first2=M. |last3=Rasson |first3=J.-P. |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=16 |issue=6 |pages=652–656}}</ref> 然而，因为确保取得大概率成功所需的时间通常超过完全搜索[[解空间]]所需的时间，所以这一理论结果并不是特别有用。{{Citation needed|date=June 2011}}
==伪代码Pseudocode==
==伪代码Pseudocode==