CSRX: A novel Crossover Operator for a Genetic Algorithm applied to the Traveling Salesperson Problem

• URL: http://arxiv.org/abs/2303.12447v2
• Date: Tue, 9 Jan 2024 12:53:38 GMT
• Title: CSRX: A novel Crossover Operator for a Genetic Algorithm applied to the Traveling Salesperson Problem
• Authors: Martin Uray, Stefan Wintersteller, Stefan Huber
• Abstract summary: We introduce a family of novel crossover operators that outperform the previous state of the art. The novel crossover operators aim to exploit symmetries in the solution space, which allows us to more effectively preserve well-performing individuals.
• Score: 0.9208007322096533
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we revisit the application of Genetic Algorithm (GA) to the Traveling Salesperson Problem (TSP) and introduce a family of novel crossover operators that outperform the previous state of the art. The novel crossover operators aim to exploit symmetries in the solution space, which allows us to more effectively preserve well-performing individuals, namely the fitness invariance to circular shifts and reversals of solutions. These symmetries are general and not limited to or tailored to TSP specifically.

Related papers

• A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem [0.0]
  This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a self-adaptive genetic algorithm. In FSTSP, optimisation is to minimise the total time to visit all locations while strategically deploying a drone to serve hard-to-reach customer locations.
  arXiv  Detail & Related papers  (2023-10-23T08:51:02Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• On High-dimensional and Low-rank Tensor Bandits [53.0829344775769]
  This work studies a general tensor bandits model, where actions and system parameters are represented by tensors as opposed to vectors. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face of Uncertainty), is developed. Theoretical analyses show that TOFU improves the best-known regret upper bound by a multiplicative factor that grows exponentially in the system order.
  arXiv  Detail & Related papers  (2023-05-06T00:43:36Z)
• 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)
• A New Lagrangian Problem Crossover: A Systematic Review and Meta-Analysis of Crossover Standerds [1.1802674324027231]
  This paper presents an overview of crossover standards classification. The significance of novel standard crossover is proposed depending on Lagrangian Dual Function (LDF) The accuracy and performance of the proposed standard have evaluated by three unimodal test functions.
  arXiv  Detail & Related papers  (2022-04-21T15:50:02Z)
• Improvements for mlrose applied to the Traveling Salesperson Problem [0.7499722271664147]
  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.
  arXiv  Detail & Related papers  (2021-09-29T12:54:09Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Tip the Balance: Improving Exploration of Balanced Crossover Operators by Adaptive Bias [2.610470075814367]
  The use of balanced crossover operators in Genetic Algorithms (GA) ensures that the binary strings generated as offsprings have the same Hamming weight of the parents. Although this method reduces the size of the search space, the resulting fitness landscape often becomes more difficult for the GA to explore. This issue has been studied in this paper by applying an adaptive bias strategy to a counter-based crossover operator.
  arXiv  Detail & Related papers  (2020-04-23T17:26:43Z)
• A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
  Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design. In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
  arXiv  Detail & Related papers  (2020-03-02T00:37:36Z)
• New mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem [2.578242050187029]
  We propose two new crossover operators and new mechanism of combination crossover operators in genetic algorithm for solving TSP. Experimental results show that, our proposed algorithm is better than the Genetic algorithm (GA) using MSCX on the min, mean cost values.
  arXiv  Detail & Related papers  (2020-01-14T13:20:44Z)
• Domain Adaptation: Learning Bounds and Algorithms [80.85426994513541]
  We introduce a novel distance between distributions, discrepancy distance, that is tailored to adaptation problems with arbitrary loss functions. We derive novel generalization bounds for domain adaptation for a wide family of loss functions. We also present a series of novel adaptation bounds for large classes of regularization-based algorithms.
  arXiv  Detail & Related papers  (2009-02-19T18:42:16Z)

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.