On the Use of Quality Diversity Algorithms for The Traveling Thief Problem

• URL: http://arxiv.org/abs/2112.08627v4
• Date: Wed, 4 Jan 2023 00:54:29 GMT
• Title: On the Use of Quality Diversity Algorithms for The Traveling Thief Problem
• Authors: Adel Nikfarjam, Aneta Neumann, and Frank Neumann
• Abstract summary: In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. In this paper, we investigate the inter-dependency of the traveling salesperson problem(TSP) and the knapsack problem(KP) by means of quality diversity(QD) approaches.
• Score: 11.590506672325668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models. TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
  arXiv  Detail & Related papers  (2023-10-06T01:40:09Z)
• Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
  We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions. Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
  arXiv  Detail & Related papers  (2023-10-02T11:24:36Z)
• On Pitfalls of Test-Time Adaptation [82.8392232222119]
  Test-Time Adaptation (TTA) has emerged as a promising approach for tackling the robustness challenge under distribution shifts. We present TTAB, a test-time adaptation benchmark that encompasses ten state-of-the-art algorithms, a diverse array of distribution shifts, and two evaluation protocols.
  arXiv  Detail & Related papers  (2023-06-06T09:35:29Z)
• Benchmarking the Reliability of Post-training Quantization: a Particular Focus on Worst-case Performance [53.45700148820669]
  Post-training quantization (PTQ) is a popular method for compressing deep neural networks (DNNs) without modifying their original architecture or training procedures. Despite its effectiveness and convenience, the reliability of PTQ methods in the presence of some extrem cases such as distribution shift and data noise remains largely unexplored. This paper first investigates this problem on various commonly-used PTQ methods.
  arXiv  Detail & Related papers  (2023-03-23T02:55:50Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) Common to these approaches is the use of graph models based on multi-head attention layers.
  arXiv  Detail & Related papers  (2022-07-04T14:31:47Z)
• Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation [8.620967398331265]
  The Travelling Thief Problem (TTP) is a challenging optimization problem that attracts many scholars. In this paper, TTP is investigated theoretically and empirically. An algorithm based on the score value calculated by our proposed formulation in picking items and sorting items in the reverse order is proposed to solve the problem.
  arXiv  Detail & Related papers  (2020-12-16T12:06:05Z)
• Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
  The Traveling Thief Problem (TTP) addresses such interactions by combining two optimisation problems. A new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function.
  arXiv  Detail & Related papers  (2020-06-05T07:07:28Z)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components. Recent state-of-the-art TTP solvers modify the underlying TTP and KP solutions in an iterative and interleaved fashion. We propose to make the search more efficient through an adaptive surrogate model that learns the characteristics of initial TSP tours that lead to good TTP solutions.
  arXiv  Detail & Related papers  (2020-05-14T02:49:16Z)
• A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm for the Bi-Objective Traveling Thief Problem [7.088487500434561]
  We propose a method to solve a bi-objective variant of the well-studied Traveling Thief Problem (TTP) We address the BI-TTP, where the goal is to minimize the overall traveling time and to maximize the profit of the collected items. Our proposed method is based on a biased-random key genetic algorithm with customizations addressing problem-specific characteristics.
  arXiv  Detail & Related papers  (2020-02-11T10:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.