《热动力学演化算法及其进展幻灯片.ppt》由会员分享，可在线阅读，更多相关《热动力学演化算法及其进展幻灯片.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、热动力学演化算法及其进展第1页，共29页，编辑于2022年，星期日内容提要群智能算法研究的关键问题热力学与统计力学动力系统与最优控制热动力学算法框架自由能极小与热力学替换规则与粒子群算法的融合总结与展望第2页，共29页，编辑于2022年，星期日群智能算法研究的关键问题回顾早期遗传算法以及相关演化算法优点：自组织、自适应、普适性优点：自组织、自适应、普适性理论：隐含并行、基因块（建筑块）假设、依概率收敛理论：隐含并行、基因块（建筑块）假设、依概率收敛基于基于SGASGA的论证的论证缺点：过早收敛、适应值平台、欺骗性问题缺点：过早收敛、适应值平台、欺骗性问题症结：选择压力与种群多样性的关系解决方法
2、：从线性选择策略到非线性选择策略 适应值变换、锦标赛竞争选择、适应值变换、锦标赛竞争选择、BoltzmannBoltzmann竞争选择、竞争选择、+选择选择减缓选择压力，保持种群多样性第3页，共29页，编辑于2022年，星期日现代启发式群智能算法：粒子群优化、差分进化、分布估计算法优点：实现简单、普适性强、快速收敛、精度高优点：实现简单、普适性强、快速收敛、精度高理论：动力学分析方法理论：动力学分析方法缺点：过早收敛、局部搜索缺点：过早收敛、局部搜索症结：种群多样性与局部搜索、广域探测与局部开采症结：种群多样性与局部搜索、广域探测与局部开采解决方法：解决方法：2E2E（Exploration&
3、Exploitation)权衡权衡 增强搜索潜力，保持种群多样性第4页，共29页，编辑于2022年，星期日热力学与统计力学研究对象-大量粒子组成的系统热现象和力的宏观关热现象和力的宏观关系系-热力学热力学从粒子运动研究宏观关系-统计力学基于宏观观测、实验的唯象分析基于运动定律、假基于运动定律、假设的统计分析设的统计分析系统的热力学性质系统的热力学性质两个方面两个方面相辅相成相辅相成封闭系统：封闭系统：能量交换能量交换孤立系统：孤立系统：与世隔绝与世隔绝开放系统：开放系统：充分交换充分交换第5页，共29页，编辑于2022年，星期日基本定律热力学第一定律热力学第一定律 系统内能的变化等于其从环境传
4、递的热量与对外所作的功之差：系统内能的变化等于其从环境传递的热量与对外所作的功之差：dE=dE=Q-Q-A A ，或，或 Q=dEQ=dE +A A，即系统吸收的热量等于系统内能的增加与系统对外做功之和，即系统吸收的热量等于系统内能的增加与系统对外做功之和，对孤立系统对孤立系统dE=0dE=0，或，或E=E=恒量恒量 能量守恒定律能量守恒定律热力学第二定律热力学第二定律 不可逆性不可逆性两个典型的现象两个典型的现象tt以以-t-t代换得到不同的方程代换得到不同的方程 T-T-温度，温度，-热传导系数：热传导系数：FourierFourier定律定律 C-C-浓度，浓度，D-D-浓度扩散系数浓度
5、扩散系数 ：FickFick定律定律 KelvinKelvin表述：不能从单一热源中取热使之完全变为有用的功而表述：不能从单一热源中取热使之完全变为有用的功而不产生任何其它影响不产生任何其它影响 ClausiusClausius表述：不可能把热从低温物体传到高温物体而不产生其表述：不可能把热从低温物体传到高温物体而不产生其它影响它影响 不可逆性，能量的耗散特性第6页，共29页，编辑于2022年，星期日熵与平衡态熵的概念系统吸收热能除以温度所得的商，标志热转化为功的程度系统吸收热能除以温度所得的商，标志热转化为功的程度d d S=S=Q/TQ/T，严格地讲应分为两部分：，严格地讲应分为两部分：d
6、 d S=S=d di i S+S+d de e S Sd di i S0S0，称为熵产生项，由系统内的热运动决定，称为熵产生项，由系统内的热运动决定d de e S S可正可负，称为熵流项，由系统与外界环境的相互作用决定孤立可正可负，称为熵流项，由系统与外界环境的相互作用决定孤立系统有系统有d d S 0S 0，但封闭系统和开放系统则不一定，但封闭系统和开放系统则不一定熵的统计力学解释 系统的一个宏观态对应着大量的微观态，一个微观态称为系系统的一个宏观态对应着大量的微观态，一个微观态称为系统统的一种的一种实现，实现的总数称作容配数实现，实现的总数称作容配数W W，则有熵，则有熵 S=klnW
7、S=klnW著名的著名的BoltzmannBoltzmann公式公式 k k称为称为 BoltzmannBoltzmann常数常数系统的平衡态对应的容配数W最多，熵最大第7页，共29页，编辑于2022年，星期日熵与序孤立系统的自发过程是熵增加的过程，最终发展到一个宏观静止的平衡态，熵达到最大值平衡态是一个最无序的状态系统的熵值反映系统的有序程度，系统的熵值越小，它越是系统的熵值反映系统的有序程度，系统的熵值越小，它越是有序，呈现某种结构；系统的熵值越大，它越是无序，难以有序，呈现某种结构；系统的熵值越大，它越是无序，难以发现其结构发现其结构系统总是力图自发地从熵值较小的状态向熵值较大（即从系统
8、总是力图自发地从熵值较小的状态向熵值较大（即从有序走向无序）的状态转变，即孤立系统的有序走向无序）的状态转变，即孤立系统的“熵值增大原熵值增大原理理”第8页，共29页，编辑于2022年，星期日信息熵自信息描述了事件集自信息描述了事件集X X中一个事件i i出现给出的信息量，整个集X的平均信息量是该集所有事件自信息的统计平均值（数学期望），称作集X X的熵p pi i表示件表示件i事发生的概率事发生的概率H（X X）度量了集）度量了集X X中各个事件未出现时所呈现的平均不中各个事件未出现时所呈现的平均不确定性，也度量了集确定性，也度量了集X X中一个事件出现时所给出的平均中一个事件出现时所给出的
9、平均信息量信息量第9页，共29页，编辑于2022年，星期日自由能极小定律等温下的封闭热力学系统遵循自由能极小定律等温下的封闭热力学系统遵循自由能极小定律 对于与周围环境交换热量而温度保持不变的封闭系统对于与周围环境交换热量而温度保持不变的封闭系统,系系统状态的自发变化总是朝着自由能减少的方向进行统状态的自发变化总是朝着自由能减少的方向进行,当自由当自由能达到最小值时系统达到平衡态能达到最小值时系统达到平衡态系统的自由能 F F E T S 能量减少与熵增加均可导致自由能减少能量减少与熵增加均可导致自由能减少,两者均有利于系统两者均有利于系统的自发变化的自发变化 任一恒定温度下任一恒定温度下,系
10、统从非平衡态自发变化到平衡态的过程系统从非平衡态自发变化到平衡态的过程,都都是能量与熵两者竞争的结果是能量与熵两者竞争的结果 而温度则决定着竞争过程中能量与熵的相对权重：高温时熵而温度则决定着竞争过程中能量与熵的相对权重：高温时熵占统治地位；低温时能量占统治地位占统治地位；低温时能量占统治地位能量能量温度温度熵熵第10页，共29页，编辑于2022年，星期日热力学系统与群智能算法热力学系统算法若干粒子组成热力学系统若干个体组成进化种群系统的能量种群的负平均适应值，与开发能力相关系统的热力学熵种群的多样性，与探索能力相关系统的温度权重控制参数T能量和熵的竞争“开发能力”与“探索能力”的适当平衡恒定
11、温度下系统朝着自由能减少的方向自发变化给定权重T下驱动种群向自由能减少的方向演化“徐徐”降温给定权重T下种群充分演化后缓慢衰减T值第11页，共29页，编辑于2022年，星期日动力系统与最优控制第12页，共29页，编辑于2022年，星期日TDEATDEA通过模拟自由能极小定律实现种群中能量和熵之间的竞争机制，从而达到定量协调算法探索能力和开发能力之间的均衡，随T递减缓慢降低自由能递减缓慢降低自由能从N个父个体和M个子个体中挑选出N个个体组成下一代种群,使其具有的自由能最小热动力学算法框架第13页，共29页，编辑于2022年，星期日两个最关键问题如何定义熵度量种群多样性 基因熵（基因熵（Mori,
12、1995Mori,1995）网格熵（胡婷,2005）等级熵（应伟勤，2007）如何设计热力学替换规则种群自由能下降贪婪热力学替换规则（Mori,1995）分量热力学替换规则（应伟勤，分量热力学替换规则（应伟勤，20072007）第14页，共29页，编辑于2022年，星期日种群的基因熵MoriMori在实现在实现TDGATDGA时采用基因熵来度量种群的基因多样性，基因熵等于种群每个基因座上的信息熵的合计值优点：很直观，易于实现缺点：只适用于离散编码；在个体编码较长时计算开销极大，这将会降低TDGA的计算效率 0 1 0 1 2 j LX1X2XN第15页，共29页，编辑于2022年，星期日种群的
13、网格熵由于基因熵无法应用于实数编码，胡婷提出了一种网由于基因熵无法应用于实数编码，胡婷提出了一种网格熵，将定义域划分为若干网格，计算个体在网格中格熵，将定义域划分为若干网格，计算个体在网格中分布的信息熵分布的信息熵x1x2G1G2GM第16页，共29页，编辑于2022年，星期日种群的等级熵活跃窗口活跃窗口wt t ：记录了到第：记录了到第t代为止搜索过程已达个体的适应度范围在对活跃窗口划分等级时,遵循了适应值区域越优分级遵循了适应值区域越优分级越精细的原则越精细的原则 0 1 0 编码空间目标空间活跃窗口f(.)等级划分示意图等级划分示意图第17页，共29页，编辑于2022年，星期日等级熵度量
14、种群中个体在适应值空间的分散程度等级熵度量种群中个体在适应值空间的分散程度当当P Pt t中所有个体全部落入同一等级时等级熵中所有个体全部落入同一等级时等级熵H H(w wt t,P Pt t)取最小值取最小值0,0,当当P Pt t中落入各等级的个体数都相等时中落入各等级的个体数都相等时,H H(w wt t,P Pt t)达到最大值达到最大值1.1.等级熵的优点：不再依赖个体的编码长度，计算成等级熵的优点：不再依赖个体的编码长度，计算成本较低本较低第18页，共29页，编辑于2022年，星期日热力学替换规则 从父代种群从父代种群P Pt t t t =(=(=(=(X X X X1 1,X
15、X X X2 2,X XN NN N)的的的的N NN N个个体与产生的个个体与产生的MMMM个子个子代种群代种群O OO Ot t=(=(X X X XN+1N+1N+1N+1,X X X XN+2N+2,X X X XN+MN+MN+MN+M)，共，共，共，共N+MN+MN+MN+M个体中挑选出个体中挑选出个体中挑选出个体中挑选出N N个个体组成下一代种群个个体组成下一代种群个个体组成下一代种群个个体组成下一代种群P P P P(E E E E)t+1t+1t+1t+1,使其具有的自由能使其具有的自由能F F F F(T T T Tt t,P P P P(E E E E)t+1t+1t+1
16、t+1)最小最小从N个父个体和M个子个体中挑选出N个个体生成下一代种群,使其具有的自由能最小第19页，共29页，编辑于2022年，星期日穷举热力学替换规则精确地最小化所有可能的下一代种群的自由能本身是一个精确地最小化所有可能的下一代种群的自由能本身是一个颇难的组合优化问题颇难的组合优化问题穷举热力学替换规则：使用穷举法计算所有可能组合成穷举热力学替换规则：使用穷举法计算所有可能组合成的临时种群的自由能，最小的那个种群即为下一代的临时种群的自由能，最小的那个种群即为下一代穷举热力学替换规则的复杂度为穷举热力学替换规则的复杂度为OO(LNCLNCNNNN+M+M),),因此因此Mori指出穷举热力
17、学替换规则在实际应用中是不可行的第20页，共29页，编辑于2022年，星期日贪婪热力学替换规则MoriMori在实现在实现TDGATDGA时采用了贪婪热力学替换规则，按照贪婪的策略逐时采用了贪婪热力学替换规则，按照贪婪的策略逐个往下一代种群中填充使临时种群自由能最小的个体个往下一代种群中填充使临时种群自由能最小的个体 复杂度：复杂度：OO(LN(N+M)(LN(N+M)贪婪热力学替换规则的计算开销较穷举热力学替换规则有很大降低贪婪热力学替换规则的计算开销较穷举热力学替换规则有很大降低,但但在实际应用中计算成本仍相当高在实际应用中计算成本仍相当高Pt1=GTR(Tt,Pt,Ot)将子种群将子种群
18、Ot与与父种群父种群Pt合并得到规模为合并得到规模为N+M的中间种群的中间种群Pt1,将将Pt1置空置空;for(i=1;i=N;i+)/采用贪婪策略逐次往采用贪婪策略逐次往Pt1中填充中填充N个个体个个体 for(j=1;j=N+M-i;j+)/在多次尝试后找到本轮最好填充个体在多次尝试后找到本轮最好填充个体 计算若将计算若将Pt1的第的第j个个体填充到个个体填充到Pt1后的自由能后的自由能F(Tt,Pt1 Pt1j),并记并记 录下本轮尝试填充中使自由能最小的个体录下本轮尝试填充中使自由能最小的个体Xjmin;将个体将个体Xjmin填充到填充到Pt1中中,并将其从并将其从中间种群中间种群P
19、t1中清除出去中清除出去;返回下一代种群返回下一代种群Pt1;第21页，共29页，编辑于2022年，星期日分量热力学替换规则-自由能分量贪婪替换规则计算开销较大的主要原因在于自由能自由能是相对是相对于于种群而言的，须首先通过尝试填充获得临时种群，然后而言的，须首先通过尝试填充获得临时种群，然后反复计算反复计算这些这些临时种群的自由能为提高计算效率，引入为提高计算效率，引入个体个体的的自由能分量自由能分量的概念，将种群的的概念，将种群的自由能分派到其各个体上，自由能分派到其各个体上，避免反复计算避免反复计算种群的自由能种群的自由能活跃窗口活跃窗口wt t和温度和温度T Tt t下个体下个体X X
20、l l在种群在种群Pt中的自由能分量 F Fc(w wt t,Tt t,P,Pt t,X,Xl)=)=e e(X Xl)+T+Tt tloglogK(n nd d/NN),),其中其中nd d表示种群表示种群P Pt t中与中与X Xl处于同一等级的个体数处于同一等级的个体数第22页，共29页，编辑于2022年，星期日分量热力学替换规则基于自由能分量的分量热力学替换规则，计算量少驱动种群自由能下降快速复杂度：O(M(N+M)，有效降低了替换规则的时间复杂度第23页，共29页，编辑于2022年，星期日分量热力学替换规则(CTR)的性质 在两个引理的基础上，运用极限夹逼准则可从理论上完整地证明在两
21、个引理的基础上，运用极限夹逼准则可从理论上完整地证明CTRCTR规则除了具有较低时间复杂度之外，还具有驱动种群自由规则除了具有较低时间复杂度之外，还具有驱动种群自由能近似最速下降的良好性质能近似最速下降的良好性质(极限夹逼准则，数学归纳法，自然极限夹逼准则，数学归纳法，自然对数性质对数性质ln(x)=x-1)ln(x)=x-1)第24页，共29页，编辑于2022年，星期日TDEA相关论文 Mori N,Yoshida J,Tamaki H,Kita H,Nishikawa Y.A thermodynamical selection Mori N,Yoshida J,Tamaki H,Kita
22、H,Nishikawa Y.A thermodynamical selection rule for the genetic algorithm.In:Fogel DB,ed.Proc.of the IEEE Conf.on rule for the genetic algorithm.In:Fogel DB,ed.Proc.of the IEEE Conf.on Evolutionary Computation.New York:IEEE Press,1995.188192.Evolutionary Computation.New York:IEEE Press,1995.188192.Mo
23、ri N,Kita H,Nishikawa Y.Adaptation to a changing environment by Mori N,Kita H,Nishikawa Y.Adaptation to a changing environment by means of the feedback thermodynamical genetic algorithm.In:Eiben AE,means of the feedback thermodynamical genetic algorithm.In:Eiben AE,et alet al.,eds.Proc.of the IEEE C
24、onf.on Parallel Problem Solving from Nature.Berlin:.,eds.Proc.of the IEEE Conf.on Parallel Problem Solving from Nature.Berlin:Springer-Verlag,1998.149158.Springer-Verlag,1998.149158.应伟勤应伟勤,李元香李元香,许承瑜许承瑜.热力学遗传算法计算效率的改进热力学遗传算法计算效率的改进.软件学报软件学报,2008,2008,19(7):1613-162219(7):1613-1622 Weiqin Ying,Yuanxi
25、ang Li,Shujuan Peng,Weiwu Wang.A Steep Weiqin Ying,Yuanxiang Li,Shujuan Peng,Weiwu Wang.A Steep Thermodynamical Selection Rule for Evolutionary Algorithms.Proc.of Int.Conf.Thermodynamical Selection Rule for Evolutionary Algorithms.Proc.of Int.Conf.on Computational Science.Beijing,China,2007:997-1004
26、on Computational Science.Beijing,China,2007:997-1004第25页，共29页，编辑于2022年，星期日与粒子群算法的融合根据粒子的自由能分量决定下一代种群根据粒子的自由能分量决定下一代种群耗散粒子群优化算法：引入负熵耗散粒子群优化算法：引入负熵自组织临界粒子群优化算法：引入临界值属性自组织临界粒子群优化算法：引入临界值属性引入分子热运动中分子力分子力、布朗运动布朗运动和和扩散现象分别从分别从三个不同层面模拟热力学机制改进粒子群优化算模拟热力学机制改进粒子群优化算法法第26页，共29页，编辑于2022年，星期日TD-PSO算法按PSO算法中的位置更新
27、公式随机选择M个粒子生成子种群1.合并父、子种群2.在新种群中计算M个父粒子和子粒子的自由能分量3.保留父、子粒子中自由能分量较小者第27页，共29页，编辑于2022年，星期日分子力、布朗运动、扩散微观 介观 宏观 模拟的角度 热运动机制 斥力引力 布朗运动 扩散现象 力分子斥力引力rforo第28页，共29页，编辑于2022年，星期日总结与展望热力学与统计力学的显著特点是普适性，在少数几个一般原理和假设的基础上，其结论可应用于完全不同的物质组成的系统，甚至社会科学和宇宙学。因此，在算法设计中的应用刚刚开始重在运用其原理，不要生搬硬套书本上的公式重在运用其原理，不要生搬硬套书本上的公式模型的建立很重要，既要注意到算法的种群毕竟是人工系统不是纯自然的，又要与原理和理论相呼应统计力学理论结合动力系统理论可望成为演化算法理论统计力学理论结合动力系统理论可望成为演化算法理论分析的新方法分析的新方法第29页，共29页，编辑于2022年，星期日