Chen Tianshi, He Jun, Sun Guangzhong, Chen Guoliang, Yao Xin
Department of Computer Science and Technology, Nature Inspired Computation and Applications Laboratory, University of Science and Technology of China, Hefei, China.
IEEE Trans Syst Man Cybern B Cybern. 2009 Oct;39(5):1092-106. doi: 10.1109/TSMCB.2008.2012167. Epub 2009 Mar 24.
In the past decades, many theoretical results related to the time complexity of evolutionary algorithms (EAs) on different problems are obtained. However, there is not any general and easy-to-apply approach designed particularly for population-based EAs on unimodal problems. In this paper, we first generalize the concept of the takeover time to EAs with mutation, then we utilize the generalized takeover time to obtain the mean first hitting time of EAs and, thus, propose a general approach for analyzing EAs on unimodal problems. As examples, we consider the so-called (N + N) EAs and we show that, on two well-known unimodal problems, leadingones and onemax , the EAs with the bitwise mutation and two commonly used selection schemes both need O(n ln n + n(2)/N) and O(n ln ln n + n ln n/N) generations to find the global optimum, respectively. Except for the new results above, our approach can also be applied directly for obtaining results for some population-based EAs on some other unimodal problems. Moreover, we also discuss when the general approach is valid to provide us tight bounds of the mean first hitting times and when our approach should be combined with problem-specific knowledge to get the tight bounds. It is the first time a general idea for analyzing population-based EAs on unimodal problems is discussed theoretically.
在过去几十年里，针对进化算法（EAs）在不同问题上的时间复杂度，已取得了许多理论成果。然而，尚未有专门为基于种群的EAs在单峰问题上设计的通用且易于应用的方法。在本文中，我们首先将接管时间的概念推广到带有变异的EAs，接着利用广义接管时间来获得EAs的平均首次击中时间，从而提出一种分析单峰问题上EAs的通用方法。作为示例，我们考虑所谓的（N + N）EAs，并表明，在两个著名的单峰问题——leadingones和onemax上，采用按位变异和两种常用选择方案的EAs分别需要O(n ln n + n(2)/N)和O(n ln ln n + n ln n/N)代才能找到全局最优解。除了上述新结果外，我们的方法还可直接用于获取基于种群的EAs在其他一些单峰问题上的结果。此外，我们还讨论了通用方法何时有效以给出平均首次击中时间的紧界，以及何时应将我们的方法与特定问题知识相结合以获得紧界。这是首次从理论上讨论分析单峰问题上基于种群的EAs的通用思路。
