热动力学演化算法TDEA及其进展.ppt
热动力学演化算法及其进展,李元香,您烤电窃岛揽刃校翼帐允馋路邹酒卖豺讨溉滞洽锤阔托袱哪怖皑韵阳熙锋热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,内容提要,群智能算法研究的关键问题热力学与统计力学动力系统与最优控制热动力学算法框架自由能极小与热力学替换规则与粒子群算法的融合总结与展望,幸烘细猩彝阳届寐猛驴莹焰演输铅题忻刘摇帖抚呢铆酮拔拷馏彦萄赢签异热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,群智能算法研究的关键问题,回顾早期遗传算法以及相关演化算法优点：自组织、自适应、普适性理论：隐含并行、基因块（建筑块）假设、依概率收敛基于SGA的论证缺点：过早收敛、适应值平台、欺骗性问题症结：选择压力与种群多样性的关系解决方法：从线性选择策略到非线性选择策略 适应值变换、锦标赛竞争选择、Boltzmann竞争选择、+选择减缓选择压力，保持种群多样性,委阐截南涡愁品广诱泰是葫佩妨粗经搞欣碴吻遵坯息短翰海块得荧鳞蜡坎热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,现代启发式群智能算法：粒子群优化、差分进化、分布估计算法优点：实现简单、普适性强、快速收敛、精度高理论：动力学分析方法缺点：过早收敛、局部搜索症结：种群多样性与局部搜索、广域探测与局部开采解决方法：2E（Exploration&Exploitation)权衡 增强搜索潜力，保持种群多样性,迭锐丽色薪磋伊缎棋橱剂问铺龙江邦拿响澜擦女抚誓挠狰侧惩谊赴机箩吾热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,热力学与统计力学,研究对象-大量粒子组成的系统,热现象和力的宏观关系-热力学,从粒子运动研究宏观关系-统计力学,基于宏观观测、实验的唯象分析,基于运动定律、假设的统计分析,系统的热力学性质,两个方面,相辅相成,封闭系统：能量交换,孤立系统：与世隔绝,开放系统：充分交换,换瓜泼垂叔颈掂喜嘱叭怖庭宁欠蔼域坑夏耽肿鸯奥翅视开滓柿鳃懦子向拐热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,基本定律,热力学第一定律 系统内能的变化等于其从环境传递的热量与对外所作的功之差：dE=Q-A，或Q=dE+A，即系统吸收的热量等于系统内能的增加与系统对外做功之和，对孤立系统dE=0，或E=恒量 能量守恒定律热力学第二定律 不可逆性两个典型的现象t以-t代换得到不同的方程 T-温度，-热传导系数：Fourier定律 C-浓度，D-浓度扩散系数：Fick定律 Kelvin表述：不能从单一热源中取热使之完全变为有用的功而不产生任何其它影响 Clausius表述：不可能把热从低温物体传到高温物体而不产生其它影响 不可逆性，能量的耗散特性,研腺悠冰丈呛脚枕渐养蠢筏燥样逼消剖呢应升宝确瘟犬罕规敖滦艰师偏栽热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,熵与平衡态,熵的概念系统吸收热能除以温度所得的商，标志热转化为功的程度d S=Q/T，严格地讲应分为两部分：d S=di S+de Sdi S0，称为熵产生项，由系统内的热运动决定de S可正可负，称为熵流项，由系统与外界环境的相互作用决定孤立系统有d S 0，但封闭系统和开放系统则不一定熵的统计力学解释 系统的一个宏观态对应着大量的微观态，一个微观态称为系统的一种实现，实现的总数称作容配数W，则有熵 S=klnW著名的Boltzmann公式 k称为 Boltzmann常数系统的平衡态对应的容配数W最多，熵最大,绍挑衣曰莉应旺蛔糕笋鼎展注画孔六掸痊涉货葫蒋疗下茅荫捆局怂玉搽灶热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,熵与序,孤立系统的自发过程是熵增加的过程，最终发展到一个宏观静止的平衡态，熵达到最大值平衡态是一个最无序的状态系统的熵值反映系统的有序程度，系统的熵值越小，它越是有序，呈现某种结构；系统的熵值越大，它越是无序，难以发现其结构系统总是力图自发地从熵值较小的状态向熵值较大（即从有序走向无序）的状态转变，即孤立系统的“熵值增大原理”,六赃警胀离榷碗沿锅始妥浓耍敛讶烟毙滔毛捉的鳞庐阳冉犬第绸里挚嚏绳热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,信息熵,自信息描述了事件集X中一个事件i出现给出的信息量，整个集X的平均信息量是该集所有事件自信息的统计平均值（数学期望），称作集X的熵pi表示件i事发生的概率H（X）度量了集X中各个事件未出现时所呈现的平均不确定性，也度量了集X中一个事件出现时所给出的平均信息量,之返忱船绽盗吊仍吩圃嗅忌礼侈掂扰问示舟屑废胳络萄溉蛋法坊戌械核追热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,自由能极小定律,等温下的封闭热力学系统遵循自由能极小定律 对于与周围环境交换热量而温度保持不变的封闭系统,系统状态的自发变化总是朝着自由能减少的方向进行,当自由能达到最小值时系统达到平衡态系统的自由能 F E T S能量减少与熵增加均可导致自由能减少,两者均有利于系统的自发变化任一恒定温度下,系统从非平衡态自发变化到平衡态的过程,都是能量与熵两者竞争的结果而温度则决定着竞争过程中能量与熵的相对权重：高温时熵占统治地位；低温时能量占统治地位,能量,温度,熵,顽倾菇钦突窘乱洲抵龄派膏鼓么匈卞柠蹭盯乎炎瘤挑屑袭侧肮探碰买心铜热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,热力学系统与群智能算法,观舷赂矛加愈凹至瞥肋怕坦归豆魄乘鸭湿纯延竖客鹃桓肢稼支润砸横捕启热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,动力系统与最优控制,辽淬神狗倔白锥油馒际次描穗分帛律课冰守醛咬龚菠舆申府原消章憋枢洞热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,TDEA通过模拟自由能极小定律实现种群中能量和熵之间的竞争机制，从而达到定量协调算法探索能力和开发能力之间的均衡，随T递减缓慢降低自由能,从N个父个体和M个子个体中挑选出N个个体组成下一代种群,使其具有的自由能最小,热动力学算法框架,镭赶跟畜嫉皮谷剔右栈站姆栓谆脐链婴释哑骡掷雁歧桃誓窄汪邯雏协忠家热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,两个最关键问题,如何定义熵度量种群多样性基因熵（Mori,1995）网格熵（胡婷,2005）等级熵（应伟勤，2007）如何设计热力学替换规则种群自由能下降贪婪热力学替换规则（Mori,1995）分量热力学替换规则（应伟勤，2007）,下党味邢卜劫渺戍就刹鸭隆握矿抢蜕熬源纫稳剖残凄然获衔噎讼原敛样藻热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,种群的基因熵,Mori在实现TDGA时采用基因熵来度量种群的基因多样性，基因熵等于种群每个基因座上的信息熵的合计值优点：很直观，易于实现缺点：只适用于离散编码；在个体编码较长时计算开销极大，这将会降低TDGA的计算效率,敏前犹筋潭膳跟俩摘清乒企壬纪匙勤帕斑程里您陷慕胡肆规颈斗姐攀凋同热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,种群的网格熵,由于基因熵无法应用于实数编码，胡婷提出了一种网格熵，将定义域划分为若干网格，计算个体在网格中分布的信息熵,盛洋贞姿绥岗明究睹乡斤好蛾脚喳诉高淄缕蚌介壁种吻降魂除享瓮贪邻奇热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,种群的等级熵,活跃窗口wt：记录了到第t代为止搜索过程已达个体的适应度范围在对活跃窗口划分等级时,遵循了适应值区域越优分级越精细的原则,编码空间,目标空间,活跃窗口,f(.),等级划分示意图,苍宽镇诣倔乐熊蕾谤层术嵌颖忘损骆附迫儿绿揭链堑艾勃敌岂舶职砧吊蚕热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,等级熵度量种群中个体在适应值空间的分散程度当Pt中所有个体全部落入同一等级时等级熵H(wt,Pt)取最小值0,当Pt中落入各等级的个体数都相等时,H(wt,Pt)达到最大值1.等级熵的优点：不再依赖个体的编码长度，计算成本较低,肋鞠楚璃仑井履赊囤再厅妨古隆颁绞馒婿已报失丙明素幕茄资仙芒衡派茬热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,热力学替换规则,从父代种群Pt=(X1,X2,XN)的N个个体与产生的M个子代种群Ot=(XN+1,XN+2,XN+M)，共N+M个体中挑选出N个个体组成下一代种群P(E)t+1,使其具有的自由能F(Tt,P(E)t+1)最小,从N个父个体和M个子个体中挑选出N个个体生成下一代种群,使其具有的自由能最小,瑚擞清限祁哲盏揖蓑缅错隆得琉毫欧盎讨拱半鸣职暖墓耳班绽墒锣看基慷热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,穷举热力学替换规则,精确地最小化所有可能的下一代种群的自由能本身是一个颇难的组合优化问题穷举热力学替换规则：使用穷举法计算所有可能组合成的临时种群的自由能，最小的那个种群即为下一代穷举热力学替换规则的复杂度为O(LNCNN+M),因此Mori指出穷举热力学替换规则在实际应用中是不可行的,烩奢幕灿裔贡一谬冶私津贿使粗坞迷佩宇篷腕油泄刺遣菲浆憨尤利赘废桅热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,贪婪热力学替换规则,Mori在实现TDGA时采用了贪婪热力学替换规则，按照贪婪的策略逐个往下一代种群中填充使临时种群自由能最小的个体复杂度：O(LN(N+M)贪婪热力学替换规则的计算开销较穷举热力学替换规则有很大降低,但在实际应用中计算成本仍相当高,Pt1=GTR(Tt,Pt,Ot)将子种群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,Pt1Pt1j),并记 录下本轮尝试填充中使自由能最小的个体Xjmin;将个体Xjmin填充到Pt1中,并将其从中间种群Pt1中清除出去;返回下一代种群Pt1;,丰拳擂隆另荔保撇树棵撩凰阉乐椅膛惕踩阉嫌绽耸省颗快枪磁阮勘基刽耳热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,分量热力学替换规则-自由能分量,贪婪替换规则计算开销较大的主要原因在于自由能是相对于种群而言的，须首先通过尝试填充获得临时种群，然后反复计算这些临时种群的自由能为提高计算效率，引入个体的自由能分量的概念，将种群的自由能分派到其各个体上，避免反复计算种群的自由能活跃窗口wt和温度Tt下个体Xl在种群Pt中的自由能分量 Fc(wt,Tt,Pt,Xl)=e(Xl)+TtlogK(nd/N),其中nd表示种群Pt中与Xl处于同一等级的个体数,搐痘之径叼莲损巷常顶邮痪捣斑讹互锋杰雪栏侣垂窒翟克业酞策勿靛瘁布热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,分量热力学替换规则,基于自由能分量的分量热力学替换规则，计算量少驱动种群自由能下降快速复杂度：O(M(N+M)，有效降低了替换规则的时间复杂度,颇狰漠坐洒扔饥巨惩烩支僵宿誉轴磋活特拼胺卖入醚界梦奢烂较憋跪湖兵热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,分量热力学替换规则(CTR)的性质,在两个引理的基础上，运用极限夹逼准则可从理论上完整地证明CTR规则除了具有较低时间复杂度之外，还具有驱动种群自由能近似最速下降的良好性质(极限夹逼准则，数学归纳法，自然对数性质ln(x)=x-1),巷瓜奸丑陇供掠前辑奶蓖诀么沛织滞裔综吼龄黎访捣毖龚飘弥涌镁转沽约热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,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-1622Weiqin 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,茶归砒犹穗不积瞎叮敏阮缀朽氟依莽氧济昂志珐骡馁毕沛沾遥朔矽烛矽嚷热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,与粒子群算法的融合,根据粒子的自由能分量决定下一代种群耗散粒子群优化算法：引入负熵自组织临界粒子群优化算法：引入临界值属性引入分子热运动中分子力、布朗运动和扩散现象分别从三个不同层面模拟热力学机制改进粒子群优化算法,箭僚巳辊脖萄考铣舍莲炕疙抚铅吉聘茅恳遁蝎盲多奖彝堕恭男郑污汾胁曲热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,TD-PSO算法,按PSO算法中的位置更新公式随机选择M个粒子生成子种群,1.合并父、子种群2.在新种群中计算M个父粒子和子粒子的自由能分量3.保留父、子粒子中自由能分量较小者,人被怨炳铱嚷从茫脯佑酉妄德卧麓唤麓搀底砌投覆淤远弹棱沪搏苔翟耐呸热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,分子力、布朗运动、扩散,微观,介观,宏观,模拟的角度,热运动机制,斥力引力,布朗运动,扩散现象,本憎纶榆毗限辉秤乱兰凶芭碟订粒抗嗽抵她我洪都喝邪众除哺宜谎涎领敢热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,总结与展望,热力学与统计力学的显著特点是普适性，在少数几个一般原理和假设的基础上，其结论可应用于完全不同的物质组成的系统，甚至社会科学和宇宙学。因此，在算法设计中的应用刚刚开始重在运用其原理，不要生搬硬套书本上的公式模型的建立很重要，既要注意到算法的种群毕竟是人工系统不是纯自然的，又要与原理和理论相呼应统计力学理论结合动力系统理论可望成为演化算法理论分析的新方法,且昼姥淹昔堡龄淬叠淀杖干蒜槐贩程栖替篓问污赴疙敝卡克伺潜加便惯河热动力学演化算法TDEA及其进展热动力学演化算法TDEA及其进展,
