International Journal of Engineering Research in Computer Science and Engineering (IJERCSE)

Applying Map Reduction Technique with Genetic Algorithm Approach to Solve Travelling Salesman Problem

Author : Rajni ¹ Sunita Rani ²

Date of Publication :17th October 2017

Abstract: Travelling salesman problem is a very old mathematical problem. It models a scenario where a salesman has many cities to visit in shortest possible time. Given the distance among the cities, he must calculate the shortest route. Researchers have been working with Travelling Salesman problem for over centuries. Many models have been introduced to solve this legendary mathematical problem. In this Research Work, genetic algorithm is used to solve Travelling Salesman Problem. Genetic algorithm is a technique used for estimating computer models based on methods adapted from the field of genetics in biology. To use this technique, one encodes possible model behaviors into ''genes". We designed a new crossover technique to increase the efficiency of crossover operator of GA for TSP. We also apply map reduce algorithm to efficiently solve the TSP.

Reference :

1. Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 2nd edition, 1994.
2. Concord TSP Solver. http://www.math. uwaterloo. ca/tsp/concorde.html.
3. Seniw, D., A Genetic algorithm for the Travelling Salesman Problem, MSc Thesis, University of North Carolina, at Charlotte. http://www.heatonresearch.com / articales/ 65/page1. html. 1996.
4. David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. AddisonWesley, 1989.
5. http:// Amsterdam optimization .com / pic / tspmip . png
6. Davis, L. (ed.) (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.
7. Grefenstette, J. J. (ed.) (1987a). Genetic Algorithms and Their Applications: Proceedings of the Second International Conference. Hillsdale, New Jersey: Lawrence Erlbaum.
8. Homaifar, A. & Guan, S. (1991). A New Approach on the Traveling Salesman Problem by Genetic Algorithm. Technical Report, North Carolina A&T State University.
9. Kylie Bryant, Arthur Benjamin, Advisor, “Genetic Algorithms and the Travelling Salesman Problem”, Department of Mathematics, December 2000.
10. Adewole Philip, Akinwale Adio Taofiki, Otunbanowo Kehinde “A Genetic Algorithm for Solving Travelling Salesman Problem”,(IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 2, No.1, January 2011.
11. Abdollah Homaifer, Shanguchuan Guan, Gunar E. Liepins “Schema Analysis of the Travelling Salesman Problem Using Genetic Algorithms”.
12. Milena Karova Vassil Smarkov Stoyan Penev,“Genetic operators crossover and mutation in solving the TSP problem”, International Conference on Computer Systems and Technologies - CompSysTechâ€Ÿ 2005.
13. Fogel, D. B. (1993). Applying Evolutionary Programming to Selected Traveling Salesman Problems. Cybernetics and Systems 24: 27–36.
14. H. Braun, “On Solving Travelling Salesman Problem by Genetic Algorithm”, in Parallel Problem- Solving from Nature, Lecture Notes in Computer Science 496, H.P. Schwefel and R. Manner Eds, Springer-Verlag, app. 129-133.
15. Varshika Dwivedi Taruna Chauhan Sanu Saxena Princie Agrawal Travelling Salesman Problem using Genetic Algorithm National Conference on Development of Reliable Information Systems, Techniques and Related Issues (DRISTI) Proceedings published in International Journal of Computer Applications® (IJCA) 2012