噪声环境下遗传算法的收敛性和收敛速度估计

An Analysis on Convergence and Convergence Rate Estimate of Genetic Algorithms in Noisy Environments

问题求解的环境往往非常复杂,不确定的环境因素、人为因素等都可导致问题处于噪声环境,从而影响实际优化问题的目标函数值的评价.噪声环境下遗传算法的研究在国内外均起步较晚,特别是收敛性和收敛速度的分析是该领域急待解决的问题.本文根据优胜劣汰遗传算法的特性,基于吸收态Markov链的数学模型证明了噪声环境下优胜劣汰遗传算法的收敛性,提出了噪声环境下优胜劣汰遗传算法的首达最优解期望时间的估算方法.

Random noise perturbs objective functions in many practical problems,and genetic algorithms（GAs） have been widely proposed as an effective optimization tool for dealing with noisy objective functions.However,there are few theoretical studies for the convergence and the convergence speed of genetic algorithms in noisy environments（GA-NE）.In this study,Objective functions are assumed to be perturbed by additive random noise.We construct a Markov chain that models elitist-worst genetic algorithms in noisy environments（EWGA-NE）.Then the convergence of EWGA-NE is deduced based on the absorbing state Markov chain.Next,the convergence rate of EWGA-NE was studied.The upper and lower bounds for the number of iterations that EWGA-NE selects a globally optimal solution were derived.