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

Velin Kralev

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.


Keywords


travelling salesman problem; genetic algorithm; crossover; mutation

Full Text:

PDF

References


Y. Wang, “A genetic algorithm with the mixed heuristics for traveling salesman problem,†International Journal of Computational Intelligence and Applications, vol. 14(1), pp. 33–46, Mar. 2015.

W. R. Alkhayri, S. S. Owais, and M. Shkoukani, "A New Selection Operator - CSM in Genetic Algorithms for Solving the TSP," International Journal of Advanced Computer Science and Applications, vol. 7(10), pp. 62-66, Oct. 2016.

M. Yamada, "1/f Noise in the Simple Genetic Algorithm Applied to a Traveling Salesman Problem," Fluctuation and Noise Letters, vol. 16(3), 1750026, Sep. 2017.

S. Meneses, R. Cueva, M. Tupia, Manuel, and M. Guanira, "A genetic algorithm to solve 3D traveling salesman problem with initial population based on a GRASP algorithm," Journal of Computational Methods in Sciences and Engineering, vol. 17(S1), pp. S1-S10, Jan. 2017.

J. Wang, O. K. Ersoy, M. He, and F. Wang, "Multi-offspring genetic algorithm and its application to the traveling salesman problem," Applied Soft Computing, vol. 43, pp. 415-423, Jun. 2016.

S. Maity, A. Roy, and M. Maiti, "A Modified Genetic Algorithm for solving uncertain Constrained Solid Travelling Salesman Problems," Computers & Industrial Engineering, vol. 83, pp. 273-296, May 2015.

P. V. Paul, N. Moganarangan, S. Sampath Kumar, R. Raju, T. Vengattaraman, and P. Dhavachelvan, "Performance analyses over population seeding techniques of the permutation-coded genetic algorithm: An empirical study based on traveling salesman problems," Applied Soft Computing, vol. 32, pp. 383-402, Jul. 2015.

V. Kralev and R. Kraleva, "A Local Search Algorithm Based on Chromatic Classes for University Course Timetabling Problem,"International Journal of Advanced Research in Computer Science, vol. 7(28), pp. 1-7, Jan. 2017.

M. Traykov, S. Angelov, and N. Yanev, "A New Heuristic Algorithm for Protein Folding in the HP Model," Journal of Computational Biology, vol. 23(8), pp. 662-668, Aug. 2016.

V. Kralev, R. Kraleva, and B. Yurukov, "An event grouping based algorithm for university course timetabling problem," International Journal of Computer Science and Information Security, vol. 14(6), pp. 222-229, Jun. 2016.

V. Kralev, "A genetic and memetic algorithm for solving the university course timetabling problem," International Journal "Information Theories & Applications, vol. 16(3), pp. 291-299, 2009.

V. Vladimirov, F. Sapundzhi, R. Kraleva, and V. Kralev, “Modified Genetic Algorithm to Traveling Salesman Problem for Large Input Datasets,†Biomath Communications, vol. 3(1), p. 71, Jun. 2016.

A. Chowdhury, A. Ghosh, S. Sinha, S. Das, and Av. Ghosh, "A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem," International Journal of Bio-Inspired Computation, vol. 5(5), pp. 303-314, Oct. 2013.

V. E. Alekseev, R. Boliac, D. V. Korobitsyn, and V. V. Lozin, “NP-hard graph problems and boundary classes of graphs,†Theoretical Computer Science, vol. 389(1), pp. 219–236, Dec. 2007.

N. A. M. Zin, S. N. H. S. Abdullah, N. F. A. Zainal, and E. Ismail, "A Comparison of Exhaustive, Heuristic and Genetic Algorithm for Travelling Salesman Problem in PROLOG," International Journal on Advanced Science, Engineering and Information Technology, vol. 2(6), pp. 49-53, Dec. 2012.

S. Yuan, B. Skinner; S. Huang, and D. Liu, "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, vol. 228(1), pp. 72-82, Jul. 2013.

C. W. Tsai, S. P. Tseng, M. C. Chiang, C. S. Yang, and T. P. Hong, "A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case," The Scientific World Journal, vol. 2014, 178621, May 2014.

Y. Nagata and D. Soler, "A new genetic algorithm for the asymmetric traveling salesman problem," Expert Systems with Applications, vol. 39(10), pp. 8947–8953, Aug. 2012.

R. J. Wilson, Introduction to Graph Theory, 5th ed., New Jersey, USA: Prentice Hall, 2010.

M. Alameen, M. Abdul-Niby, A. Salhieh, and A. Radhi, "Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming," Engineering Technology & Applied Science Research, vol. 6(2), pp.927-930, Apr. 2016.

A. F. El-Samak and W. Ashour, "Optimization of Traveling Salesman Problem Using Affinity Propagation Clustering and Genetic Algorithm," Journal of Artificial Intelligence and Soft Computing Research, vol. 5(4), pp. 239-245, Oct. 2015.

C. Groba, A. Sartal, and X. H. Vazquez, "Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices," Computers & Operations Research, vol. 56, pp. 22-32, Apr. 2015.

Y. Wang, "A Genetic Algorithm with the Mixed Heuristics for Traveling Salesman Problem," International Journal of Computational Intelligence and Applications, vol. 14(1), 1550003, Mar. 2015.

M. K. Rafsanjani, S. Eskandari, and A. B. Saeid, "A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem," Neural Computing & Applications, vol. 26(1), pp. 213-222, Jan. 2015.

V. Kralev,"An Analysis of a Recursive and an Iterative Algorithm for Generating Permutations Modified for Travelling Salesman Problem," International Journal on Advanced Science, Engineering and Information Technology, vol. 7(5), pp. 1685-1692, Oct. 2017.

C. Changdar, G. S. Mahapatra, and R. K. Pal, "An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness," Swarm and Evolutionary Computation, vol. 15, pp. 27-37, Apr. 2014.

Y. Nagata and S. Kobayashi, "A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem," Informs Journal on Computing, vol. 25(2), pp. 346-363, Sep. 2013.

A. B. A. Hassanat, E. Alkafaween, N. A. Al-Nawaiseh, M. A. Abbadi, M. Alkasassbeh, and M. B. Alhasanat, "Enhancing Genetic Algorithms using Multi Mutations: Experimental Results on the Travelling Salesman Problem," International Journal of Computer Science and Information Security, vol. 14(7), pp. 785-801, Jul. 2016.

M. Albayrak and N. Allahverdi, "Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms," Expert Systems with Applications, vol. 38(3), pp. 1313-1320, Mar. 2011.

D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study, 2nd ed., Princeton, USA: Princeton University Press, 2007.

G. Gutin and A.P. Punnen, The Traveling Salesman Problem and Its Variations (Combinatorial Optimization), 2nd ed., New York City, USA: Springer, 2007.

A. Khanra, M. K Maiti, and M. Maiti, “A hybrid heuristic algorithm for single and multi-objective imprecise traveling salesman problems,†Journal of Intelligent and Fuzzy Systems, vol. 30(4), pp. 1987–2001, Mar. 2016.

M. Mestria, “A hybrid heuristic algorithm for the clustered traveling salesman problem,†Pesquisa Operacional, vol. 36(1), pp. 113–132, Jan-Apr. 2016.

Z. A. Othman, N. H. Al-Dhwai, A. Srour, and W. Diyi, "Water Flow-Like Algorithm with Simulated Annealing for Travelling Salesman Problems," International Journal on Advanced Science, Engineering and Information Technology, vol. 7(2), pp. 669-675, Apr. 2017.

M. Battarra, A. A. Pessoa, A. Subramanian, and E. Uchoa, “Exact algorithms for the traveling salesman problem with draft limits,†European Journal of Operational Research, vol. 235(1), pp. 115–128, May. 2014.

J. Kinable, B. Smeulders, E. Delcour, F. C. R. Spieksma, “Exact algorithms for the Equitable Traveling Salesman Problem,†European Journal of Operational Research, vol. 261(2), pp. 1339–1351, Sep. 2017.

Y. Deng, Y. Liu, and D. Zhou, "An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP," Mathematical Problems in Engineering, vol. 2015, 212794, Oct. 2015.

A. Hussain, Y. S. Muhammad, M. N. Sajid, I. Hussain, A. M. Shoukry, and S. Gani, "Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator," Computational Intelligence and Neuroscience, vol. 2017, 7430125, Oct. 2017.

C. Contreras-Bolton and V. Parada, "Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem," PLoS ONE, vol. 10(9), 0137724, Sep. 2015.




DOI: http://dx.doi.org/10.18517/ijaseit.8.3.4867

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development