Campus Event Calendar
Event Entry
What and Who
On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling
Prof. Frank Neumann
University of Adelaide
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 15 May 2015
13:00
30 Minutes
E1 4
024
Saarbrücken
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
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.
Joint work with Carsten Witt
To appear at IJCAI 2015
Contact
Christina Fries
--email hidden
passcode not visible
logged in users only
Christina Fries, 04/21/2015 10:30 -- Created document.