Surrogate Assisted Optimisation for Travelling Thief Problems
- URL: http://arxiv.org/abs/2005.06695v1
- Date: Thu, 14 May 2020 02:49:16 GMT
- Title: Surrogate Assisted Optimisation for Travelling Thief Problems
- Authors: Majid Namazi, Conrad Sanderson, M.A. Hakim Newton, Abdul Sattar
- Abstract summary: 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.
- Score: 14.836145520657592
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The travelling thief problem (TTP) is a multi-component optimisation problem
involving two interdependent NP-hard components: the travelling salesman
problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP
solvers modify the underlying TSP and KP solutions in an iterative and
interleaved fashion. The TSP solution (cyclic tour) is typically changed in a
deterministic way, while changes to the KP solution typically involve a random
search, effectively resulting in a quasi-meandering exploration of the TTP
solution space. Once a plateau is reached, the iterative search of the TTP
solution space is restarted by using a new initial TSP tour. We propose to make
the search more efficient through an adaptive surrogate model (based on a
customised form of Support Vector Regression) that learns the characteristics
of initial TSP tours that lead to good TTP solutions. The model is used to
filter out non-promising initial TSP tours, in effect reducing the amount of
time spent to find a good TTP solution. Experiments on a broad range of
benchmark TTP instances indicate that the proposed approach filters out a
considerable number of non-promising initial tours, at the cost of omitting
only a small number of the best TTP solutions.
Related papers
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
This paper develops a learning method for a special class of traveling salesman problems (TSP)
It finds the shortest tour along a sequence of one-to-one pickup-and-delivery nodes.
In PDTSP, precedence constraints need to be satisfied that each pickup node must be visited before its corresponding delivery node.
arXiv Detail & Related papers (2024-04-17T15:05:51Z) - Semi-Supervised Coupled Thin-Plate Spline Model for Rotation Correction and Beyond [84.56978780892783]
We propose CoupledTPS, which iteratively couples multiple TPS with limited control points into a more flexible and powerful transformation.
In light of the laborious annotation cost, we develop a semi-supervised learning scheme to improve warping quality by exploiting unlabeled data.
Experiments demonstrate the superiority and universality of CoupledTPS over the existing state-of-the-art solutions for rotation correction.
arXiv Detail & Related papers (2024-01-24T13:03:28Z) - 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) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics.
Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency.
We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
arXiv Detail & Related papers (2023-04-19T03:48:32Z) - Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions.
Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem.
In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
arXiv Detail & Related papers (2022-11-02T14:35:13Z) - 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) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
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.
arXiv Detail & Related papers (2021-12-16T05:08:39Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications.
There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints.
We show that PDD-SSCA can achieve superior performance over existing solutions.
arXiv Detail & Related papers (2021-05-05T03:36:00Z) - 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) - 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.