模拟退火算法新课件

1 1第五章第五章 模拟退模拟退火火2 2第五章第五章 模拟退火模拟退火一一.导言导言二.退火过程和Bolzman方程三.SA的算法构造及步骤四.计算举例五.SA的收敛性分析六.SA的应用举例3 31.1.模拟退火的产生模拟退火的产生(SA)19531953年年 MetropolisMetropolis提出原始的提出原始的SA算法，未引算法，未引起反响起反响19821982年年 KirkpatrickKirkpatrick提出现代的提出现代的SA算法，得到算法，得到广泛的应用广泛的应用一一.导言导言（1 1）4 42.2.基本思想基本思想模拟热力学当中的退火过程模拟热力学当中的退火过程退火过程：退火过程：物体：物体：高温高温低温低温 高能状态高能状态低能状态低能状态一一.导言导言（2 2）缓慢下降缓慢下降缓慢下降缓慢下降5 5淬火：淬火：快速冷却，使金属处于高能状态，较硬易断快速冷却，使金属处于高能状态，较硬易断退火：退火：缓慢冷却，使金属处于低能状态，较为柔韧缓慢冷却，使金属处于低能状态，较为柔韧一一.导言导言（3 3）6 63.3.模拟退火在模拟退火在SA中的应用中的应用在在SA中将目标函数作为能量函数中将目标函数作为能量函数模拟：模拟：初始高温初始高温 温度缓慢下降温度缓慢下降 终止在低温终止在低温这时能量函数达到极小，目标函数最小这时能量函数达到极小，目标函数最小一一.导言导言（4 4）7 71.1.热力学中的退火过程热力学中的退火过程变温物体缓慢降温从而达到分子之间能量最变温物体缓慢降温从而达到分子之间能量最低的状态低的状态二二.退火过程和退火过程和BolzmanBolzman方程方程（1 1）8 8二二.退火过程和退火过程和BolzmanBolzman方程方程（2 2）9 92.2.2.2.BolzmanBolzman方程方程二二.退火过程和退火过程和BolzmanBolzman方程方程（3 3）10103.3.温度温度 对对 的影响的影响当当 很大时，很大时，各状态的概率几乎相等，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降开始做广域搜索，随着温度的下降 差别差别扩大扩大二二.退火过程和退火过程和BolzmanBolzman方程方程（4 4）1111当当 时，时，与与 的小差别带来的小差别带来 和和 的巨大差别的巨大差别例如：例如：=90，=100，二二.退火过程和退火过程和BolzmanBolzman方程方程（5 5）1212I.I.当当=100时时二二.退火过程和退火过程和BolzmanBolzman方程方程（6 6）1313II.II.当当 =1时时此时此时结论结论:时，以概率时，以概率1趋于最小能量状态趋于最小能量状态二二.退火过程和退火过程和BolzmanBolzman方程方程（7 7）14141.1.SA的模拟要求的模拟要求初始温度足够高初始温度足够高降温过程足够慢降温过程足够慢终止温度足够低终止温度足够低三.SA的算法构造及步骤（1 1）15152.2.问题的描述及要素问题的描述及要素三.SA的算法构造及步骤（2 2）16163.3.SA的计算步骤的计算步骤初始化初始化,任选初始解任选初始解,给定初始温度给定初始温度 ，终止温度终止温度 ，令迭代指标，令迭代指标 。注：选择注：选择 时，要足够高，使时，要足够高，使随机产生一个邻域解，随机产生一个邻域解，计算目标值增量计算目标值增量三.SA的算法构造及步骤（3 3）1717若若 转步转步 (j(j比比i i好无条件转移好无条件转移)；否则产生；否则产生 (j(j比比i i好，有条件转移好，有条件转移)。注：注：高时，广域搜索；高时，广域搜索；低时，局域搜索低时，局域搜索若达到热平衡若达到热平衡(内循环次数大于内循环次数大于 )转步转步，否则转步，否则转步。三.SA的算法构造及步骤（4 4）1818 降低降低 ，若，若 停止，否则转步停止，否则转步。注：降低注：降低 的方法有以下两种的方法有以下两种流程框图见下页流程框图见下页三.SA的算法构造及步骤（5 5）1919内循环内循环内循环内循环产生产生产生产生开始开始开始开始停止停止停止停止Y YN NY YN N，降温，降温，降温，降温外循环外循环外循环外循环设定设定设定设定产生产生产生产生 计算计算计算计算Y YY YN NN N20201.1.1.1.问题的提出问题的提出单机极小化总流水时间的排序问题单机极小化总流水时间的排序问题四个工作：四个工作：，求，求 的最优顺序。的最优顺序。四.计算举例（1 1）2121预备知识：按预备知识：按SPTSPT准则，最优顺序为准则，最优顺序为3-1-4-23-1-4-2四.计算举例（2 2）2222用用SA求解这个问题求解这个问题状态表达：顺序编码状态表达：顺序编码邻域定义：两两换位定义为邻域移动邻域定义：两两换位定义为邻域移动解：解：设设降温过程定义为降温过程定义为初始解：初始解：i=1-4-2-3四.计算举例（3 3）2323 注释：注释：注释：注释：1.1.无条件转移；无条件转移；无条件转移；无条件转移；2.2.为有条件转移；为有条件转移；为有条件转移；为有条件转移；3.3.在在在在中，虽然目标值变坏，但搜索范围变大；中，虽然目标值变坏，但搜索范围变大；中，虽然目标值变坏，但搜索范围变大；中，虽然目标值变坏，但搜索范围变大；4.4.是随机产生的是随机产生的是随机产生的是随机产生的 四.计算举例（4 4）2424注释：注释：1.1.有条件转移；有条件转移；2.2.为无条件转移；为无条件转移；3.3.在在中，停在中，停在4-3-1-2状态，目标值仍为状态，目标值仍为109；四.计算举例（5 5）2525注释：注释：注释：注释：1.1.无条件转移；无条件转移；无条件转移；无条件转移；2.2.在在在在中，停在中，停在中，停在中，停在3-1-4-23-1-4-2状态，目标值仍为状态，目标值仍为状态，目标值仍为状态，目标值仍为9292；SASA没有历史最优，不会终止在最优解，故算法一没有历史最优，不会终止在最优解，故算法一没有历史最优，不会终止在最优解，故算法一没有历史最优，不会终止在最优解，故算法一定要保持历史最优。定要保持历史最优。定要保持历史最优。定要保持历史最优。四.计算举例（6 6）2626SA终止在最优解上的条件：终止在最优解上的条件：初始温度足够高初始温度足够高热平衡时间足够长热平衡时间足够长终止温度足够低终止温度足够低降温过程足够慢降温过程足够慢以上条件实际中很难满足，所以只能记录历以上条件实际中很难满足，所以只能记录历史最优解。史最优解。四.计算举例（7 7）2727SA特点：编程最容易，理论最完善。下面基于特点：编程最容易，理论最完善。下面基于Markov过程分析收敛性。过程分析收敛性。四.计算举例（8 8）28281.1.Markov过程的基本概念过程的基本概念举例说明：盲人一维游走、醉汉或青蛙在举例说明：盲人一维游走、醉汉或青蛙在3块石块石头上随机跳动，这头上随机跳动，这3中状况可用来说明这个问中状况可用来说明这个问题，他们行动的共同特点是无记忆性。题，他们行动的共同特点是无记忆性。五.SA的收敛性分析（1 1）2929基本概念基本概念状态：状态：处于系统中的一种特定状态表达。处于系统中的一种特定状态表达。状态转移概率：状态转移概率：从状态从状态 i 转移到状态转移到状态 j 的可能性。的可能性。无后效应：无后效应：到一个状态后，决策只与本状态有关，与以到一个状态后，决策只与本状态有关，与以前的历史状态无关。前的历史状态无关。五.SA的收敛性分析（2 2）3030以青蛙跳动为例说明状态转移概率以青蛙跳动为例说明状态转移概率用石头唯一的表达青蛙所处的状态，假设青蛙用石头唯一的表达青蛙所处的状态，假设青蛙跳动具有无后效应的特点。跳动具有无后效应的特点。五.SA的收敛性分析（3 3）1/31/31/31/31/41/41/41/41/21/21/21/2青蛙跳动图示青蛙跳动图示青蛙跳动图示青蛙跳动图示状态转移概率矩阵：状态转移概率矩阵：状态转移概率矩阵：状态转移概率矩阵：1/31/31/41/41/41/43131t时刻处在各状态的概率向量时刻处在各状态的概率向量是行向量，假设系统在是行向量，假设系统在t+1时达到稳态，则时达到稳态，则五.SA的收敛性分析（4 4）3232解方程组：解方程组：可得结果：可得结果：可见青蛙是跳到第三块石头上的机会多一些可见青蛙是跳到第三块石头上的机会多一些五.SA的收敛性分析（5 5）33332.2.SA的收敛性分析的收敛性分析问题：问题：将状态按目标值进行升序编号，将状态按目标值进行升序编号，即即五.SA的收敛性分析（6 6）3434状态间的转移概率状态间的转移概率设设 为为 i 选选 j 为邻域点时，为邻域点时，i j的转移概率的转移概率五.SA的收敛性分析（7 7）3535设设是系统处于状态是系统处于状态 i 时选择时选择 j 为邻域移动点为邻域移动点的概率，的概率，为状态为状态 i 的邻域点的个数，则的邻域点的个数，则则状态则状态 i 到状态到状态 j 的转移概率为的转移概率为五.SA的收敛性分析（8 8）3636当当Tk很大时，则状态转移矩阵为：很大时，则状态转移矩阵为：分两种情况讨论：分两种情况讨论：五.SA的收敛性分析（9 9）3737I.I.当当五.SA的收敛性分析（1010）3838II.II.当当当当状态状态1是是“捕捉的捕捉的”（任何状态到（任何状态到1状态后都无状态后都无法法转出）即青蛙跳到石头转出）即青蛙跳到石头1上无法跳出。上无法跳出。五.SA的收敛性分析（1111）3939推理证明：推理证明：证毕证毕即即SA将以概率将以概率1停在状态（石头）停在状态（石头）1上。上。五.SA的收敛性分析（1212）4040定理：当定理：当定理：当定理：当P P对称时，当达到热平衡时，对所有对称时，当达到热平衡时，对所有对称时，当达到热平衡时，对所有对称时，当达到热平衡时，对所有有：有：有：有：定理证明见下页。定理证明见下页。定理证明见下页。定理证明见下页。五.SA的收敛性分析（1313）4141定理证明：定理证明：定理证明：定理证明：当达到热平衡时有当达到热平衡时有当达到热平衡时有当达到热平衡时有五.SA的收敛性分析（1414）42421.1.问题：成组技术中加工中心的组成问题问题：成组技术中加工中心的组成问题设有设有m台机器，要组成若干个加工中心，每个台机器，要组成若干个加工中心，每个加工中心可有最多加工中心可有最多q台、最少台、最少p台机器，有台机器，有n种种加工工作要在这些机器上加工。加工工作要在这些机器上加工。如何组织加工中心，可使总的各中心的机器相如何组织加工中心，可使总的各中心的机器相似性最好。似性最好。六.SA的应用举例（1 1）4343六.SA的应用举例（2 2）4444六.SA的应用举例（3 3）4545六.SA的应用举例（4 4）4646所有相似的机器放在同一个中心，极大化成组相似性所有相似的机器放在同一个中心，极大化成组相似性所有相似的机器放在同一个中心，极大化成组相似性所有相似的机器放在同一个中心，极大化成组相似性指定唯一性，一个机器只能放一个中心指定唯一性，一个机器只能放一个中心指定唯一性，一个机器只能放一个中心指定唯一性，一个机器只能放一个中心每一个中心的机器数小于每一个中心的机器数小于每一个中心的机器数小于每一个中心的机器数小于q q台台台台每一个中心的机器数至少有每一个中心的机器数至少有每一个中心的机器数至少有每一个中心的机器数至少有p p台台台台六.SA的应用举例（5 5）4747用用SA求解求解六.SA的应用举例（6 6）4848六.SA的应用举例（7 7）不够时的惩罚不够时的惩罚不够时的惩罚不够时的惩罚多了时的惩罚多了时的惩罚多了时的惩罚多了时的惩罚4949六.SA的应用举例（8 8）控制参数控制参数控制参数控制参数50501.1.编程最容易编程最容易2.2.大时，广域搜索性能好大时，广域搜索性能好 小时，局域搜索性能好小时，局域搜索性能好3.3.理论上停止在最优解上，但实际上很难做到理论上停止在最优解上，但实际上很难做到4.4.SA是达优性较差的算法是达优性较差的算法七.学习SA的几点体会（1 1）