On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling

2015/04/23 by Frank Neumann, Neumann, Frank, Carsten Witt +1 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #cs.DS #cs.NE

paper · pdf · doi:10.48550/arxiv.1504.06363

Conference version appears at IJCAI 2015

arxiv created 2015/04/23 · arxiv updated 2015/04/27

Abstract

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.

Cited by

• Runtime Analysis of Evolutionary NAS for Multiclass Classification

Related

• Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem
• Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem
• Oiling the Wheels of Change: The Role of Adaptive Automatic Problem Decomposition in Non--Stationary Environments
• Genetic Algorithm enhanced by Deep Reinforcement Learning in parent selection mechanism and mutation : Minimizing makespan in permutation flow shop scheduling problems
• Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms