模拟退火 - 版本历史

乐多多：/* 参数选择 */

2020-05-21T03:40:37Z

参数选择

乐多多：/* 相关算法 */

2020-05-19T08:37:27Z

乐多多：/* 退火时间表 */

2020-05-19T08:36:42Z

退火时间表

2020年5月19日 (二) 08:30 乐多多

2020-05-19T08:30:01Z

乐多多：/* 参数选择 */

2020-05-19T08:26:28Z

参数选择

乐多多：/* 概述 */

2020-05-19T08:26:05Z

概述

乐多多：/* 编者推荐 */

2020-05-19T08:25:03Z

编者推荐

乐多多：/* 参数选择 */

2020-05-19T08:23:01Z

参数选择

乐多多：/* 参数选择 */

2020-05-19T08:21:39Z

参数选择

乐多多：/* 编者推荐 */

2020-05-19T08:20:40Z

编者推荐

←上一版本		2020年5月21日 (四) 03:40的版本
第116行：		第116行：

	===避障===		===避障===
−	~~在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。~~
−	这种能量函数的“封闭集水盆地”可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以指数形式反映周围状态与盆地底部的能量差)困住模拟退火算法。
−
−	~~--~~这句话我有些不太理解只能先直译一下，感觉有些像说盆地是指较优点，会困住模拟退火算法~~
	在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。这种局部优解的聚集相当于在解空间形成了“盆地”，使得对应的能量函数可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以周围状态与盆地底部的能量差的指数形式反映)困住模拟退火算法。		在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。这种局部优解的聚集相当于在解空间形成了“盆地”，使得对应的能量函数可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以周围状态与盆地底部的能量差的指数形式反映)困住模拟退火算法。

@@ 第137行： / 第137行： @@
 ==相关算法==
-*[[交互Metropolis–Hasting算法]](又名顺序蒙特卡罗算法)<ref name=":3">{{Cite journal|title = Sequential Monte Carlo samplers - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library| doi=10.1111/j.1467-9868.2006.00553.x|volume=68| issue=3|journal=Journal of the Royal Statistical Society, Series B|pages=411–436|arxiv=cond-mat/0212648|year = 2006|last1 = Del Moral|first1 = Pierre| last2=Doucet| first2=Arnaud| last3=Jasra| first3=Ajay}}</ref>)结合模拟退火算法，采用交互循环机制，对最适合的个体进行接受-拒绝。
+*[[交互Metropolis–Hasting算法]](又名顺序蒙特卡罗算法)<ref name=":3">{{Cite journal|title = Sequential Monte Carlo samplers - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library| doi=10.1111/j.1467-9868.2006.00553.x|volume=68| issue=3|journal=Journal of the Royal Statistical Society, Series B|pages=411–436|arxiv=cond-mat/0212648|year = 2006|last1 = Del Moral|first1 = Pierre| last2=Doucet| first2=Arnaud| last3=Jasra| first3=Ajay}}</ref>结合模拟退火算法，采用交互循环机制，对最适合的个体进行接受-拒绝。
 *[[量子退火 Quantum annealing]]使用“量子涨落 quantum fluctuations”而不是热涨落来穿过目标函数中高而薄的屏障。

@@ 第51行： / 第51行： @@
 === 退火时间表 ===
-[[File:fast.jpg|150px|right]]
+[[File:fast.jpg|150px|thumb|right]]
 [[File:slow.jpg|150px|thumb|right|举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（上）和缓慢冷却过程（下）获得的，分别产生类似于非晶态和结晶态固体。]]
 算法的名称和灵感需要在算法的运行特性中嵌入一个与温度变化有关的有趣特征，并随着模拟的进行逐渐降低温度。该算法首先将<math>T</math>设置为一个大值(或无穷大) ，然后按照某种退火时间表(可由用户指定，但必须在分配的时间预算结束时以<math>T=0</math>结束)逐步减少。通过这种方式，系统可以按照预期最初在包含良好解的广阔搜索空间游走，忽略能量函数的小特征; 然后向越来越窄的低能量区域漂移; 最后根据梯度下降法启发式向下移动。

←上一版本		2020年5月19日 (二) 08:30的版本
第1行：		第1行：
		+	{{#seo:
		+	\|keywords=模拟退火,蒙特卡罗,最优化算法
		+	\|description=模拟退火 Simulated annealing,最优化算法
		+	}}
	[[File:Travelling1.gif\|300px\|thumb\|right\|模拟退火可以用来解决组合问题。这里我们将它应用到旅行商问题-最小化连接所有125个点的路径长度]]		[[File:Travelling1.gif\|300px\|thumb\|right\|模拟退火可以用来解决组合问题。这里我们将它应用到旅行商问题-最小化连接所有125个点的路径长度]]
	'''模拟退火 Simulated annealing SA'''是一种用于逼近给定函数全局最优值的概率方法。具体来说，它是在大搜索空间中针对优化问题近似全局优化提出的一种元启发法。当搜索空间是离散的(例如旅行商问题)时，经常使用它。对于那些在一定时间内找到一个近似的全局最优解比找到一个精确的局部最优解更重要的问题，模拟退火可能比诸如梯度下降等替代方法更可取。		'''模拟退火 Simulated annealing SA'''是一种用于逼近给定函数全局最优值的概率方法。具体来说，它是在大搜索空间中针对优化问题近似全局优化提出的一种元启发法。当搜索空间是离散的(例如旅行商问题)时，经常使用它。对于那些在一定时间内找到一个近似的全局最优解比找到一个精确的局部最优解更重要的问题，模拟退火可能比诸如梯度下降等替代方法更可取。

@@ 第77行： / 第77行： @@
-=== 跃迁概率 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 ===
+=== 接受概率===
 {{code|neighbour()}}, {{code|P()}}和{{code|temperature()}}的规范部分是多余的。在实际应用中，对许多问题使用相同的验收函数，并根据具体问题对其他两个函数进行调整，这是很常见的。

@@ 第19行： / 第19行： @@
-=== 基本迭代The basic iteration ===
+=== 基本迭代 ===
 在每个步骤中，模拟退火这种启发式算法都会考虑当前状态<math>s</math>的某个相邻状态<math>s*</math>，并概率性地决定系统的下一个状态是移至状态<math>s*</math>还是保持状态<math>s</math>。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。
-=== 城市的邻居 The neighbours of a state ===
+=== 城市的邻居===
 解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守改变给定状态而产生的新状态。例如在[[旅行商问题]]中，每个地点通常被定义为要访问的城市的排列，通过反转任意两个邻近城市顺序产生邻居的排列集合，不同的移动方式将产生不同的近邻城市集。这种明确界定的改变各地以产生邻近城市集合的方式被称为“移动”。这些移动最后通常会让状态的更改迭代量降到最低，尝试通过迭代改善解决方案的组成部分（例如旅行商问题中的城市联系）来逐步改善解决方案。
 像爬山这样的简单启发式方法通过逐步寻找更好的邻居移动，在没有更好邻居处停止，这种方法结果很容易得到局部最优解，而实际最优解可能是有所不同的全局最优解。元启发法为避免陷入局部最优，通过改变选择邻居的方法（即尽管他们更喜欢更好的邻居，但他们也接受更坏的邻居）把解的邻居用作探索解空间。如果运行足够长的时间，这种方法可以找到全局最优值。
@@ 第41行： / 第40行： @@
-The <math>P</math>函数的选择通常是为了降低接受移动的概率。
+The <math>P</math>函数的选择通常是为了降低接受移动的概率。<math>e'-e</math>增加意味着小的上坡动作比大的动作更有可能发生。如果符合上述要求，这一要求并非绝对必要。

@@ 第243行： / 第243行： @@
 ----
-本中文词条由[[用户:趣木木|趣木木]]用户参与编译，[[用户:木子二月鸟|木子二月鸟]]审校，[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。
+本中文词条由[[用户:沐晨|沐晨]]、[[用户:趣木木|趣木木]]用户参与编译，[[用户:乐多多|乐多多]]编辑，欢迎在讨论页面留言。
 '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''

←上一版本		2020年5月19日 (二) 08:23的版本
第78行：		第78行：

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

@@ 第119行： / 第119行： @@
 这种能量函数的“封闭集水盆地”可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以指数形式反映周围状态与盆地底部的能量差)困住模拟退火算法。
+ --~~这句话我有些不太理解 只能先直译一下，感觉有些像说 盆地是指较优点，会困住模拟退火算法
 在选择候选生成器时，还必须尝试减少具有比所有相邻状态低得多的能量的“深层”局部最小状态(或连接状态集)的数量。这种局部优解的聚集相当于在解空间形成了“盆地”，使得对应的能量函数可能以很高的概率(大致与盆地内的状态数成正比)并在很长一段时间内(大致以周围状态与盆地底部的能量差的指数形式反映)困住模拟退火算法。

@@ 第224行： / 第224行： @@
 ==编者推荐==
-[[File:1201005378_0_1_800x800.jpg|200px|thumb|right《随机模拟方法与应用》封面|]]
+[[File:1201005378_0_1_800x800.jpg|250px|thumb|right|《随机模拟方法与应用》封面|]]
 ===书籍推荐===
 *[https://book.douban.com/subject/26287261/ 随机模拟方法与应用]