更改

==Selecting the parameters==

==参数选择==

In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function {{code|E()}}, the candidate generator procedure {{code|neighbour()}}, the acceptance probability function {{code|P()}}, and the annealing schedule {{code|temperature()}} AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness.  Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem.  The following sections give some general guidelines.

In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function {{code|E()}}, the candidate generator procedure {{code|neighbour()}}, the acceptance probability function {{code|P()}}, and the annealing schedule {{code|temperature()}} AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness.  Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem.  The following sections give some general guidelines.

In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function , the candidate generator procedure , the acceptance probability function , and the annealing schedule  AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness.  Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem.  The following sections give some general guidelines.

In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function , the candidate generator procedure , the acceptance probability function , and the annealing schedule  AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness.  Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem.  The following sections give some general guidelines.

===Sufficiently near neighbour===

 

 

===充分相邻 Sufficiently near neighbour===

Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the {{code|neighbour()}} function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum{{snd}} the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>.

Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the {{code|neighbour()}} function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum{{snd}} the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>.

Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the  function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>.

Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the  function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>.

模拟退火可以被建模为一个搜索图上的随机游动，其顶点都是可能的状态，其边是候选移动。函数的一个基本要求是它必须提供一条足够短的路径，从初始状态到任何可能是全局最优的状态，搜索图的直径必须很小。例如，在上面的旅行推销员例子中，n 20个城市的搜索空间有 n！2,432,902,008,176,640,000(2.4次方)状态; 然而每个顶点的邻接数是 math { k 1} ^ n-1} k frac { n (n-1)}{2}190 / math 棱，图的直径是 math n-1 / math。

模拟退火可以建立成一个搜索图上的随机游动模型，其顶点是所有可能的状态，其边是候选移动。对于函数的一个基本要求是模拟退火必须提供一条足够短的路径，从初始状态所到达的任何状态都可能是全局最优状态，搜索图的直径必须很小。例如，在上面的旅行推销员示例中，n = 20个城市的搜索空间有n!= 2,432,902,008,176,640,000 (2.4 quintillion)个州;然而，每个顶点的邻接数是<math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math>边，图的直径是<math>n-1</math>。

===Transition probabilities===

===跃迁概率 Transition probabilities===

To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the ''transition probabilities'' that result from the various design choices made in the implementation of the algorithm.  For each edge <math>(s,s')</math> of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state  <math>s'</math> when its current state is <math>s</math>.  This probability depends on the current temperature as specified by {{code|temperature()}}, on the order in which the candidate moves are generated by the {{code|neighbour()}} function, and on the acceptance probability function {{code|P()}}. (Note that the transition probability is '''not''' simply <math>P(e, e', T)</math>, because the candidates are tested serially.)

To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the ''transition probabilities'' that result from the various design choices made in the implementation of the algorithm.  For each edge <math>(s,s')</math> of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state  <math>s'</math> when its current state is <math>s</math>.  This probability depends on the current temperature as specified by {{code|temperature()}}, on the order in which the candidate moves are generated by the {{code|neighbour()}} function, and on the acceptance probability function {{code|P()}}. (Note that the transition probability is '''not''' simply <math>P(e, e', T)</math>, because the candidates are tested serially.)

To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the transition probabilities that result from the various design choices made in the implementation of the algorithm.  For each edge <math>(s,s')</math> of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state  <math>s'</math> when its current state is <math>s</math>.  This probability depends on the current temperature as specified by , on the order in which the candidate moves are generated by the  function, and on the acceptance probability function . (Note that the transition probability is not simply <math>P(e, e', T)</math>, because the candidates are tested serially.)

To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the transition probabilities that result from the various design choices made in the implementation of the algorithm.  For each edge <math>(s,s')</math> of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state  <math>s'</math> when its current state is <math>s</math>.  This probability depends on the current temperature as specified by , on the order in which the candidate moves are generated by the  function, and on the acceptance probability function . (Note that the transition probability is not simply <math>P(e, e', T)</math>, because the candidates are tested serially.)

===Acceptance probabilities===

===接受概率 Acceptance probabilities===

The specification of {{code|neighbour()}}, {{code|P()}}, and {{code|temperature()}} is partially redundant.  In practice, it's common to use the same acceptance function {{code|P()}} for many problems, and adjust the other two functions according to the specific problem.

The specification of {{code|neighbour()}}, {{code|P()}}, and {{code|temperature()}} is partially redundant.  In practice, it's common to use the same acceptance function {{code|P()}} for many problems, and adjust the other two functions according to the specific problem.

The specification of , , and  is partially redundant.  In practice, it's common to use the same acceptance function  for many problems, and adjust the other two functions according to the specific problem.

The specification of , , and  is partially redundant.  In practice, it's common to use the same acceptance function  for many problems, and adjust the other two functions according to the specific problem.

 

 

In the formulation of the method by Kirkpatrick et al., the acceptance probability function <math>P(e, e', T)</math> was defined as 1 if <math>e' < e</math>, and <math>\exp(-(e'-e)/T)</math> otherwise. This formula was superficially justified by analogy with the transitions of a physical system; it corresponds to the Metropolis–Hastings algorithm, in the case where T=1 and the proposal distribution of Metropolis–Hastings is symmetric. However, this acceptance probability is often used for simulated annealing even when the  function, which is analogous to the proposal distribution in Metropolis–Hastings, is not symmetric, or not probabilistic at all. As a result, the transition probabilities of the simulated annealing algorithm do not correspond to the transitions of the analogous physical system, and the long-term distribution of states at a constant temperature <math>T</math> need not bear any resemblance to the thermodynamic equilibrium distribution over states of that physical system, at any temperature. Nevertheless, most descriptions of simulated annealing assume the original acceptance function, which is probably hard-coded in many implementations of SA.

In the formulation of the method by Kirkpatrick et al., the acceptance probability function <math>P(e, e', T)</math> was defined as 1 if <math>e' < e</math>, and <math>\exp(-(e'-e)/T)</math> otherwise. This formula was superficially justified by analogy with the transitions of a physical system; it corresponds to the Metropolis–Hastings algorithm, in the case where T=1 and the proposal distribution of Metropolis–Hastings is symmetric. However, this acceptance probability is often used for simulated annealing even when the  function, which is analogous to the proposal distribution in Metropolis–Hastings, is not symmetric, or not probabilistic at all. As a result, the transition probabilities of the simulated annealing algorithm do not correspond to the transitions of the analogous physical system, and the long-term distribution of states at a constant temperature <math>T</math> need not bear any resemblance to the thermodynamic equilibrium distribution over states of that physical system, at any temperature. Nevertheless, most descriptions of simulated annealing assume the original acceptance function, which is probably hard-coded in many implementations of SA.

在 Kirkpatrick 等人提出的方法中，接受概率密度函数 / 数学 p (e，e’ ，t) / math 被定义为1 if math e’ e / math，和 math exp (- (e’-e) / t) / math otherwise。这个公式表面上是通过类比物理系统的转变来证明的; 它相当于大都会-黑斯廷斯算法，在 t 1和大都会-黑斯廷斯的提案分布是对称的情况下。然而，这种接受概率经常用于模拟退火，即使函数类似于 Metropolis-Hastings 中的建议分布，不是对称的，或者根本不是概率的。因此，模拟退火算法的跃迁概率并不对应于类似物理系统的跃迁，并且在恒温数学 t / math 中状态的长期分布不需要与该物理系统在任何温度下状态上的热力学平衡分布有任何相似之处。尽管如此，大多数关于模拟退火的描述都假定了最初的验收函数，这个函数在许多 SA 实现中可能是硬编码的。

在Kirkpatrick等人的方法中，如果<math>e' < e</math>， <math>\exp(-(e'-e)/T)</math>，则接受概率函数<math>P(e, e'， T)</math>定义为1。

这一公式实际上是通过类比物理系统的变迁而得到证明的;在T=1且建议分布对称的情况下，对应于Metropolis-Hastings算法。

然而，这个接受概率经常被用于模拟退火算法，甚至当函数(类似于Metropolis-Hastings中的建议分布)不是对称的，或者根本不是概率性的时候也是如此。

因此，模拟退火算法的跃迁概率并不对应于类似物理系统的跃迁概率，并且，在恒温<math>T</math>状态下的长期分布与物理系统在任何温度下状态上的热力学平衡分布并不相似。

In 1990, Moscato and Fontanari <ref>{{citation |journal=Physics Letters A |pages= 204–208 |last1=Moscato |first1=P. |last2=Fontanari |first2=J.F.| title=Stochastic versus deterministic update in simulated annealing |volume=146 |issue=4 |year=1990|doi=10.1016/0375-9601(90)90166-L}}</ref>, and independently Dueck and Scheuer <ref>{{citation |journal=Journal of Computational Physics| pages=161–175 | last1=Dueck |first1=G.| last2=Scheuer| first2=T.| title=Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing| volume=90 | issue=1 | year=1990 | issn=0021-9991 |  

In 1990, Moscato and Fontanari<ref>{{citation |journal=Journal of Computational Physics| pages=161–175 | last1=Dueck |first1=G.| last2=Scheuer| first2=T.| title=Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing| volume=90 | issue=1 | year=1990 | issn=0021-9991 |doi=10.1016/0021-9991(90)90201-B}}</ref>, proposed that a deterministic update (i.e. one that is not based on the probabilistic acceptance rule) could speed-up the optimization process without impacting on the final quality. Moscato and Fontanari conclude from observing the analogous of the "specific heat" curve of the "threshold updating" annealing originating from their study that "the stochasticity of the Metropolis updating in the simulated annealing algorithm does not play a major role in the search of near-optimal minima". Instead, they proposed that "the smoothening of the cost function landscape at high temperature and the gradual definition of the minima during the cooling process are the fundamental ingredients for the success of simulated annealing." The method subsequently popularized under the denomination of "threshold accepting" due to Dueck and Scheuer's denomination. In 2001, Franz, Hoffmann and Salamon showed that the deterministic update strategy is indeed the optimal one within the large class of algorithms that simulate a random walk on the cost/energy landscape . 

 

1990年，莫斯卡托 Moscato 和丰塔纳里 Fontanari<ref>{{citation |journal=Journal of Computational Physics| pages=161–175 | last1=Dueck |first1=G.| last2=Scheuer| first2=T.| title=Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing| volume=90 | issue=1 | year=1990 | issn=0021-9991 |doi=10.1016/0021-9991(90)90201-B}}</ref>提出确定性更新(即不基于概率接受规则的更新)，其可以在不影响最终质量的情况下加快优化过程。

 

在2001年，Franz, Hoffmann和Salamon证明了确定性更新策略确实是在模拟成本/能源景观上随机行走的大类算法中最优的。

 

doi=10.1016/0021-9991(90)90201-B}}</ref>, proposed that a deterministic update (i.e. one that is not based on the probabilistic acceptance rule) could speed-up the optimization process without impacting on the final quality. Moscato and Fontanari conclude from observing the analogous of the "specific heat" curve of the "threshold updating" annealing originating from their study that "the stochasticity of the Metropolis updating in the simulated annealing algorithm does not play a major role in the search of near-optimal minima". Instead, they proposed that "the smoothening of the cost function landscape at high temperature and the gradual definition of the minima during the cooling process are the fundamental ingredients for the success of simulated annealing." The method subsequently popularized under the denomination of "threshold accepting" due to Dueck and Scheuer's denomination. In 2001, Franz, Hoffmann and Salamon showed that the deterministic update strategy is indeed the optimal one within the large class of algorithms that simulate a random walk on the cost/energy landscape <ref>{{citation |journal=Physical Review Letters| pages=5219–5222 | volume=86 | issue=3 | title= Best optimal strategy for finding ground states | last1=Franz | first1=A. | last2=Hoffmann | first2=K.H. | last3=Salamon | first3= P | doi=10.1103/PhysRevLett.86.5219}}</ref>. 

 

doi=10.1016/0021-9991(90)90201-B}}</ref>, proposed that a deterministic update (i.e. one that is not based on the probabilistic acceptance rule) could speed-up the optimization process without impacting on the final quality. Moscato and Fontanari conclude from observing the analogous of the "specific heat" curve of the "threshold updating" annealing originating from their study that "the stochasticity of the Metropolis updating in the simulated annealing algorithm does not play a major role in the search of near-optimal minima". Instead, they proposed that "the smoothening of the cost function landscape at high temperature and the gradual definition of the minima during the cooling process are the fundamental ingredients for the success of simulated annealing." The method subsequently popularized under the denomination of "threshold accepting" due to Dueck and Scheuer's denomination. In 2001, Franz, Hoffmann and Salamon showed that the deterministic update strategy is indeed the optimal one within the large class of algorithms that simulate a random walk on the cost/energy landscape . 

 

Doi 10.1016 / 0021-9991(90)90201-B } / ref，提出一个确定性更新(即。一个不是基于概率接受规则)可以加快优化过程，而不影响最终的质量。Moscato 和 Fontanari 通过观察起源于他们研究的“阈值更新”退火的类似“比热”曲线得出结论: “模拟退火算法中 Metropolis 更新的随机性在近似最优极小值的搜索中不起主要作用”。相反，他们提出“在高温下平滑的成本函数和在冷却过程中逐渐定义的最小值是模拟退火成功的基本要素。”这种方法后来由于 Dueck 和 Scheuer 的命名而在“门槛接受”的命名下推广。在2001年，Franz，Hoffmann 和 Salamon 证明了确定性更新策略确实是大量算法中的最优策略，这些算法模拟了成本 / 能源景观上的随机游走。

===Efficient candidate generation===

===Efficient candidate generation===

用来证明模拟退火的物理类比是假设冷却速率足够低，以至于当前状态的概率分布在任何时候都接近热力学平衡。不幸的是，弛豫时间——温度变化后必须等待平衡恢复的时间——强烈地依赖于能量函数的“地形”和当前的温度。在模拟退火算法中，松弛时间以一种非常复杂的方式也依赖于候选生成器。请注意，所有这些参数通常作为黑盒函数提供给模拟退火算法。因此，理想的冷却速率不能事先确定，而应根据每个问题进行经验调整。自适应模拟退火算法通过连接冷却计划和搜索进度来解决这个问题。其他的自适应方法，如热力学模拟退火，根据美国热力学定律协会的说法，可以根据两种状态之间的能量差自动调节每一步的温度。

用来证明模拟退火的物理类比是假设冷却速率足够低，以至于当前状态的概率分布在任何时候都接近热力学平衡。不幸的是，弛豫时间——温度变化后必须等待平衡恢复的时间——强烈地依赖于能量函数的“地形”和当前的温度。在模拟退火算法中，松弛时间以一种非常复杂的方式也依赖于候选生成器。请注意，所有这些参数通常作为黑盒函数提供给模拟退火算法。因此，理想的冷却速率不能事先确定，而应根据每个问题进行经验调整。自适应模拟退火算法通过连接冷却计划和搜索进度来解决这个问题。其他的自适应方法，如热力学模拟退火，根据美国热力学定律协会的说法，可以根据两种状态之间的能量差自动调节每一步的温度。

==Restarts==

==Restarts==