论文部分内容阅读
演化算法是受自然演化机制启发而提出的一大类随机优化算法的总称。它将复杂的处理对象转化为各种编码、基于自然界的群体策略搜索、模拟自然法则产生新个体、以迭代方式优化无特别严格条件的适应值函数来达到求解问题的目的。演化算法尤其适合于传统搜索方法难以解决的高复杂度的非线性问题,受到许多领域的广泛而持久的关注。它以遗传算法为早期代表,经过几十年的蓬勃发展,新的演化算法分支和变种不断涌现,最终形成人工智能领域的一个重要分支-演化计算。关于演化算法的绝大部分成果立足于模拟实验和实际应用,总体来看,演化计算更像是一门实验科学。即便如此,我们现在离使用演化算法中所有潜在的有用的演化特性也还相差甚远。究其原因,现有的结论并没有完满解决演化算法的基本理论问题。为了更好地理解它们复杂的随机行为从而开发更多的潜能,有必要进一步研究其理论基础。本文运用随机稳定性理论和非负矩阵理论(主要是谱分析)探讨各类演化算法的渐近行为,紧紧围绕收敛性、收敛速度和计算时间复杂性这三个基本主题展开研究,通过提升现有理论成果、刻画各主题内部和主题间的联系,试图为基于有限马氏链描述的演化算法的一般性理论分析框架的建立作出贡献。本文既关注针对各类演化算法的定性结论并以此提供分析的主线,也关注结论的实际意义因而辅以若干案例验证说明。具体地,本文的主要贡献包括下面几个方面。(1)探讨各类演化算法满足不同强度收敛性的条件。本文依据演化算法所伴随的Markov链的表现形式将其归结为几大类:时齐(非时变)/非时齐(时变)与强精英/渐近可约(主要是渐近强精英)。针对时齐的强精英演化算法,以简单的过程证明了非时变算法以概率1在有限步内收敛、完全收敛至全局最优,同时给出了比以往相关文献更弱的、一般性的、意义更明确的充分条件,并进一步将其推广至时变的情形。针对渐近可约的演化算法,借助非负矩阵理论提出了两类全局收敛的条件,并通过对模拟退火遗传算法、带变量删除因子的稳态演化算法等的分析加以验证。(2)基于两类衡量准则刻画演化算法的收敛速度。首先,本文在特殊的距离度量下建立了衡量方式之间的联系。然后,对于强精英演化算法,基于谱分析分别利用转移矩阵的两个特征值刻画两准则下的收敛速度。其中,我们既推广了已有的结论至具有多个非周期正常返类的演化算法:转移矩阵幂的收敛速度由修正谱半径决定,也证明了:未发现最优的概率趋于零的速度由非最优状态对应的矩阵分块的谱半径决定。进一步地,通过分析转移矩阵的谱,我们发现这两个特征值间存在着与衡量方式间一致的关系。与相关文献相比,本文关于收敛速度的讨论是对以往结论的细化和较大提升。(3)精确刻画强精英演化算法的收敛速度与首达时间之间的计算关系。以未发现最优的概率趋于零的速度为衡量准则,通过建立该概率的表达式,结合首达最优的时间和平均计算时间的表达式,发现它们都系在转移矩阵的同一个矩阵分块上,从而精确刻画了它们的表达式关系。该关系是下述已有结论的本质刻画:首达最优的时间这一随机变量以未发现最优的概率为概率分布。基于此关系,本文还以简单的方式为平均计算时间提供意义更为明确的上下界,并辅以案例验证其实用性。相关结论同时适用于非时变与时变的精英演化算法。(4)针对多峰适应值函数,研究精英保留演化算法的收敛性质。多解优化问题和非正则的编码均会导出多峰适应值函数,然而人们通常假定适应值函数只有一个最优解甚至为单值的。在更具一般性的假定下,本文通过分析精英记录策略的两种具体实施所对应的不同更新矩阵,应用非时变强精英演化算法的相关结论获得了精英保留演化算法的收敛性与收敛速度,并粗略估计相关特征值,进一步完善了对精英保留演化算法的研究。这其中,我们得到两个在形式上大相径庭的更新矩阵,它们都异于以往在单值函数假设下所得的布尔矩阵,但是,算法在收敛性态上却具有与以往相似的性质。作为理论结论的应用,以基因表达式编程算法为例具体分析了一类精英保留演化算法的收敛性质。针对其非正则编码所致的多峰适应值函数,通过深入分析各算子的性质,重新刻画了精英保留基因表达式编程算法的数学模型,探讨了在不同的精英策略实施方式下该算法的收敛性质以及收敛速度与算法参数之间的关系,从而进一步完善了已有的结论。