Login Register Cart 0
Generic placeholder image

Recent Advances in Computer Science and Communications

Editor-in-Chief

ISSN (Print): 2666-2558
ISSN (Online): 2666-2566

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

Optimized Solution of TSP (Travelling Salesman Problem) Based on Mendelian Inheritance

Author(s): Vivek Sharma*, Rakesh Kumar and Sanjay Tyagi

Volume 13, Issue 5, 2020

Page: [909 - 916] Pages: 8

DOI: 10.2174/2213275912666190617155828

Price: $65

Abstract

Background: TSP problem has been the part of literature from many decades; it’s an important optimization issue in operation research. TSP problem always remain greedy for the better results especially if chosen working field are Genetic Algorithms (GA).

Objective: This paper presents a TSP solution, which performed the modified selection and crossover operations as well as takes advantage of Mendelian inheritance while producing the generations.

Methods: GA has very broad resolution scope for optimization problems and it is capable enough for generating well-optimized results if right GA technique has been applied on right point of issue in controlled manner. here the proposed agenda is to utilize the GA concept for TSP by applying mendels rules which is never applied before for the same issue. Here the proposed scheme applies some modification in traditional Mendel process. In general, full chromosome window has been utilized in mendel inheritance process but in presented scheme we have utilizes Most Significant Bits (MSB) only which helps in to control the convergence aptitude of the process.

Results: The scheme uses advanced modified Mendel operation which helps in to control convergence aptitude of the operation. It efficiently minimizes the total travelled distance of the graph which was the ultimate objective of the problem and that has been successfully achieved.

Conclusion: The validation of the scheme has been confirmed from the obtained results, which are better enough as comparison to traditional TSP-GA.

Keywords: Travelling salesman problem, mendel, genotype, gametes, MSB, genetic algorithm.

Graphical Abstract

[1]
B. Keresztury, "Genetic algorithms and the Traveling Salesman Problem", Proceedings of the first International Conference on Genetic Algorithms and their Applications, vol. 160 No. 168,, 2017
[2]
Z.H. Ahmed, "Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator", Int. J. Biometrics Bioinform., vol. 3, no. 6, p. 96, 2010.
[3]
L. Zhang, M. Yao, and N. Zheng, "Optimization and improvement of genetic algorithms solving traveling salesman problem. Image analysis and signal processing", In International Conference on Image Analysis and Signal Processing, pp. 327-332 2009
[4]
L. Zhang, M. Yao, and N. Zheng, "Optimization and improvement of genetic algorithms solving traveling salesman problem In", 2009 International Conference on Image Analysis and Signal Processing, 2009pp. 327-332
[5]
G. Üçoluk, "Genetic algorithm solution of the TSP avoiding special crossover and mutation", Intell. Automat. Soft Comput., vol. 8, no. 3, pp. 265-272, 2002.
[http://dx.doi.org/10.1080/10798587.2000.10642829]
[6]
A. Al-Dallal, "Using genetic algorithm with combinational crossover to solve travelling salesman problem In IEEE 7th International Joint Conference on Computational Intelligence (IJCCI), vol 1", 2015
[7]
G. Vahdati, M. Yaghoubi, and M. Poostchi, "A new approach to solve traveling salesman problem using genetic algorithm based on heuristic crossover and mutation operator", In IEEE International Conference of Soft Computing and Pattern Recognition, pp. 112-116 2009
[http://dx.doi.org/10.1109/SoCPaR.2009.33]
[8]
S.D. Dao, K. Abhary, and R. Marian, "An effective genetic algorithm for large-scale traveling salesman problems In ", Proceedings of the World Congress on Engineering and Computer Science, vol. 1, 2016
[9]
N. Kumar, and R.K. Karambir, "A comparative analysis of pmx, cx and ox crossover operators for solving traveling salesman problem", Int. J. Latest Res. Sci. Tech., vol. 1, no. 2, pp. 98-101, 2012.
[10]
A.J. Umbarkar, and P.D. Sheth, "Crossover operators in genetic algorithms: A review", J. Soft Comput, vol. 6, no. 1, 2015.
[11]
N. Soni, and T. Kumar, "Study of various mutation operators in genetic algorithms", Int. J. Comput. Sci. Inf. Technol., vol. 5, no. 3, pp. 4519-4521, 2014.
[12]
C.S. Park, "Modified Mendel operation for multimodal function optimization", In Proceedings of the 2001 Congress on Evolutionary Computation, vol. 2, 2001
[http://dx.doi.org/10.1109/CEC.2001.934353]

Rights & Permissions Print Cite
Article Metrics
4
© 2024 Bentham Science Publishers | Privacy Policy