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

1、热动力学演化算法及其进展,李元香,内容提要,群智能算法研究的关键问题 热力学与统计力学 动力系统与最优控制 热动力学算法框架 自由能极小与热力学替换规则 与粒子群算法的融合 总结与展望,群智能算法研究的关键问题,回顾早期遗传算法以及相关演化算法 优点：自组织、自适应、普适性 理论：隐含并行、基因块（建筑块）假设、依概率收敛基于SGA的论证 缺点：过早收敛、适应值平台、欺骗性问题 症结：选择压力与种群多样性的关系 解决方法：从线性选择策略到非线性选择策略 适应值变换、锦标赛竞争选择、Boltzmann竞争选择、+选择 减缓选择压力，保持种群多样性,现代启发式群智能算法：粒子群优化、差分进化、分布

2、估计算法 优点：实现简单、普适性强、快速收敛、精度高 理论：动力学分析方法 缺点：过早收敛、局部搜索 症结：种群多样性与局部搜索、广域探测与局部开采 解决方法：2E（Exploration 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; ,分量热力学替换规则-自由能分量,

3、贪婪替换规则计算开销较大的主要原因在于自由能是相对于种群而言的，须首先通过尝试填充获得临时种群，然后反复计算这些临时种群的自由能 为提高计算效率，引入个体的自由能分量的概念，将种群的自由能分派到其各个体上，避免反复计算种群的自由能 活跃窗口wt和温度Tt下个体Xl在种群Pt中的自由能分量 Fc(wt,Tt,Pt,Xl)=e(Xl)+TtlogK(nd /N), 其中nd表示种群Pt中与Xl处于同一等级的个体数,分量热力学替换规则,基于自由能分量的分量热力学替换规则，计算量少驱动种群自由能下降快速 复杂度：O(M(N+M)，有效降低了替换规则的时间复杂度,分量热力学替换规则(CTR)的性质,在两

4、个引理的基础上，运用极限夹逼准则可从理论上完整地证明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

5、 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. 应伟勤, 李元香, 许承瑜. 热力学遗传算法

6、计算效率的改进. 软件学报, 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.保留父、子粒子中自由能分量较小者,分子力、布朗运动、扩散,微观,介观,宏观,模拟的角度,热运动机制,斥力引力,布朗运动,扩散现象,总结与展望,热力学与统计力学的显著特点是普适性，在少数几个一般原理和假设的基础上，其结论可应用于完全不同的物质组成的系统，甚至社会科学和宇宙学。因此，在算法