热动力学演化算法TDEA及其进展

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