Published on Mon Apr 29 2013

A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem

Xiaolin Tang, Chunhua Yang, Xiaojun Zhou, Weihua Gui

Generalized traveling salesman problem (GTSP) is a combinatorial optimization problem. An efficient discrete state transition algorithm (DSTA) for GTSP is proposed. DSTA has better search ability than its competitors.

0
0
0
Abstract

Generalized traveling salesman problem (GTSP) is an extension of classical traveling salesman problem (TSP), which is a combinatorial optimization problem and an NP-hard problem. In this paper, an efficient discrete state transition algorithm (DSTA) for GTSP is proposed, where a new local search operator named \textit{K-circle}, directed by neighborhood information in space, has been introduced to DSTA to shrink search space and strengthen search ability. A novel robust update mechanism, restore in probability and risk in probability (Double R-Probability), is used in our work to escape from local minima. The proposed algorithm is tested on a set of GTSP instances. Compared with other heuristics, experimental results have demonstrated the effectiveness and strong adaptability of DSTA and also show that DSTA has better search ability than its competitors.

Wed Sep 10 2014
Neural Networks
An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem
The Traveling salesman problem (TSP) is proved to be NP-complete in most cases. The genetic algorithm (GA) is one of the most useful algorithms for solving this problem. In this paper a conventional GA is compared with an improved hybrid GA.
0
0
0
Wed Feb 19 2014
Neural Networks
A Powerful Genetic Algorithm for Traveling Salesman Problem
This paper presents a powerful genetic algorithm(GA) to solve the traveling salesman problem (TSP) To construct a powerful GA, I use edge swapping(ES) with a local search procedure.
0
0
0
Thu Aug 04 2016
Artificial Intelligence
A Polynomial-Time Deterministic Approach to the Traveling Salesperson Problem
Proposed algorithm ranks cities based on their priorities calculated using a power function. It then connects the cities to their neighbors in the order of their priorities. The time complexity of the proposed algorithm is , where is the number of cities.
0
0
0
Fri Jun 05 2020
Neural Networks
Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. A new problem has been introduced where nodes have weights that influence the cost of the tour. The W-TSP often can be solved better using the TTP fitness function.
0
0
0
Thu Jun 30 2011
Artificial Intelligence
Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
In recent years, there has been much interest in phase transitions of combinatorial problems. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem. We empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp
0
0
0
Wed Dec 21 2016
Neural Networks
Stochastic Runtime Analysis of a Cross Entropy Algorithm for Traveling Salesman Problems
This article analyzes the stochastic runtime of a Cross-Entropy Algorithm on two classes of traveling salesman problems. The algorithm shares main features of the famous Max-Min Ant System with iteration-best reinforcement. For simple instances that have a -valued distance function and aunique optimal solution, we prove a stochastically runtime of for an edge-based random solution generation.
0
0
0