基于关系模型的进化算法收敛性分析与对比

摘要

研究建立了一种等态等价关系与强/弱态偏序关系模型,用于分析进化算法在收敛性上的等价性与可比性.基于吸收态Markov(马尔可夫)性,满足等态关系的进化算法具有等价的收敛性,从而在收敛性意义上实现了进化算法的等价类划分.在等态关系基础上,建立了弱态和强态的偏序关系,提出了一种对比进化算法收敛性的数学工具,在此基础上设计了更为强态的进化算法.文章运用所得理论分析了采用不同变异算子的(1+1)EA算法之间的关系,并用数值实验予以验证.文章提出的关系模型可以作为研究进化算法在收敛性上等价、对比和改进的一种理论基础.%A relation-based model is proposed to analyze the equivalence and ordering of evolutionary algorithm (EA) in convergence. Based on the property of absorbing Markov chain, the EA of the same equivalence-in-status relation has the equal convergence, so that the partition of EAs can be implemented in convergence. According to equivalence-in-status relation, an ordering of stronger/weaker-in-status relation is proposed as a mathematical tool for comparing the convergence of evolutionary algorithm. Furthermore, a stronger EA is given to improve the convergence of EA. The relation of four (1+1)EAs with different mutation is analyzed by the proposed theorems as case studies with a proof of numerical results. The presented model and theorem can be a foundation to study the equivalence, ordering and improvement of evolutionary algorithm.