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

先进计算模型（4）自然计算模型系列之模拟退火算法

SimulatedAnnealing四川大学计算机学院2008-2009博士生课程（粒子群-鱼群算法(PSO)，遗传算法，基因表达式编程

贪心算法，模拟退火,

蚁群算法，….)唐常杰

四川大学计算机学院2/4/20231目录，大致计划第一次自然计算模型系列1：概述篇自然计算模型系列2粒子群（

鱼群/鸟群）算法自然计算模型系列3基因表达式编程第二次自然计算模型系列4：模拟退火算法自然计算模型系列5：蚁群算法自然计算模型系列6：免疫计算模型（思路和比喻）下载URL:校园网和学院网

http:///~chjtang/teach/tang_teaching.htm

7/~tangchangjie/teach/tang_teaching.htm2/4/20232上一次

自然计算模型（NatureComputing)概述PSO

粒子群算法鱼群鸟群算法GEP基因表达式编程今天

蚁群算法模拟退火算法人工免疫思想（比喻）

……

欢迎同学发言（5-30分钟均可）（如A先讲，可跳至32页）提纲2/4/20233致谢和参考资料出处参考资料：本PPT仅作和同学们在讨论版内交流之用参考了若干教科书，文献和论文和报告。在末尾列出50多篇，但参考的文献不只这些,主要是遗传算法、基因表达式编程、粒子群算法的相关作者等等，包括国内外，校内外专家和本实验室成员的工作对未列出的文献作者也在此一并致谢。参考文献可能有遗漏，欢迎未列出的文献作者及时指出，以便即时在参考文献中补充、引用。作PPT类似于把小说改编为剧本，有重新创作的成分，也希望其它引用本PPT材料的标注本PPT2/4/20234课程计划和特点有多位（7-8位）博士生导师作专题讲座，每个老师讲课8小时（大约需要准备40--60小时）特点广---N位导师，N=8~9,N+

个领域，M个课题，(M>N).“N家讲座”，不敢比百家…新---要求报告新技术前沿浅–因为时间短，主要将思想，方法，介绍成果。不可能深入到公式和算法细节实---结合实际，结合博士生可能的选题2/4/20235

这里根据情况插讲自然计算模型PPT欢迎同学报告、讨论，发言补充（5-30分钟均可）介绍…..2/4/20236

贪心算法及其批判---模拟退火算法GreedyAlgorithmandSimulatedAnnealingAlgorithm唐常杰川大计算机学院2/4/20237贪心算法GreedyAlgorithm贪心算法属于自然计算吗？勉强算是。模拟了部分人、在部分时间的心理社会行为人性善：理性（理想、信仰、道德）>非理性时。部分人/在部分时间，上述不等式反过来了，表现出贪心。贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大贪心算法的基本思想：追求每一步获利最大人贪心固然不好，但贪心算法有时是好用的。不贪心的人，在生活中会贪心算法吗？会。且看下页。2/4/20238贪心算法GreedyAlgorithm贪心算法属于自然计算吗？勉强算是。模拟了部分人、在部分时间的心理社会行为人性善：理性（理想、信仰、道德）>非理性时。部分人/在部分时间，上述不等式反过来了，表现出贪心。贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大贪心算法的基本思想：追求每一步获利最大人贪心固然不好，但贪心算法有时是好用的。不贪心的人，在生活中会用贪心算法吗？

会。且看下页。2/4/20239贪心算法GreedyAlgorithm贪心算法属于自然计算吗？勉强算是。模拟了部分人、在部分时间的心理社会行为人性善：理性（理想、信仰、道德）>非理性时。部分人/在部分时间，上述不等式反过来了，表现出贪心。贪心时，目光短浅，只顾眼前最大利益，追求每步获利最大贪心算法的基本思想：追求每一步获利最大（启发性知识）人贪心固然不好，但贪心算法有时是好用的。不贪心的人，在生活中会贪心算法吗？

会。且看下页。2/4/202310贪心算法例子BCAD这里有天桥这里没有天桥，但绿灯亮这里红灯亮下页…..2/4/202311贪心算法例子BCAD过马路十字路口，拟从A到C，70%的人会用贪心算法。通常那一个方向代价低（时间及其他资源），则先过该方向，先把看得见的实利（时间）抢到手。（这是一条启发性知识）但不总是快，例如刚刚走到B,大量救火车南北方向通行，且持续10分钟。

欲速不达，这里红灯亮但有天桥这里没有天桥，但绿灯亮2/4/202312贪心算法例子2求职时，看当前那个给的工资高，不管以后几年的发展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法：一米长的探测棒，在这里发现往西边走，打工工资高其实在这里打工工资才最高关键：探测棒太短了2/4/202313贪心算法例子2求职时，看当前那个给的工资高，不管以后几年的发展SearchspaceFitnessf(x)localoptimumglobaloptimumlocaloptimumlocaloptimum0xx1x2x4x5x3瞎子爬山法HillClimbing，选邻近最好点，一米长的探测棒，在这里发现往西边走工资升高其实在这里工资才最高关键：探测棒太短了。目光短浅2/4/202314生活中的贪心算法初学者下象棋围棋，常常吃子上当，高手常弃子攻杀贪心人上当的例子….瞎子下山、瞎子上山（最大梯度法）2/4/202315贪心算法的实现好写、简单FunctionFind-Direction-With-Max-Score-in-One-Step(){MaxScore=0;MaxDirection=0;forEachpossibleDirectionPointer,{m=Get-Score-in-next-step(*DirectionPointer

);//追求眼前最大利益If(MaxScore<m){.MaxScore=m;MaxDirection=DirectionPointer;}returnMaxDirection;}};

Mian(){While(notok){Find-Direction-With-Max-Score-in-One-Step();//眼前利益在何处？Make-One-Step();//实施追求眼前利益}}2/4/202316贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往成为批判对象在论文中往往处于丫环地位，用来衬托小姐程序的漂亮，对比分析时用2/4/202317贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往成为批判对象戏剧中常常用丫环“来衬托”小姐“的漂亮金庸。古龙的小说中也有。在论文中往往处于“丫环“地位，用来衬托”小姐程序“的漂亮，对比分析时用2/4/202318贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往称为批判对象戏剧中常常用丫环“来衬托”小姐“的漂亮金庸。古龙的小说中也有。在论文中贪心算法

往往处于“丫环“地位，用来衬托”小姐程序“的漂亮，对比分析时用为什么？比较的需要。没有“丫环“也要造一个（电器中也有丫环机型），贪心算法最好造。还有点启发性知识人生中，有时没有选择的权利，就尽可能做好能作的每一步，也是贪心算法，不乏成功者。慢一点，累一点不要把人生规划和计算机程序搅混了2/4/202319贪心算法广泛地用在计算机程序中好写、简单，容易想到和实现，往往称为批判对象戏剧中常常用丫环“地位衬托”小姐“的漂亮金庸。古龙的小说中也有。在论文中贪心算法

往往处于“丫环“地位，用来衬托”小姐程序“的漂亮，对比分析时用为什么？比较的需要。没有“丫环“也要造一个（电器中也有丫环机型），贪心算法最好造。还有点启发性知识人生中，有时没有选择的权利，就尽可能做好能作的每一步，说来也是贪心算法，但不乏成功者，慢一点。不要把人生规划和计算机程序搅混了2/4/202320

对贪心算法的一种批判---模拟退火算法本PPT用贪心算法来衬托模拟退火算法2/4/202321历史沿革模拟退火（SimulatedAnnealing；SA）N.Metropolis

等

1953年所提出，被忽略1983年，Kirkpatricketal.提出蒙特卡罗模拟法（MonteCarloSimulated）的随机搜寻技巧，求解的组合最佳化问题时人们才重新想起模拟退火。

科学历史上类似事情很多2/4/202322看看工厂中的淬火和退火工艺淬火，把锥尖部分烧红，在水中急速冷却，硬而脆中国古代铸剑技术莫邪干将，夫差剑….（请学热处理专业的同学讲）高频淬火：利用电流趋肤效应，只加热表面，然后急速冷却，表面收缩，预应力或残应力，使得皮硬心韧适合轴表面，刀刃等。（利用预应力或残应力）退火---淬火的逆向工艺，减少应力，是的材料舒缓，铸件退火，金属铸件，日晒雨淋几个月，在后期，气温区间，温度随气温有升有降，利于充分释放应力，如铸造的刹车鼓，机器座等。均匀，不脆，好加工

自然退火，先热(粒子温升,无序，内能增大)，后慢冷(粒子渐趋有序内能减为最小)

。2/4/202323金属工艺学的解释金属加热至一定的温度后，分子结构--被打散瓦解—准液态直接地贪心地一路下降温度，可能部分紧张的结构冷成紧张结构死结，无法舒缓，解决方法，小小地加一点热。让其成准液态降温过程

巧妙控制，巧在何处

大的冷却趋势中—有局部小的加热—冷10点热3点冷10点----热3点----冷10点----热3点----冷10点----热3点----

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

巧妙控制，巧在何处

大的冷却趋势中—有局部小的加热—冷10点热3点冷10点----热3点----冷10点----热3点----冷10点----热3点----

使其分子在液态结构转变为固体结构时，重新排列成我们所预期的稳定状态当冷进行得不好时，晶粒结构紧张，重新小加热--，随机地接受一个暂劣解，跳出局部优化（早熟），有机会能达到全局最优，2/4/202325

生活中的模拟退火--巧妙转达坏消息向一个心理素质不好的人转告坏消息（亲属受伤…,Fen-Sou)可以用模拟退火算法，大趋势：逐步降温，发现其心态很差时，偶尔升温，避免走向极端可防止精神紧张，防止出问题（精神错乱，自杀，等等）使其精神状态从强烈期待和紧张，安全地转化为平常心，如果用瞎子下山法（贪心），降温太快，可能导致精神崩溃2/4/202326

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

贪心算法是对部分人性的模拟。思想：弛中有张，争中有让，可能是99%的弛，1%的张大趋势是弛（降温，释放应力）争99步，不放让一步战争中不拘泥于一城一池的得失2/4/202328技术要点热力学：溫度为t，能量差所表現的概率P(ΔE)=exp(-ΔE/kt)接受法则（AcceptingRule）并行退火程序（AnnealingSchedule成功关键：合理退火规划2/4/202329数学建模（符号假定和简化）考虑搜索最优解过程i代表在时间k的当前解，成本为C(i)下一个解，成本为C(j)两个解之间的成本差，如图所示DE=C(j)-C(i)为搜索方向2/4/202330补充预备知识：通过随机实现公平设计一个抽签函数(下页）既体现随机的公平（客观或运气），又体现主观努力，优胜劣汰（适应度）。为什么需要这个函数？否则庶民个体会问：王侯将相宁有种乎？2/4/202331数学建模（符号假定和简化）遇到困难j的成本大于i时，掷骰子，随机定是否接受j来取代i成新解（按概率允许小的失败）困难时要妥协以下按概率决定是否妥协，退步。SAMetrolopis

接受法则

+退火计划，温度渐降，掷骰子定是否接受较差新解，当温度越低时（即越接近胜利），越少妥协

弛中有张，可能是99%的弛，1%的张，大趋势是弛（降温，释放应力），争99步，让一步2/4/202332退火算法四要点系统状态或配置（Configuration）：三元组（温度，初始解，作当前解）搜索（干预）规则：

退火过程中，系统状态经—干预---跳至另一种状态常用方法

梯度法（GradientType）迭代法（IterativeImprovement）2/4/202333退火算法四要素成本函数（CostFunction）：用来衡量某一系统状态下之能量函数，类似于GEP中适应度退火规划（AnnealingProcess）：

含参数：初温、降温机制、冷却率，终止温度

策略：

温高时（早期），多妥协，比方争99步，让一步

温低时（后期），少妥协，比方争999步，让一步

2/4/202334退火参数经验初始温度为防止局部早熟，初温

须使

大部份的转移均可被接受

Kirkpatrick等(1983)建议：初温度

为10

Heragu

，

(1992)建议：初温

999初温

可由

移转接受概率门限P0

反推

Kouvelis

以及Chiang(1992)建议初温度

T0=Delta/ln(1/P0)2/4/202335退火参数：终止条件简单方式：

指定固定温度

降温次数=预定值

复杂方式：

检查解是否达标

是否早熟：1992年Kouvelis

与Chiang

设定N次降温

无改善退出2/4/202336退火参数经验：降温时机降温时机---马可夫链长度，同一温度下所应反覆进行Metropolis演算的次数直接方式：设固定长度，与问题规模有关，1992年Kouvelis

与Chiang将其设定为邻近解个数之比率。降温时机

为移转接受次数已达一定值，Heragu

以及Alfa（1992）所用

但当温降至很低时，移转接受之机率将会很小，导致马可夫链过长，须同时限定马可夫链的长度2/4/202337退火参数经验：温度控制达到降温时机时，下降多少？（比率）参数小，差距大，下一温度

达成均衡

所需的马可夫链长求解时间增加。Kirkpatrick（1983）设为0.9，

一般

0.5～0.9线性降溫

Temp=Temp-x非线性降溫Temp=Temp*y

(y:0.5~0.99)2/4/202338退火算法的预备：一个抽签函数补充预备知识：通过随机实现自然放松设计一个抽签函数(下页）设计一个抽签既体现偶尔升温的随机（客观或运气），又体现当前温度的机会函数。2/4/202339准备一个函数：机会留给有准备的对象（主观+客观）设计一个机遇函数既体现随机的公平（客观或运气），又体现当前温度。降温大趋势中，按Rate=exp(-Δt′/T)的几率降温这一步应该降温吗，掷个骰子（古人用甲骨文占卜)：Bool

GetChance(Rate,CurrT，Threshold){redomaize();chance=Radom(1);return=(Chance<rate)&&(CurrT<=Threshold)}|-----|-----------|------……..------------------------------------|0chan