# Evolutionary Diversity Optimisation for The Traveling Thief Problem

arXiv: https://arxiv.org/abs/2204.02709 · HTML: https://mlsanity.com/paper/2204.02709/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2022.

## Built on by (most cited first, 5 of 5)

- [Automated Design of Metaheuristic Algorithms: A Survey](https://mlsanity.com/paper/2303.06532/) (2023)
- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)
- [Trust Region-Based Bayesian Optimisation to Discover Diverse Solutions](https://mlsanity.com/paper/2511.00750/) (2025)
- [The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics](https://mlsanity.com/paper/2604.06724/) (2026)

## Abstract (arXiv)

There has been a growing interest in the evolutionary computation community to compute a diverse set of high-quality solutions for a given optimisation problem. This can provide the practitioners with invaluable information about the solution space and robustness against imperfect modelling and minor problems' changes. It also enables the decision-makers to involve their interests and choose between various solutions. In this study, we investigate for the first time a prominent multi-component optimisation problem, namely the Traveling Thief Problem (TTP), in the context of evolutionary diversity optimisation. We introduce a bi-level evolutionary algorithm to maximise the structural diversity of the set of solutions. Moreover, we examine the inter-dependency among the components of the problem in terms of structural diversity and empirically determine the best method to obtain diversity. We also conduct a comprehensive experimental investigation to examine the introduced algorithm and compare the results to another recently introduced framework based on the use of Quality Diversity (QD). Our experimental results show a significant improvement of the QD approach in terms of structural diversity for most TTP benchmark instances.