---
_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: '48872'
abstract:
- lang: eng
text: Quality diversity (QD) is a branch of evolutionary computation that gained
increasing interest in recent years. The Map-Elites QD approach defines a feature
space, i.e., a partition of the search space, and stores the best solution for
each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean
optimisation on the "number of ones" feature space, where the ith cell stores
the best solution amongst those with a number of ones in [(i - 1)k, ik - 1]. Here
k is a granularity parameter 1 {$\leq$} k {$\leq$} n+1. We give a tight bound
on the expected time until all cells are covered for arbitrary fitness functions
and for all k and analyse the expected optimisation time of QD on OneMax and other
problems whose structure aligns favourably with the feature space. On combinatorial
problems we show that QD finds a (1 - 1/e)-approximation when maximising any monotone
sub-modular function with a single uniform cardinality constraint efficiently.
Defining the feature space as the number of connected components of a connected
graph, we show that QD finds a minimum spanning tree in expected polynomial 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. Runtime Analysis of Quality Diversity Algorithms. In:
Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’23.
Association for Computing Machinery; 2023:1546–1554. doi:10.1145/3583131.3590383'
apa: Bossek, J., & Sudholt, D. (2023). Runtime Analysis of Quality Diversity
Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference,
1546–1554. https://doi.org/10.1145/3583131.3590383
bibtex: '@inproceedings{Bossek_Sudholt_2023, place={New York, NY, USA}, series={GECCO’23},
title={Runtime Analysis of Quality Diversity Algorithms}, DOI={10.1145/3583131.3590383},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt,
Dirk}, year={2023}, pages={1546–1554}, collection={GECCO’23} }'
chicago: 'Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity
Algorithms.” In Proceedings of the Genetic and Evolutionary Computation Conference,
1546–1554. GECCO’23. New York, NY, USA: Association for Computing Machinery, 2023.
https://doi.org/10.1145/3583131.3590383.'
ieee: 'J. Bossek and D. Sudholt, “Runtime Analysis of Quality Diversity Algorithms,”
in Proceedings of the Genetic and Evolutionary Computation Conference,
2023, pp. 1546–1554, doi: 10.1145/3583131.3590383.'
mla: Bossek, Jakob, and Dirk Sudholt. “Runtime Analysis of Quality Diversity Algorithms.”
Proceedings of the Genetic and Evolutionary Computation Conference, Association
for Computing Machinery, 2023, pp. 1546–1554, doi:10.1145/3583131.3590383.
short: 'J. Bossek, D. Sudholt, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2023, pp.
1546–1554.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:48:26Z
department:
- _id: '819'
doi: 10.1145/3583131.3590383
extern: '1'
keyword:
- quality diversity
- runtime analysis
language:
- iso: eng
page: 1546–1554
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: Runtime Analysis of Quality Diversity Algorithms
type: conference
user_id: '102979'
year: '2023'
...
---
_id: '48886'
abstract:
- lang: eng
text: 'Generating new instances via evolutionary methods is commonly used to create
new benchmarking data-sets, with a focus on attempting to cover an instance-space
as completely as possible. Recent approaches have exploited Quality-Diversity
methods to evolve sets of instances that are both diverse and discriminatory with
respect to a portfolio of solvers, but these methods can be challenging when attempting
to find diversity in a high-dimensional feature-space. We address this issue by
training a model based on Principal Component Analysis on existing instances to
create a low-dimension projection of the high-dimension feature-vectors, and then
apply Novelty Search directly in the new low-dimension space. We conduct experiments
to evolve diverse and discriminatory instances of Knapsack Problems, comparing
the use of Novelty Search in the original feature-space to using Novelty Search
in a low-dimensional projection, and repeat over a given set of dimensions. We
find that the methods are complementary: if treated as an ensemble, they collectively
provide increased coverage of the space. Specifically, searching for novelty in
a low-dimension space contributes 56% of the filled regions of the space, while
searching directly in the feature-space covers the remaining 44%.'
author:
- first_name: Alejandro
full_name: Marrero, Alejandro
last_name: Marrero
- first_name: Eduardo
full_name: Segredo, Eduardo
last_name: Segredo
- first_name: Emma
full_name: Hart, Emma
last_name: Hart
- 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
citation:
ama: 'Marrero A, Segredo E, Hart E, Bossek J, Neumann A. Generating Diverse and
Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions
of Feature-Space. In: Proceedings of the Genetic} and Evolutionary Computation
Conference. GECCO’23. Association for Computing Machinery; 2023:312–320. doi:10.1145/3583131.3590504'
apa: Marrero, A., Segredo, E., Hart, E., Bossek, J., & Neumann, A. (2023). Generating
Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable
Dimensions of Feature-Space. Proceedings of the Genetic} and Evolutionary Computation
Conference, 312–320. https://doi.org/10.1145/3583131.3590504
bibtex: '@inproceedings{Marrero_Segredo_Hart_Bossek_Neumann_2023, place={New York,
NY, USA}, series={GECCO’23}, title={Generating Diverse and Discriminatory Knapsack
Instances by Searching for Novelty in Variable Dimensions of Feature-Space}, DOI={10.1145/3583131.3590504}, booktitle={Proceedings
of the Genetic} and Evolutionary Computation Conference}, publisher={Association
for Computing Machinery}, author={Marrero, Alejandro and Segredo, Eduardo and
Hart, Emma and Bossek, Jakob and Neumann, Aneta}, year={2023}, pages={312–320},
collection={GECCO’23} }'
chicago: 'Marrero, Alejandro, Eduardo Segredo, Emma Hart, Jakob Bossek, and Aneta
Neumann. “Generating Diverse and Discriminatory Knapsack Instances by Searching
for Novelty in Variable Dimensions of Feature-Space.” In Proceedings of the
Genetic} and Evolutionary Computation Conference, 312–320. GECCO’23. New York,
NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3583131.3590504.'
ieee: 'A. Marrero, E. Segredo, E. Hart, J. Bossek, and A. Neumann, “Generating Diverse
and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions
of Feature-Space,” in Proceedings of the Genetic} and Evolutionary Computation
Conference, 2023, pp. 312–320, doi: 10.1145/3583131.3590504.'
mla: Marrero, Alejandro, et al. “Generating Diverse and Discriminatory Knapsack
Instances by Searching for Novelty in Variable Dimensions of Feature-Space.” Proceedings
of the Genetic} and Evolutionary Computation Conference, Association for Computing
Machinery, 2023, pp. 312–320, doi:10.1145/3583131.3590504.
short: 'A. Marrero, E. Segredo, E. Hart, J. Bossek, A. Neumann, in: Proceedings
of the Genetic} and Evolutionary Computation Conference, Association for Computing
Machinery, New York, NY, USA, 2023, pp. 312–320.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:49:32Z
department:
- _id: '819'
doi: 10.1145/3583131.3590504
extern: '1'
keyword:
- evolutionary computation
- instance generation
- instance-space analysis
- knapsack problem
- novelty search
language:
- iso: eng
page: 312–320
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: Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty
in Variable Dimensions of Feature-Space
type: conference
user_id: '102979'
year: '2023'
...