On 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 focusing on only one component. The traveling thief problem~(TTP) belongs to this category and is formed by the integration of the traveling salesperson problem~(TSP) and the knapsack problem~(KP). In this paper, we investigate the inter-dependency of the TSP and the KP by means of quality diversity~(QD) approaches. QD algorithms provide a powerful tool not only to obtain high-quality solutions but also to illustrate the distribution of high-performing solutions in the behavioural space. We introduce a MAP-Elite based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as the behavioural descriptor. Afterwards, we conduct comprehensive experimental studies that show the usefulness of using the QD approach applied to the TTP. First, we provide insights regarding high-quality TTP solutions in the TSP/KP behavioural space. Afterwards, we show that better solutions for the TTP can be obtained by using our QD approach and it can improve the best-known solution for a number of TTP instances used for benchmarking in the literature.
Code (0)
등록된 구현이 없습니다.
Tasks
BenchmarkingDiversityMethods 이 논문이 사용한 방법론
Similar 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…
DiversityLeveraging Symbolic Regression for Heuristic Design in the Traveling Thief Problem
The Traveling Thief Problem is an NP-hard combination of the well known traveling salesman and knapsack packing problems. In this paper, we use symbolic regression to learn useful features of near-optimal packing plans, …
regressionSymbolic RegressionEvolutionary 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 informat…
DiversityA case study of algorithm selection for the traveling thief problem
Many real-world problems are composed of several interacting components. In order to facilitate research on such interactions, the Traveling Thief Problem (TTP) was created in 2013 as the combination of two well-understo…
Combinatorial OptimizationA weighted-sum method for solving the bi-objective traveling thief problem
Many real-world optimization problems have multiple interacting components. Each of these can be NP-hard and they can be in conflict with each other, i.e., the optimal solution for one component does not necessarily repr…