763
个编辑
更改
跳到导航
跳到搜索
第91行：
第91行： − + − + − 模拟退火可以建立成一个搜索图上的随机游动模型，其顶点是所有可能的状态，其边是候选移动。对于函数的一个基本要求是模拟退火必须提供一条足够短的路径，从初始状态所到达的任何状态都可能是全局最优状态，搜索图的直径必须很小。例如，在上面的旅行推销员示例中，<math>n=20</math>个城市的搜索空间有<math>n!= 2,432,902,008,176,640,000 (2.4 亿个州)</math>个州;然而，每个顶点的邻接数是<math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math>边，图的直径是<math>n-1</math>。+ − − + − 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.) − − − 为了研究模拟退火在特定问题上的行为，考虑算法实现过程中的各种设计选择所产生的跃迁概率是很有用的。对于搜索图的每条边<math>(s,s')</math>，跃迁概率定义为模拟退火算法在当前状态<math>s'</math> </math> s</math>时移动到状态<math>s'</math>的概率。此概率取决于指定的当前温度、函数生成候选移动的顺序以及接受概率函数。注意，跃迁概率不是简单地<math>P(e, e'， T)</math>，因为候选对象是连续进行测试的。 + − 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.+ − 和的规范部分是多余的。在实际应用中，对许多问题使用相同的验收函数，并根据具体问题对其他两个函数进行调整，这是很常见的。 − 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 {{code|neighbour()}} 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等人的方法中，如果<math>e' < e</math>， <math>\exp(-(e'-e)/T)</math>，则接受概率函数<math>P(e, e'， T)</math>定义为1。 − 这一公式实际上是通过类比物理系统的变迁而得到证明的;在T=1且建议分布对称的情况下，对应于Metropolis-Hastings算法。 − 然而，这个接受概率经常被用于模拟退火算法，甚至当函数(类似于Metropolis-Hastings中的建议分布)不是对称的，或者根本不是概率性的时候也是如此。 − 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 | 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>. + − 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>提出确定性更新(即不基于概率接受规则的更新)，其可以在不影响最终质量的情况下加快优化过程。 − Moscato和Fontanari通过观察源自他们的研究的类似于“阈值更新”退火的“比热”曲线得出结论：“模拟退火算法中的Metropolis更新的随机性在寻找近似最优最小值中没有发挥主要作用”。相反，他们提出“在高温下平滑成本函数景观和在冷却过程中逐渐定义最小值是模拟退火成功的基本要素。” − 这种方法后来被Dueck和Scheuer命名为“阈值接受”而推广开来。 − 在2001年，Franz, Hoffmann和Salamon证明了确定性更新策略确实是在模拟成本/能量趋势图上随机行走的大类算法中最优的。 − ---~~energy landscape 能量绘景，能量图景，能源景观，能量景貌 译为能量图？能量趋势图+ − ===有效的备选 Efficient candidate generation=== − When choosing the candidate generator {{code|neighbour()}}, one must consider that after a few iterations of the simulated annealing algorithm, the current state is expected to have much lower energy than a random state. Therefore, as a general rule, one should skew the generator towards candidate moves where the energy of the destination state <math>s'</math> is likely to be similar to that of the current state. This [[heuristic]] (which is the main principle of the [[Metropolis–Hastings algorithm]]) tends to exclude "very good" candidate moves as well as "very bad" ones; however, the former are usually much less common than the latter, so the heuristic is generally quite effective.+ + − When choosing the candidate generator , one must consider that after a few iterations of the simulated annealing algorithm, the current state is expected to have much lower energy than a random state. Therefore, as a general rule, one should skew the generator towards candidate moves where the energy of the destination state <math>s'</math> is likely to be similar to that of the current state. This heuristic (which is the main principle of the Metropolis–Hastings algorithm) tends to exclude "very good" candidate moves as well as "very bad" ones; however, the former are usually much less common than the latter, so the heuristic is generally quite effective. − 在选择候选产生器时，必须考虑到经过模拟退火算法的多次迭代后，当前状态的能量比随机状态低得多。因此，通常的规则是，当目标状态<math>s'</math>的能量可能与当前状态类似时，应该使生成器向候选的地方移动倾斜。这种启发式(这是Metropolis-Hastings算法的主要原则)倾向于排除“非常好的”候选移动和“非常糟糕的”候选移动;+ − 然而，前者通常比后者少得多，所以启发式通常是相当有效的。 − In the traveling salesman problem above, for example, swapping two ''consecutive'' cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two ''arbitrary'' cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbour generator is expected to perform better than the arbitrary-swap one, even though the latter could provide a somewhat shorter path to the optimum (with <math>n-1</math> swaps, instead of <math>n(n-1)/2</math>).+ − − In the traveling salesman problem above, for example, swapping two consecutive cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two arbitrary cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbour generator is expected to perform better than the arbitrary-swap one, even though the latter could provide a somewhat shorter path to the optimum (with <math>n-1</math> swaps, instead of <math>n(n-1)/2</math>). − − 例如，在上面的旅行商问题中，也就是TSP问题（Traveling Salesman Problem）。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 − 在一个寻找最短路径的旅行中，对两个连续的城市所走的顺序进行交换，预计会对其能量(长度)产生适度的影响;而交换两个任意的城市的移动顺序更有可能增加而不是减少城市的长度。 − 因此，预期连续交换邻接生成器的性能要优于任意交换生成器，尽管后者可以提供更短的路径来达到最佳状态(使用<math>n-1</math>交换，而不是<math>n(n-1)/2</math>)。 − − A more precise statement of the heuristic is that one should try first candidate states <math>s'</math> for which <math>P(E(s), E(s'), T)</math> is large. For the "standard" acceptance function <math>P</math> above, it means that <math>E(s') - E(s)</math> is on the order of <math>T</math> or less. Thus, in the traveling salesman example above, one could use a {{code|neighbour()}} function that swaps two random cities, where the probability of choosing a city-pair vanishes as their distance increases beyond <math>T</math>. − A more precise statement of the heuristic is that one should try first candidate states <math>s'</math> for which <math>P(E(s), E(s'), T)</math> is large. For the "standard" acceptance function <math>P</math> above, it means that <math>E(s') - E(s)</math> is on the order of <math>T</math> or less. Thus, in the traveling salesman example above, one could use a function that swaps two random cities, where the probability of choosing a city-pair vanishes as their distance increases beyond <math>T</math>.+ − − 关于这种启发式的一个更精确的陈述是，人们应该尝试第一个候选状态的数学 s / math，对于这个状态的数学 p (e (s) ，e (s’) ，t) / math 是很大的。对于上面提到的“标准”接受函数数学 p / math，它意味着数学 e (s’)-e (s) / math 的顺序是数学 t / math 或更少。因此，在上面的旅行推销员的例子中，我们可以使用一个交换两个随机城市的函数，其中选择一个城市对的概率消失了，因为它们的距离增加超过了数学 t / math。 − − − 对于上面的“标准”接受函数<math>P</math>，这意味着<math>E(s') - E(s)</math>的长度是<math>T</math>或更少。 − 因此，在上面的旅行商问题中，我们可以使用一个函数来交换两个随机城市，当它们的距离超过<math>T</math>时，就不再选择该城市对。 − − When choosing the candidate generator {{code|neighbour()}} one must also try to reduce the number of "deep" local minima—states (or sets of connected states) that have much lower energy than all its neighbouring states. Such "closed [[drainage basin|catchment]] basins" of the energy function may trap the simulated annealing algorithm with high probability (roughly proportional to the number of states in the basin) and for a very long time (roughly exponential on the energy difference between the surrounding states and the bottom of the basin). − − When choosing the candidate generator one must also try to reduce the number of "deep" local minima—states (or sets of connected states) that have much lower energy than all its neighbouring states. Such "closed catchment basins" of the energy function may trap the simulated annealing algorithm with high probability (roughly proportional to the number of states in the basin) and for a very long time (roughly exponential on the energy difference between the surrounding states and the bottom of the basin). − − − --~~这句话我有些不太理解 只能先直译一下，感觉有些像说 盆地是指较优点，会困住模拟退火算法+ + + + − As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of simulated annealing by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours <math>A</math>, <math>B</math>, with nearly equal lengths, such that (1) <math>A</math> is optimal, (2) every sequence of city-pair swaps that converts <math>A</math> to <math>B</math> goes through tours that are much longer than both, and (3) <math>A</math> can be transformed into <math>B</math> by flipping (reversing the order of) a set of consecutive cities. In this example, <math>A</math> and <math>B</math> lie in different "deep basins" if the generator performs only random pair-swaps; but they will be in the same basin if the generator performs random segment-flips. − As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of simulated annealing by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours <math>A</math>, <math>B</math>, with nearly equal lengths, such that (1) <math>A</math> is optimal, (2) every sequence of city-pair swaps that converts <math>A</math> to <math>B</math> goes through tours that are much longer than both, and (3) <math>A</math> can be transformed into <math>B</math> by flipping (reversing the order of) a set of consecutive cities. In this example, <math>A</math> and <math>B</math> lie in different "deep basins" if the generator performs only random pair-swaps; but they will be in the same basin if the generator performs random segment-flips.+ − − 一般来说，不可能设计一个候选生成器，既能满足这个目标，又能优先考虑具有类似能量的候选人。另一方面，人们通常可以通过对生成器进行相对简单的改变来大大提高模拟退火的效率。例如，在旅行推销员问题中，不难发现两个长度几乎相等的旅行数学 a / 数学 b / 数学，比如(1)数学 a / 数学是最优的; (2)每一个将数学 a / 数学转换为数学 b / 数学的城市对交换序列都要经过比两者都长得多的旅行; (3)数学 a / 数学可以通过翻转一组连续的城市转换为数学 b / 数学。在这个例子中，如果生成器只进行随机对偶交换，数学 a / math 和数学 b / math 位于不同的“深盆”中; 但是如果生成器执行随机分段翻转，它们将位于同一盆中。 − 通常，不可能设计一个候选生成器来满足这个目标，并且优先考虑具有相同能量的候选。 − 第193行：
第149行： − + − + − − The physical analogy that is used to justify simulated annealing assumes that the cooling rate is low enough for the probability distribution of the current state to be near [[thermodynamic equilibrium]] at all times. Unfortunately, the ''relaxation time''—the time one must wait for the equilibrium to be restored after a change in temperature—strongly depends on the "topography" of the energy function and on the current temperature. In the simulated annealing algorithm, the relaxation time also depends on the candidate generator, in a very complicated way. Note that all these parameters are usually provided as [[procedural parameter|black box functions]] to the simulated annealing algorithm. Therefore, the ideal cooling rate cannot be determined beforehand, and should be empirically adjusted for each problem. [[Adaptive simulated annealing]] algorithms address this problem by connecting the cooling schedule to the search progress. Other adaptive approach as Thermodynamic Simulated Annealing<ref>{{cite journal |doi=10.1016/j.physleta.2003.08.070 |title=Placement by thermodynamic simulated annealing |year=2003 |last1=De Vicente |first1=Juan |last2=Lanchares |first2=Juan |last3=Hermida |first3=Román |journal=Physics Letters A |volume=317 |issue=5–6 |pages=415–423|bibcode=2003PhLA..317..415D }}</ref>, automatically adjusts the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics. − − The physical analogy that is used to justify simulated annealing assumes that the cooling rate is low enough for the probability distribution of the current state to be near thermodynamic equilibrium at all times. Unfortunately, the relaxation time—the time one must wait for the equilibrium to be restored after a change in temperature—strongly depends on the "topography" of the energy function and on the current temperature. In the simulated annealing algorithm, the relaxation time also depends on the candidate generator, in a very complicated way. Note that all these parameters are usually provided as black box functions to the simulated annealing algorithm. Therefore, the ideal cooling rate cannot be determined beforehand, and should be empirically adjusted for each problem. Adaptive simulated annealing algorithms address this problem by connecting the cooling schedule to the search progress. Other adaptive approach as Thermodynamic Simulated Annealing, automatically adjusts the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics. − − 用来证明模拟退火合理性的物理类比是假定冷却速率足够低，使当前状态的概率分布在任何时候都接近热力学平衡。 − 遗憾的是，弛豫时间——一个人必须等待平衡在温度变化后恢复的时间——强烈地依赖于能量函数的“地形”和当前的温度。 − 在模拟退火算法中，弛豫时间也以非常复杂的方式依赖于候选生成器。 − 注意，所有这些参数通常都作为黑盒函数提供给模拟退火算法。 − 因此，理想的冷却速率不能预先确定，应该根据实际情况对每个问题进行调整。 − 自适应模拟退火算法通过将冷却计划与搜索过程相结合来解决这个问题。 − 其他自适应方法如热力模拟退火，根据美国热力学定律协会的说法，可以根据两种状态之间的能量差自动调节每一步的温度。
→参数选择
==参数选择==
==参数选择==
为了将模拟退火算法应用于具体问题，退火过程由冷却进度表 Cooling Schedule 控制，包括控制参数的初值<math>t</math>及其衰减因子<math>Δt</math>、每个<math>t</math>值时的迭代次数<math>L</math>和停止条件<math>S</math>。模拟退火算法必须指定以下参数:状态空间、能量(目标)函数、候选生成器过程、接受概率函数以及退火时刻表和初始温度。这些参数的选择能对模拟退火算法的有效性和准确性产生很大的影响。遗憾的是，并没有适用于所有问题的参数选择方法，也没有找到对于给定问题的最佳参数选择的通用方法。下面几节给出一些一般的指导原则。
为了将模拟退火算法应用于具体问题，退火过程由冷却进度表 Cooling Schedule 控制，包括控制参数的初值<math>t</math>及其衰减因子<math>Δt</math>、每个<math>t</math>值时的迭代次数<math>L</math>和停止条件<math>S</math>。模拟退火算法必须指定以下参数:状态空间、能量(目标)函数 {{code|E()}}、候选生成器过程{{code|neighbour()}}、接受概率函数{{code|P()}}以及退火时刻表和初始温度<init temp>。这些参数的选择能对模拟退火算法的有效性和准确性产生很大的影响。遗憾的是，并没有适用于所有问题的参数选择方法，也没有找到对于给定问题的最佳参数选择的通用方法。下面几节给出一些一般的指导原则。
===充分相邻 Sufficiently near neighbour===
===充分相邻===
模拟退火可以建立成一个搜索图上的随机游动模型，其顶点是所有可能的状态，其边是候选移动。对于{{code|neighbour()}}函数的一个基本要求是模拟退火必须提供一条足够短的路径，从初始状态所到达的任何状态都可能是全局最优状态，搜索图的直径必须很小。例如，在上面的旅行推销员示例中，<math>n=20</math>个城市的搜索空间有<math>n!= 2,432,902,008,176,640,000 (2.4 亿个州)</math>个州;然而，每个顶点的邻接数是<math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math>边，图的直径是<math>n-1</math>。
=== 跃迁概率 Transition probabilities ===
=== 跃迁概率 Transition probabilities ===
为了研究模拟退火在特定问题上的行为，考虑算法实现过程中的各种设计选择所产生的跃迁概率是很有用的。对于搜索图的每条边<math>(s,s')</math>，跃迁概率定义为模拟退火算法在当前状态<math>s'</math> </math> s</math>时移动到状态<math>s'</math>的概率。此概率取决于指定的当前温度、{{code|temperature()}}函数生成候选移动的顺序以及接受概率{{code|P()}}函数。注意，跃迁概率不是简单地<math>P(e, e'， T)</math>，因为候选对象是连续进行测试的。
=== 接受概率 Acceptance probabilities ===
=== 接受概率 Acceptance probabilities ===
{{code|neighbour()}}, {{code|P()}}和{{code|temperature()}}的规范部分是多余的。在实际应用中，对许多问题使用相同的验收函数，并根据具体问题对其他两个函数进行调整，这是很常见的。
在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>状态下的长期分布与物理系统在任何温度下状态上的热力学平衡分布并不相似。
因此，模拟退火算法的跃迁概率并不对应于类似物理系统的跃迁概率，并且，在恒温<math>T</math>状态下的长期分布与物理系统在任何温度下状态上的热力学平衡分布并不相似。
然而，大多数关于模拟退火的描述都假定了最初的接受函数，这使得可能在SA的许多实现中都是'''硬编码 hard-coded'''的。硬编码指“将可变变量用一个固定数值表示”，这种方式在编码的过程中会导致变量很难修改。
然而，大多数关于模拟退火的描述都假定了最初的接受函数，这使得可能在SA的许多实现中都是'''硬编码 hard-coded'''的。硬编码指“将可变变量用一个固定数值表示”，这种方式在编码的过程中会导致变量很难修改。
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>提出确定性更新(即不基于概率接受规则的更新)，其可以在不影响最终质量的情况下加快优化过程。Moscato和Fontanari通过观察源自他们的研究的类似于“阈值更新”退火的“比热”曲线得出结论：“模拟退火算法中的Metropolis更新的随机性在寻找近似最优最小值中没有发挥主要作用”。相反，他们提出“在高温下平滑成本函数景观和在冷却过程中逐渐定义最小值是模拟退火成功的基本要素。”这种方法后来被Dueck和Scheuer命名为“阈值接受”而推广开来。
在2001年，Franz, Hoffmann和Salamon证明了确定性更新策略确实是在模拟成本/能量趋势图上随机行走的大类算法中最优的。<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>.
===有效的备选 ===
在选择候选产生器 {{code|neighbour()}}时，必须考虑到经过模拟退火算法的多次迭代后，当前状态的能量比随机状态低得多。因此，通常的规则是，当目标状态<math>s'</math>的能量可能与当前状态类似时，应该使生成器向候选的地方移动倾斜。这种启发式(这是Metropolis-Hastings算法的主要原则)倾向于排除“非常好的”候选移动和“非常糟糕的”候选移动;然而，前者通常比后者少得多，所以启发式通常是相当有效的。
例如，在上面的旅行商问题中，也就是TSP问题（Traveling Salesman Problem）。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。在一个寻找最短路径的旅行中，对两个连续的城市所走的顺序进行交换，预计会对其能量(长度)产生适度的影响;而交换两个任意的城市的移动顺序更有可能增加而不是减少城市的长度。因此，预期连续交换邻接生成器的性能要优于任意交换生成器，尽管后者可以提供更短的路径来达到最佳状态(使用<math>n-1</math>交换，而不是<math>n(n-1)/2</math>)。
关于这种启发式的一个更精确的陈述是，人们应该尝试第一个候选状态的数学 s / math，对于这个状态的数学 p (e (s) ，e (s’) ，t) / math 是很大的。对于上面提到的“标准”接受函数数学 p / math，它意味着数学 e (s’)-e (s) / math 的顺序是数学 t / math 或更少。因此，在上面的旅行推销员的例子中，我们可以使用一个交换两个随机城市的函数，其中选择一个城市对的概率消失了，因为它们的距离增加超过了数学 t / math。
一个更精确的启发式陈述是，我们应该尝试第一个候选状态<math>s'</math>，其中<math>P(E(s)， E(s')， T)</math>很大。对于上面的“标准”接受函数<math>P</math>，这意味着<math>E(s') - E(s)</math>的长度是<math>T</math>或更少。因此，在上面的旅行商问题中，我们可以使用一个函数来交换两个随机城市，当它们的距离超过<math>T</math>时，就不再选择该城市对。
一个更精确的启发式陈述是，我们应该尝试第一个候选状态<math>s'</math>，其中<math>P(E(s)， E(s')， T)</math>很大。
===避障Barrier avoidance===
===避障Barrier avoidance===
在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。
在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。
这种能量函数的“封闭集水盆地”可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以指数形式反映周围状态与盆地底部的能量差)困住模拟退火算法。
这种能量函数的“封闭集水盆地”可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以指数形式反映周围状态与盆地底部的能量差)困住模拟退火算法。
在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。这种局部优解的聚集相当于在解空间形成了“盆地”，使得对应的能量函数可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以周围状态与盆地底部的能量差的指数形式反映)困住模拟退火算法。
--~~这句话我有些不太理解 只能先直译一下，感觉有些像说 盆地是指较优点，会困住模拟退火算法
一般来说，不可能设计一个候选生成器，既能满足这个目标，又能优先考虑具有类似能量的候选移动。另一方面，通过对生成器进行相对简单的更改，可以极大地提高模拟退火的效率。例如在旅行商问题中，不难看出旅行<math>A</math>, <math>B</math>有着近似相等的长度：
一般来说，不可能设计一个候选生成器，既能满足这个目标，又能优先考虑具有类似能量的候选移动。另一方面，通过对生成器进行相对简单的更改，可以极大地提高模拟退火的效率。例如在旅行商问题中，不难看出旅行<math>A</math>, <math>B</math>有着近似相等的长度
（1）<math>A</math>处最优；
（1）<math>A</math>处最优；
（2）从<math>A</math>到<math>B</math>的每个城市对相互转换，经过更长的旅程
（2）从<math>A</math>到<math>B</math>的每个城市对相互转换，经过更长的旅程
===冷却时刻表===
===冷却时刻表Cooling schedule===
用来证明模拟退火合理性的物理类比是假定冷却速率足够低，使当前状态的概率分布在任何时候都接近[[热力学平衡]]。遗憾的是，弛豫时间——一个人必须等待平衡在温度变化后恢复的时间——强烈地依赖于能量函数的“地形”和当前的温度。在模拟退火算法中，弛豫时间也以非常复杂的方式依赖于候选生成器。注意，所有这些参数通常都作为[[黑盒函数]]提供给模拟退火算法。因此，理想的冷却速率不能预先确定，应该根据实际情况对每个问题进行调整。自适应模拟退火算法通过将冷却计划与搜索过程相结合来解决这个问题。其他自适应方法如热力模拟退火<ref>{{cite journal |doi=10.1016/j.physleta.2003.08.070 |title=Placement by thermodynamic simulated annealing |year=2003 |last1=De Vicente |first1=Juan |last2=Lanchares |first2=Juan |last3=Hermida |first3=Román |journal=Physics Letters A |volume=317 |issue=5–6 |pages=415–423|bibcode=2003PhLA..317..415D }}</ref>，根据美国热力学定律协会的说法，可以根据两种状态之间的能量差自动调节每一步的温度。
==重新启动Restarts==
==重新启动Restarts==