First hitting time analysis of continuous evolutionary algorithms based on average gain
First hitting time analysis of continuous evolutionary algorithms based on average gain
复制标题
基于平均增益的连续进化算法首次命中时间分析
DOI：
10.1007/s10586-016-0587-4
复制
发表时间：
2016
影响因子：
4.4
通讯作者：
Hu Guiwu
中科院分区：
文献类型：
--
作者：
Zhang Yushan;Huang Han;Hao Zhifeng;Hu Guiwu
连续进化算法的性能分析是进化计算理论研究中的一个难点，相对于离散进化算法，目前的研究成果相对较少。本文引入鞅和停时理论，建立了一个一般平均增益模型来估计期望首中时间的上界。该模型建立在非负随机过程的基础上，不需要马尔可夫性假设，具有更强的一般性。之后，我们演示了如何提出的模型可以应用于连续EA的运行时分析。最后，作为一个案例研究，我们分析了使用所提出的方法在球函数上的自适应步长的ES的运行时间，并推导出了一个封闭的形式的时间上界的三维情况下。为了保证算法的收敛性，我们还讨论了步长和后代数之间的关系.实验结果表明，该方法有助于得到连续进化算法的期望首中时间的严格上界。
Runtime analysis of continuous evolutionary algorithms (EAs) is a hard topic in the theoretical research of evolutionary computation, relatively few results have been obtained compared to the discrete EAs. In this paper, we introduce the martingale and stopping time theory to establish a general average gain model to estimate the upper bound for theexpected first hitting time. The proposed model is established on a non-negative stochastic process and does not need the assumption of Markov property, thus is more general. Afterwards, we demonstrate how the proposed model can be applied to runtime analysis of continuous EAs. In the end, as a case study, we analyze the runtime of (1,ES with adaptive step-size on Sphere function using the proposed approach, and derive a closed-form expression of the time upper bound for 3-dimensional case. We also discuss the relationship between the step size and the offspring sizeto ensure convergence. The experimental results show that the proposed approach helps to derive tight upper bound for theexpected first hitting timeof continuous EAs.