International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

A Representation with Novel Crossover Technique of the Genetic Algorithm for the Travelling Salesmen Problem

Author Affiliations

  • 1University of Colombo School of Computing, Colombo, SRILANKA
  • 2Department of Physical Science, Vavuniya Campus of the University of Jaffna, SRILANKA
  • 3Department of Physical Science, Vavuniya Campus of the University of Jaffna, SRILANKA

Res. J. Mathematical & Statistical Sci., Volume 3, Issue (2), Pages 1-3, February,12 (2015)

Abstract

Genetic Algorithm (GA) is a search technique that mimics the process of natural selection. It is routinely used to generate useful solutions to optimization problems. In a GA, we simulate the survival of the fittest among individuals over consecutive generation for solving problems. Choosing a representation in the design of the GA is the major problem. In this research, Travelling Salesmen Problem (TSP) is solved by a new representation of GA. An encoding mechanism is developed and selection, crossover and mutation operators are defined. We have presented a GA variant for solving the TSP that uses the novel cross over method. In the crossover that uses one of the parents position of the gene structure to mate with other parents chromosomes. Our GA representation is tested with 17, 26 and 42 cities and found that our algorithm performs accordingly and generates expected near optimal results within acceptable levels. Using Brute force search for 17 cities problem, TSP would have needed checking 2.092279 x 1013 possibilities, But GA within 1000 iterations gives the optimal solution. The actual answer for 17 cities TSP is 2085. We also ran GA for 26 cities and 42 cities TSP’s with average results of 1034 (actual 937) and 944 (actual 699) respectively for 5 runs. Population size, Number of generations are increased to 500, 2000 and to 8 respectively, we got average of 994 and 837 for 26 cities and 42 cities TSP’s respectively. So we could see that tuning the GA parameters optimizes the result.

References

  1. Michalewicz Z, Genetic Algorithms + Data Structures =Evolution Programs, Springer-Verlag, Berlin (1994)
  2. P. Larrañaga, C.M.H. Kuijpers, R.H. Murga, I. Inza and S.Dizdarevic, Genetic Algorithms for the TravellingSalesman Problem: A Review of Representations andOperators, (1999)
  3. J. Kirk, Traveling Salesman Problem – GeneticAlgorithm, Matlab Central, (2009)
  4. Mou L., An efficient ant colony system for solving thenew generalized traveling salesman problem, CCIS2011 -Proceedings: 2011 IEEE International Conference onCloud Computing and Intelligence Systems, 407 (2011)
  5. R. Durbin and D. Willshaw, An Analogue Approach tothe Traveling Salesman Problem Using an Elastic NetMethod, Nature, vol. 326
  6. N. Ernest and K. Cohen, Fuzzy clustering based geneticalgorithm for the multi-depot polygon visiting Dubinsmultiple traveling salesman problem, in Proceedings ofthe 2012 AIAA InfotechAerospace, no. AIAA-2012-2562.Garden Grove, CA: (2012)
  7. N. Ernest and K. Cohen, Self-Crossover Based GeneticAlgorithm for Performance Augmentation of theTraveling Salesman Problem, AIAA,Infotech
  8. Aerospace 2011, St. Louis, Missouri (2011), undefined, undefined
  9. Bhattacharya Sourabh, Applications of DSTATCOMMATLAB/Simulation in Power System, Res. J. RecentSci., 1(ISC-2011), 430-433 (2012)
  10. PitalúaDíaz N., Lagunas Jiménez R. and GonzálezAngelesa, Tuning Fuzzy Control Rules via GeneticAlgorithms: An Experimental Evaluation, ResearchJournal of Recent Sciences, 2(10), 81-87, (2013)
  11. Esmail Limouzade, Capacitor Replacement in DistributionNetworks using Genetic Algorithm, Research Journal ofRecent Sciences, 2(12), 54-64, (2013)