王 辉 徐晓英
(武汉理工大学理学院 武汉 430070)
作为一类模拟进化计算方法,遗传算法的基本框架、构成要素及操作策略已经形成,其搜索机理及收敛性理论也得到了深入的探索研究.目前,关于遗传算法的基础理论,较为完善的有Schema理论、遗传算法的马氏链分析及遗传算法的收敛理论[1].
与收敛理论紧密相关的另一基本理论问题是遗传算法的收敛速度该如何表达.针对这一基本问题,文献[2]中Aytug和Koehlen利用马氏链中的首次访问时间概念,估计出遗传算法在一定的置信水平下访问到所有种群状态所需要的进化代数;文献[3]从转移矩阵的第二大特征值出发研究了标准遗传算法的停时准则;文献[4]中基于鞅理论研究了保留精英策略遗传算法的收敛速度,并给出了最大收敛代数的估算公式.
从目前多种估算方式和判断准则的研究中可以发现:(1)在判断遗传算法是否达到最优解时很少甚至并未考虑前代的信息,过于拘泥于概率意义上的计算;(2)在推导遗传算法最大收敛代数的估算公式中利用到全局最优解或最优解域的信息,而如何判断种群已达到最优解并未给出.
本文从遗传算法收敛性的定义出发,分析遗传算法的收敛特点,利用不同种群中最优个体适应值的一致性、种群的多样性分布,提出判断算法自动停止迭代的方法.为建立合适的停机准则及统一的遗传算法收敛速度度量方法提供参考.
设S为个体空间,SN为种群空间,P为SN上的概率分布,{(n)}是遗传算法所生成的第n代种群序列,f:s→R+为适应值函数,记全体最优解集为M={X;……