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

Convergence Analysis and Comparison of Evolutionary Algorithms Based on Relation Model

研究建立了一种等态等价关系与强/弱态偏序关系模型,用于分析进化算法在收敛性上的等价性与可比性.基于吸收态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.