进化算法收敛性分析的新方法.pdf

进化算法收敛性分析的新方法*) NewMethodfor of ConvergencyAnalysisEvolutionaryAlgorithms 邱玉霞谢刚阎高伟谢克明 (太原理工大学信息工程学院 太原030024) AbstmdThe evolutionisresearchedandthe fimessfunctionandthe fitnesschainarede- population population popu】ation aS fined．Theevolutionaryofthe in is arealnumber processpopulationevolutionaryalgorithmsmapped sequenc色Theper- formanceofthe describesthestatusofthe thechainrrxxtdisusedtO theconvd- sequence evolving population．Then analyze ofsonle lasta of isachieved． gency typicalevolutionaryalgorithms．Atproofglobalastringency fitness KeywotdsEvolutionary c±l￡L访，Convergencyanalysis calculation，Population 数的可行域，厂：卜R1是目标函数。一个全局极小 1 引言 化问题就是要近似地寻找全局最小值f‘一in￡， 近年来随着对相应的进化算法的基本理论、模 (z)，或全局最小值的点z。=argmi∥(2)。 拟进化方法与算法、与其它技术相结合的研究应用 定义1设算法群体规模为N，在k时刻种群 和实验验证，“进化计算”已经作为一个独立的学科 被确立，并在实际运用中表现出很强的大规模信息 体规模心(惫)(i=l，2，…，N)为种群中的个体。适 处理能力。 应度函数为f，惫则定义 进化计算方法具有鲜明的生物基础，但其理论 舟(志)=g({f(ai(是))}) (2) 基础(特别是数学基础)公认是不完善的n一]。这种 k为种群适应值函数，g(·)为泛函。 不完善主要表现在没有完整的理论解释算法的机 定义2设映射^为进化算法的种群适值函 理，缺少广泛而完整的有关算法的收敛性理论。 数，k为进化代数，称序列： 到目前为止，已有不同的方法对进化计算的收 {^(是)}k=0，1，2，… (3) 敛性进行分析，主要是应用Markov过程证明其收 为种群适值链，记为FP。 敛性。本文从种群进化的角度出发，定义了进化计 对于解空间中的点(种群中的个体)，我们最关 算的种群适值函数及种群适值链，并应用该模型对 心的就是它的目标函数值，即它的优化程度，而这种 典型进化算法的全局