9.1 固体退火过程

1 固体退火过程

• 先将固体加热至熔化，然后再徐徐冷却使之凝固成规整晶体的热力学过程。

 

 

 

 

• 退火过程要求温度缓慢下降，退火过程必须“徐徐”进行，
• 是为了使系统在每一个温度下都达到平衡态，最终达到固体的基态。
• 退火过程中系统的熵值不断减小，
  • 系统的能量也随温度的下降趋于最小值。

 

2 某一温度下固体所处的微观状态

• 在某一温度,受随机因素影响,固体可处于不同的微观状态
• 对每一个微观状态,固体内部是一个系统,系统有其自身的能量。

 

 

 

9.2 Metropolis准则

9.3 模拟退火算法

• 1982年，Kirk-patrick等
  • 固体退火过程与组合最优化问题之间存在类似。
• 把固体退火过程的Metro-polis准则引入到最优化问题的优化过程中，
  • 得到一种以Metropolis算法为基础的求解组合最优化问题的算法。
  • 称“模拟退火算法”。

 

 

• 最优化问题的模拟退火。

• 模拟退火算法流程图

 

• 一个是内循环，一个是外循环。
• 内循环是在同一个温度下，按一定规则随机搜索，
  • 目的是找到“较好”的解。

 

• 内循环的循环次数应多少？

 

• 外循环应该循环多少次？

 

• 例题9.3.1
• 5个城市的TSP，
• A起点

 

• 计算在30度时的内循环迭代过程；
• 20时的内循环迭代过程。
• 每个内循环中，新的迭代点的产生，用随机互换两个城市位置得到。

 

30度的时候迭代

 

---

---

 

 

---

 

---

 

---

 

---

 

• 经若干次迭代后,温度为30时的迭代过程停止,
• 得到温度为30时的“较好”的解
  ABCED
  44

20度的时候迭代

• 计算20时的迭代过程。
• 从30时的“较好”的解
  ABCED
• 出发,进行20时的迭代。

 

 

---

 

---

• 经过若干迭代,20时的迭代过程停止,
• 得到20时的“较好”解
  ACBED
  43

 

---

• 1)内循环的迭代次数应该是多少
• 2)外循环的迭代次数应该是多少
• 3)算法是否收敛
• 下面数学理论将回答这些问题

9.4 模拟退火算法的收敛性

9.4.1 随机过程简介

• 一族无穷多随机变量$\{X(t),t\in\}${X(t),t∈}称随机过程。

• $T$T称为参数集

• 对于随机变量序列$\{X(n),n=0,1…\}${X(n),n=0,1…}

  • 如果满足

• 则称马尔可夫过程。
• 为强调参数是非负整,又称马尔可夫链。

 

 

9.5 冷却进度表

9.6 模拟退火算法的应用