---
_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: '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'
...