---
_id: '63053'
author:
- first_name: Carlos
full_name: Hernández, Carlos
last_name: Hernández
- first_name: Angel E.
full_name: Rodriguez-Fernandez, Angel E.
last_name: Rodriguez-Fernandez
- first_name: Lennart
full_name: Schäpermeier, Lennart
last_name: Schäpermeier
- first_name: Oliver
full_name: Cuate, Oliver
last_name: Cuate
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
- first_name: Oliver
full_name: Schütze, Oliver
last_name: Schütze
citation:
ama: Hernández C, Rodriguez-Fernandez AE, Schäpermeier L, Cuate O, Trautmann H,
Schütze O. An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization. IEEE Transactions on Evolutionary
Computation. Published online 2025:1-1. doi:10.1109/TEVC.2025.3637276
apa: Hernández, C., Rodriguez-Fernandez, A. E., Schäpermeier, L., Cuate, O., Trautmann,
H., & Schütze, O. (2025). An Evolutionary Approach for the Computation of
∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization. IEEE
Transactions on Evolutionary Computation, 1–1. https://doi.org/10.1109/TEVC.2025.3637276
bibtex: '@article{Hernández_Rodriguez-Fernandez_Schäpermeier_Cuate_Trautmann_Schütze_2025,
title={An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization}, DOI={10.1109/TEVC.2025.3637276},
journal={IEEE Transactions on Evolutionary Computation}, author={Hernández, Carlos
and Rodriguez-Fernandez, Angel E. and Schäpermeier, Lennart and Cuate, Oliver
and Trautmann, Heike and Schütze, Oliver}, year={2025}, pages={1–1} }'
chicago: Hernández, Carlos, Angel E. Rodriguez-Fernandez, Lennart Schäpermeier,
Oliver Cuate, Heike Trautmann, and Oliver Schütze. “An Evolutionary Approach for
the Computation of ∈-Locally Optimal Solutions for Multi-Objective Multimodal
Optimization.” IEEE Transactions on Evolutionary Computation, 2025, 1–1.
https://doi.org/10.1109/TEVC.2025.3637276.
ieee: 'C. Hernández, A. E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann,
and O. Schütze, “An Evolutionary Approach for the Computation of ∈-Locally Optimal
Solutions for Multi-Objective Multimodal Optimization,” IEEE Transactions on
Evolutionary Computation, pp. 1–1, 2025, doi: 10.1109/TEVC.2025.3637276.'
mla: Hernández, Carlos, et al. “An Evolutionary Approach for the Computation of
∈-Locally Optimal Solutions for Multi-Objective Multimodal Optimization.” IEEE
Transactions on Evolutionary Computation, 2025, pp. 1–1, doi:10.1109/TEVC.2025.3637276.
short: C. Hernández, A.E. Rodriguez-Fernandez, L. Schäpermeier, O. Cuate, H. Trautmann,
O. Schütze, IEEE Transactions on Evolutionary Computation (2025) 1–1.
date_created: 2025-12-12T06:13:06Z
date_updated: 2025-12-12T06:13:51Z
department:
- _id: '819'
doi: 10.1109/TEVC.2025.3637276
keyword:
- Optimization
- Evolutionary computation
- Hands
- Proposals
- Convergence
- Computational efficiency
- Artificial intelligence
- Accuracy
- Approximation algorithms
- Aerospace electronics
- Multi-objective optimization
- evolutionary algorithms
- nearly optimal solutions
- multimodal optimization
- archiving
- continuation
language:
- iso: eng
page: 1-1
publication: IEEE Transactions on Evolutionary Computation
status: public
title: An Evolutionary Approach for the Computation of ∈-Locally Optimal Solutions
for Multi-Objective Multimodal Optimization
type: journal_article
user_id: '15504'
year: '2025'
...
---
_id: '48869'
abstract:
- lang: eng
text: Evolutionary algorithms have been shown to obtain good solutions for complex
optimization problems in static and dynamic environments. It is important to understand
the behaviour of evolutionary algorithms for complex optimization problems that
also involve dynamic and/or stochastic components in a systematic way in order
to further increase their applicability to real-world problems. We investigate
the node weighted traveling salesperson problem (W-TSP), which provides an abstraction
of a wide range of weighted TSP problems, in dynamic settings. In the dynamic
setting of the problem, items that have to be collected as part of a TSP tour
change over time. We first present a dynamic setup for the dynamic W-TSP parameterized
by different types of changes that are applied to the set of items to be collected
when traversing the tour. Our first experimental investigations study the impact
of such changes on resulting optimized tours in order to provide structural insights
of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary
algorithms and study the impact of the mutation operators and the use of populations
with dealing with the dynamic changes to the node weights of the problem.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. On the Impact of Basic Mutation Operators
and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling
Salesperson Problem. In: Proceedings of the Genetic and Evolutionary Computation
Conference. GECCO’23. Association for Computing Machinery; 2023:248–256. doi:10.1145/3583131.3590384'
apa: Bossek, J., Neumann, A., & Neumann, F. (2023). On the Impact of Basic Mutation
Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted
Traveling Salesperson Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 248–256. https://doi.org/10.1145/3583131.3590384
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2023, place={New York, NY, USA},
series={GECCO’23}, title={On the Impact of Basic Mutation Operators and Populations
within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson
Problem}, DOI={10.1145/3583131.3590384},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Aneta and Neumann, Frank}, year={2023}, pages={248–256}, collection={GECCO’23}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “On the Impact of Basic
Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic
Weighted Traveling Salesperson Problem.” In Proceedings of the Genetic and
Evolutionary Computation Conference, 248–256. GECCO’23. New York, NY, USA:
Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590384.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “On the Impact of Basic Mutation Operators
and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling
Salesperson Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2023, pp. 248–256, doi: 10.1145/3583131.3590384.'
mla: Bossek, Jakob, et al. “On the Impact of Basic Mutation Operators and Populations
within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson
Problem.” Proceedings of the Genetic and Evolutionary Computation Conference,
Association for Computing Machinery, 2023, pp. 248–256, doi:10.1145/3583131.3590384.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2023, pp. 248–256.'
date_created: 2023-11-14T15:58:56Z
date_updated: 2023-12-13T10:46:27Z
department:
- _id: '819'
doi: 10.1145/3583131.3590384
extern: '1'
keyword:
- dynamic optimization
- evolutionary algorithms
- re-optimization
- weighted traveling salesperson problem
language:
- iso: eng
page: 248–256
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- '9798400701191'
publisher: Association for Computing Machinery
series_title: GECCO’23
status: public
title: On the Impact of Basic Mutation Operators and Populations within Evolutionary
Algorithms for the Dynamic Weighted Traveling Salesperson Problem
type: conference
user_id: '102979'
year: '2023'
...
---
_id: '48871'
abstract:
- lang: eng
text: 'Most runtime analyses of randomised search heuristics focus on the expected
number of function evaluations to find a unique global optimum. We ask a fundamental
question: if additional search points are declared optimal, or declared as desirable
target points, do these additional optima speed up evolutionary algorithms? More
formally, we analyse the expected hitting time of a target set OPT{$\cup$}S where
S is a set of non-optimal search points and OPT is the set of optima and compare
it to the expected hitting time of OPT. We show that the answer to our question
depends on the number and placement of search points in S. For all black-box algorithms
and all fitness functions with polynomial expected optimisation times we show
that, if additional optima are placed randomly, even an exponential number of
optima has a negligible effect on the expected optimisation time. Considering
Hamming balls around all global optima gives an easier target for some algorithms
and functions and can shift the phase transition with respect to offspring population
sizes in the (1,{$\lambda$}) EA on OneMax. However, for the one-dimensional Ising
model the time to reach Hamming balls of radius (1/2-{$ϵ$})n around optima does
not reduce the asymptotic expected optimisation time in the worst case. Finally,
on functions where search trajectories typically join in a single search point,
turning one search point into an optimum drastically reduces the expected optimisation
time.'
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
citation:
ama: Bossek J, Sudholt D. Do Additional Target Points Speed Up Evolutionary Algorithms?
Theoretical Computer Science. Published online 2023:113757. doi:10.1016/j.tcs.2023.113757
apa: Bossek, J., & Sudholt, D. (2023). Do Additional Target Points Speed Up
Evolutionary Algorithms? Theoretical Computer Science, 113757. https://doi.org/10.1016/j.tcs.2023.113757
bibtex: '@article{Bossek_Sudholt_2023, title={Do Additional Target Points Speed
Up Evolutionary Algorithms?}, DOI={10.1016/j.tcs.2023.113757},
journal={Theoretical Computer Science}, author={Bossek, Jakob and Sudholt, Dirk},
year={2023}, pages={113757} }'
chicago: Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up
Evolutionary Algorithms?” Theoretical Computer Science, 2023, 113757. https://doi.org/10.1016/j.tcs.2023.113757.
ieee: 'J. Bossek and D. Sudholt, “Do Additional Target Points Speed Up Evolutionary
Algorithms?,” Theoretical Computer Science, p. 113757, 2023, doi: 10.1016/j.tcs.2023.113757.'
mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Target Points Speed Up Evolutionary
Algorithms?” Theoretical Computer Science, 2023, p. 113757, doi:10.1016/j.tcs.2023.113757.
short: J. Bossek, D. Sudholt, Theoretical Computer Science (2023) 113757.
date_created: 2023-11-14T15:58:56Z
date_updated: 2023-12-13T10:51:07Z
department:
- _id: '819'
doi: 10.1016/j.tcs.2023.113757
keyword:
- Evolutionary algorithms
- pseudo-Boolean functions
- runtime analysis
language:
- iso: eng
page: '113757'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
status: public
title: Do Additional Target Points Speed Up Evolutionary Algorithms?
type: journal_article
user_id: '102979'
year: '2023'
...
---
_id: '48894'
abstract:
- lang: eng
text: Recently different evolutionary computation approaches have been developed
that generate sets of high quality diverse solutions for a given optimisation
problem. Many studies have considered diversity 1) as a mean to explore niches
in behavioural space (quality diversity) or 2) to increase the structural differences
of solutions (evolutionary diversity optimisation). In this study, we introduce
a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component
traveling thief problem. The results show the capability of the co-evolutionary
algorithm to achieve significantly higher diversity compared to the baseline evolutionary
diversity algorithms from the literature.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- 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
citation:
ama: 'Nikfarjam A, Neumann A, Bossek J, Neumann F. Co-Evolutionary Diversity Optimisation
for the Traveling Thief Problem. In: Rudolph G, Kononova AV, Aguirre H, Kerschke
P, Ochoa G, Tu\v sar T, eds. Parallel Problem Solving from Nature (PPSN XVII).
Lecture Notes in Computer Science. Springer International Publishing; 2022:237–249.
doi:10.1007/978-3-031-14714-2_17'
apa: Nikfarjam, A., Neumann, A., Bossek, J., & Neumann, F. (2022). Co-Evolutionary
Diversity Optimisation for the Traveling Thief Problem. In G. Rudolph, A. V. Kononova,
H. Aguirre, P. Kerschke, G. Ochoa, & T. Tu\v sar (Eds.), Parallel Problem
Solving from Nature (PPSN XVII) (pp. 237–249). Springer International Publishing.
https://doi.org/10.1007/978-3-031-14714-2_17
bibtex: '@inproceedings{Nikfarjam_Neumann_Bossek_Neumann_2022, place={Cham}, series={Lecture
Notes in Computer Science}, title={Co-Evolutionary Diversity Optimisation for
the Traveling Thief Problem}, DOI={10.1007/978-3-031-14714-2_17},
booktitle={Parallel Problem Solving from Nature (PPSN XVII)}, publisher={Springer
International Publishing}, author={Nikfarjam, Adel and Neumann, Aneta and Bossek,
Jakob and Neumann, Frank}, editor={Rudolph, Günter and Kononova, Anna V. and Aguirre,
Hernán and Kerschke, Pascal and Ochoa, Gabriela and Tu\v sar, Tea}, year={2022},
pages={237–249}, collection={Lecture Notes in Computer Science} }'
chicago: 'Nikfarjam, Adel, Aneta Neumann, Jakob Bossek, and Frank Neumann. “Co-Evolutionary
Diversity Optimisation for the Traveling Thief Problem.” In Parallel Problem
Solving from Nature (PPSN XVII), edited by Günter Rudolph, Anna V. Kononova,
Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, and Tea Tu\v sar, 237–249. Lecture
Notes in Computer Science. Cham: Springer International Publishing, 2022. https://doi.org/10.1007/978-3-031-14714-2_17.'
ieee: 'A. Nikfarjam, A. Neumann, J. Bossek, and F. Neumann, “Co-Evolutionary Diversity
Optimisation for the Traveling Thief Problem,” in Parallel Problem Solving
from Nature (PPSN XVII), 2022, pp. 237–249, doi: 10.1007/978-3-031-14714-2_17.'
mla: Nikfarjam, Adel, et al. “Co-Evolutionary Diversity Optimisation for the Traveling
Thief Problem.” Parallel Problem Solving from Nature (PPSN XVII), edited
by Günter Rudolph et al., Springer International Publishing, 2022, pp. 237–249,
doi:10.1007/978-3-031-14714-2_17.
short: 'A. Nikfarjam, A. Neumann, J. Bossek, F. Neumann, in: G. Rudolph, A.V. Kononova,
H. Aguirre, P. Kerschke, G. Ochoa, T. Tu\v sar (Eds.), Parallel Problem Solving
from Nature (PPSN XVII), Springer International Publishing, Cham, 2022, pp. 237–249.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:51Z
department:
- _id: '819'
doi: 10.1007/978-3-031-14714-2_17
editor:
- first_name: Günter
full_name: Rudolph, Günter
last_name: Rudolph
- first_name: Anna V.
full_name: Kononova, Anna V.
last_name: Kononova
- first_name: Hernán
full_name: Aguirre, Hernán
last_name: Aguirre
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Gabriela
full_name: Ochoa, Gabriela
last_name: Ochoa
- first_name: Tea
full_name: Tu\v sar, Tea
last_name: Tu\v sar
extern: '1'
keyword:
- Co-evolutionary algorithms
- Evolutionary diversity optimisation
- Quality diversity
- Traveling thief problem
language:
- iso: eng
page: 237–249
place: Cham
publication: Parallel Problem Solving from Nature (PPSN XVII)
publication_identifier:
isbn:
- 978-3-031-14714-2
publication_status: published
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem
type: conference
user_id: '102979'
year: '2022'
...
---
_id: '48853'
abstract:
- lang: eng
text: In practise, it is often desirable to provide the decision-maker with a rich
set of diverse solutions of decent quality instead of just a single solution.
In this paper we study evolutionary diversity optimization for the knapsack problem
(KP). Our goal is to evolve a population of solutions that all have a profit of
at least (1 - {$ϵ$}) {$\cdot$} OPT, where OPT is the value of an optimal solution.
Furthermore, they should differ in structure with respect to an entropy-based
diversity measure. To this end we propose a simple ({$\mu$} + 1)-EA with initial
approximate solutions calculated by a well-known FPTAS for the KP. We investigate
the effect of different standard mutation operators and introduce biased mutation
and crossover which puts strong probability on flipping bits of low and/or high
frequency within the population. An experimental study on different instances
and settings shows that the proposed mutation operators in most cases perform
slightly inferior in the long term, but show strong benefits if the number of
function evaluations is severely limited.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Breeding Diverse Packings for the Knapsack
Problem by Means of Diversity-Tailored Evolutionary Algorithms. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO ’21. Association
for Computing Machinery; 2021:556–564. doi:10.1145/3449639.3459364'
apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.
Proceedings of the Genetic and Evolutionary Computation Conference, 556–564.
https://doi.org/10.1145/3449639.3459364
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
series={GECCO ’21}, title={Breeding Diverse Packings for the Knapsack Problem
by Means of Diversity-Tailored Evolutionary Algorithms}, DOI={10.1145/3449639.3459364},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Aneta and Neumann, Frank}, year={2021}, pages={556–564}, collection={GECCO ’21}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.”
In Proceedings of the Genetic and Evolutionary Computation Conference,
556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021.
https://doi.org/10.1145/3449639.3459364.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the
Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 556–564,
doi: 10.1145/3449639.3459364.'
mla: Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by
Means of Diversity-Tailored Evolutionary Algorithms.” Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
2021, pp. 556–564, doi:10.1145/3449639.3459364.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2021, pp. 556–564.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:22Z
department:
- _id: '819'
doi: 10.1145/3449639.3459364
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- knapsack problem
- tailored operators
language:
- iso: eng
page: 556–564
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored
Evolutionary Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48860'
abstract:
- lang: eng
text: In the area of evolutionary computation the calculation of diverse sets of
high-quality solutions to a given optimization problem has gained momentum in
recent years under the term evolutionary diversity optimization. Theoretical insights
into the working principles of baseline evolutionary algorithms for diversity
optimization are still rare. In this paper we study the well-known Minimum Spanning
Tree problem (MST) in the context of diversity optimization where population diversity
is measured by the sum of pairwise edge overlaps. Theoretical results provide
insights into the fitness landscape of the MST diversity optimization problem
pointing out that even for a population of {$\mu$} = 2 fitness plateaus (of constant
length) can be reached, but nevertheless diverse sets can be calculated in polynomial
time. We supplement our theoretical results with a series of experiments for the
unconstrained and constraint case where all solutions need to fulfill a minimal
quality threshold. Our results show that a simple ({$\mu$} + 1)-EA can effectively
compute a diversified population of spanning trees of high quality.
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
citation:
ama: 'Bossek J, Neumann F. Evolutionary Diversity Optimization and the Minimum Spanning
Tree Problem. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:10.1145/3449639.3459363'
apa: Bossek, J., & Neumann, F. (2021). Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. https://doi.org/10.1145/3449639.3459363
bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO
’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem}, DOI={10.1145/3449639.3459363},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2021}, pages={198–206}, collection={GECCO ’21} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization
and the Minimum Spanning Tree Problem.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. GECCO ’21. New York, NY, USA: Association
for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459363.'
ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum
Spanning Tree Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2021, pp. 198–206, doi: 10.1145/3449639.3459363.'
mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 198–206,
doi:10.1145/3449639.3459363.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp.
198–206.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:37Z
department:
- _id: '819'
doi: 10.1145/3449639.3459363
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- minimum spanning tree
- runtime analysis
language:
- iso: eng
page: 198–206
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48862'
abstract:
- lang: eng
text: 'Most runtime analyses of randomised search heuristics focus on the expected
number of function evaluations to find a unique global optimum. We ask a fundamental
question: if additional search points are declared optimal, or declared as desirable
target points, do these additional optima speed up evolutionary algorithms? More
formally, we analyse the expected hitting time of a target set OPT {$\cup$} S
where S is a set of non-optimal search points and OPT is the set of optima and
compare it to the expected hitting time of OPT. We show that the answer to our
question depends on the number and placement of search points in S. For all black-box
algorithms and all fitness functions we show that, if additional optima are placed
randomly, even an exponential number of optima has a negligible effect on the
expected optimisation time. Considering Hamming balls around all global optima
gives an easier target for some algorithms and functions and can shift the phase
transition with respect to offspring population sizes in the (1,{$\lambda$}) EA
on One-Max. Finally, on functions where search trajectories typically join in
a single search point, turning one search point into an optimum drastically reduces
the expected optimisation time.'
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
citation:
ama: 'Bossek J, Sudholt D. Do Additional Optima Speed up Evolutionary Algorithms?
In: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms. Association for Computing Machinery; 2021:1–11.'
apa: Bossek, J., & Sudholt, D. (2021). Do Additional Optima Speed up Evolutionary
Algorithms? In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms (pp. 1–11). Association for Computing Machinery.
bibtex: '@inbook{Bossek_Sudholt_2021, place={New York, NY, USA}, title={Do Additional
Optima Speed up Evolutionary Algorithms?}, booktitle={Proceedings of the 16th
ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association
for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2021},
pages={1–11} }'
chicago: 'Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
Algorithms?” In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 1–11. New York, NY, USA: Association for Computing
Machinery, 2021.'
ieee: 'J. Bossek and D. Sudholt, “Do Additional Optima Speed up Evolutionary Algorithms?,”
in Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms, New York, NY, USA: Association for Computing Machinery, 2021,
pp. 1–11.'
mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
Algorithms?” Proceedings of the 16th ACM/SIGEVO Conference on Foundations of
Genetic Algorithms, Association for Computing Machinery, 2021, pp. 1–11.
short: 'J. Bossek, D. Sudholt, in: Proceedings of the 16th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms, Association for Computing Machinery, New
York, NY, USA, 2021, pp. 1–11.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:31Z
department:
- _id: '819'
extern: '1'
keyword:
- evolutionary algorithms
- pseudo-boolean functions
- runtime analysis
- theory
language:
- iso: eng
page: 1–11
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publication_status: published
publisher: Association for Computing Machinery
status: public
title: Do Additional Optima Speed up Evolutionary Algorithms?
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48876'
abstract:
- lang: eng
text: In recent years, Evolutionary Algorithms (EAs) have frequently been adopted
to evolve instances for optimization problems that pose difficulties for one algorithm
while being rather easy for a competitor and vice versa. Typically, this is achieved
by either minimizing or maximizing the performance difference or ratio which serves
as the fitness function. Repeating this process is useful to gain insights into
strengths/weaknesses of certain algorithms or to build a set of instances with
strong performance differences as a foundation for automatic per-instance algorithm
selection or configuration. We contribute to this branch of research by proposing
fitness-functions to evolve instances that show large performance differences
for more than just two algorithms simultaneously. As a proof-of-principle, we
evolve instances of the multi-component Traveling Thief Problem (TTP) for three
incomplete TTP-solvers. Our results point out that our strategies are promising,
but unsurprisingly their success strongly relies on the algorithms’ performance
complementarity.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
citation:
ama: 'Bossek J, Wagner M. Generating Instances with Performance Differences for
More than Just Two Algorithms. In: Proceedings of the Genetic and Evolutionary
Computation Conference Companion. GECCO’21. Association for Computing Machinery;
2021:1423–1432. doi:10.1145/3449726.3463165'
apa: Bossek, J., & Wagner, M. (2021). Generating Instances with Performance
Differences for More than Just Two Algorithms. Proceedings of the Genetic and
Evolutionary Computation Conference Companion, 1423–1432. https://doi.org/10.1145/3449726.3463165
bibtex: '@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21},
title={Generating Instances with Performance Differences for More than Just Two
Algorithms}, DOI={10.1145/3449726.3463165},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob
and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }'
chicago: 'Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance
Differences for More than Just Two Algorithms.” In Proceedings of the Genetic
and Evolutionary Computation Conference Companion, 1423–1432. GECCO’21. New
York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449726.3463165.'
ieee: 'J. Bossek and M. Wagner, “Generating Instances with Performance Differences
for More than Just Two Algorithms,” in Proceedings of the Genetic and Evolutionary
Computation Conference Companion, 2021, pp. 1423–1432, doi: 10.1145/3449726.3463165.'
mla: Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences
for More than Just Two Algorithms.” Proceedings of the Genetic and Evolutionary
Computation Conference Companion, Association for Computing Machinery, 2021,
pp. 1423–1432, doi:10.1145/3449726.3463165.
short: 'J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation
Conference Companion, Association for Computing Machinery, New York, NY, USA,
2021, pp. 1423–1432.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:41Z
department:
- _id: '819'
doi: 10.1145/3449726.3463165
extern: '1'
keyword:
- evolutionary algorithms
- evolving instances
- fitness function
- instance hardness
- traveling thief problem (TTP)
language:
- iso: eng
page: 1423–1432
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion
publication_identifier:
isbn:
- 978-1-4503-8351-6
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Generating Instances with Performance Differences for More than Just Two Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48893'
abstract:
- lang: eng
text: Computing diverse sets of high-quality solutions has gained increasing attention
among the evolutionary computation community in recent years. It allows practitioners
to choose from a set of high-quality alternatives. In this paper, we employ a
population diversity measure, called the high-order entropy measure, in an evolutionary
algorithm to compute a diverse set of high-quality solutions for the Traveling
Salesperson Problem. In contrast to previous studies, our approach allows diversifying
segments of tours containing several edges based on the entropy measure. We examine
the resulting evolutionary diversity optimisation approach precisely in terms
of the final set of solutions and theoretical properties. Experimental results
show significant improvements compared to a recently proposed edge-based diversity
optimisation approach when working with a large population of solutions or long
segments.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Entropy-Based Evolutionary Diversity
Optimisation for the Traveling Salesperson Problem. In: Proceedings of the
Genetic and Evolutionary Computation Conference. GECCO’21. Association for
Computing Machinery; 2021:600–608. doi:10.1145/3449639.3459384'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. Proceedings
of the Genetic and Evolutionary Computation Conference, 600–608. https://doi.org/10.1145/3449639.3459384
bibtex: '@inproceedings{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York,
NY, USA}, series={GECCO’21}, title={Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem}, DOI={10.1145/3449639.3459384},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Nikfarjam, Adel and Bossek,
Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={600–608}, collection={GECCO’21}
}'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” In
Proceedings of the Genetic and Evolutionary Computation Conference, 600–608.
GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459384.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Entropy-Based Evolutionary
Diversity Optimisation for the Traveling Salesperson Problem,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 600–608,
doi: 10.1145/3449639.3459384.'
mla: Nikfarjam, Adel, et al. “Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 600–608,
doi:10.1145/3449639.3459384.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
Genetic and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2021, pp. 600–608.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:50:06Z
department:
- _id: '819'
doi: 10.1145/3449639.3459384
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimisation
- high-order entropy
- traveling salesperson problem
language:
- iso: eng
page: 600–608
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson
Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48891'
abstract:
- lang: eng
text: Submodular functions allow to model many real-world optimisation problems.
This paper introduces approaches for computing diverse sets of high quality solutions
for submodular optimisation problems with uniform and knapsack constraints. We
first present diversifying greedy sampling approaches and analyse them with respect
to the diversity measured by entropy and the approximation quality of the obtained
solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO)
approach to further improve diversity of the set of solutions. We carry out experimental
investigations on popular submodular benchmark problems and analyse trade-offs
in terms of solution quality and diversity of the resulting solution sets.
author:
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- 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
citation:
ama: 'Neumann A, Bossek J, Neumann F. Diversifying Greedy Sampling and Evolutionary
Diversity Optimisation for Constrained Monotone Submodular Functions. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO’21. Association
for Computing Machinery; 2021:261–269. doi:10.1145/3449639.3459385'
apa: Neumann, A., Bossek, J., & Neumann, F. (2021). Diversifying Greedy Sampling
and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.
Proceedings of the Genetic and Evolutionary Computation Conference, 261–269.
https://doi.org/10.1145/3449639.3459385
bibtex: '@inproceedings{Neumann_Bossek_Neumann_2021, place={New York, NY, USA},
series={GECCO’21}, title={Diversifying Greedy Sampling and Evolutionary Diversity
Optimisation for Constrained Monotone Submodular Functions}, DOI={10.1145/3449639.3459385},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Neumann, Aneta and Bossek,
Jakob and Neumann, Frank}, year={2021}, pages={261–269}, collection={GECCO’21}
}'
chicago: 'Neumann, Aneta, Jakob Bossek, and Frank Neumann. “Diversifying Greedy
Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular
Functions.” In Proceedings of the Genetic and Evolutionary Computation Conference,
261–269. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021.
https://doi.org/10.1145/3449639.3459385.'
ieee: 'A. Neumann, J. Bossek, and F. Neumann, “Diversifying Greedy Sampling and
Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions,”
in Proceedings of the Genetic and Evolutionary Computation Conference,
2021, pp. 261–269, doi: 10.1145/3449639.3459385.'
mla: Neumann, Aneta, et al. “Diversifying Greedy Sampling and Evolutionary Diversity
Optimisation for Constrained Monotone Submodular Functions.” Proceedings of
the Genetic and Evolutionary Computation Conference, Association for Computing
Machinery, 2021, pp. 261–269, doi:10.1145/3449639.3459385.
short: 'A. Neumann, J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2021, pp. 261–269.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:49:25Z
department:
- _id: '819'
doi: 10.1145/3449639.3459385
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimisation
- sub-modular functions
language:
- iso: eng
page: 261–269
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained
Monotone Submodular Functions
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48892'
abstract:
- lang: eng
text: Evolutionary algorithms based on edge assembly crossover (EAX) constitute
some of the best performing incomplete solvers for the well-known traveling salesperson
problem (TSP). Often, it is desirable to compute not just a single solution for
a given problem, but a diverse set of high quality solutions from which a decision
maker can choose one for implementation. Currently, there are only a few approaches
for computing a diverse solution set for the TSP. Furthermore, almost all of them
assume that the optimal solution is known. In this paper, we introduce evolutionary
diversity optimisation (EDO) approaches for the TSP that find a diverse set of
tours when the optimal tour is known or unknown. We show how to adopt EAX to not
only find a high-quality solution but also to maximise the diversity of the population.
The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse
high-quality tours when the optimal solution for the TSP is known or unknown.
A comparison to existing approaches shows that they are clearly outperformed by
EAX-EDO.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Computing Diverse Sets of High
Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In: Proceedings
of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–11.'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Computing
Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation.
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms (pp. 1–11). Association for Computing Machinery.
bibtex: '@inbook{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
title={Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation}, booktitle={Proceedings of the 16th ACM}/SIGEVO Conference
on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery},
author={Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank},
year={2021}, pages={1–11} }'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Computing
Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.”
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms, 1–11. New York, NY, USA: Association for Computing Machinery,
2021.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Computing Diverse Sets
of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation,” in
Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms,
New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.'
mla: Nikfarjam, Adel, et al. “Computing Diverse Sets of High Quality TSP Tours by
EAX-Based Evolutionary Diversity Optimisation.” Proceedings of the 16th ACM}/SIGEVO
Conference on Foundations of Genetic Algorithms, Association for Computing
Machinery, 2021, pp. 1–11.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, Association
for Computing Machinery, New York, NY, USA, 2021, pp. 1–11.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:59Z
department:
- _id: '819'
extern: '1'
keyword:
- edge assembly crossover (EAX)
- evolutionary algorithms
- evolutionary diversity optimisation (EDO)
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–11
place: New York, NY, USA
publication: Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48854'
abstract:
- lang: eng
text: We contribute to the theoretical understanding of randomized search heuristics
for dynamic problems. We consider the classical vertex coloring problem on graphs
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. The (1+1) Evolutionary Algorithm and RLS operate in a
setting where the number of colors is bounded and we are minimizing the number
of conflicts. Iterated local search algorithms use an unbounded color palette
and aim to use the smallest colors and, consequently, 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. We
further show that tailoring mutation operators to parts of the graph where changes
have occurred can significantly reduce the expected reoptimization time. In most
settings the expected reoptimization time for such tailored algorithms is linear
in the number of added edges. However, tailored algorithms cannot prevent exponential
times in settings where the original algorithm is inefficient.
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. Time Complexity Analysis of Randomized
Search Heuristics for the Dynamic Graph Coloring Problem. Algorithmica.
2021;83(10):3148–3179. doi:10.1007/s00453-021-00838-3
apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2021). Time Complexity
Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.
Algorithmica, 83(10), 3148–3179. https://doi.org/10.1007/s00453-021-00838-3
bibtex: '@article{Bossek_Neumann_Peng_Sudholt_2021, title={Time Complexity Analysis
of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}, volume={83},
DOI={10.1007/s00453-021-00838-3},
number={10}, journal={Algorithmica}, author={Bossek, Jakob and Neumann, Frank
and Peng, Pan and Sudholt, Dirk}, year={2021}, pages={3148–3179} }'
chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Time Complexity
Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.”
Algorithmica 83, no. 10 (2021): 3148–3179. https://doi.org/10.1007/s00453-021-00838-3.'
ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Time Complexity Analysis
of Randomized Search Heuristics for the Dynamic Graph Coloring Problem,” Algorithmica,
vol. 83, no. 10, pp. 3148–3179, 2021, doi: 10.1007/s00453-021-00838-3.'
mla: Bossek, Jakob, et al. “Time Complexity Analysis of Randomized Search Heuristics
for the Dynamic Graph Coloring Problem.” Algorithmica, vol. 83, no. 10,
2021, pp. 3148–3179, doi:10.1007/s00453-021-00838-3.
short: J. Bossek, F. Neumann, P. Peng, D. Sudholt, Algorithmica 83 (2021) 3148–3179.
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:51:34Z
department:
- _id: '819'
doi: 10.1007/s00453-021-00838-3
intvolume: ' 83'
issue: '10'
keyword:
- Dynamic optimization
- Evolutionary algorithms
- Running time analysis
language:
- iso: eng
page: 3148–3179
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
status: public
title: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph
Coloring Problem
type: journal_article
user_id: '102979'
volume: 83
year: '2021'
...
---
_id: '48847'
abstract:
- lang: eng
text: Dynamic optimization problems have gained significant attention in evolutionary
computation as evolutionary algorithms (EAs) can easily adapt to changing environments.
We show that EAs can solve the graph coloring problem for bipartite graphs more
efficiently by using dynamic optimization. In our approach the graph instance
is given incrementally such that the EA can reoptimize its coloring when a new
edge introduces a conflict. We show that, when edges are inserted in a way that
preserves graph connectivity, Randomized Local Search (RLS) efficiently finds
a proper 2-coloring for all bipartite graphs. This includes graphs for which RLS
and other EAs need exponential expected time in a static optimization scenario.
We investigate different ways of building up the graph by popular graph traversals
such as breadth-first-search and depth-first-search and analyse the resulting
runtime behavior. We further show that offspring populations (e. g. a (1 + {$\lambda$})
RLS) lead to an exponential speedup in {$\lambda$}. Finally, an island model using
3 islands succeeds in an optimal time of {$\Theta$}(m) on every m-edge bipartite
graph, outperforming offspring populations. This is the first example where an
island model guarantees a speedup that is not bounded in the number of islands.
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. More Effective Randomized Search Heuristics
for Graph Coloring through Dynamic Optimization. In: Proceedings of the Genetic
and Evolutionary Computation Conference. GECCO ’20. Association for Computing
Machinery; 2020:1277–1285. doi:10.1145/3377930.3390174'
apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2020). More Effective
Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.
Proceedings of the Genetic and Evolutionary Computation Conference, 1277–1285.
https://doi.org/10.1145/3377930.3390174
bibtex: '@inproceedings{Bossek_Neumann_Peng_Sudholt_2020, place={New York, NY, USA},
series={GECCO ’20}, title={More Effective Randomized Search Heuristics for Graph
Coloring through Dynamic Optimization}, DOI={10.1145/3377930.3390174},
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={2020}, pages={1277–1285}, collection={GECCO
’20} }'
chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “More Effective
Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.”
In Proceedings of the Genetic and Evolutionary Computation Conference,
1277–1285. GECCO ’20. New York, NY, USA: Association for Computing Machinery,
2020. https://doi.org/10.1145/3377930.3390174.'
ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “More Effective Randomized
Search Heuristics for Graph Coloring through Dynamic Optimization,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2020, pp. 1277–1285,
doi: 10.1145/3377930.3390174.'
mla: Bossek, Jakob, et al. “More Effective Randomized Search Heuristics for Graph
Coloring through Dynamic Optimization.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2020, pp. 1277–1285,
doi:10.1145/3377930.3390174.
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, 2020, pp. 1277–1285.'
date_created: 2023-11-14T15:58:53Z
date_updated: 2023-12-13T10:43:41Z
department:
- _id: '819'
doi: 10.1145/3377930.3390174
extern: '1'
keyword:
- dynamic optimization
- evolutionary algorithms
- running time analysis
- theory
language:
- iso: eng
page: 1277–1285
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’20
status: public
title: More Effective Randomized Search Heuristics for Graph Coloring through Dynamic
Optimization
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48851'
abstract:
- lang: eng
text: Several important optimization problems in the area of vehicle routing can
be seen as variants of the classical Traveling Salesperson Problem (TSP). In the
area of evolutionary computation, the Traveling Thief Problem (TTP) has gained
increasing interest over the last 5 years. In this paper, we investigate the effect
of weights on such problems, in the sense that the cost of traveling increases
with respect to the weights of nodes already visited during a tour. This provides
abstractions of important TSP variants such as the Traveling Thief Problem and
time dependent TSP variants, and allows to study precisely the increase in difficulty
caused by weight dependence. We provide a 3.59-approximation for this weight dependent
version of TSP with metric distances and bounded positive weights. Furthermore,
we conduct experimental investigations for simple randomized local search with
classical mutation operators and two variants of the state-of-the-art evolutionary
algorithm EAX adapted to the weighted TSP. Our results show the impact of the
node weights on the position of the nodes in the resulting tour.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Katrin
full_name: Casel, Katrin
last_name: Casel
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Casel K, Kerschke P, Neumann F. The Node Weight Dependent Traveling
Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.
In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’20. Association for Computing Machinery; 2020:1286–1294. doi:10.1145/3377930.3390243'
apa: 'Bossek, J., Casel, K., Kerschke, P., & Neumann, F. (2020). The Node Weight
Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized
Search Heuristics. Proceedings of the Genetic and Evolutionary Computation
Conference, 1286–1294. https://doi.org/10.1145/3377930.3390243'
bibtex: '@inproceedings{Bossek_Casel_Kerschke_Neumann_2020, place={New York, NY,
USA}, series={GECCO ’20}, title={The Node Weight Dependent Traveling Salesperson
Problem: Approximation Algorithms and Randomized Search Heuristics}, DOI={10.1145/3377930.3390243},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Casel,
Katrin and Kerschke, Pascal and Neumann, Frank}, year={2020}, pages={1286–1294},
collection={GECCO ’20} }'
chicago: 'Bossek, Jakob, Katrin Casel, Pascal Kerschke, and Frank Neumann. “The
Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms
and Randomized Search Heuristics.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 1286–1294. GECCO ’20. New York, NY, USA: Association
for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390243.'
ieee: 'J. Bossek, K. Casel, P. Kerschke, and F. Neumann, “The Node Weight Dependent
Traveling Salesperson Problem: Approximation Algorithms and Randomized Search
Heuristics,” in Proceedings of the Genetic and Evolutionary Computation Conference,
2020, pp. 1286–1294, doi: 10.1145/3377930.3390243.'
mla: 'Bossek, Jakob, et al. “The Node Weight Dependent Traveling Salesperson Problem:
Approximation Algorithms and Randomized Search Heuristics.” Proceedings of
the Genetic and Evolutionary Computation Conference, Association for Computing
Machinery, 2020, pp. 1286–1294, doi:10.1145/3377930.3390243.'
short: 'J. Bossek, K. Casel, P. Kerschke, F. Neumann, in: Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2020, pp. 1286–1294.'
date_created: 2023-11-14T15:58:53Z
date_updated: 2023-12-13T10:43:33Z
department:
- _id: '819'
doi: 10.1145/3377930.3390243
extern: '1'
keyword:
- dynamic optimization
- evolutionary algorithms
- running time analysis
- theory
language:
- iso: eng
page: 1286–1294
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’20
status: public
title: 'The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms
and Randomized Search Heuristics'
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48845'
abstract:
- lang: eng
text: In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems
(VRPs) often imply repeated decision making on dynamic customer requests. As in
classical VRPs, tours have to be planned short while the number of serviced customers
has to be maximized at the same time resulting in a multi-objective problem. Beyond
that, however, dynamic requests lead to the need for re-planning of not yet realized
tour parts, while already realized tour parts are irreversible. In this paper
we study this type of bi-objective dynamic VRP including sequential decision making
and concurrent realization of decisions. We adopt a recently proposed Dynamic
Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend
it to the more realistic (here considered) scenario of multiple vehicles. We empirically
show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant
variant of the proposed DEMOA as well as with the dynamic single-vehicle approach
proposed earlier.
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: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Grimme C, Trautmann H. Dynamic Bi-Objective Routing of Multiple
Vehicles. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’20. Association for Computing Machinery; 2020:166–174. doi:10.1145/3377930.3390146'
apa: Bossek, J., Grimme, C., & Trautmann, H. (2020). Dynamic Bi-Objective Routing
of Multiple Vehicles. Proceedings of the Genetic and Evolutionary Computation
Conference, 166–174. https://doi.org/10.1145/3377930.3390146
bibtex: '@inproceedings{Bossek_Grimme_Trautmann_2020, place={New York, NY, USA},
series={GECCO ’20}, title={Dynamic Bi-Objective Routing of Multiple Vehicles},
DOI={10.1145/3377930.3390146},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme,
Christian and Trautmann, Heike}, year={2020}, pages={166–174}, collection={GECCO
’20} }'
chicago: 'Bossek, Jakob, Christian Grimme, and Heike Trautmann. “Dynamic Bi-Objective
Routing of Multiple Vehicles.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 166–174. GECCO ’20. New York, NY, USA: Association
for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390146.'
ieee: 'J. Bossek, C. Grimme, and H. Trautmann, “Dynamic Bi-Objective Routing of
Multiple Vehicles,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2020, pp. 166–174, doi: 10.1145/3377930.3390146.'
mla: Bossek, Jakob, et al. “Dynamic Bi-Objective Routing of Multiple Vehicles.”
Proceedings of the Genetic and Evolutionary Computation Conference, Association
for Computing Machinery, 2020, pp. 166–174, doi:10.1145/3377930.3390146.
short: 'J. Bossek, C. Grimme, H. Trautmann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2020, pp. 166–174.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:43:24Z
department:
- _id: '819'
doi: 10.1145/3377930.3390146
extern: '1'
keyword:
- decision making
- dynamic optimization
- evolutionary algorithms
- multi-objective optimization
- vehicle routing
language:
- iso: eng
page: 166–174
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’20
status: public
title: Dynamic Bi-Objective Routing of Multiple Vehicles
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48852'
abstract:
- lang: eng
text: The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial
optimisation problems. However, many real-world problems are composed of several
interacting components. The Traveling Thief Problem (TTP) addresses such interactions
by combining two combinatorial optimisation problems, namely the TSP and the Knapsack
Problem (KP). Recently, a new problem called the node weight dependent Traveling
Salesperson Problem (W-TSP) has been introduced where nodes have weights that
influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate
the structure of the optimised tours for W-TSP and TTP and the impact of using
each others fitness function. Our experimental results suggest (1) that the W-TSP
often can be solved better using the TTP fitness function and (2) final W-TSP
and TTP solutions show different distributions when compared with optimal TSP
or weighted greedy solutions.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Optimising Tours for the Weighted Traveling
Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of
Solutions. In: Parallel Problem Solving from Nature (PPSN XVI). Springer-Verlag;
2020:346–359. doi:10.1007/978-3-030-58112-1_24'
apa: 'Bossek, J., Neumann, A., & Neumann, F. (2020). Optimising Tours for the
Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural
Comparison of Solutions. Parallel Problem Solving from Nature (PPSN XVI),
346–359. https://doi.org/10.1007/978-3-030-58112-1_24'
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2020, place={Berlin, Heidelberg},
title={Optimising Tours for the Weighted Traveling Salesperson Problem and the
Traveling Thief Problem: A Structural Comparison of Solutions}, DOI={10.1007/978-3-030-58112-1_24},
booktitle={Parallel Problem Solving from Nature (PPSN XVI)}, publisher={Springer-Verlag},
author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={346–359}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Optimising Tours for
the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A
Structural Comparison of Solutions.” In Parallel Problem Solving from Nature
(PPSN XVI), 346–359. Berlin, Heidelberg: Springer-Verlag, 2020. https://doi.org/10.1007/978-3-030-58112-1_24.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Optimising Tours for the Weighted
Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison
of Solutions,” in Parallel Problem Solving from Nature (PPSN XVI), 2020,
pp. 346–359, doi: 10.1007/978-3-030-58112-1_24.'
mla: 'Bossek, Jakob, et al. “Optimising Tours for the Weighted Traveling Salesperson
Problem and the Traveling Thief Problem: A Structural Comparison of Solutions.”
Parallel Problem Solving from Nature (PPSN XVI), Springer-Verlag, 2020,
pp. 346–359, doi:10.1007/978-3-030-58112-1_24.'
short: 'J. Bossek, A. Neumann, F. Neumann, in: Parallel Problem Solving from Nature
(PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp. 346–359.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:44:54Z
department:
- _id: '819'
doi: 10.1007/978-3-030-58112-1_24
extern: '1'
keyword:
- Evolutionary algorithms
- Node weight dependent TSP
- Traveling Thief Problem
language:
- iso: eng
page: 346–359
place: Berlin, Heidelberg
publication: Parallel Problem Solving from Nature (PPSN XVI)
publication_identifier:
isbn:
- 978-3-030-58111-4
publication_status: published
publisher: Springer-Verlag
status: public
title: 'Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling
Thief Problem: A Structural Comparison of Solutions'
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48879'
abstract:
- lang: eng
text: Evolving diverse sets of high quality solutions has gained increasing interest
in the evolutionary computation literature in recent years. With this paper, we
contribute to this area of research by examining evolutionary diversity optimisation
approaches for the classical Traveling Salesperson Problem (TSP). We study the
impact of using different diversity measures for a given set of tours and the
ability of evolutionary algorithms to obtain a diverse set of high quality solutions
when adopting these measures. Our studies show that a large variety of diverse
high quality tours can be achieved by using our approaches. Furthermore, we compare
our approaches in terms of theoretical properties and the final set of tours obtained
by the evolutionary diversity optimisation algorithm.
author:
- first_name: Anh Viet
full_name: Do, Anh Viet
last_name: Do
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Do AV, Bossek J, Neumann A, Neumann F. Evolving Diverse Sets of Tours for
the Travelling Salesperson Problem. In: Proceedings of the Genetic and Evolutionary
Computation Conference. GECCO’20. Association for Computing Machinery; 2020:681–689.
doi:10.1145/3377930.3389844'
apa: Do, A. V., Bossek, J., Neumann, A., & Neumann, F. (2020). Evolving Diverse
Sets of Tours for the Travelling Salesperson Problem. Proceedings of the Genetic
and Evolutionary Computation Conference, 681–689. https://doi.org/10.1145/3377930.3389844
bibtex: '@inproceedings{Do_Bossek_Neumann_Neumann_2020, place={New York, NY, USA},
series={GECCO’20}, title={Evolving Diverse Sets of Tours for the Travelling Salesperson
Problem}, DOI={10.1145/3377930.3389844},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Do, Anh Viet and Bossek,
Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={681–689}, collection={GECCO’20}
}'
chicago: 'Do, Anh Viet, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Evolving
Diverse Sets of Tours for the Travelling Salesperson Problem.” In Proceedings
of the Genetic and Evolutionary Computation Conference, 681–689. GECCO’20.
New York, NY, USA: Association for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3389844.'
ieee: 'A. V. Do, J. Bossek, A. Neumann, and F. Neumann, “Evolving Diverse Sets of
Tours for the Travelling Salesperson Problem,” in Proceedings of the Genetic
and Evolutionary Computation Conference, 2020, pp. 681–689, doi: 10.1145/3377930.3389844.'
mla: Do, Anh Viet, et al. “Evolving Diverse Sets of Tours for the Travelling Salesperson
Problem.” Proceedings of the Genetic and Evolutionary Computation Conference,
Association for Computing Machinery, 2020, pp. 681–689, doi:10.1145/3377930.3389844.
short: 'A.V. Do, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2020, pp. 681–689.'
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:48:50Z
department:
- _id: '819'
doi: 10.1145/3377930.3389844
extern: '1'
keyword:
- diversity maximisation
- evolutionary algorithms
- travelling salesperson problem
language:
- iso: eng
page: 681–689
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publisher: Association for Computing Machinery
series_title: GECCO’20
status: public
title: Evolving Diverse Sets of Tours for the Travelling Salesperson Problem
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48895'
abstract:
- lang: eng
text: Evolutionary algorithms (EAs) are general-purpose problem solvers that usually
perform an unbiased search. This is reasonable and desirable in a black-box scenario.
For combinatorial optimization problems, often more knowledge about the structure
of optimal solutions is given, which can be leveraged by means of biased search
operators. We consider the Minimum Spanning Tree (MST) problem in a single- and
multi-objective version, and introduce a biased mutation, which puts more emphasis
on the selection of edges of low rank in terms of low domination number. We present
example graphs where the biased mutation can significantly speed up the expected
runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate
that bias can lead to exponential runtime if "heavy" edges are necessarily part
of an optimal solution. However, on general graphs in the single-objective setting,
we show that a combined mutation operator which decides for unbiased or biased
edge selection in each step with equal probability exhibits a polynomial upper
bound - as unbiased mutation - in the worst case and benefits from bias if the
circumstances are favorable.
author:
- first_name: Vahid
full_name: Roostapour, Vahid
last_name: Roostapour
- 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
citation:
ama: 'Roostapour V, Bossek J, Neumann F. Runtime Analysis of Evolutionary Algorithms
with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. In:
Proceedings of the 2020 Genetic and Evolutionary Computation Conference.
{GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:10.1145/3377930.3390168'
apa: Roostapour, V., Bossek, J., & Neumann, F. (2020). Runtime Analysis of Evolutionary
Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree
Problem. Proceedings of the 2020 Genetic and Evolutionary Computation Conference,
551–559. https://doi.org/10.1145/3377930.3390168
bibtex: '@inproceedings{Roostapour_Bossek_Neumann_2020, place={New York, NY, USA},
series={{GECCO} ’20}, title={Runtime Analysis of Evolutionary Algorithms with
Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem}, DOI={10.1145/3377930.3390168}, booktitle={Proceedings
of the 2020 Genetic and Evolutionary Computation Conference}, publisher={Association
for Computing Machinery}, author={Roostapour, Vahid and Bossek, Jakob and Neumann,
Frank}, year={2020}, pages={551–559}, collection={{GECCO} ’20} }'
chicago: 'Roostapour, Vahid, Jakob Bossek, and Frank Neumann. “Runtime Analysis
of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum
Spanning Tree Problem.” In Proceedings of the 2020 Genetic and Evolutionary
Computation Conference, 551–559. {GECCO} ’20. New York, NY, USA: Association
for Computing Machinery, 2020. https://doi.org/10.1145/3377930.3390168.'
ieee: 'V. Roostapour, J. Bossek, and F. Neumann, “Runtime Analysis of Evolutionary
Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree
Problem,” in Proceedings of the 2020 Genetic and Evolutionary Computation Conference,
2020, pp. 551–559, doi: 10.1145/3377930.3390168.'
mla: Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with
Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” Proceedings
of the 2020 Genetic and Evolutionary Computation Conference, Association for
Computing Machinery, 2020, pp. 551–559, doi:10.1145/3377930.3390168.
short: 'V. Roostapour, J. Bossek, F. Neumann, in: Proceedings of the 2020 Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2020, pp. 551–559.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:38Z
department:
- _id: '819'
doi: 10.1145/3377930.3390168
extern: '1'
keyword:
- biased mutation
- evolutionary algorithms
- minimum spanning tree problem
- runtime analysis
language:
- iso: eng
page: 551–559
place: New York, NY, USA
publication: Proceedings of the 2020 Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-7128-5
publisher: Association for Computing Machinery
series_title: '{GECCO} ’20'
status: public
title: Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective
Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2020'
...
---
_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: '48838'
abstract:
- lang: eng
text: 'The majority of algorithms can be controlled or adjusted by parameters. Their
values can substantially affect the algorithms’ performance. Since the manual
exploration of the parameter space is tedious – even for few parameters – several
automatic procedures for parameter tuning have been proposed. Recent approaches
also take into account some characteristic properties of the problem instances,
frequently termed instance features. Our contribution is the proposal of a novel
concept for feature-based algorithm parameter tuning, which applies an approximating
surrogate model for learning the continuous feature-parameter mapping. To accomplish
this, we learn a joint model of the algorithm performance based on both the algorithm
parameters and the instance features. The required data is gathered using a recently
proposed acquisition function for model refinement in surrogate-based optimization:
the profile expected improvement. This function provides an avenue for maximizing
the information required for the feature-parameter mapping, i.e., the mapping
from instance features to the corresponding optimal algorithm parameters. The
approach is validated by applying the tuner to exemplary evolutionary algorithms
and problems, for which theoretically grounded or heuristically determined feature-parameter
mappings are available.'
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Bernd
full_name: Bischl, Bernd
last_name: Bischl
- first_name: Tobias
full_name: Wagner, Tobias
last_name: Wagner
- first_name: Günter
full_name: Rudolph, Günter
last_name: Rudolph
citation:
ama: 'Bossek J, Bischl B, Wagner T, Rudolph G. Learning Feature-Parameter Mappings
for Parameter Tuning via the Profile Expected Improvement. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO ’15. Association
for Computing Machinery; 2015:1319–1326. doi:10.1145/2739480.2754673'
apa: Bossek, J., Bischl, B., Wagner, T., & Rudolph, G. (2015). Learning Feature-Parameter
Mappings for Parameter Tuning via the Profile Expected Improvement. Proceedings
of the Genetic and Evolutionary Computation Conference, 1319–1326. https://doi.org/10.1145/2739480.2754673
bibtex: '@inproceedings{Bossek_Bischl_Wagner_Rudolph_2015, place={New York, NY,
USA}, series={GECCO ’15}, title={Learning Feature-Parameter Mappings for Parameter
Tuning via the Profile Expected Improvement}, DOI={10.1145/2739480.2754673},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Bischl,
Bernd and Wagner, Tobias and Rudolph, Günter}, year={2015}, pages={1319–1326},
collection={GECCO ’15} }'
chicago: 'Bossek, Jakob, Bernd Bischl, Tobias Wagner, and Günter Rudolph. “Learning
Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement.”
In Proceedings of the Genetic and Evolutionary Computation Conference,
1319–1326. GECCO ’15. New York, NY, USA: Association for Computing Machinery,
2015. https://doi.org/10.1145/2739480.2754673.'
ieee: 'J. Bossek, B. Bischl, T. Wagner, and G. Rudolph, “Learning Feature-Parameter
Mappings for Parameter Tuning via the Profile Expected Improvement,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2015, pp. 1319–1326,
doi: 10.1145/2739480.2754673.'
mla: Bossek, Jakob, et al. “Learning Feature-Parameter Mappings for Parameter Tuning
via the Profile Expected Improvement.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2015, pp. 1319–1326,
doi:10.1145/2739480.2754673.
short: 'J. Bossek, B. Bischl, T. Wagner, G. Rudolph, in: Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2015, pp. 1319–1326.'
date_created: 2023-11-14T15:58:51Z
date_updated: 2023-12-13T10:40:30Z
department:
- _id: '819'
doi: 10.1145/2739480.2754673
extern: '1'
keyword:
- evolutionary algorithms
- model-based optimization
- parameter tuning
language:
- iso: eng
page: 1319–1326
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-3472-3
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’15
status: public
title: Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected
Improvement
type: conference
user_id: '102979'
year: '2015'
...