Improved time complexity analysis of the Simple Genetic Algorithm
Improved time complexity analysis of the Simple Genetic Algorithm
复制标题
DOI：
10.1016/j.tcs.2015.01.002
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
P. S. Oliveto;C. Witt
中科院分区：
文献类型：
--
作者：
P. S. Oliveto;C. Witt
本文对求解OneMax问题的简单遗传算法（Simple Genetic Algorithm， SGA）进行了运行时分析，证明了当种群大小为μ≤n 1/8−ε时，该算法所需的时间具有压倒性的指数概率。本文提出了一种改进的分析方法，克服了以前的分析方法的一些局限性。首先，新结果适用于种群大小为μ≤n 1/4−ε的情况，这是一个2倍的改进。其次，我们提出了一种不需要带宽约束的种群多样性约束技术。除了允许更强的结果之外，我们相信这是对未来GAs系统分析中技术可重用性的重大改进。最后，我们考虑使用带替换的选择而不是不替换的更自然的SGA，尽管结果适用于两种算法版本。实验提出了探索新的和以前的数学技术的局限性。
A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤ n 1/8− ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤ n 1/4− ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.