New mechanism of combination crossover operators in genetic algorithm
for solving the traveling salesman problem
- URL: http://arxiv.org/abs/2001.11590v1
- Date: Tue, 14 Jan 2020 13:20:44 GMT
- Title: New mechanism of combination crossover operators in genetic algorithm
for solving the traveling salesman problem
- Authors: Pham Dinh Thanh, Huynh Thi Thanh Binh, Bui Thu Lam
- Abstract summary: 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.
- Score: 2.578242050187029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Traveling salesman problem (TSP) is a well-known in computing field. There
are many researches to improve the genetic algorithm for solving TSP. In this
paper, we propose two new crossover operators and new mechanism of combination
crossover operators in genetic algorithm for solving TSP. We experimented on
TSP instances from TSP-Lib and compared the results of proposed algorithm with
genetic algorithm (GA), which used MSCX. Experimental results show that, our
proposed algorithm is better than the GA using MSCX on the min, mean cost
values.
Related papers
- Deep Learning-Based Operators for Evolutionary Algorithms [1.7751300245073598]
We present two novel domain-independent genetic operators that harness the capabilities of deep learning: a crossover operator for genetic algorithms and a mutation operator for genetic programming.
arXiv Detail & Related papers (2024-07-15T07:05:34Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties.
We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
arXiv Detail & Related papers (2023-10-18T10:29:58Z) - Modified LAB Algorithm with Clustering-based Search Space Reduction
Method for solving Engineering Design Problems [0.7789406630452325]
A modified LAB algorithm is introduced in this paper.
The proposed algorithm incorporates the roulette wheel approach and a reduction factor introducing inter-group competition.
The algorithm exhibited improved and superior robustness as well as search space exploration capabilities.
arXiv Detail & Related papers (2023-10-04T12:35:13Z) - Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic
Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
Genetic Algorithms (GAs) are known for their efficiency in solving optimization problems.
This paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts.
arXiv Detail & Related papers (2023-09-28T13:05:30Z) - A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman
Problem [0.9790236766474201]
This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP)
A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population.
Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against benchmark sets.
arXiv Detail & Related papers (2023-07-14T01:57:10Z) - CSRX: A novel Crossover Operator for a Genetic Algorithm applied to the
Traveling Salesperson Problem [0.9208007322096533]
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.
arXiv Detail & Related papers (2023-03-22T10:34:23Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
Bilevel optimization has been applied to a wide variety of machine learning models.
Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data.
We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
arXiv Detail & Related papers (2022-06-30T05:29:52Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm.
We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights.
We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
arXiv Detail & Related papers (2020-10-13T08:02:38Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
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.