Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem

Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith a set of solutions represented by a population of chromosomes and then uses the idea of survival of the fittest in the selection process to select some fitter chromosomes.It uses a crossover operator to create better offspring chromosomes and thus,converges the population.Also,it uses a mutation operator to explore the unexplored areas by the crossover operator,and thus,diversifies the GA search space.A combination of crossover and mutation operators makes the GA search strong enough to reach the optimal solution.However,appropriate selection and combination of crossover operator and mutation operator can lead to a very good GA for solving an optimization problem.In this present paper,we aim to study the benchmark traveling salesman problem(TSP).We developed several genetic algorithms using seven crossover operators and six mutation operators for the TSP and then compared them to some benchmark TSPLIB instances.The experimental studies show the effectiveness of the combination of a comprehensive sequential constructive crossover operator and insertion mutation operator for the problem.The GA using the comprehensive sequential constructive crossover with insertion mutation could find average solutions whose average percentage of excesses from the best-known solutions are between 0.22 and 14.94 for our experimented problem instances.

A Novel Insertion Solution for the Travelling Salesman Problem

The studypresents theHalfMax InsertionHeuristic (HMIH) as a novel approach to solving theTravelling SalesmanProblem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) andNearest Neighbour Heuristic (NNH). The paper discusses the limitations of current construction tour heuristics,focusing particularly on the significant margin of error in FIH. It then proposes HMIH as an alternative thatminimizes the increase in tour distance and includes more nodes. HMIH improves tour quality by starting withan initial tour consisting of a ‘minimum’ polygon and iteratively adding nodes using our novel Half Max routine.The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSPbenchmarks. The results indicate that HMIH consistently delivers superior performance, particularly with respectto tour cost and computational efficiency. HMIH’s tours were sometimes 16% shorter than those generated by FIHand NNH, showcasing its potential and value as a novel benchmark for TSP solutions. The study used statisticalmethods, including Friedman’s Non-parametric Test, to validate the performance of HMIH over FIH and NNH.This guarantees that the identified advantages are statistically significant and consistent in various situations. Thiscomprehensive analysis emphasizes the reliability and efficiency of the heuristic, making a compelling case for itsuse in solving TSP issues. The research shows that, in general, HMIH fared better than FIH in all cases studied,except for a few instances (pr439, eil51, and eil101) where FIH either performed equally or slightly better thanHMIH. HMIH’s efficiency is shown by its improvements in error percentage (δ) and goodness values (g) comparedto FIH and NNH. In the att48 instance, HMIH had an error rate of 6.3%, whereas FIH had 14.6% and NNH had20.9%, indicating that HMIH was closer to the optimal solution. HMIH consistently showed superior performanceacross many benchmarks, with lower percentage error and higher goodness values, suggesting a closer match tothe optimal tour costs. This study substantially contributes to combinatorial optimization by enhancing currentinsertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem. It also createsnew possibilities for progress in heuristic design and optimization methodologies.

On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem

The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. .

An Improved Farmland Fertility Algorithm with Hyper-Heuristic Approach for Solving Travelling Salesman Problem

Travelling Salesman Problem(TSP)is a discrete hybrid optimization problem considered NP-hard.TSP aims to discover the shortest Hamilton route that visits each city precisely once and then returns to the starting point,making it the shortest route feasible.This paper employed a Farmland Fertility Algorithm(FFA)inspired by agricultural land fertility and a hyper-heuristic technique based on the Modified Choice Function(MCF).The neighborhood search operator can use this strategy to automatically select the best heuristic method formaking the best decision.Lin-Kernighan(LK)local search has been incorporated to increase the efficiency and performance of this suggested approach.71 TSPLIB datasets have been compared with different algorithms to prove the proposed algorithm’s performance and efficiency.Simulation results indicated that the proposed algorithm outperforms comparable methods of average mean computation time,average percentage deviation(PDav),and tour length.

Use the Power of a Genetic Algorithm to Maximize and Minimize Cases to Solve Capacity Supplying Optimization and Travelling Salesman in Nested Problems

Using Genetic Algorithms (GAs) is a powerful tool to get solution to large scale design optimization problems. This paper used GA to solve complicated design optimization problems in two different applications. The aims are to implement the genetic algorithm to solve these two different (nested) problems, and to get the best or optimization solutions.

K-DSA for the multiple traveling salesman problem

Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.

A Scheme Library-Based Ant Colony Optimization with 2-Opt Local Search for Dynamic Traveling Salesman Problem

The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant colony optimization(ACO)with a two-optimization(2-opt)strategy to solve the DTSP efficiently.The work is novel and contributes to three aspects:problemmodel,optimization framework,and algorithmdesign.Firstly,in the problem model,traditional DTSP models often consider the change of travel distance between two nodes over time,while this paper focuses on a special DTSP model in that the node locations change dynamically over time.Secondly,in the optimization framework,the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment.The framework of offline optimization and online application is proposed due to the fact that the environmental change inDTSPis caused by the change of node location,and therefore the newenvironment is somehowsimilar to certain previous environments.This way,in the offline optimization,the solutions for possible environmental changes are optimized in advance,and are stored in a mode scheme library.In the online application,when an environmental change is detected,the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity.Thirdly,in the algorithm design,the ACO cooperates with the 2-opt strategy to enhance search efficiency.To evaluate the performance of ACO with 2-opt,we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms.The experimental results show that ACO with 2-opt can solve the DTSPs effectively.

Fast Algorithm for the Travelling Salesman Problem and the Proof of P = NP

In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for it with a polynomial time of biquadrate, which greatly reduces the computational complexity. Since this problem is also NP-complete, as a corollary, P = NP is proved to be true. It indicates the crack of the well-known open problem named “P versus NP”.

Using Data Mining to Find Patterns in Ant Colony Algorithm Solutions to the Travelling Salesman Problem

Travelling Salesman Problem(TSP) is a classical optimization problem and it is one of a class of NP-Problem.The purposes of this work is to apply data mining methodologies to explore the patterns in data generated by an Ant Colony Algorithm(ACA) performing a searching operation and to develop a rule set searcher which approximates the ACA′s searcher.An attribute-oriented induction methodology was used to explore the relationship between an operations′ sequence and its attributes and a set of rules has been developed.At the end of this paper,the experimental results have shown that the proposed approach has good performance with respect to the quality of solution and the speed of computation.

求解TSP的离散野马优化算法

针对求解TSP问题,提出一种新的元启发式算法离散野马优化算法(DWHO),应用最小位置匹配值法(MPMV)对求解结果进行离散化解码;为提高算法搜索能力,结合野马放牧、交配、领导者交流与选拔行为,引入变邻域搜索策略,增强了算法的局部搜索能力、加快算法收敛速度。选取TSPLIB标准库33个算例进行实验,并与交换序列人工蜂群算法(ABCSS)、离散蜘蛛猴优化算法(DSMO)两种算法进行比较。实验结果表明,DWHO求得的最优解与ABCSS、DSMO两种算法的最优解相比,最优解改进率最大值分别达到4.52%和3.41%。同时,将离散野马优化算法求解TSP收敛速度与以上两种算法进行比较,其收敛速度具有一定的优势。结果表明离散野马优化算法求解能力和精度具有优势。

A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery

In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization （ACO） is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem （TSP） is among the most important combinato- rial problems. An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature con- vergence problem of the basic ACO algorithm on TSP. The main idea is to partition artificial ants into two groups： scout ants and common ants. The common ants work according to the search manner of basic ant colony algorithm, but scout ants have some differences from common ants, they calculate each route＇s muta- tion probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability. Simulation on TSP shows that the improved algorithm has high efficiency and robustness.

基于信息熵的改进蚁群算法求解TSP问题

针对蚁群算法求解精度低、易陷入局部最优的缺点,提出一种基于信息熵的自适应改进蚁群算法。通过算法自身特性定义结合熵值对种群参数进行自适应优化;采用分组合作的信息素更新策略,通过较活跃性个体引导整个种群,扩大搜索范围;通过对较优路径的奖励,平衡收敛速度和搜索范围之间的关系;在种群信息熵过低时,加入局部搜索策略,进一步提高算法精度。实验结果表明,相较于蚁群算法,改进算法具有较好的求解精度以及跳出局部最优的能力。

Traveling Salesman Problem Using an Enhanced Hybrid Swarm Optimization Algorithm

The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.

Collision-free Scheduling of Multi-bridge Machining Systems： A Colored Traveling Salesman Problem-based Approach

Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.

The Quantum Approximate Algorithm for Solving Traveling Salesman Problem

The Quantum Approximate Optimization Algorithm(QAOA)is an algorithmic framework for finding approximate solutions to combinatorial optimization problems.It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians.To fit this framework,one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians.In this paper,for the well-known NP-hard Traveling Salesman Problem(TSP),we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian.Moreover,we map edges(routes)connecting each pair of cities to qubits,which decreases the search space significantly in comparison to other approaches.As a result,our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach.We argue the formalization approach presented in this paper would lead to a generalized framework for finding,in the context of QAOA,high-quality approximate solutions to NP optimization problems.

Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey

The Traveling Salesman Problem (TSP) and its allied problems like Vehicle Routing Problem (VRP) are one of the most widely studied problems in combinatorial optimization. It has long been known to be NP-hard and hence research on developing algorithms for the TSP has focused on approximate methods in addition to exact methods. Tabu search is one of the most widely applied metaheuristic for solving the TSP. In this paper, we review the tabu search literature on the TSP and its variations, point out trends in it, and bring out some interesting research gaps in this literature.

ISPO: A New Way to Solve Traveling Salesman Problem

This paper first introduces the concepts of mobile operators and mobile sequence, with which it redefines the rate of particle swarm optimization algorithm and the formula of position updating. Combining this discrete PSO algorithm with neighbors, the paper puts forward Hybrd Particle Swarm Optimization Algorithm, whose effectiveness is verified at the end of this paper.

Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization(DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt(C2-opt) algorithm to enhance the local search ability.Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization(PDLSO) algorithm is proposed.The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

基于蚁群算法的Traveling Salesman Problem研究

本文介绍了一种求解复杂组合优化问题的新的拟生态算法——蚁群算法.阐述了该算法的基本原理以及蚁群算法在TSP问题上的应用,并提出了改进算法,使得算法有更好的全局性.