Evolutionary Diversity Optimisation for The Traveling Thief Problem
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversitySimilar Papers 제목 키워드 기반
Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem
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 exp…
DiversityOn the Use of Quality Diversity Algorithms for The Traveling Thief Problem
In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focus…
BenchmarkingDiversityOptimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
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) ad…
Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem
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…
DiversityThe Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (…