差分进化算法马尔可夫链模型及收敛性分析

Analysis of Differential Evolution's Markov Chain Model and Convergence

差分进化算法是一种基于种群差异的优化算法,主要应用于解决连续空间的优化问题。目前,研究人员主要在算法的改进和应用方面研究差分进化算法,很少从理论角度对其进行研究。为了分析差分进化算法的收敛性,定义优化个体、种群的状态转移,并提出种群的最优状态集合。根据差分进化算法的操作算子计算出个体的状态迁移概率,并证明种群状态序列是有限齐次马尔可夫链,进而建立差分进化算法的马尔可夫链模型;最后,证明差分进化算法无法保证全局收敛。理论研究结果表明,适当保证种群的多样性能够提高差分进化算法的性能。

As a modern optimization algorithm, differential evolution algorithm which is based on the individual differential reconstruction idea is designed for the global continuous optimization problem. Up to now ,the improvement and application of the algorithm are mainly focused by researchers but theoretical analysis of the algorithm is seldom taken into account. In order to analyze the convergence of the al- gorithm, the concepts of state transition for individual and population are defined and the optimal state set of population is proposed. The individual state transition probability is computed according to the operators of differential evolution algorithm. The state sequence of pop- ulation has been proved to be Finite Nonhomogeneous Markov chain and the Markov chain model of differential evolution is proposed. At last,the theory analysis of the differential evolution demonstrates that it is not able to guarantee the global convergence. The result of the theory research shows that keeping the population diversity will improve the performance of the algorithm.