论文部分内容阅读
遗传算法是借助生物界自然选择和遗传学机理而建立的一种迭代全局优化随机搜索算法,是一种求解复杂系统优化问题的通用框架。它不依赖于问题的具体领域,具有简单、通用、较强的自适应性和鲁棒性,以及适于并行处理等显著特点,因此被广泛应用于众多领域。 作为一种仿生算法,遗传算法的应用研究远远领先于算法的基础理论研究。现有的遗传算法的相关理论:修正的模式定理、马氏链收敛分析等在一定程度上奠定了遗传算法的理论基石,促进了理论研究和应用研究的进一步发展。但是,遗传算法的全局收敛性、计算复杂性、算子的运行机理等方面还缺乏严格意义上的数学分析,这已经成为遗传算法发展的瓶颈。 本文对遗传算法的一些基本问题,如算法的编码方式、收敛性、算法参数设置和算子设计等方面,进行了深入的研究分析,提出了一些有效的分析方法。具体包括以下几部分内容: 1.针对各种遗传算法的收敛性,提出了一个统一的收敛准则。在利用马氏链分析了三种典型的遗传算法的收敛性的基础上,通过对比几个证明过程的异同点,提出了一个统一的收敛性判断准则。可以对不同的遗传算法分析其收敛性,而无需考虑GA模型差异,无需烦杂推理和大规模计算,有利于在实际应用中判断遗传算法的敛散性和设计新的遗传算子。 2.遗传算法以决策变量的编码作为运算对象,三种基本的遗传算子的选择和设计都依赖于编码的方式。编码策略是设计遗传算法的一个重要步骤,编码也成为遗传算法应用中的首要问题,因而建立完善的编码方面的理论指导是必要的。通过研究二进制码和格雷码的编码、解码公式,分析了编码差异、个体差异和适应度差异之间的联系,指出了部分文献中的漏误之处,并进一步通过理论分析说明了两种不同编码对遗传算子搜索能力的影响。 3.实践和理论都已经证明,遗传算子所采用的参数会影响算法的搜索效率和收敛速度。本文针对遗传参数缺乏理论指导的问题,采用简单的概率分析方法,从遗传算子的搜索能力的角度出发,分析了变异算子作用机理,得出部分算法参11 浙江大学硕士学位论文数的关联约束。基于得到的关联约束,提出了设置算法参数的应该遵循的部分规则。然后通过对应用实例的分析说明了规则的合理性。 最后,在总结全文的基础上,指出了遗传算法基础理论上有待深入研究的若干问题。