进化算法中多种信息的利用

摘要

优化和搜索是两个普遍问题，科学和应用中的许多问题都可以转化成优化问题或者搜索问题。进化算法，作为一种模拟生物优胜劣汰过程的智能搜索和优化算法，有着非常广泛的应用前景。现阶段，它已经被大量应用到生物信息学、飞行器设计、机器人、人工生命等领域。但是，有关进化算法的理论并不完善，并且进化算法的时间性能和精度性能都有待提高。本文研究如何利用多种信息来提高已有进化算法的性能和开发出新的进化计算模型，力求进一步完善进化计算的基本理论和扩大其在实际中的应用。 文中只涉及进化算法中存在的两种基本信息：位重要性和群体的统计特性。位重要性普遍存在于二值编码的进化算法之中。我们主要阐述了位重要性和位收敛顺序性的概念及其存在的可能性；为了提高遗传算法中交叉算子的性能，我们提出了基于位重要性的基因重排算法的设计方案，并用实验证明了该方案的可行性；建立在位重要性概念的基础上，我们提出了分层进化的思想以及基于该思想的位重要性进化算法。 进化算法是一种群体搜索算法，统计特性，作为群体的固有特性，理应在进化算法中得到充分利用。在文中，我们主要分析了变量不相关边缘分布估计算法（UMDA）的遗传漂移现象；提出了UMDA的自适应群体规模设定策略，研究了UMDA在有噪声环境下的性能；在本文的最后部分，我们进一步扩展了上面提出的UMDA的有噪声优化理论，证明了概率分布估计算法(EDA)在有噪声环境下的全局收敛性，从而奠定了EDA在有噪声优化中应用的理论基础。文中为了说明我们所提出 观点的正确性，一方面通过严格的理论分析、证明，另一方面通过大量 的仿真实验。理论和实验相结合增加了本文所提出方法的可靠性和可扩展性。 本文的创新点主要包括如下： 发现了进化算法中的位重要性和位收敛性现象；给出了基于位重要性的基因重排算子的设计方案，提出了分层进化的思想以及建立在该思想基础上的位重要性进化算法；发现了UMDA中的遗传漂移现象，在对漂移特性进行分析的基础上，提出了带平滑滤波器的UMDA；给出了空间熵的概念，以及建立在该概念基础上的UMDA自适应群体规模设定；将概率分布估计算法(EDA)扩展到有噪声优化领域， 给出了噪声环境下EDA的动力学模型，证明了UMDA和EDA在噪声环境下的全局收敛性。