---
_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: '48861'
abstract:
- lang: eng
text: Generating instances of different properties is key to algorithm selection
methods that differentiate between the performance of different solvers for a
given combinatorial optimization problem. A wide range of methods using evolutionary
computation techniques has been introduced in recent years. With this paper, we
contribute to this area of research by providing a new approach based on quality
diversity (QD) that is able to explore the whole feature space. QD algorithms
allow to create solutions of high quality within a given feature space by splitting
it up into boxes and improving solution quality within each box. We use our QD
approach for the generation of TSP instances to visualize and analyze the variety
of instances differentiating various TSP solvers and compare it to instances generated
by established approaches from the literature.
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. Exploring the Feature Space of TSP Instances Using Quality
Diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’22. Association for Computing Machinery; 2022:186–194. doi:10.1145/3512290.3528851'
apa: Bossek, J., & Neumann, F. (2022). Exploring the Feature Space of TSP Instances
Using Quality Diversity. Proceedings of the Genetic and Evolutionary Computation
Conference, 186–194. https://doi.org/10.1145/3512290.3528851
bibtex: '@inproceedings{Bossek_Neumann_2022, place={New York, NY, USA}, series={GECCO
’22}, title={Exploring the Feature Space of TSP Instances Using Quality Diversity},
DOI={10.1145/3512290.3528851},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2022}, pages={186–194}, collection={GECCO ’22} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP
Instances Using Quality Diversity.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 186–194. GECCO ’22. New York, NY, USA: Association
for Computing Machinery, 2022. https://doi.org/10.1145/3512290.3528851.'
ieee: 'J. Bossek and F. Neumann, “Exploring the Feature Space of TSP Instances Using
Quality Diversity,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2022, pp. 186–194, doi: 10.1145/3512290.3528851.'
mla: Bossek, Jakob, and Frank Neumann. “Exploring the Feature Space of TSP Instances
Using Quality Diversity.” Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, 2022, pp. 186–194, doi:10.1145/3512290.3528851.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2022, pp.
186–194.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:56Z
department:
- _id: '819'
doi: 10.1145/3512290.3528851
extern: '1'
keyword:
- instance features
- instance generation
- quality diversity
- TSP
language:
- iso: eng
page: 186–194
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-9237-2
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’22
status: public
title: Exploring the Feature Space of TSP Instances Using Quality Diversity
type: conference
user_id: '102979'
year: '2022'
...
---
_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'
...