31
个编辑
更改
跳到导航
跳到搜索
第227行：
第227行： + 第238行：
第239行： − 算法的名称和灵感要求在算法的运行特性中嵌入一个与温度变化有关的有趣特征。这需要随着模拟的进行逐渐降低温度。该算法首先将 math t / math 设置为一个高值(或无穷大) ，然后按照某种退火时间表(可能由用户指定，但必须在分配的时间预算结束时以 math t 0 / math 结束)逐步减少。通过这种方式，系统被期望最初走向包含良好解的搜索空间的广阔区域，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。+ 第246行：
第247行： − 对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近1。然而，这一理论结果并不特别有用，因为确保取得重大成功的可能性所需的时间通常超过完全搜索解决方案空间所需的时间。+ 第256行：
第257行： − 下面的伪代码展示了上面描述的模拟退火启发式代码。它从一个状态开始，一直持续到采取了最多个步骤。在这个过程中，调用应该产生一个给定状态的随机选择的邻居; 调用应该选择并返回一个范围内的值，均匀地随机。退火时间表是由调用定义的，它应该产生使用的温度，给定的部分时间预算已经花费到目前为止。+
无编辑摘要
冷却时间表对模拟退火性能的影响的例子。问题在于重新排列图像的像素点，使某个势能函数最小化，从而导致相似的颜色在短距离内相互吸引，在稍大的距离内相互排斥。Elementary 移动交换两个相邻的像素。这些图像获得了一个快速冷却时间表(左)和一个缓慢的冷却时间表(右) ，产生的结果分别类似于非晶和晶体固体。
冷却时间表对模拟退火性能的影响的例子。问题在于重新排列图像的像素点，使某个势能函数最小化，从而导致相似的颜色在短距离内相互吸引，在稍大的距离内相互排斥。Elementary 移动交换两个相邻的像素。这些图像获得了一个快速冷却时间表(左)和一个缓慢的冷却时间表(右) ，产生的结果分别类似于非晶和晶体固体。
举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（左）和缓慢冷却过程（右）获得的，分别产生类似于非晶态和结晶态固体。
}}
}}
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>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。
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。然而，因为确保取得大概率成功所需的时间通常超过完全搜索解决方案空间所需的时间，所以这一理论结果并不是特别有用，
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''<sub>0</sub></math>开始，一直持续到已经采取了最多<math>''k''<sub>max</sub></math>个步骤。在这个过程中，调用<math>neighbour(''s'')</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(''r'')</math>定义，给定到目前为止所花费的时间预算的分数<mvar>r<\mvar>，调用该温度来产生要使用的温度。