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