First Steps Towards a Runtime Analysis When Starting With a Good Solution
Denis Antipov, Maxim Buzdalov, Benjamin Doerr
进化算法的数学运行时分析传统上认为算法在随机种群初始化时需要找到一定质量的解决方案的时间。 在实际应用中,可以猜测比随机解决方案更好的解决方案。 我们针对此类情况开始数学运行时分析。 我们观察到不同的算法从更好的初始化到非常不同的程度。 我们还表明,算法的最佳参数化可以强烈依赖于初始解决方案的质量。 为了克服这个困难,自我调整和随机的重尾参数选择可以有利可图。 最后,我们观察到我们发现的最佳进化算法的性能与相应的黑箱复杂性之间存在更大的差距。 这可能表明,更好地利用良好的初始解决方案的进化算法仍有待找到。 这些第一个发现源于分析OneMax基准上(1+1)进化算法和静态,自我调整和重尾(1 +(λ,λ))GA的性能。 我们乐观地认为,除了这些第一个例子之外,如何从良好的初始解决方案中获利的问题很有趣。
The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterizatio...
