Zhang Yushan, Hu Guiwu
School of Mathematics and Statistics, Guangdong University of Finance and Economics, Guangzhou 510320, China.
Comput Intell Neurosci. 2015;2015:485215. doi: 10.1155/2015/485215. Epub 2015 Aug 12.
Although there have been many studies on the runtime of evolutionary algorithms in discrete optimization, relatively few theoretical results have been proposed on continuous optimization, such as evolutionary programming (EP). This paper proposes an analysis of the runtime of two EP algorithms based on Gaussian and Cauchy mutations, using an absorbing Markov chain. Given a constant variation, we calculate the runtime upper bound of special Gaussian mutation EP and Cauchy mutation EP. Our analysis reveals that the upper bounds are impacted by individual number, problem dimension number n, searching range, and the Lebesgue measure of the optimal neighborhood. Furthermore, we provide conditions whereby the average runtime of the considered EP can be no more than a polynomial of n. The condition is that the Lebesgue measure of the optimal neighborhood is larger than a combinatorial calculation of an exponential and the given polynomial of n.
尽管在离散优化中已经有许多关于进化算法运行时间的研究，但在连续优化方面，如进化规划（EP），相对较少有理论成果被提出。本文使用吸收马尔可夫链对基于高斯变异和柯西变异的两种进化规划算法的运行时间进行了分析。给定一个恒定的变异，我们计算了特殊高斯变异进化规划和柯西变异进化规划的运行时间上界。我们的分析表明，这些上界受到个体数量、问题维度数(n)、搜索范围以及最优邻域的勒贝格测度的影响。此外，我们给出了所考虑的进化规划的平均运行时间不超过(n)的多项式的条件。该条件是最优邻域的勒贝格测度大于一个指数的组合计算结果与给定的(n)的多项式的乘积。
