GENETIC ALGORITHM APPLIANCE FOR TRAVELING SALESMAN PROBLEM FOR GRAPHS WITH DE BRUIJN TOPOLOGY

Authors

  • Maksym Bondarchuk National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine
  • Artem Volokyta National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine
  • Heorhii Loutskii National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine

Keywords:

De Bruijn topology, genetic algorithm, traveling salesman problem

Abstract

Article reviews appropriateness for genetic algorithms to be used for traveling salesman problem for graphs with De Bruijn topologies. For this reason, article reviews requirements for graph and verifies whether De Bruijn topology satisfies requirements. Article also presents new crossover function and compares its quality with two existing functions.

References

Conforto, S., Hussain, A., Muhammad, Y.S., Nauman Sa., Hussain, I., Mohamd Shoukry & A., Gani, S. (2017). “Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator”, Computational Intelligence and Neuroscience, Hindawi. DOI 10.1155/2017/7430125.

Pál, K.F. (1993). “Genetic algorithms for the traveling salesman problem based on a heuristic crossover operation”. Biological Cybernetics. Vol. 69, pp. 539–546. DOI 10.1007/BF01185425.

Liao, Y.-F., Yau, D.-H. & Chen, C.-L. (2012). “Evolutionary algorithm to traveling salesman problems”. Computers & Mathematics with Applications. Vol. 64, Iss. 5, pp. 788-797. DOI 10.1016/j.camwa.2011.12.018.

Kaabi J. & Harrath Y. (2019). “Permutation rules and genetic algorithm to solve the traveling salesman problem”. Arab Journal of Basic and Applied Sciences. Vol. 26, Iss. 1. DOI 10.1080/25765299.2019.1615172.

Loutskii H., Volokyta A., Rehida P. & Goncharenko O. (2019). “Using excess code to design fault-tolerant topologies”. Technical sciences and technologies. National University "Chernihiv Polytechnic". Vol. 1 (15). DOI 10.25140/2411-5363-2019-1(15)-134-144.

Li J. (2010). “A Review of Tournament Selection in Genetic Programming”. Advances in Computation and Intelligence: 5th International Symposium, ISICA 2010, China, Wuhan. pp.181-192. DOI 10.1007/978-3-642-16493-4_19.

Bondarchuk M. Genetic De Bruijn Travelling Salesman Problem. GitHub repository. [Electronic resource]. – Available at: https://github.com/MaxBondarchuk/GeneticDeBruijnTravellingSalesmanProblem. – Active link: 06.06.2020.

Downloads

Published

2023-06-08

Issue

Section

Additional Section