Genetic algorithm based approach to solve travelling salesman problem with one point crossover operator:

Authors

  • Sharadindu Roy Sonarpur Mahavidyalaya, University of Calcutta

DOI:

https://doi.org/10.24297/ijct.v10i3.3269

Keywords:

Genetic algorithm, Crossover, Mutation, Travelling salesman problem, NP-complete, Cost matrix, Fitness

Abstract

In this paper, the travelling salesman problem using genetic algorithm has been attempted. In this practical paper solution is easy and we can easily apply genetic operator in this type of problem. Complexity is both in time and space, provided size of the problem an as integer (count is infinite). The solution of the traveling salesman problem is global optimum. There are cities and given distances between them. Traveling salesman has to visit all of them. TSP main objective is to find traveling sequence of cities to minimize the traveling distance.* traverse one time*initially we select parent1 & parent2 by Roulette wheel concept. Apply one point crossover operator on parents and produce the offspring. Again we apply the mutation operator on offspring and created child. But the no. of bits (cities) will be inverted by the mutation operator, that is depended on mutation probability (pm). So one generation contain 6 individual. Then count fitness of the individuals in each generation. For the next generation (for parent1 & parent2) two individuals will be selected whose fitness is best in generation. Here we see crossover between two good solution may not always yield a better or as good a solution. Since parents are good, so the probability of the child being good is high. Every time we have to do, identity the good solution in the population and make multiple copies of the good solution. 

Downloads

Download data is not yet available.

Author Biography

Sharadindu Roy, Sonarpur Mahavidyalaya, University of Calcutta

Asst. professor, Dept. of computer science

Downloads

Published

2013-08-05

How to Cite

Roy, S. (2013). Genetic algorithm based approach to solve travelling salesman problem with one point crossover operator:. INTERNATIONAL JOURNAL OF COMPUTERS &Amp; TECHNOLOGY, 10(3), 1393–1400. https://doi.org/10.24297/ijct.v10i3.3269

Issue

Section

Research Articles