使用自由能分量的热力学演化算法

《使用自由能分量的热力学演化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cn1使用自由能分量的热力学演化算法11,213应伟勤，李元香，王玲玲，王轩1武汉大学软件工程国家重点实验室，湖北武汉(430072)2武汉大学计算机学院，湖北武汉(430079)3华中师范大学信息技术系，湖北武汉(430079)E-mail:weiqinying@yahoo.com.cn摘要：为了解决传统遗传算法经常由于种群多样性的流失而陷入早熟收敛的问题，本文提出了一种使用使用自由能分量的热力学演化算法。该算法主要模拟固体退火过程中能量与熵的竞争模式来协调遗传算法中“选择压力”和“种群

2、多样性”之间的矛盾。它使用了一种快速而有效的自由能分量竞争算子来模拟自由能减少定律。本文也证明了该算子有驱动种群自由能近似最速下降的能力。实验数据表明，该算法有效地避免了早熟现象，显著地提高了全局寻优能力和收敛速度。关键词：遗传算法热力学系统退火自由能分量熵中图分类号：TP301.61.引言在目前的算法研究中，Fox[1]提出的“按自然法则计算”(PhysicalComputation)的思想越来越受到人们的关注。按自然法则计算就是将大量的自然科学领域的思想与方法应用于其传统领域之外的其它领域，将原思想、方法的本质提取出来，用于解

3、决新领域中的问题。它在承认自然科学的特殊性的同时追求其普遍性，通过数学的、模型化的方法将其它学科具有普遍意义的规律引入计算机科学，构成新的计算模型。按自然法则计算的思想早已渗透到一些领域，如模拟退火算法、人工神经网络、弹性网络方法、确定性退火技术等。另一方面，遗传算法(geneticalgorithm,GA)作为一种通用的自适应随机搜索算法，目前还存在着早熟收敛和收敛速度慢这两个难题。近年来，很多学者对此作了研究。Whitley[2]认为，GA中最重要的两个因素就是“种群多样性”和“选择压力”。而选择压力过大是导致早熟收敛的一个重

4、要原因。过大的选择压力虽然可以加快算法的收敛速度，却会使种群中适应值较低的个体迅速“死亡”，种群的多样性遭到破坏，使得算法搜索空间减小，进而导致算法错误地收敛到局部最优值。降低选择压力虽然可以增大算法搜索到全局最优值的概率，但却会降低搜索效率，使算法的收敛速度变慢。因此，为了使算法具有良好的性能，必须在提高选择压力和保持种群多样性之间维持某种平衡。自然界始终是人类灵感的重要来源，引入自然法则来解决遗传算法易陷入局部最优的问题是值得尝试的方向。李元香教授[3]提出的动力学演化算法(dynamicalevolutionaryalgor

5、ithm,DEA)就借用了统计力学中的思想，它将GA中种群视为一个动力学系统，个体视为粒子，遗传操作视为粒子的碰撞或移动。系统中的每个粒子都有各自的动量(momentum)和活性(activity)，算法根据这两个属性来驱动所有粒子都参与运动，使群体保持足够的多样1本课题得到高等学校博士学科点专项科研基金（项目编号：20030486049）资助。-1-http://www.paper.edu.cn性，避免算法陷入局部最优解。该算法目前已成功应用于数值优化领域。文献[4]也初步提出了一种新颖的基于自由能减小定律的动力学演化算法，但是

6、要实际取得好的效果该算法诸多方面还有待改进。本文提出的热力学演化算法(thermodynamicalevolutionaryalgorithm,TEA)主要借鉴了固体退火过程中能量与熵的竞争模式，来协调种群收敛过程中“选择压力”和“种群多样性”之间的矛盾。该算法继承了文献[3,4]的部分思想，将种群视为一个热力学系统，种群中的个体视为系统中的粒子，也引入了自由能减少定律。但该算法在种群多样性的度量、自由能减少过程和竞争算子等方面都做了改进。它使用等级熵来度量种群多样性，在种群的每一代进化过程中使用自由能分量竞争算子来模拟自由能减少

7、定律。自由能分量竞争算子的优势在于它具有较低的复杂度，而且可以证明它能驱动种群的自由能至少以接近最快的进化速度下降。本文最后给出了使用TEA求解0-1背包问题的实例，实验结果表明，该算法在避免早熟收敛、寻优能力和收敛速度等方面，较简单GA和稳态GA都有显著的提高。2.热力学演化算法的物理背景热力学演化算法的主要思想是把固体退火过程中能量与熵的竞争机制引入到遗传算法中来。固体退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程[5]，属于热力学与统计物理研究的范畴。2.1固体退火的热力学过程先应将固体加热至熔解温度，使

8、固体熔解为液体，消除系统中原来可能存在的非均匀状态。然后冷却时当温度降至结晶温度后，液体将凝固成固体的晶态。若温度下降充分缓慢，使系统在每一温度下都达到平衡态，那么当温度趋于零时,系统最终可达到固体的基态。退火过程必须“徐徐”进行,否则若急剧降低温