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

使用自由能分量的热力学演化算法1 1 1,2 1 3 应伟勤 ，李元香 ，王玲玲 ，王 轩 1 武汉大学软件工程国家重点实验室，湖北武汉(430072) 2 武汉大学计算机学院，湖北武汉(430079) 3 华中师范大学信息技术系，湖北武汉(430079) E-mail: weiqinying@ 摘 要： 为了解决传统遗传算法经常由于种群多样性的流失而陷入早熟收敛的问题，本文 提出了一种使用使用自由能分量的热力学演化算法。该算法主要模拟固体退火过程中能量与 熵的竞争模式来协调遗传算法中“选择压力”和“种群多样性”之间的矛盾。它使用了一种快速 而有效的自由能分量竞争算子来模拟自由能减少定律。本文也证明了该算子有驱动种群自由 能近似最速下降的能力。实验数据表明，该算法有效地避免了早熟现象，显著地提高了全局 寻优能力和收敛速度。 关键词：遗传算法 热力学系统 退火 自由能分量 熵 中图分类号：TP301.6 1. 引 言 在目前的算法研究中，Fox[1]提出的“按自然法则计算”(Physical Computation) 的思想越 来越受到人们的关注。按自然法则计算就是将大量的自然科学领域的思想与方法应用于其传 统领域之外的其它领域，将原思想、方法的本质提取出来，用于解决新领域中的问题。它在 承认自然科学的特殊性的同时追求其普遍性，通过数学的、模型化的方法将其它学科具有普 遍意义的规律引入计算机科学，构成新的计算模型。按自然法则计算的思想早已渗透到一些 领域，如模拟退火算法、人工神经网络、弹性网络方法、确定性退火技术等。 另一方面，遗传算法(genetic algorithm, GA)作为一种通用的自适应随机有哪些信誉好的足球投注网站算法，目前 还存在着早熟收敛和收敛速度慢这两个难题。近年来，很多学者对此作了研究。Whitley[2] 认为，GA 中最重要的两个因素就是“种群多样性”和“选择压力” 。而选择压力过大是导致早 熟收敛的一个重要原因。过大的选择压力虽然可以加快算法的收敛速度，却会使种群中适应 值较低的个体迅速“死亡”，种群的多样性遭到破坏，使得算法有哪些信誉好的足球投注网站空间减小，进而导致算法 错误地收敛到局部最优值。降低选择压力虽然可以增大算法有哪些信誉好的足球投注网站到全局最优值的概率，但却 会降低有哪些信誉好的足球投注网站效率，使算法的收敛速度变慢。因此，为了使算法具有良好的性能，必须在提高 选择压力和保持种群多样性之间维持某种平衡。 自然界始终是人类灵感的重要来源，引入自然法则来解决遗传算法易陷入局部最优的问 题是值得尝试的方向。李元香教授[3]提 出的动力学演化算法(dynamical evolutionary algorithm, DEA)就借用了统计力学中的思想，它将 GA 中种群视为一个动力学系统，个体视 为粒子，遗传操作视为粒子的碰撞或移动。系统中的每个粒子都有各 自的动量(momentum) 和活性(activity) ，算法根据这两个属性来驱动所有粒子都参与运动，使群体保持足够的多样 1 本课题得到高等学校博士学科点专项科研基金（项目编号：20030486049 ）资助。 - 1 - 性，避免算法陷入局部最优解。该算法目前已成功应用于数值优化领域。文献[4]也初步提 出了一种新颖的基于自由能减小定律的动力学演化算法，但是要实际取得好的效果该算法诸 多方面还有待改进。 本文提出的热力学演化算法(thermodynamical evolutionary algorithm, TEA)主要借鉴了固 体退火过程中能量与熵的竞争模式，来协调种群收敛过程中“选择压力”和“种群多样性”之间 的矛盾。该算法继承了文献[3,4]的部分思想，将种群视为一个热力学系统，种群中的个体视 为系统中的粒子，也引入了自由能减少定律