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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI '15) |
| Publisher | AAAI Press |
| Publication date | 2015 |
| Pages | 3742-3748 |
| Article number | 3742 |
| ISBN (Print) | 978-1-57735-738-4 |
| Publication status | Published - 2015 |
| Event | 24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015 Conference number: 24 http://ijcai-15.org/ |
Conference
| Conference | 24th International Joint Conference on Artificial Intelligence |
|---|---|
| Number | 24 |
| Country/Territory | Argentina |
| City | Buenos Aires |
| Period | 25/07/2015 → 31/07/2015 |
| Internet address |