Improvements for mlrose applied to the Traveling Salesperson Problem
- URL: http://arxiv.org/abs/2109.14392v3
- Date: Mon, 15 Apr 2024 13:09:34 GMT
- Title: Improvements for mlrose applied to the Traveling Salesperson Problem
- Authors: Stefan Wintersteller, Martin Uray, Michael Lehenauer, Stefan Huber,
- Abstract summary: We discuss the application of Artificial Intelligence (AI) to the exemplary industrial use case of the two-dimensional commissioning problem in a high-bay storage.
Our focus is on two methods, namely Genetic Algorithm (GA) and Hill Climbing (HC), which are provided by mlrose.
We present improvements for both methods that yield shorter tour lengths, by moderately exploiting the problem structure of the Traveling Salesperson Problem.
- Score: 0.7499722271664147
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper we discuss the application of Artificial Intelligence (AI) to the exemplary industrial use case of the two-dimensional commissioning problem in a high-bay storage, which essentially can be phrased as an instance of Traveling Salesperson Problem (TSP). We investigate the mlrose library that provides an TSP optimizer based on various heuristic optimization techniques. Our focus is on two methods, namely Genetic Algorithm (GA) and Hill Climbing (HC), which are provided by mlrose. We present improvements for both methods that yield shorter tour lengths, by moderately exploiting the problem structure of TSP. That is, the proposed improvements have a generic character and are not limited to TSP only.
Related papers
- CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
Solving Traveling Salesman Problem [4.190087134771218]
This paper introduces CARSS, a novel approach to address the Traveling Salesman Problem (TSP)
CARSS decomposes the TSP solving process into two distinct yet synergistic steps: "subpath generation" and "subpath merging"
Empirical experiments reveal CARSS's superiority compared to single-agent alternatives.
arXiv Detail & Related papers (2023-12-24T05:25:43Z) - Online Multi-Task Learning with Recursive Least Squares and Recursive Kernel Methods [50.67996219968513]
We introduce two novel approaches for Online Multi-Task Learning (MTL) Regression Problems.
We achieve exact and approximate recursions with quadratic per-instance cost on the dimension of the input space.
We compare our online MTL methods to other contenders in a real-world wind speed forecasting case study.
arXiv Detail & Related papers (2023-08-03T01:41:34Z) - 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) - 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) - Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods.
This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
arXiv Detail & Related papers (2021-03-23T20:46:20Z) - Robust Optimal Transport with Applications in Generative Modeling and
Domain Adaptation [120.69747175899421]
Optimal Transport (OT) distances such as Wasserstein have been used in several areas such as GANs and domain adaptation.
We propose a computationally-efficient dual form of the robust OT optimization that is amenable to modern deep learning applications.
Our approach can train state-of-the-art GAN models on noisy datasets corrupted with outlier distributions.
arXiv Detail & Related papers (2020-10-12T17:13:40Z) - Solving the Clustered Traveling Salesman Problem via TSP methods [16.304413942851397]
The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP)
In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP.
arXiv Detail & Related papers (2020-07-10T08:56:06Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching.
We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
arXiv Detail & Related papers (2020-06-10T15:00:09Z)
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.