763
个编辑
更改
跳到导航
跳到搜索
第54行：
第54行： − {{multiple image − − {{multiple image − − {多重图像 − − | align = right − − | align = right − − 右对齐 − − | total_width = 400 − − | total_width = 400 − − 总宽度400 − − | image_gap = 0 − − | image_gap = 0 − − 图像缺口0 − − − − | image1 = SimulatedAnnealingFast.jpg − − | image1 = SimulatedAnnealingFast.jpg − − | image1 = SimulatedAnnealingFast.jpg − − | alt1 = Fast − − | alt1 = Fast − − 1 Fast − − | caption1 = Fast − − | caption1 = Fast − − 1 Fast − − − − | image2 = SimulatedAnnealingSlow.jpg − − | image2 = SimulatedAnnealingSlow.jpg − − | image2 = SimulatedAnnealingSlow.jpg − − | alt2 = Slow − − | alt2 = Slow − − 2 Slow − − | caption2 = Slow − − | caption2 = Slow − − 2慢 − − − − | footer= Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the [[pixel]]s of an image so as to minimize a certain [[potential energy]] function, which causes similar [[colour]]s to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to [[amorphous solid|amorphous]] and [[crystalline solid]]s, respectively. − − | footer= Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the pixels of an image so as to minimize a certain potential energy function, which causes similar colours to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to amorphous and crystalline solids, respectively. − − }} − − }} − − }} − − − For any given finite problem, the probability that the simulated annealing algorithm terminates with a [[global optimum|global optimal]] solution approaches 1 as the annealing schedule is extended.<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> 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 [[Brute-force search|complete search]] of the [[solution space]].{{Citation needed|date=June 2011}} − − 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.
→退火时间表
=== 退火时间表 ===
=== 退火时间表 ===
举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（左）和缓慢冷却过程（右）获得的，分别产生类似于非晶态和结晶态固体。
举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（左）和缓慢冷却过程（右）获得的，分别产生类似于非晶态和结晶态固体。
算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。
算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。
对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近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}}
对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近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}}