更改

This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the global optimal solution. In general, simulated annealing algorithms work as follows. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions, which during the search respectively remain at 1 (or positive) and decrease towards zero.

This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the global optimal solution. In general, simulated annealing algorithms work as follows. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions, which during the search respectively remain at 1 (or positive) and decrease towards zero.

模拟退火算法中实现的缓慢冷却的概念可被理解为探索解决方案空间时接受较差解决方案的概率缓慢下降。由于元启发法允许对全局最优解进行更广泛的搜索,所以接受较差的解可以说是元启发法的一个基本属性。一般来说，模拟退火算法的工作原理如下：温度从最初的正值逐渐降低到零。该算法在每个时间步长上随机选择一个接近当前解的解，测量其质量，并根据温度相关的概率选择更好或更坏的解，在搜索过程中分别保持在1(或正值)并向零递减。

模拟退火算法中实现缓慢冷却的概念可被理解为探索解决方案空间时接受较差解决方案的概率缓慢下降。由于元启发法允许对全局最优解进行更广泛的搜索，所以接受较差的解可以说是元启发法的一个基本属性。一般来说，模拟退火算法的工作原理如下：温度从最初的正值逐渐降低到零。该算法在每个时间步长上随机选择一个接近当前解的解，测量其质量并根据温度相关的概率选择更好或更坏的解，在搜索过程中分别保持在1(或正值)并向零递减。

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.

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的某个相邻状态s *，并概率性地决定系统的下一个状态是移至状态s *还是保持状态s。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。

在每个步骤中，模拟退火这种启发式算法都会考虑当前状态s的某个相邻状态<math>s*<\math>，并概率性地决定系统的下一个状态是移至状态<math>s*<\math>还是保持状态<math>s<\math>。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。

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.

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.

从当前状态<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>，这个特性可以防止陷入比全局最小值糟糕的局部最小值。

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.

当<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>的过程，只有下坡过渡，简化为贪婪算法。

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.

在模拟退火的原始描述中，当<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> 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

The <math>P</math>函数的选择通常是为了降低接受移动的概率

The <math>P</math>函数的选择通常是为了降低接受移动的概率。

<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>很小时，它对精细能量变化更为敏感。

考虑到这些性质，因为温度<math>T</math>对系统能量变化很敏感，所以它在控制系统状态<math>s</math>的演化方面起着至关重要的作用。准确地说，对于一个庞大的<math>T</math>来说，<math>s</math>的变化对比粗略的能量变化更为敏感，当<math>T</math>很小时，它对精细能量变化更为敏感。

===The annealing schedule===

===The annealing schedule===

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.

算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征。需要随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。

算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。

The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state  and continues until a maximum of  steps have been taken. In the process, the call  should generate a randomly chosen neighbour of a given state ; the call  should pick and return a value in the range , uniformly at random. The annealing schedule is defined by the call , which should yield the temperature to use, given the fraction  of the time budget that has been expended so far.

The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state  and continues until a maximum of  steps have been taken. In the process, the call  should generate a randomly chosen neighbour of a given state ; the call  should pick and return a value in the range , uniformly at random. The annealing schedule is defined by the call , which should yield the temperature to use, given the fraction  of the time budget that has been expended so far.

下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>''s''₀</math>开始，一直持续到已经采取了最多<math>k_max</math>个步骤。在这个过程中，调用<math>neighbour(s)</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(r)</math>定义，给定到目前为止所花费的时间预算的分数<math>r<\math>，调用该温度来产生要使用的温度。

下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>s₀</math>开始，一直持续到已经采取了最多<math>k_max</math>个步骤。在这个过程中，调用<math>neighbour(s)</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(r)</math>定义，给定到目前为止所花费的时间预算的分数<math>r<\math>，调用该温度来产生要使用的温度。