# Developing a Java-based Genetic Algorithm to Solve the Travelling Salesman Problem

### Abstract

In this paper, software was developed to solve the travelling salesman problem. The Travelling Salesman Problem is a computational optimization problem that requires a lot of time to solve using brute force algorithm. The research aims at developing java-based software that provides an optimum solution to the Travelling Salesman Problem using the concepts of genetic algorithm within reasonable time frame.

### References

. Jean-Yves, P. (1996) ‘Genetic algorithms for the travelling salesman problem’, Annals of Operations Research. 63(3), pp 337-370

. Dario, F. and Claudio M. (2008) Bio-Inspired Artificial Intelligence. London: The MIT Press Cambridge, Massachusetts.

. Holland, J. H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, USA,1975.

. ‘Genetic Algorithm’ (2014) Wikipedia. Available at: http://en.wikipedia.org/wiki/Genetic_algorithm (accessed on 24/06/2014)

. Sivanandan, S.N., and Deepa, S.N. (2008) Introduction to Genetic Algorithms, Springer

. Pedro A. and Dean F. (2007) Initial Population for Genetic Algorithm: A metric Approach: School of computer science, University of Oklahoma, Norman. USA. Available at: http://www.cameron.edu/~pdiaz-go/GAsPopMetric.pdf (accessed 12/08/2014)

. Uniform crossover (2014) Wikipedia. Available at: http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) (accessed on 26/06/2014)

. Proportionate Selection (2014) Wikipedia. Available at: http://en.wikipedia.org/wiki/Fitness_proportionate_selection(accessed on 27/06/2014)

. Khalid J., and Mohammed M.,(2013) ‘Selection Methods for Genetic Algorithms’ int. J. Emerg. Sci. 3(4), pp.333-334. Available at: http://ijes.info/3/4/42543401.pdf

. Goldberg E., and Lingle R., ‘Alleles, loci, and travelling salesman problem’. InProc. Of the International Conference on Genetic Algorithms and Their Applications, pp. 154-159, Pittsburgh, PA, 1985.

. Oliver, I.M., and Smith, D.J., and Holland, J.R.C. ‘A study of permutation crossover operation on travelling salesman problem’. Proceedings of the second International Conference on Genetic Algorithms on Genetic algorithm and their application, pp. 244-230. NJ, USA 1987.

. Noraini M., and John G., (2011) ‘Genetic Algorithm performance with Different Selection Strategies in Solving TSP’, Proceedings of the World Congress on Engineering. Vol II, London, U.K. Available at: http://www.iaeng.org/publication/WCE2011/WCE2011_pp1134-1139.pdf (accessed 28/06/2014)

. Lee (2012) Applying a genetic algorithm to the traveling salesman problem http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 (accessed 28/06/2014)

. Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, New York, NY, 1989.

. Zbigniew, M., (1994) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 2nd edition, 1994.

. Rajesh, M., Surya, P. S., and Murari, L. M., (2010) Travelling Salesman Problem :An Overview of Applications, Formulations, and Solution Approaches; Department of Management Studies, Indian Institute of Technology Delhi, New Delhi, Available at: http://cdn.intechopen.com/pdfs-wm/12736.pdf (accessed 12/08/2014)

. Zhifeng, H., Huang, H., and Cai, R., (2008) Bio-inspired Algorithms for TSP and Generalized TSP. Travelling Salesman Problem. Shanghai, China. Available at: http://cdn.intechweb.org/pdfs/4606.pdf (accessed 20/08/2014)

. Kumar R., Gopal G., (2013) ‘Novel Crossover Operator for Genetic Algorithm for Permutation Problems’, International Journal of Soft Computing and Engineering 3(2) pp. 2231-2307

. MATLAB www.matlab.com

. Heaton, J., 2005. Introduction to Neutral Network with Java. (1st ed). U.S.A: Heaton Research, Inc.

. Deitel, P. and Deitel, H., (2013) Java: How to Program. (9th ed). New Jersey, U.S.A: Pearson Education, Inc.

. Cornell and Horstmann (2008) Core Java, volume I/II (8th ed). U.S,A :Prentice Hall

. Lewis, J. and Loftus, W., (2007). Java Software Solution: foundations of program design. (5th ed). U.S.A: Addison Wesley

. Noraini, M and John G., (2011) ‘Genetic Algorithm Performance with Different Selection Strategies in solving TSP’. Proceedings of the World Congress on Engineering Vol II, London, U.K

. Srinivas, M., and Patnaik, L.M., (1994) ‘Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms’. IEEE Transactions on System, man and cybernetic, Vol. 24, No 4, April 1994.

*International Journal of Computer (IJC)*,

*30*(1), 43-49. Retrieved from https://ijcjournal.org/index.php/InternationalJournalOfComputer/article/view/1259

Authors who submit papers with this journal agree to the following terms:

- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
- By submitting the processing fee, it is understood that the author has agreed to our terms and conditions which may change from time to time without any notice.
- It should be clear for authors that the Editor In Chief is responsible for the final decision about the submitted papers; have the right to accept\reject any paper. The Editor In Chief will choose any option from the following to review the submitted papers:A. send the paper to two reviewers, if the results were negative by one reviewer and positive by the other one; then the editor may send the paper for third reviewer or he take immediately the final decision by accepting\rejecting the paper. The Editor In Chief will ask the selected reviewers to present the results within 7 working days, if they were unable to complete the review within the agreed period then the editor have the right to resend the papers for new reviewers using the same procedure. If the Editor In Chief was not able to find suitable reviewers for certain papers then he have the right to reject the paper.
- Author will take the responsibility what so ever if any copyright infringement or any other violation of any law is done by publishing the research work by the author
- Before publishing, author must check whether this journal is accepted by his employer, or any authority he intends to submit his research work. we will not be responsible in this matter.
- If at any time, due to any legal reason, if the journal stops accepting manuscripts or could not publish already accepted manuscripts, we will have the right to cancel all or any one of the manuscripts without any compensation or returning back any kind of processing cost.
- The cost covered in the publication fees is only for online publication of a single manuscript.