Optimization of Travel Salesman Problem (TSP) Using Genetic Algorithms

Session

Computer Science and Communication Engineering

Description

The traveling salesman problem (TSP) is one of the most famous benchmarks, significant, historic, and very hard combinatorial optimization problem. TSP was documented by Euler in 1759, whose interest was in solving the knight’s tour problem [1]. It is the fundamental problem in the fields of computer science, engineering, operations research, discrete mathematics, graph theory, and so forth. TSP can be described as the minimization of the total distance traveled by touring all cities exactly once and return to depot city. The traveling salesman problems (TSPs) are classified into two groups on the basis of the structure of the distance matrix as symmetric and asymmetric. The TSP is symmetric if , cij = cji, where i and j represent the row and column of a distance (cost) matrix, respectively, otherwise is asymmetric. To tackle the traveling salesman problem we used genetic algorithms. Genetic algorithms (GAs) are a heuristic search and optimization technique inspired by natural evolution. They have been successfully applied to a wide range of real-world problems of significant complexity. Genetic algorithms are evolutionary techniques used for optimization purposes according to the survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for difficult problems, especially the traveling salesman problem. The genetic algorithm depends on the initialization approach, selection criteria, crossover, and mutation operators. There are various representations such as binary, path, adjacency, ordinal, and matrix representations. This project aims to minimize the distance traveled by a hypothetical salesperson. By giving a list of cities and the distance between each pair of cities, finding the shortest path to visit all cities and return to the initial city. Genetic algorithms (GAs) are derivative-free stochastic approach based on biological evolutionary processes proposed by Holland [2]. In nature, the most suitable individuals are likely to survive and mate; therefore, the next generation should be healthier and fitter than previous one. A lot of work and applications have been done about GAs in a frequently cited book by Golberg [3]. GAs work with population of chromosomes that are represented by some underlying parameters set codes.

Keywords:

TSP, GAs, Genetic Operators, Selection Policies

Session Chair

Bertan Karahoda

Session Co-Chair

Besnik Qehaja

Proceedings Editor

Edmond Hajrizi

ISBN

978-9951-437-96-7

Location

Lipjan, Kosovo

Start Date

31-10-2020 10:45 AM

End Date

31-10-2020 12:30 PM

DOI

10.33107/ubt-ic.2020.517

This document is currently not available here.

Share

COinS
 
Oct 31st, 10:45 AM Oct 31st, 12:30 PM

Optimization of Travel Salesman Problem (TSP) Using Genetic Algorithms

Lipjan, Kosovo

The traveling salesman problem (TSP) is one of the most famous benchmarks, significant, historic, and very hard combinatorial optimization problem. TSP was documented by Euler in 1759, whose interest was in solving the knight’s tour problem [1]. It is the fundamental problem in the fields of computer science, engineering, operations research, discrete mathematics, graph theory, and so forth. TSP can be described as the minimization of the total distance traveled by touring all cities exactly once and return to depot city. The traveling salesman problems (TSPs) are classified into two groups on the basis of the structure of the distance matrix as symmetric and asymmetric. The TSP is symmetric if , cij = cji, where i and j represent the row and column of a distance (cost) matrix, respectively, otherwise is asymmetric. To tackle the traveling salesman problem we used genetic algorithms. Genetic algorithms (GAs) are a heuristic search and optimization technique inspired by natural evolution. They have been successfully applied to a wide range of real-world problems of significant complexity. Genetic algorithms are evolutionary techniques used for optimization purposes according to the survival of the fittest idea. These methods do not ensure optimal solutions; however, they give good approximation usually in time. The genetic algorithms are useful for difficult problems, especially the traveling salesman problem. The genetic algorithm depends on the initialization approach, selection criteria, crossover, and mutation operators. There are various representations such as binary, path, adjacency, ordinal, and matrix representations. This project aims to minimize the distance traveled by a hypothetical salesperson. By giving a list of cities and the distance between each pair of cities, finding the shortest path to visit all cities and return to the initial city. Genetic algorithms (GAs) are derivative-free stochastic approach based on biological evolutionary processes proposed by Holland [2]. In nature, the most suitable individuals are likely to survive and mate; therefore, the next generation should be healthier and fitter than previous one. A lot of work and applications have been done about GAs in a frequently cited book by Golberg [3]. GAs work with population of chromosomes that are represented by some underlying parameters set codes.