On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
复制标题
DOI：
--
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
F. Neumann;C. Witt
中科院分区：
文献类型：
--
作者：
F. Neumann;C. Witt
进化算法经常用于动态优化问题。通过本文，我们对这一研究领域的理论认识有所贡献。本文首次对经典组合优化问题的动态变体即最大完工时间调度的进化算法进行了计算复杂度分析。我们研究了一个强对手的模型，它被允许每隔一定的时间间隔换一个工作。此外，我们还研究了随机变化的设置。我们的结果表明，随机局部搜索和一个简单的进化算法在动态跟踪问题实例的变化方面非常有效。
Evolutionary algorithms have been frequently used for dynamic optimization problems. With this paper, we contribute to the theoretical understanding of this research area. We present the first computational complexity analysis of evolutionary algorithms for a dynamic variant of a classical combinatorial optimization problem, namely makespan scheduling. We study the model of a strong adversary which is allowed to change one job at regular intervals. Furthermore, we investigate the setting of random changes. Our results show that randomized local search and a simple evolutionary algorithm are very effective in dynamically tracking changes made to the problem instance.