1、CS_Dept.Sichaun Univ.2022/5/181/44Simulated AnnealingCS_Dept.Sichaun Univ.2022/5/182/44CS_Dept.Sichaun Univ.2022/5/183/44 提纲CS_Dept.Sichaun Univ.2022/5/184/44参考资料：参考资料： 本本PPT仅作和同学们在讨论版内交流之用仅作和同学们在讨论版内交流之用参考了若干教科书，文献和论文和报告。n在末尾列出50多篇，但参考的文献不只这些,主要是遗传算法、基因表达式编程、粒子群算法 的相关作者等等，包括 国内外，校内外专家和本实验室成员的工作n对未列
2、出的文献作者也在此一并致谢。n参考文献可能有遗漏，欢迎未列出的文献作者及时指出，以便即时在参考文献中补充、引用。n作PPT类似于把小说改编为剧本，有重新创作的成分，也希望其它引用本PPT材料的标注 本PPTCS_Dept.Sichaun Univ.2022/5/185/44n有多位（7-8位）博士生导师作专题讲座，n 每个老师讲课8小时（大约需要准备 40-60小时）n特点n广- N位导师，N=89 ,N + 个领域，M个课题，(MN).n “N家讲座” ，不敢比 百家n新 -要求报告 新技术前沿n浅 因为时间短，主要将思想，方法，介绍成果。不可能深入到公式和算法细节n实-结合实际，结合博士生
3、可能的选题CS_Dept.Sichaun Univ.2022/5/186/44n这里根据情况 插讲 自然计算模型PPTn欢迎同学 报告、讨论，发言补充 （5-30分钟 均可）n介绍.CS_Dept.Sichaun Univ.2022/5/187/44贪心算法及其批判-模拟退火 算法Greedy Algorithm andSimulated Annealing Algorithm唐常杰川大计算机学院CS_Dept.Sichaun Univ.2022/5/188/44n贪心算法属于自然计算吗？ 勉强 算是。n模拟了 部分人、在部分时间的心理社会行为n人性善：理性（理想、信仰、道德） 非理性时。n部
4、分人/在部分时间 ，上述不等式 反过来了，表现出贪心。n贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大n贪心算法的基本思想：追求每一步获利最大n人 贪心 固然 不好， 但贪心算法但贪心算法 有时是好用的有时是好用的 。n不贪心的人， 在生活中 会贪心算法吗？ 会。且看下页。CS_Dept.Sichaun Univ.2022/5/189/44n贪心算法属于自然计算吗？ 勉强 算是。n模拟了 部分人、在部分时间的心理社会行为n人性善：理性（理想、信仰、道德） 非理性时。n部分人/在部分时间 ，上述不等式 反过来了，表现出贪心。n贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大n贪心算法的
5、基本思想：追求每一步获利最大n人 贪心 固然 不好， 但贪心算法但贪心算法 有时是好用的有时是好用的 。n不贪心的人， 在生活中 会用贪心算法吗？n 会。且看下页。CS_Dept.Sichaun Univ.2022/5/1810/44n贪心算法属于自然计算吗？ 勉强 算是。n模拟了 部分人、在部分时间的心理社会行为n人性善：理性（理想、信仰、道德） 非理性时。n部分人/在部分时间 ，上述不等式 反过来了，表现出贪心。n贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大n贪心算法的基本思想：追求每一步获利最大（启发性知识）n人 贪心 固然 不好， 但贪心算法但贪心算法 有时是好用的有时是好用的
6、 。n不贪心的人， 在生活中 会贪心算法吗？n 会。且看下页。会。且看下页。CS_Dept.Sichaun Univ.2022/5/1811/44BCAD这里有天桥这里没有天桥，但绿灯亮这里红灯亮下页 .CS_Dept.Sichaun Univ.2022/5/1812/44BCAD过马路十字路口 ，拟从A到C，70%的人会用贪心算法。通常 那一个方向代价低（时间及其他资源），则先过该方向，先把看得见的实利（时间）抢到手。实利（时间）抢到手。（这是一条启发（这是一条启发性知识）性知识）但不总是快，例如刚刚走到B, 大量救火车南北方向通行，且持续10分钟。 欲速不达，欲速不达，这里红灯亮但有天桥这
7、里没有天桥，但绿灯亮CS_Dept.Sichaun Univ.2022/5/1813/44n求职时，看当前那个给的工资高， 不管以后几年的发展Search spaceFitnessf(x)local optimumglobal optimumlocal optimumlocal optimum0 xx1x2x4x5x3瞎子爬山法：一米长的探测棒，在这里发现往西边走 ，打工工资高其实 在这里 打工 工资才最高关键：探测棒 太短了CS_Dept.Sichaun Univ.2022/5/1814/44n求职时，看当前那个给的工资高， 不管以后几年的发展Search spaceFitnessf(x)l
8、ocal optimumglobal optimumlocal optimumlocal optimum0 xx1x2x4x5x3瞎子爬山法Hill Climbing， 选邻近最好点，一米长的探测棒，在这里发现往西边走 工资升高其实在这里 工资才最高关键：探测棒关键：探测棒 太短了。目光短浅太短了。目光短浅CS_Dept.Sichaun Univ.2022/5/1815/44n初学者 下象棋 围棋 ，常常吃子上当， 高手常 弃子攻杀n贪心人上当 的例子.n瞎子下山、瞎子上山（ 最大梯度法）CS_Dept.Sichaun Univ.2022/5/1816/44Function Find-Dire
9、ction-With-Max-Score-in-One-Step( ) MaxScore=0; MaxDirection=0; for Each possible DirectionPointer, m=Get-Score-in-next-step( * DirectionPointer );/追求眼前最大利益 If (MaxScorem) . MaxScore=m; MaxDirection= DirectionPointer; return MaxDirection; ; Mian( ) While (not ok) Find-Direction-With-Max-Score-in-One
10、-Step( ); /眼前利益在何处？眼前利益在何处？ Make-One-Step( ); / 实施实施 追求眼前利益追求眼前利益 CS_Dept.Sichaun Univ.2022/5/1817/44n好写、简单，容易想到和实现，n往往成为批判对象n在论文中往往处于丫环地位，n用来衬托小姐程序的漂亮， 对比分析时用CS_Dept.Sichaun Univ.2022/5/1818/44n好写、简单，容易想到和实现，n往往成为批判对象n戏剧中 常常用丫环“来衬托 ”小姐“的漂亮n金庸。古龙的小说中也有。n在论文中往往处于 “丫环“地位，n用来衬托 ”小姐程序“的漂亮， 对比分析时用CS_Dept
11、.Sichaun Univ.2022/5/1819/44n好写、简单，容易想到和实现，n往往称为批判对象n戏剧中 常常用丫环“ 来衬托 ”小姐“的漂亮n金庸。古龙的小说中也有。n在论文中在论文中 贪心算法 往往处于往往处于 “丫环丫环“地位，地位，n用来衬托用来衬托 ”小姐程序小姐程序“的漂亮，的漂亮， 对比分析时用对比分析时用n为什么？为什么？ 比较的需要。没有比较的需要。没有“丫环丫环“也要造一个（电器中也也要造一个（电器中也有丫环机型），有丫环机型），贪心算法 最好造。还有点启发性知识n人生中，有时没有选择的权利，就尽可能做好能作的每一步，也是贪心算法，不乏成功者。慢一点，累一点n不要
12、把人生规划 和 计算机程序 搅混了CS_Dept.Sichaun Univ.2022/5/1820/44n好写、简单，容易想到和实现，n往往称为批判对象n戏剧中 常常用丫环“地位衬托 ”小姐“的漂亮n金庸。古龙的小说中也有。n在论文中在论文中 贪心算法 往往处于往往处于 “丫环丫环“地位，地位，n用来衬托用来衬托 ”小姐程序小姐程序“的漂亮，的漂亮， 对比分析时用对比分析时用n为什么？为什么？ 比较的需要。没有比较的需要。没有“丫环丫环“也要造一个（电器中也也要造一个（电器中也有丫环机型），有丫环机型），贪心算法 最好造。还有点启发性知识n人生中，有时没有选择的权利，就尽可能做好能作的每一步，
13、说来也是贪心算法，但不乏成功者，慢一点。n不要 把人生规划 和 计算机程序 搅混了CS_Dept.Sichaun Univ.2022/5/1821/44对贪心算法的一种批判-模拟退火 算法本PPT用贪心算法来衬托模拟退火 算法CS_Dept.Sichaun Univ.2022/5/1822/44nN.Metropolis 等 1953 年所提出，被忽略n1983 年， Kirkpatrick et al. 提出蒙特卡罗模拟法（MonteCarlo Simulated）n的随机搜寻技巧，求解的组合最佳化问题时n人们才重新想起 模拟退火。 n科学历史上类似事情很多CS_Dept.Sichaun U
14、niv.2022/5/1823/44淬火，把锥尖部分烧红，在水中急速冷却， 硬而脆 中国古代 铸剑 技术 莫邪 干将 ，夫差 剑.（请 学热处理专业的同学讲）高频淬火：利用电流趋肤效应，只加热表面，然后急速冷却， 表面收缩， 预应力 或 残应力， 使得皮硬心韧 适合轴表面，刀刃等。（利用 预应力 或 残应力）退火 - 淬火的逆向工艺， 减少应力，是的材料舒缓，铸件退火，金属铸件，日晒雨淋几个月，在后期，气温区间，温度随气温有升有降，利于充分释放应力，如铸造的刹车鼓，机器座等。均匀，不脆，好加 工 自然退火，先热(粒子温升,无序，内能增大)，后慢冷(粒子渐趋有序内能减为最小) 。CS_Dept.
15、Sichaun Univ.2022/5/1824/44n金属加热至一定的温度后，分子结构-被打散瓦解准液态n直接地 贪心地 一路下降温度，可能部分紧张的结构 冷成紧张结构死结， 无法舒缓， 解决方法，小小地加一点热。让其成准液态n降温过程 巧妙控制，巧在何处n 大的 冷却趋势中有局部小的加热 冷10点 热3点n冷10点- 热3点-冷10点- 热3点-冷10点- 热3点-n 使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态n当当冷进行得冷进行得 不好不好时时，晶粒结构 紧张，重新重新小小加热加热-，随机，随机地地接受一个暂接受一个暂劣解劣解，跳跳出局部优化（早熟）出局部优化（早
16、熟），有机会能达到，有机会能达到全局最优，全局最优，CS_Dept.Sichaun Univ.2022/5/1825/44n金属加热至一定的温度后，分子结构-被打散瓦解准液态n直接地 贪心地 一路下降温度，可能部分紧张的结构 冷成紧张结构死结， 无法舒缓， 解决方法，小小地加一点热。让其成准液态n降温过程 巧妙控制，巧在何处n 大的 冷却趋势中有局部小的加热 冷10点 热3点n冷10点- 热3点-冷10点- 热3点-冷10点- 热3点-n 使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态n当当冷进行得冷进行得 不好不好时时，晶粒结构 紧张，重新重新小小加热加热-，随机，随机地
17、地接受一个暂接受一个暂劣解劣解，跳跳出局部优化（早熟）出局部优化（早熟），有机会能达到，有机会能达到全局最优，全局最优，CS_Dept.Sichaun Univ.2022/5/1826/44n向一个心理素质不好的人转告坏消息（亲属受伤,Fen-Sou)n可以用模拟退火算法，n大趋势：逐步降温，n发现其心态很差时， 偶尔升温，避免走向极端n 可防止精神紧张，防止出问题（精神错乱，自杀，等等）n使其精神状态 从强烈期待和紧张，安全地转化为 平常心，n如果用瞎子下山法（贪心），降温太快，可能导致精神崩溃CS_Dept.Sichaun Univ.2022/5/1827/44n向一个心理素质不好的人转告
18、坏消息，n可以用模拟退火算法，n大趋势：逐步降温，n发现其心态很差时， 偶尔升温，避免走向极端n 可防止精神紧张，防止出问题（精神错论，自杀等等）n使其精神状态 从强烈期待和紧张，安全地转化为 平常心，n如果用瞎子下山法（贪心），降温太快，可能导致精神崩溃CS_Dept.Sichaun Univ.2022/5/1828/44n有坚定的信念，允许暂时的失败。n是对贪心算法的一种批判是对贪心算法的一种批判n 贪心算法是对贪心算法是对 部分人性的模拟。部分人性的模拟。n思想： 弛中有张，争中有让，可能 是 99%的弛 ，1%的张n 大趋势是弛（降温，释放应力）n 争 99步，不放让一步n 战争中 不
19、拘泥于 一城一池的得失CS_Dept.Sichaun Univ.2022/5/1829/44热力学：溫度为t，能量差所表現的概率P(E)=exp(-E / kt)n接受法则（Accepting Rule）n并行退火程序（Annealing Schedulen成功关键：合理退火规划CS_Dept.Sichaun Univ.2022/5/1830/44n考虑搜索最优解过程ni 代表在时间k 的当前解，成本为C(i)n下一个解，成本为C(j)n两个解之间的成本差，如图所示D E = C(j) - C(i)为搜索方向CS_Dept.Sichaun Univ.2022/5/1831/44n设计设计 一个
20、一个 抽签函数抽签函数(下页）下页）n 既体现随机的公平（客观或运气），既体现随机的公平（客观或运气），n 又体现主观努力，优胜劣汰（适应度又体现主观努力，优胜劣汰（适应度 ）。n为什么需要这个函数？为什么需要这个函数？n否则 n 庶民个体会问： 王侯将相 宁有种乎？CS_Dept.Sichaun Univ.2022/5/1832/44H遇到困难 j 的成本大于i 时，掷骰子，随机定是否接受j来取代i 成新解（按概率允许小的失败）H困难时 要妥协以下 按概率决定是否妥协，退步。HSA Metrolopis 接受法则 + 退火计划，H温度渐降，掷骰子 定 是否接受较差新解，H当温度越低时（即越接
21、近胜利）（即越接近胜利），越少妥协越少妥协 弛中有张弛中有张，可能，可能 是是 99%的弛的弛 ，1%的张，的张， 大趋势是弛大趋势是弛（降温，释放应力降温，释放应力），），争99步，让一步CS_Dept.Sichaun Univ.2022/5/1833/44n四要点n系统状态或配置（Configuration）：n 三元组 （温度，初始解，作当前解）n搜索（干预）规则：n 退火过程中，系统状态经干预-跳至另一种状态n常用方法 n 梯度法（ Gradient Type） n 迭代法（ Iterative Improvement）CS_Dept.Sichaun Univ.2022/5/1834/
22、44n成本函数（Cost Function）：用来衡量某一系统状态下之能量函数 ， 类似于GEP中适应度n退火规划（Annealing Process）：n 含参数：初温、降温机制、冷却率，终止温度 n策略：n 温高时（早期），多妥协，比方 争99步，让一步n 温低时（后期），少妥协，比方 争999步，让一步n CS_Dept.Sichaun Univ.2022/5/1835/44n初始温度n为防止局部早熟，初温 须使 大部份的转移均可被接受n Kirkpatrick等 ( 1983 )建议：初温度 为10n Heragu ， ( 1992 )建议： 初温 999n初温 可由 移转接受概率 门
23、限 P 0 反推n Kouvelis 以及 Chiang( 1992 ) 建议初温度 n T0 =Delta / ln(1/P0)CS_Dept.Sichaun Univ.2022/5/1836/44n简单方式：H 指定固定温度H 降温次数=预定值n 复杂方式：H 检查解是否达标H 是否早熟： 1992 年Kouvelis 与 Chiangn 设定N次降温 无改善 退出CS_Dept.Sichaun Univ.2022/5/1837/44n降温时机-马可夫链长度，同一温度下所应反覆进行Metropolis 演算的次数n直接方式：设固定长度，与问题规模有关，1992 年Kouvelis 与Chi
24、ang 将其设定为邻近解个数之比率。n降温时机 为移转接受次数已达一定值，Heragu 以及 Alfa（1992）所用H 但当温降至很低时，移转接受之机率将会很小，导致马可夫链过长，须同时限定马可夫链的长度CS_Dept.Sichaun Univ.2022/5/1838/44n达到降温时机时，下降多少？（比率）n参数小，差距大，下一温度 达成均衡 所需的马可夫链长求解时间增加。nKirkpatrick（1983）设为0.9， 一般 0.50.9 线性降溫 Temp=Temp-x 非线性降溫 Temp=Temp*y (y : 0.50.99)CS_Dept.Sichaun Univ.2022/5
25、/1839/44n补充预备知识：通过随机 实现 自然放松n设计设计 一个一个 抽签函数抽签函数( (下页）下页） 设计设计 一个一个抽签抽签 既体现既体现 偶尔升温的偶尔升温的 随机（客观或运气）随机（客观或运气），又体现当前温度的机会函数。，又体现当前温度的机会函数。CS_Dept.Sichaun Univ.2022/5/1840/44n设计设计 一个一个 机遇函数既体现随机的公平（客观或运气），又机遇函数既体现随机的公平（客观或运气），又体现当前温度。体现当前温度。n降温大趋势中，按降温大趋势中，按Rate = exp(-t/T)的几率的几率 降温降温n这一步这一步 应该应该 降温吗，掷个
26、骰子降温吗，掷个骰子（古人（古人 用甲骨文占卜用甲骨文占卜)：nBool GetChance( Rate, CurrT，Threshold)n redomaize( );n chance=Radom(1); n return = ( Chancerate) & ( CurrT = Threshold)n |-|-|- .-|n 0 chance rate =1% 1温度很高的时候不需要升温升温机会CS_Dept.Sichaun Univ.2022/5/1841/44模拟退火法圖随机初始解扰动，產生一個新解是否接受?修改目前解应该降溫？減溫 中止條件?NoYesYesYesNoNo针对循环：在前
27、解为的小邻域中 随机化 取解。初使化最优解CS_Dept.Sichaun Univ.2022/5/1842/44初始化：初温T(充分大)，初解S(算法迭代起点)， 迭代次数L While (1) for (k=1， KL,K+) ： 产生新解S 计算增量t=C(S)-C(S)，其中C(S)为评价函数 if (t0) 接受S作新解， else if GetChance(exp(-t/T) , CurrT，Threshold.) 接受S作为新解 if (满足终止条件) return ( 当前解) /作为最优解， 按降温规则（一般 0.50.9）降温 这里体现偶尔的让步CS_Dept.Sichaun
28、 Univ.2022/5/1843/44n初始化可能影响收敛速度， （类似遗传算法）n初始化不影响求得的解n渐近收敛性，H理论上，以概率l 收敛于全局最优解4一定得到最优解，这点与遗传算法不同4 道路是曲曲折的， 前途是光明的H全局优化算法；n有并行性。 CS_Dept.Sichaun Univ.2022/5/1844/44n初始化可能影响收敛速度， （类似遗传算法）n初始化不影响求得的解n渐近收敛性，H理论上，以概率l 收敛于全局最优解4一定得到最优解，这点与遗传算法不同4 道路是曲折的， 前途是光明的H全局优化算法；n有并行性。 CS_Dept.Sichaun Univ.2022/5/1845/44
