An enhanced hybrid genetic algorithm for solving traveling salesman problem

Zeravan Arif Ali, Subhi Ahmed Rasheed, Nabeel No’man Ali

Abstract


Robust known the exceedingly famed NP-hard problem in combinatorial optimization is the Traveling Salesman Problem (TSP), promoting the skillful algorithms to get the solution of TSP   have been the burden for several scholars. For inquiring global optimal solution, the presented algorithm hybridizes genetic and local search algorithm to take out the uplifted quality results. The genetic algorithm gives the best individual of population by enhancing both cross over and mutation operators while local search gives the best local solutions by testing all neighbor solution. By comparing with the conventional genetic algorithm, the numerical outcomes acts that the presented algorithm is more adequate to attain optimal or very near to it. Problems arrested from the TSP library strongly trial the algorithm and shows that the proposed algorithm can reap outcomes within reach optimal. For more details, please download TEMPLATE HELP FILE from the website.

Keywords


TSP; Genetic Algorithm; Local Search

References


REFERENCES

E. Osaba, R. Carballedo, F. Diaz, and A. Perallos, “Analysis of the suitability of using blind crossover operators in genetic algorithms for solving rouning problems”. IEEE International Symposium on Applied Computational Intelligence and Informatics , 2013, pp. 17-22.

P. Chang, , W. Huang, , C. Ting, and W. Chang, “A varietal genetic algorithm by external self-evolving multiple-archives for combinatorial optimization problems”. Proceedings of the 11th IEEE International Conference on High Performance Computing and Communications , 2009, pp. 609-614.

Y. Wu, , T. Weise, and R. Chiong, “Local search for the traveling salesman problem: a comparartive study”. Proceedings of the 14th IEEE Int1 Conf. on Cognitive Informatics & Cognitive Computing , 2015, pp. 213-220.

J. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University Michigan Press, Ann Arbor, MI, USA, 1975.

J. Grefenstette, R. Gopal, B. Rosimaita, and D. Gucht, Genetic Algorithms for the Traveling Salesman Problem. Proc. Int. Conf. Genetic Algorithms and Their Applications , July 1985, pp. 160-168.

S. Kirkpatrick, Jr. Gelatt, and M. Vecchi, Optimization by Simulated Annealing. Science , 1983, 498-516.

J. Kennedy and R. Eberhart, “Particle swarm optimization”. Proceedings of IEEE International Conference on Neural Networks , 1995, pp. 1942-1948.

F. Glover, Tabu Search, Part I. ORSA Journal on Computing , 1989, pp. 190-206.

J. Potvin, The Traveling Salesman Problem: A Neural Network Perspective. ORSA J. Comput. , 1993, 328-348.

P. Chang, W. Huang, C. Ting, and W. Chang, “A varietal genetic algorithm by external self-evolving multiple-archives for combinatorial optimization problems”. Proceedings of the 11th IEEE International Conference on High Performance Computing and Communications , 1995, pp. 609-614.

Y. Wu, T. Weise, and R. Chiong, “Local search for the traveling salesman problem: a comparartive study”. Proceedings of the 14th IEEE Int1 Conf. on Cognitive Informatics & Cognitive Computing , 2015, pp. 213-220.

D. Pham, and T. Huynh, An Effective Combination of Genetic Algorithms and the Variable Neighborhood Search for Solving Travelling Salesman Problem”. IEEE Conference on Technologies and Applications of Artificial Intelligence , 2015, pp. 142-149.

D. Zvi, Tabu Search and Hybrid Genetic Algorithms for Quadratic Assignment Problems. European Journal of Operational Research, 2008, pp. 90-107.

D. Zeebaree, H. Haron, A. Muhsin, and S. Zeebaree. Combination of K-means clustering with Genetic Algorithm: A review. International Journal of Applied Engineering Research, 2017, pp. 14238-14245.

S. Shubhra, B. Sanghamitra, and K. Sankar. New Operators of Genetic Algorithms for Traveling Salesman Problem. International Conference on Pattern Recognition, 2004, pp. 497-500.

Bajeh, and K. Abolarinwa. Optimization: A Comparative Study of Genetic and Tabu Search Algorithms. International Journal of Computer Applications, 2011, pp. 43-48.

Arananayakgi, Reduce Total Distance and Time Using Genetic Algorithm. International Journal of Computer Science and Engineering Technology, 2014, pp. 815-819.

H. Zar, and K. May, An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem. International Conference on Information Communication and Management, 2011, pp. 54-59.

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.

Eesa, A. S., Orman, Z., & Brifcani, A. M. A. (2015). A new feature selection model based on ID3 and bees algorithm for intrusion detection system. Turkish Journal of Electrical Engineering & Computer Sciences, 23(2), 615-622.

Eesa, A. S., Orman, Z., & Brifcani, A. M. A. (2015). A novel feature-selection approach based on the cuttlefish optimization algorithm for intrusion detection systems. Expert Systems with Applications, 42(5), 2670-2679.

Surakhi, O., Khanafseh, M., & Jaffal, Y. An enhanced Biometric-based Face Recognition System using Genetic and CRO Algorithms.‏

Al-Obaidi, A. T. S., Abdullah, H. S., & Ahmed, Z. O. (2018). Meerkat clan algorithm: A new swarm intelligence algorithm. Indonesian Journal of Electrical Engineering and Computer Science, 10(1), 354-360.‏




DOI: http://doi.org/10.11591/ijeecs.v18.i2.pp%25p
Total views : 7 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

shopify stats IJEECS visitor statistics