遗传算法的模式理论及收敛理论

遗传算法的已有研究主要集中于设计新的算法，或改进已有算法及应用已有算法去解决实际问题。而相关基础理论的研究相对滞后，研究成果也相对较少，其中模式理论和算法的收敛理论是两个核心的理论问题。本文主要针对这两个核心的理论问题进行了研究，主要创新成果如下： 1．深入研究了单点杂交的模式理论。对于单点杂交算子，目前的模式理论主要研究它对模式存活的影响。只有极少数文献研究了它对模式的新建(指在杂交算子作用下模式从无到有)的影响，但这些研究结果还存在一些严重缺陷，如不能区分开它对模式的存活和新建的各自影响。为了能分别研究杂交算子对模式存活和新建的影响。本文提出一种三进制表示法，利用这种表示法能完全区分模式的存活情况和新建情况，从而既可以分别研究杂交算子对模式的存活和新建能力的影响。又可研究在存活和新建共同作用下单点杂交对模式的影响。这是已有研究所没有的。 2．研究了均匀杂交的模式理论。目前广泛使用的杂交算子有很多种，其中均匀杂交算子是最常使用的杂交方式之一。基于三进制表示法，深入研究了均匀杂交对模式的存活能力和新建能力的影响，然后研究了在存活和新建共同作用下均匀杂交对模式的影响。并且，比较了单点杂交和均匀杂交对模式的存活和新建的影响。 3．将前述的研究结果推广到任意杂交算子中去，研究了任意杂交算子的模式理论。 4．建立了一类遗传算法的模型，该类算法包含常用的经典遗传算法在内的许多算法，利用Markov链模型，证明了该类算法的全局收敛性，并估计了该类遗传算法的收敛速度。讨论收敛速度的方法与已有的方法不同，而且较于其他收敛速度的结果，本文的结果具有更强的实用性。 5．研究了一类不使用精英保留策略的遗传算法的收敛速度。利用Markov链一个特殊的minorization条件，讨论了该类遗传算法的收敛速度。它推广了已有的结论。