---
_id: '48843'
abstract:
- lang: eng
text: We contribute to the theoretical understanding of randomized search heuristics
for dynamic problems. We consider the classical graph coloring problem and investigate
the dynamic setting where edges are added to the current graph. We then analyze
the expected time for randomized search heuristics to recompute high quality solutions.
This includes the (1+1) EA and RLS in a setting where the number of colors is
bounded and we are minimizing the number of conflicts as well as iterated local
search algorithms that use an unbounded color palette and aim to use the smallest
colors and - as a consequence - the smallest number of colors. We identify classes
of bipartite graphs where reoptimization is as hard as or even harder than optimization
from scratch, i. e. starting with a random initialization. Even adding a single
edge can lead to hard symmetry problems. However, graph classes that are hard
for one algorithm turn out to be easy for others. In most cases our bounds show
that reoptimization is faster than optimizing from scratch. Furthermore, we show
how to speed up computations by using problem specific operators concentrating
on parts of the graph where changes have occurred.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
- first_name: Pan
full_name: Peng, Pan
last_name: Peng
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
citation:
ama: 'Bossek J, Neumann F, Peng P, Sudholt D. Runtime Analysis of Randomized Search
Heuristics for Dynamic Graph Coloring. In: Proceedings of the Genetic and Evolutionary
Computation Conference. GECCO ’19. Association for Computing Machinery; 2019:1443–1451.
doi:10.1145/3321707.3321792'
apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2019). Runtime Analysis
of Randomized Search Heuristics for Dynamic Graph Coloring. Proceedings of
the Genetic and Evolutionary Computation Conference, 1443–1451. https://doi.org/10.1145/3321707.3321792
bibtex: '@inproceedings{Bossek_Neumann_Peng_Sudholt_2019, place={New York, NY, USA},
series={GECCO ’19}, title={Runtime Analysis of Randomized Search Heuristics for
Dynamic Graph Coloring}, DOI={10.1145/3321707.3321792},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank and Peng, Pan and Sudholt, Dirk}, year={2019}, pages={1443–1451}, collection={GECCO
’19} }'
chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Runtime Analysis
of Randomized Search Heuristics for Dynamic Graph Coloring.” In Proceedings
of the Genetic and Evolutionary Computation Conference, 1443–1451. GECCO ’19.
New York, NY, USA: Association for Computing Machinery, 2019. https://doi.org/10.1145/3321707.3321792.'
ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Runtime Analysis of Randomized
Search Heuristics for Dynamic Graph Coloring,” in Proceedings of the Genetic
and Evolutionary Computation Conference, 2019, pp. 1443–1451, doi: 10.1145/3321707.3321792.'
mla: Bossek, Jakob, et al. “Runtime Analysis of Randomized Search Heuristics for
Dynamic Graph Coloring.” Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, 2019, pp. 1443–1451, doi:10.1145/3321707.3321792.
short: 'J. Bossek, F. Neumann, P. Peng, D. Sudholt, in: Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2019, pp. 1443–1451.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:42:37Z
department:
- _id: '819'
doi: 10.1145/3321707.3321792
extern: '1'
keyword:
- dynamic optimization
- evolutionary algorithms
- running time analysis
- theory
language:
- iso: eng
page: 1443–1451
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-6111-8
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’19
status: public
title: Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring
type: conference
user_id: '102979'
year: '2019'
...
---
_id: '48840'
abstract:
- lang: eng
text: Research has shown that for many single-objective graph problems where optimum
solutions are composed of low weight sub-graphs, such as the minimum spanning
tree problem (MST), mutation operators favoring low weight edges show superior
performance. Intuitively, similar observations should hold for multi-criteria
variants of such problems. In this work, we focus on the multi-criteria MST problem.
A thorough experimental study is conducted where we estimate the probability of
edges being part of non-dominated spanning trees as a function of the edges’ non-domination
level or domination count, respectively. Building on gained insights, we propose
several biased one-edge-exchange mutation operators that differ in the used edge-selection
probability distribution (biased towards edges of low rank). Our empirical analysis
shows that among different graph types (dense and sparse) and edge weight types
(both uniformly random and combinations of Euclidean and uniformly random) biased
edge-selection strategies perform superior in contrast to the baseline uniform
edge-selection. Our findings are in particular strong for dense graphs.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Christian
full_name: Grimme, Christian
last_name: Grimme
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Grimme C, Neumann F. On the Benefits of Biased Edge-Exchange Mutation
for the Multi-Criteria Spanning Tree Problem. In: Proceedings of the Genetic
and Evolutionary Computation Conference. GECCO ’19. Association for Computing
Machinery; 2019:516–523. doi:10.1145/3321707.3321818'
apa: Bossek, J., Grimme, C., & Neumann, F. (2019). On the Benefits of Biased
Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem. Proceedings
of the Genetic and Evolutionary Computation Conference, 516–523. https://doi.org/10.1145/3321707.3321818
bibtex: '@inproceedings{Bossek_Grimme_Neumann_2019, place={New York, NY, USA}, series={GECCO
’19}, title={On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria
Spanning Tree Problem}, DOI={10.1145/3321707.3321818},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme,
Christian and Neumann, Frank}, year={2019}, pages={516–523}, collection={GECCO
’19} }'
chicago: 'Bossek, Jakob, Christian Grimme, and Frank Neumann. “On the Benefits of
Biased Edge-Exchange Mutation for the Multi-Criteria Spanning Tree Problem.” In
Proceedings of the Genetic and Evolutionary Computation Conference, 516–523.
GECCO ’19. New York, NY, USA: Association for Computing Machinery, 2019. https://doi.org/10.1145/3321707.3321818.'
ieee: 'J. Bossek, C. Grimme, and F. Neumann, “On the Benefits of Biased Edge-Exchange
Mutation for the Multi-Criteria Spanning Tree Problem,” in Proceedings of the
Genetic and Evolutionary Computation Conference, 2019, pp. 516–523, doi: 10.1145/3321707.3321818.'
mla: Bossek, Jakob, et al. “On the Benefits of Biased Edge-Exchange Mutation for
the Multi-Criteria Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2019, pp. 516–523,
doi:10.1145/3321707.3321818.
short: 'J. Bossek, C. Grimme, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2019, pp. 516–523.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:42:24Z
department:
- _id: '819'
doi: 10.1145/3321707.3321818
extern: '1'
keyword:
- biased mutation
- combinatorial optimization
- minimum spanning tree
- multi-objective optimization
language:
- iso: eng
page: 516–523
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-6111-8
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’19
status: public
title: On the Benefits of Biased Edge-Exchange Mutation for the Multi-Criteria Spanning
Tree Problem
type: conference
user_id: '102979'
year: '2019'
...