Using Genetic Algorithm to Solve Travelling Salesman Optimization Problem Based on Google Map Coordinates for Duhok City Areas
DOI:
https://doi.org/10.25007/ajnu.v7n3a207Keywords:
Genetic Algorithm, Optimization, Non Deterministic Problem, Travelling Salesman Problem, Google coordinateAbstract
This research aims to solve one of the Non-Deterministic Polynomial (NDP) Problems by using one of the artificial intelligence techniques, which is genetic algorithm. Travelling salesman problem (TSP) is one of the difficult optimization problems, the aim of this problem is to get the optimal solution which is represented by the shortest path for (n) visited areas of the city. The number of possible solutions that will be generated, searched and compared when solving this problem for (n) areas is equal to (n!). This number exponentially increased with the increasing of the number of areas. With the large number of areas, which produces a huge number of possible solutions, the traditional search algorithms will be collapsed, and the problem will become a hard (NDP) Problem. In this case it becomes necessary to rely on artificial intelligence techniques, which are based on the biologically-inspired principle. During this research the travelling salesman problem was formulated and programmed in proportion to the concept of genetic algorithm (GA) to produce Travelling Salesman Genetic Algorithm (TSGA). One of the cities of Kurdistan Region of Iraq (Duhok) was selected as a case study to implement the TSGA algorithm. Initially, the study depends on Google earth program to determine the coordinates for number of Duhok’s areas. These coordinates were saved as a (.kml) file format, then the required cleaning and normalization operations were accomplished on this file to produce the pure coordinates, that were stored as an excel file format (.xls) . TSGA algorithm depends on these excel coordinates as an input file to create the initial generation of paths, then the objective function for each path of the this generation was calculated, and then the parent selection, crossover and mutation functions were applied to get the group of the best paths. TSGA algorithm, then, continues to regenerate a number of successive generations, and afterwards recalculate and create the new group of the best paths for each generation to enhance the result. Finally, and depending on the criterion of stopping, this algorithm will cease to create new generations and suggest the final result that represents the shortest path for visited areas. Matlab program was used to implement the TSGA algorithm and to analyze the result. The results of this algorithm were optimum and near optimum for most of the problems at a reasonable time.
Downloads
References
Mukherjee, Swahum; Ganguly, Srinjoy; Das, Swagatam. (2012) “A Strategy Adaptive Genetic Algorithm for Solving the Travelling Salesman Problem”, SEMCCO, India. PP: 778-784.
Al-Sabawi Ahmed Mahmoud Mohammed, (2012) “Using the Branch and bound algorithm and genetic algorithm to solve the Travelling Salesman Problem”. Iraqi Journal of Statistical Sciences, Iraq, Volume 12, Issue 21, PP:69-96.(Arabic reference).
Grosan, Crina; ABRAHAM, Ajith. (2011) “Intelligent systems: A modern approach”. Springer Science & Business Media.Sivanandam, S. N.; DEEPA, S. N. (2007) “Introduction to genetic algorithms”. Springer Science & Business Media.
Hussein, Rana B., Thabet, Hamsa M. (2014)“The Genetic Coefficient with Some Applications”. Tanmiat Al-Rafidain Journal, Iraq, Volume 36, Issue 116. (Arabic reference).
Hazim, Ziyad.(1999), ”Comparing Different Programming Techniques for Solving. Assignment Problem”. College of computer sciences and Mathematics, University of Mosul, Iraq, M.Sc. thesis.
Al-Jawahiri, Zuhair Abdul Wahab Mohammed Hassan. (2011),”Evaluate the coordinate’s accuracy for the Google earth program”. UOBabylon Journal of Applied and Pure Sciences, Iraq, Issue No 2, Volume No 19. (Arabic reference).
(2016), “KML Data format”. Retrieved, from http://geojournalism.org/tracks/type /data-format/ .
Abramson, M. A. (2004), “Genetic algorithm and direct search toolbox”. Natick, MA: The Math Work Inc.
Chipperfield, A. J.; Fleming, P. J. “The MATLAB genetic algorithm toolbox In Applied control techniques using MATLAB”, IEE Colloquium on (pp. 10-1). IET, 1995.
Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright
The use of a Creative Commons License enables authors/editors to retain copyright to their work. Publications can be reused and redistributed as long as the original author is correctly attributed.
- Copyright
- The researcher(s), whether a single or joint research paper, must sell and transfer to the publisher (the Academic Journal of Nawroz University) through all the duration of the publication which starts from the date of entering this Agreement into force, the exclusive rights of the research paper/article. These rights include the translation, reuse of papers/articles, transmit or distribute, or use the material or parts(s) contained therein to be published in scientific, academic, technical, professional journals or any other periodicals including any other works derived from them, all over the world, in English and Arabic, whether in print or in electronic edition of such journals and periodicals in all types of media or formats now or that may exist in the future. Rights also include giving license (or granting permission) to a third party to use the materials and any other works derived from them and publish them in such journals and periodicals all over the world. Transfer right under this Agreement includes the right to modify such materials to be used with computer systems and software, or to reproduce or publish it in e-formats and also to incorporate them into retrieval systems.
- Reproduction, reference, transmission, distribution or any other use of the content, or any parts of the subjects included in that content in any manner permitted by this Agreement, must be accompanied by mentioning the source which is (the Academic Journal of Nawroz University) and the publisher in addition to the title of the article, the name of the author (or co-authors), journal’s name, volume or issue, publisher's copyright, and publication year.
- The Academic Journal of Nawroz University reserves all rights to publish research papers/articles issued under a “Creative Commons License (CC BY-NC-ND 4.0) which permits unrestricted use, distribution, and reproduction of the paper/article by any means, provided that the original work is correctly cited.
- Reservation of Rights
The researcher(s) preserves all intellectual property rights (except for the one transferred to the publisher under this Agreement).
- Researcher’s guarantee
The researcher(s) hereby guarantees that the content of the paper/article is original. It has been submitted only to the Academic Journal of Nawroz University and has not been previously published by any other party.
In the event that the paper/article is written jointly with other researchers, the researcher guarantees that he/she has informed the other co-authors about the terms of this agreement, as well as obtaining their signature or written permission to sign on their behalf.
The author further guarantees:
- The research paper/article does not contain any defamatory statements or illegal comments.
- The research paper/article does not violate other's rights (including but not limited to copyright, patent, and trademark rights).
This research paper/article does not contain any facts or instructions that could cause damages or harm to others, and publishing it does not lead to disclosure of any confidential information.