Open AccessApplication of genetic algorithm in solving the travelling Salesman problem
Author(s) -
Fatka Kulenović,
Azra Hošić
Publication year - 2021
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/1208/1/012032
Subject(s) - travelling salesman problem , genetic algorithm , selection (genetic algorithm) , mathematical optimization , algorithm , mutation , meta optimization , computer science , path (computing) , population based incremental learning , matlab , genetic operator , mathematics , 2 opt , artificial intelligence , biochemistry , chemistry , gene , programming language , operating system
The Travelling Salesman Problem is categorized as NP-complete problems called combinatorial optimization problems. For the growing number of cities it is unsolvable with the use of exact methods in a reasonable time. Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These methods do not ensure optimal solutions, however they give good approximation usually in time. Studies have shown that the proposed genetic algorithm can find a shorter route in real time, compared with the existing manipulator model of path selection. The genetic algorithm depends on the selection criteria, crosses, and mutation operators described in detail in this paper. Possible settings of the genetic algorithm are listed and described, as well as the influence of mutation and crossing operators on the efficiency of the genetic algorithm. The optimization results are presented graphically in the MATLAB software package for different cases, after which a comparison of the efficiency of the genetic algorithm with respect to the given parameters is performed.