Cite Article

Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem

Choose citation format

BibTeX

@article{IJASEIT4867,
   author = {Velin Kralev},
   title = {Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem},
   journal = {International Journal on Advanced Science, Engineering and Information Technology},
   volume = {8},
   number = {3},
   year = {2018},
   pages = {762--770},
   keywords = {travelling salesman problem; genetic algorithm; crossover; mutation},
   abstract = {

This paper presents the results of an analysis of three algorithms for the Travelling Salesman Problem (TSP). The basic steps of genetic algorithms (GAs) and their benefits in solving combinatorial optimization problems are also presented. Moreover, several studies related to TPS and some approaches to its solution are discussed. An optimized version of the standard recursive algorithm for solving TSP using the backtracking method is presented. This algorithm is used to generate optimal solutions concerning the studied graphs. In addition, a standard genetic algorithm for solving TSP and its modification are also presented. The modified algorithm uses the genetic operator mutation in a different way. The results show that the recursive algorithm can be used successfully to solve the TSP for graphs with a small number of vertices, for instance, 25-30. The results of the two GAs were different. The modified GA found the optimal solutions for all tested graphs, while the standard GA found the optimal solutions in only 40% of the cases. These results were obtained for a reasonable time (in seconds), with appropriate values of the control parameters - population size and reproduction number. It appeared that the use of the genetic mutation operator yields better results when applied to identical solutions. If pairs of identical solutions are found in a population, then every second must mutate. The methodology and the conditions for conducting the experiments are described in details.

},    issn = {2088-5334},    publisher = {INSIGHT - Indonesian Society for Knowledge and Human Development},    url = {http://ijaseit.insightsociety.org/index.php?option=com_content&view=article&id=9&Itemid=1&article_id=4867},    doi = {10.18517/ijaseit.8.3.4867} }

EndNote

%A Kralev, Velin
%D 2018
%T Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem
%B 2018
%9 travelling salesman problem; genetic algorithm; crossover; mutation
%! Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem
%K travelling salesman problem; genetic algorithm; crossover; mutation
%X 

This paper presents the results of an analysis of three algorithms for the Travelling Salesman Problem (TSP). The basic steps of genetic algorithms (GAs) and their benefits in solving combinatorial optimization problems are also presented. Moreover, several studies related to TPS and some approaches to its solution are discussed. An optimized version of the standard recursive algorithm for solving TSP using the backtracking method is presented. This algorithm is used to generate optimal solutions concerning the studied graphs. In addition, a standard genetic algorithm for solving TSP and its modification are also presented. The modified algorithm uses the genetic operator mutation in a different way. The results show that the recursive algorithm can be used successfully to solve the TSP for graphs with a small number of vertices, for instance, 25-30. The results of the two GAs were different. The modified GA found the optimal solutions for all tested graphs, while the standard GA found the optimal solutions in only 40% of the cases. These results were obtained for a reasonable time (in seconds), with appropriate values of the control parameters - population size and reproduction number. It appeared that the use of the genetic mutation operator yields better results when applied to identical solutions. If pairs of identical solutions are found in a population, then every second must mutate. The methodology and the conditions for conducting the experiments are described in details.

%U http://ijaseit.insightsociety.org/index.php?option=com_content&view=article&id=9&Itemid=1&article_id=4867 %R doi:10.18517/ijaseit.8.3.4867 %J International Journal on Advanced Science, Engineering and Information Technology %V 8 %N 3 %@ 2088-5334

IEEE

Velin Kralev,"Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem," International Journal on Advanced Science, Engineering and Information Technology, vol. 8, no. 3, pp. 762-770, 2018. [Online]. Available: http://dx.doi.org/10.18517/ijaseit.8.3.4867.

RefMan/ProCite (RIS)

TY  - JOUR
AU  - Kralev, Velin
PY  - 2018
TI  - Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem
JF  - International Journal on Advanced Science, Engineering and Information Technology; Vol. 8 (2018) No. 3
Y2  - 2018
SP  - 762
EP  - 770
SN  - 2088-5334
PB  - INSIGHT - Indonesian Society for Knowledge and Human Development
KW  - travelling salesman problem; genetic algorithm; crossover; mutation
N2  - 

This paper presents the results of an analysis of three algorithms for the Travelling Salesman Problem (TSP). The basic steps of genetic algorithms (GAs) and their benefits in solving combinatorial optimization problems are also presented. Moreover, several studies related to TPS and some approaches to its solution are discussed. An optimized version of the standard recursive algorithm for solving TSP using the backtracking method is presented. This algorithm is used to generate optimal solutions concerning the studied graphs. In addition, a standard genetic algorithm for solving TSP and its modification are also presented. The modified algorithm uses the genetic operator mutation in a different way. The results show that the recursive algorithm can be used successfully to solve the TSP for graphs with a small number of vertices, for instance, 25-30. The results of the two GAs were different. The modified GA found the optimal solutions for all tested graphs, while the standard GA found the optimal solutions in only 40% of the cases. These results were obtained for a reasonable time (in seconds), with appropriate values of the control parameters - population size and reproduction number. It appeared that the use of the genetic mutation operator yields better results when applied to identical solutions. If pairs of identical solutions are found in a population, then every second must mutate. The methodology and the conditions for conducting the experiments are described in details.

UR - http://ijaseit.insightsociety.org/index.php?option=com_content&view=article&id=9&Itemid=1&article_id=4867 DO - 10.18517/ijaseit.8.3.4867

RefWorks

RT Journal Article
ID 4867
A1 Kralev, Velin
T1 Different Applications of the Genetic Mutation Operator for Symetric Travelling Salesman Problem
JF International Journal on Advanced Science, Engineering and Information Technology
VO 8
IS 3
YR 2018
SP 762
OP 770
SN 2088-5334
PB INSIGHT - Indonesian Society for Knowledge and Human Development
K1 travelling salesman problem; genetic algorithm; crossover; mutation
AB 

This paper presents the results of an analysis of three algorithms for the Travelling Salesman Problem (TSP). The basic steps of genetic algorithms (GAs) and their benefits in solving combinatorial optimization problems are also presented. Moreover, several studies related to TPS and some approaches to its solution are discussed. An optimized version of the standard recursive algorithm for solving TSP using the backtracking method is presented. This algorithm is used to generate optimal solutions concerning the studied graphs. In addition, a standard genetic algorithm for solving TSP and its modification are also presented. The modified algorithm uses the genetic operator mutation in a different way. The results show that the recursive algorithm can be used successfully to solve the TSP for graphs with a small number of vertices, for instance, 25-30. The results of the two GAs were different. The modified GA found the optimal solutions for all tested graphs, while the standard GA found the optimal solutions in only 40% of the cases. These results were obtained for a reasonable time (in seconds), with appropriate values of the control parameters - population size and reproduction number. It appeared that the use of the genetic mutation operator yields better results when applied to identical solutions. If pairs of identical solutions are found in a population, then every second must mutate. The methodology and the conditions for conducting the experiments are described in details.

LK http://ijaseit.insightsociety.org/index.php?option=com_content&view=article&id=9&Itemid=1&article_id=4867 DO - 10.18517/ijaseit.8.3.4867