基因表达式编程教学4课件

1、先进计算模型（4）自然计算模型系列 之 模拟退火算法Simulated Annealing四川大学计算机学院2008 -2009博士生课程（粒子群-鱼群算法(PSO)，遗传算法，基因表达式编程 贪心算法， 模拟退火, 蚁群算法，.)唐常杰 四川大学计算机学院9/8/20221目录，大致计划第一次自然计算模型系列1：概述篇自然计算模型系列2 粒子群（ 鱼群/鸟群） 算法自然计算模型系列3 基因表达式编程第二次自然计算模型系列4：模拟退火算法自然计算模型系列5：蚁群算法 自然计算模型系列6：免疫计算模型（思路和比喻）下载URL: 校园网 和 学院网 /chjtang/teach/tang_teac

2、hing.htm 7/tangchangjie/teach/tang_teaching.htm9/8/20222上一次 自然计算模型 （Nature Computing)概述PSO 粒子群算法 鱼群 鸟群算法GEP 基因表达式编程今天 蚁群算法 模拟退火算法 人工免疫 思想 （比喻） 欢迎同学发言 （5-30分钟均可）（ 如 A 先讲， 可跳至32页 ）提纲9/8/20223致谢 和 参考资料 出处参考资料： 本PPT仅作和同学们在讨论版内交流之用参考了若干教科书，文献和论文和报告。在末尾列出50多篇，但参考的文献不只这些,主要是遗传算法、基因表达式编程、粒子群算法 的相关作者等等，包括 国内

3、外，校内外专家和本实验室成员的工作对未列出的文献作者也在此一并致谢。参考文献可能有遗漏，欢迎未列出的文献作者及时指出，以便即时在参考文献中补充、引用。作PPT类似于把小说改编为剧本，有重新创作的成分，也希望其它引用本PPT材料的标注 本PPT9/8/20224课程计划和特点有多位（7-8位）博士生导师作专题讲座， 每个老师讲课8小时（大约需要准备 40-60小时）特点广- N位导师，N=89 ,N + 个领域，M个课题，(MN). “N家讲座” ，不敢比 百家新 -要求报告 新技术前沿浅 因为时间短，主要将思想，方法，介绍成果。不可能深入到公式和算法细节实-结合实际，结合博士生可能的选题9/8

4、/20225 这里根据情况 插讲 自然计算模型PPT欢迎同学 报告、讨论，发言补充 （5-30分钟 均可）介绍.9/8/20226 贪心算法及其批判-模拟退火 算法Greedy Algorithm andSimulated Annealing Algorithm唐常杰川大计算机学院9/8/20227贪心算法 Greedy Algorithm贪心算法属于自然计算吗？ 勉强 算是。模拟了 部分人、在部分时间的心理社会行为人性善：理性（理想、信仰、道德） 非理性时。部分人/在部分时间 ，上述不等式 反过来了，表现出贪心。贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大贪心算法的基本思想：追求每一

5、步获利最大（启发性知识）人 贪心 固然 不好， 但贪心算法 有时是好用的 。不贪心的人， 在生活中 会贪心算法吗？ 会。且看下页。9/8/202210贪心算法例子BCAD这里有天桥这里没有天桥，但绿灯亮这里红灯亮下页 .9/8/202211贪心算法例子BCAD过马路十字路口 ，拟从A到C，70%的人会用贪心算法。通常 那一个方向代价低（时间及其他资源），则先过该方向，先把看得见的实利（时间）抢到手。（这是一条启发性知识）但不总是快，例如刚刚走到B, 大量救火车南北方向通行，且持续10分钟。 欲速不达，这里红灯亮但有天桥这里没有天桥，但绿灯亮9/8/202212贪心算法的实现 好写、简单Func

6、tion Find-Direction-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-Ma

7、x-Score-in-One-Step( ); /眼前利益在何处？ Make-One-Step( ); / 实施 追求眼前利益 9/8/202216贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往成为批判对象在论文中往往处于丫环地位，用来衬托小姐程序的漂亮， 对比分析时用9/8/202217贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往成为批判对象戏剧中 常常用丫环“来衬托 ”小姐“的漂亮金庸。古龙的小说中也有。在论文中往往处于 “丫环“地位，用来衬托 ”小姐程序“的漂亮， 对比分析时用9/8/202218贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，

8、往往称为批判对象戏剧中 常常用丫环“ 来衬托 ”小姐“的漂亮金庸。古龙的小说中也有。在论文中 贪心算法 往往处于 “丫环“地位，用来衬托 ”小姐程序“的漂亮， 对比分析时用为什么？ 比较的需要。没有“丫环“也要造一个（电器中也有丫环机型），贪心算法 最好造。还有点启发性知识人生中，有时没有选择的权利，就尽可能做好能作的每一步，也是贪心算法，不乏成功者。慢一点，累一点不要 把人生规划 和 计算机程序 搅混了9/8/202219 看看 工厂中的淬火和退火工艺淬火，把锥尖部分烧红，在水中急速冷却， 硬而脆 中国古代 铸剑 技术 莫邪 干将 ，夫差 剑.（请 学热处理专业的同学讲）高频淬火：利用电流趋

9、肤效应，只加热表面，然后急速冷却， 表面收缩， 预应力 或 残应力， 使得皮硬心韧 适合轴表面，刀刃等。（利用 预应力 或 残应力）退火 - 淬火的逆向工艺， 减少应力，是的材料舒缓，铸件退火，金属铸件，日晒雨淋几个月，在后期，气温区间，温度随气温有升有降，利于充分释放应力，如铸造的刹车鼓，机器座等。均匀，不脆，好加 工 自然退火，先热(粒子温升,无序，内能增大)，后慢冷(粒子渐趋有序内能减为最小) 。9/8/202223金属工艺学的解释金属加热至一定的温度后，分子结构-被打散瓦解准液态直接地 贪心地 一路下降温度，可能部分紧张的结构 冷成紧张结构死结， 无法舒缓， 解决方法，小小地加一点热。

10、让其成准液态降温过程 巧妙控制，巧在何处 大的 冷却趋势中有局部小的加热 冷10点 热3点冷10点- 热3点-冷10点- 热3点-冷10点- 热3点- 使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态当冷进行得 不好时，晶粒结构 紧张，重新小加热-，随机地接受一个暂劣解，跳出局部优化（早熟），有机会能达到全局最优，9/8/202224金属工艺学的解释金属加热至一定的温度后，分子结构-被打散瓦解准液态直接地 贪心地 一路下降温度，可能部分紧张的结构 冷成紧张结构死结， 无法舒缓， 解决方法，小小地加一点热。让其成准液态降温过程 巧妙控制，巧在何处 大的 冷却趋势中有局部小的加热

11、 冷10点 热3点冷10点- 热3点-冷10点- 热3点-冷10点- 热3点- 使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态当冷进行得 不好时，晶粒结构 紧张，重新小加热-，随机地接受一个暂劣解，跳出局部优化（早熟），有机会能达到全局最优，9/8/202225 生活中的模拟退火- 巧妙转达坏消息向一个心理素质不好的人转告坏消息（亲属受伤,Fen-Sou)可以用模拟退火算法，大趋势：逐步降温，发现其心态很差时， 偶尔升温，避免走向极端 可防止精神紧张，防止出问题（精神错乱，自杀，等等）使其精神状态 从强烈期待和紧张，安全地转化为 平常心，如果用瞎子下山法（贪心），降温太快，

12、可能导致精神崩溃9/8/202226 生活中的模拟退火- 巧妙转达 坏消息向一个心理素质不好的人转告坏消息，可以用模拟退火算法，大趋势：逐步降温，发现其心态很差时， 偶尔升温，避免走向极端 可防止精神紧张，防止出问题（精神错论，自杀等等）使其精神状态 从强烈期待和紧张，安全地转化为 平常心，如果用瞎子下山法（贪心），降温太快，可能导致精神崩溃9/8/202227比喻 弛中有张 ，慢功细活有坚定的信念，允许暂时的失败。是对贪心算法的一种批判 贪心算法是对 部分人性的模拟。思想： 弛中有张，争中有让，可能 是 99%的弛 ，1%的张 大趋势是弛（降温，释放应力） 争 99步，不放让一步 战争中 不

13、拘泥于 一城一池的得失9/8/202228技术要点热力学：溫度为t，能量差所表現的概率P(E)=exp(-E / kt)接受法则（Accepting Rule）并行退火程序（Annealing Schedule成功关键：合理退火规划9/8/202229数学建模 （符号假定和简化）考虑搜索最优解过程i 代表在时间k 的当前解，成本为C(i)下一个解，成本为C(j)两个解之间的成本差，如图所示D E = C(j) - C(i)为搜索方向9/8/202230补充预备知识：通过随机 实现公平设计 一个 抽签函数(下页） 既体现随机的公平（客观或运气）， 又体现主观努力，优胜劣汰（适应度 ）。为什么需要

14、这个函数？否则 庶民个体会问： 王侯将相 宁有种乎？9/8/202231 退火算法 四要素成本函数（Cost Function）：用来衡量某一系统状态下之能量函数 ， 类似于GEP中适应度退火规划（Annealing Process）： 含参数：初温、降温机制、冷却率，终止温度 策略： 温高时（早期），多妥协，比方 争99步，让一步 温低时（后期），少妥协，比方 争999步，让一步 9/8/202234退火参数 经验初始温度为防止局部早熟，初温 须使 大部份的转移均可被接受 Kirkpatrick等 ( 1983 )建议：初温度 为10 Heragu ， ( 1992 )建议： 初温 999初

15、温 可由 移转接受概率 门限 P 0 反推 Kouvelis 以及 Chiang( 1992 ) 建议初温度 T0 =Delta / ln(1/P0)9/8/202235退火参数 ：终止条件简单方式： 指定固定温度 降温次数=预定值 复杂方式： 检查解是否达标 是否早熟： 1992 年Kouvelis 与 Chiang 设定N次降温 无改善 退出9/8/202236退火参数 经验：降温时机降温时机-马可夫链长度，同一温度下所应反覆进行Metropolis 演算的次数直接方式：设固定长度，与问题规模有关，1992 年Kouvelis 与Chiang 将其设定为邻近解个数之比率。降温时机 为移转接

16、受次数已达一定值，Heragu 以及 Alfa（1992）所用 但当温降至很低时，移转接受之机率将会很小，导致马可夫链过长，须同时限定马可夫链的长度9/8/202237退火参数 经验 ：温度控制达到降温时机时，下降多少？（比率）参数小，差距大，下一温度 达成均衡 所需的马可夫链长求解时间增加。Kirkpatrick（1983）设为0.9， 一般 0.50.9 线性降溫 Temp=Temp-x 非线性降溫 Temp=Temp*y (y : 0.50.99)9/8/202238退火算法的预备： 一个抽签函数补充预备知识：通过随机 实现 自然放松设计 一个 抽签函数(下页）设计 一个抽签 既体现 偶

17、尔升温的 随机（客观或运气），又体现当前温度的机会函数。9/8/202239准备一个函数：机会留给有准备的对象（主观+客观）设计 一个 机遇函数既体现随机的公平（客观或运气），又体现当前温度。降温大趋势中，按Rate = exp(-t/T)的几率 降温这一步 应该 降温吗，掷个骰子（古人 用甲骨文占卜)：Bool GetChance( Rate, CurrT，Threshold) redomaize( ); chance=Radom(1); return = ( Chancerate) & ( CurrT = Threshold) |-|-|- .-| 0 chance rate =1% 1温

18、度很高的时候不需要升温升温机会9/8/202240模拟退火法圖随机初始解扰动，產生一個新解是否接受?修改目前解应该降溫？減溫 中止條件?NoYesYesYesNoNo针对循环：在前解为的小邻域中 随机化 取解。初使化最优解9/8/202241退火算法 伪代码初始化：初温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）降温 这里体现偶尔的让