More Web Proxy on the site http://driver.im/

Article

On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling

Authors:

Carsten WittAuthors Info & Claims

IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

Pages 3742 - 3748

Published: 25 July 2015 Publication History

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.

References

[1]

Anne Auger and Benjamin Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., 2011.

Digital Library

[2]

Sylvain Colin, Benjamin Doerr, and Gaspard Férey. Monotonic functions in EC: anything but monotone! In Proc. of GECCO '14, pages 753-760. ACM Press, 2014.

Digital Library

[3]

Benjamin Doerr, Daniel Johannsen, and CarolaWinzen. Multiplicative drift analysis. Algorithmica, 64(4):673-697, 2012.

Digital Library

[4]

Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276:51-81, 2002.

Digital Library

[5]

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, and Carsten Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617-633, 2010.

Digital Library

[6]

Jun He and Xin Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57-85, 2001.

Digital Library

[7]

Jun He and Xin Yao. Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artificial Intelligence, 145(1-2):59-97, 2003.

Digital Library

[8]

Christian Horoba. Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. Evolutionary Computation, 18(3):357-381, 2010.

Digital Library

[9]

Thomas Jansen and Christine Zarges. Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problem. In Proc. of GECCO '14, pages 975-982. ACM Press, 2014.

Digital Library

[10]

Thomas Jansen. On the brittleness of evolutionary algorithms. In Proc. of FOGA '07, pages 54-69. ACM Press, 2007.

Digital Library

[11]

Thomas Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013.

Digital Library

[12]

Timo Kötzing and Hendrik Molter. ACO beats EA on a dynamic pseudo-boolean function. In Proc. of PPSN' 12, pages 113-122. Springer, 2012.

Digital Library

[13]

David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009.

[14]

Andrei Lissovoi and Carsten Witt. MMAS versus population-based EA on a family of dynamic fitness functions. Algorithmica, 2015. In press, final version: http://dx.doi.org/10.1007/s00453-015-9975-z.

[15]

Andrei Lissovoi and Carsten Witt. Runtime analysis of ant colony optimization on dynamic shortest path problems. Theoretical Computer Science, 561:73-85, 2015.

Digital Library

[16]

Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[17]

Frank Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European Journal of Operational Research, 181(3):1620-1629, 2007.

[18]

Pietro S. Oliveto and Christine Zarges. Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change. In Proc. of GECCO '13, pages 837-844. ACM Press, 2013.

Digital Library

[19]

Chao Qian, Yang Yu, and Zhi-Hua Zhou. An analysis on recombination in multi-objective evolutionary optimization. Artificial Intelligence, 204:99-119, 2013.

Digital Library

[20]

Philipp Rohlfshagen, Per Kristian Lehre, and Xin Yao. Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change. In Proc. of GECCO '09, pages 1713-1720. ACM Press, 2009.

Digital Library

[21]

Andrew M. Sutton and Frank Neumann. A parameterized runtime analysis of evolutionary algorithms for the Euclidean traveling salesperson problem. In Proc. of AAAI '12, 2012.

[22]

Andrew M. Sutton and Frank Neumann. A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In Proc. of PPSN '12, pages 52-61. Springer, 2012.

Digital Library

[23]

Carsten Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS '05, pages 44-56. Springer, 2005.

Digital Library

[24]

Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing, 22(2):294-318, 2013.

[25]

Yang Yu and Zhi-Hua Zhou. A new approach to estimating the expected first hitting time of evolutionary algorithms. In Proc. of AAAI '06. AIII Press, 2006.

Digital Library

[26]

Yang Yu, Xin Yao, and Zhi-Hua Zhou. On the approximation ability of evolutionary optimization with application to minimum set cover: Extended abstract. In Proc. of IJCAI '13. IJCAI/AAAI, 2013.

Digital Library

Cited By

Bossek JNeumann FPeng PSudholt DCoello Coello C(2020)More effective randomized search heuristics for graph coloring through dynamic optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390174(1277-1285)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390174
Bossek JNeumann FPeng PSudholt DAuger AStützle T(2019)Runtime analysis of randomized search heuristics for dynamic graph coloringProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321792(1443-1451)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321792
Doerr BDoerr CNeumann FAuger AStützle T(2019)Fast re-optimization via structural diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321731(233-241)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321731
Show More Cited By

On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Evolutionary parallel local search for function optimization

This paper proposes a kind of evolutionary parallel local search technique (EPLS) that integrates the reproduction mechanisms from evolutionary algorithms and simplex method. The major aim is to explore the tradeoff between exploration and exploitation ...
Population size versus runtime of a simple evolutionary algorithm

Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often ...
A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling

This paper considers dynamic multi-objective machine scheduling problems in response to continuous arrival of new jobs, under the assumption that jobs can be rejected and job processing time is controllable. The operational cost and the cost of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

July 2015

4429 pages

ISBN:9781577357384

Editors:
Qiang Yang
Hong Kong University of Science and Technology
,
Michael Wooldridge
University of Oxford

Sponsors

The International Joint Conferences on Artificial Intelligence, Inc. (IJCAI)

Publisher

AAAI Press

Publication History

Published: 25 July 2015

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bossek JNeumann FPeng PSudholt DCoello Coello C(2020)More effective randomized search heuristics for graph coloring through dynamic optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390174(1277-1285)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390174
Bossek JNeumann FPeng PSudholt DAuger AStützle T(2019)Runtime analysis of randomized search heuristics for dynamic graph coloringProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321792(1443-1451)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321792
Doerr BDoerr CNeumann FAuger AStützle T(2019)Fast re-optimization via structural diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321731(233-241)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321731
Shi FNeumann FWang JFriedrich TDoerr CArnold D(2019)Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340314(133-146)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340314
Jain PKanesh LMadathil JSaurabh STakadama K(2018)A parameterized runtime analysis of randomized local search and evolutionary algorithm for max l-uncutProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3205749(326-327)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3205749
Shi FNeumann FWang JTakadama K(2018)Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205580(1515-1522)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205580

View Options

View options

Media

Figures

Other

Tables

View Table of Contents