International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 11, No. 12, 8 Dec. 2019
Cover page and Table of Contents: PDF (size: 425KB)
Development a New Crossover Scheme for Traveling Salesman Problem by aid of Genetic Algorithm
Full Text (PDF, 425KB), PP.46-52
Views: 0 Downloads: 0
Author(s)
Ehtasham-ul-Haq
1,*
Abid Hussain
2
Ishfaq Ahmad
1
Index Terms
NP-hard, Traveling salesman problems, Genetic algorithms, Multi-offspring, Crossover operators
Abstract
This research work provides a detailed working principle and analysis technique of multi- offspring crossover operator. The proposed approach is an extension of the basic partially- mapped crossover (PMX) based upon survival of the fittest theory. It improves the performance of the genetic algorithm (GA) for solving the well-known combinatorial optimization problem, the traveling salesman problem (TSP). This study is based on numerical experiments of the proposed with other traditional crossover operators for eighteen benchmarks TSPLIB instances. The simulation results show a considerable improvement because the proposed operator enhances the opportunity of having better offspring. Moreover, the t-test also establishes the improved significance of the proposed operator. Its preferable results not only confirm the advantages over others, but also show the long run survival of a generation having a number of offspring more than the number of parents with the help of mathematical ecology theory.
Cite This Paper
Ehtasham-ul-Haq, Abid Hussain, Ishfaq Ahmad, "Development a New Crossover Scheme for Traveling Salesman Problem by aid of Genetic Algorithm", International Journal of Intelligent Systems and Applications(IJISA), Vol.11, No.12, pp.46-52, 2019. DOI:10.5815/ijisa.2019.12.05
Reference
[1]J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
[2]A. Philip, A. A. Taofiki, and O. Kehinde. A genetic algorithm for solving travelling salesman problem. International Journal of Advanced Computer Science and Applications, vol. 2, pp. 26–29, 2011.
[3]M. H. Ha, N. Bostel, A. Langevin, and L.-M. Rousseau. An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size. Computers & Operations Research, vol. 43, pp. 9–19, 2014.
[4]W. Ho and P. Ji. An integrated scheduling problem of pcb components on sequential pickand-place machines: Mathematical models and heuristic solutions. Expert Systems with Applications, vol. 36, pp. 7002–7010, 2009.
[5]K. Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, vol. 126, pp. 106–130, 2000.
[6]H.-X. Huang, J.-C. Li, and C.-L. Xiao. A proposed iteration optimization approach integrating backpropagation neural network with genetic algorithm. Expert Systems with Applications, vol. 42, pp. 146–155, 2015.
[7]E. Ruiz, M. Albareda-Sambola, E. Fernandez, and M. G. C. Resende. A biased randomkey genetic algorithm for the capacitated minimum spanning tree problem. Computers & Operations Research, vol. 57, pp. 95–108, 2015.
[8]W. P. Coutinho, R. Q. Nascimento, A. A. Pessoa, and A. Subramanian. A branch-and-bound algorithm for the close-enough traveling salesman problem. INFORMS Journal on Computing, vol. 28, pp. 752–765, 2016.
[9]L. Gouveia, M. Leitner, and M. Ruthmair. Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem. European Journal of Operational Research, vol. 262, pp. 908–928, 2017.
[10]M. Gunduz, M. S. Kiran, and E. Ozceylan. A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turkish Journal of Electrical Engineering & Computer Sciences, vol. 23, pp. 103–117, 2015.
[11]S.-H. Zhan, J. Lin, Z.-J. Zhang, and Y.-W. Zhong. List-based simulated annealing algorithm for traveling salesman problem. Computational intelligence and neuroscience, vol. 2016, pp. 1–8, 2016.
[12]J. B. Escario, J. F. Jimenez, and J. M. Giron-Sierra. Ant colony extended: experiments on the travelling salesman problem. Expert Systems with Applications, vol. 42, pp. 390–410, 2015.
[13]T. A. S. Masutti and L. N. de Castro. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Information Sciences, vol. 179, pp. 1454– 1468, 2009.
[14]J. Knox. Tabu search performance on the symmetric traveling salesman problem. Computers & Operations Research, vol. 21, pp. 867–876, 1994.
[15]M. Bhattacharyya and A. K. Bandyopadhyay. Comparative study of some solution methods for traveling salesman problem using genetic algorithms. Cybernetics and Systems, vol. 40, pp. 1–24, 2008.
[16]Y. Nagata and D. Soler. A new genetic algorithm for the asymmetric traveling salesman problem. Expert Systems with Applications, vol. 39, pp. 8947–8953, 2012.
[17]A. Hussain, Y. S. Muhammad, N. S. Muhammad, I. Hussain, S. A. Mohamd, and S. Gani. Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Computational intelligence and neuroscience, vol. 2017, pp. 1–7, 2017.
[18]K. Deep and H. Mebrahtu. New variations of order crossover for traveling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, vol. 2, pp. 2–13, 2011.
[19]A. Piwonska. Genetic algorithm finds routes in traveling salesman problem with profits. Zeszyty Naukowe Politechniki Bia lostockiej. Informatyka, pp. 51–65, 2010.
[20]L. M. A. Drummond, L. S. Ochi, and D. S. Vianna. An asynchronous parallel metaheuristic for the period vehicle routing problem. Future generation computer systems, vol. 17, pp. 379–386, 2001.
[21]K. Ganesh and T. T. Narendran. Cloves: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up. European Journal of Operational Research, vol. 178, pp. 699–717, 2007.
[22]I.-C. Choi, S.-I. Kim, and H.-S. Kim. A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Computers & Operations Research, vol. 30, pp. 773–786, 2003.
[23]Z. Ursani, D. Essam, D. Cornforth, and R. Stocker. Localized genetic algorithm for vehicle routing problem with time windows. Applied Soft Computing, vol. 11, pp. 5375–5390, 2011.
[24]C. Prins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, vol. 31, pp.1985–2002, 2004.
[25]K. C. Tan, Y. H. Chew, and L. H. Lee. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications, vol. 34, pp. 115–151, 2006.
[26]J. Wang, O. K. Ersoy, M. He, and F. Wang. Multi-offspring genetic algorithm and its application to the traveling salesman problem. Applied Soft Computing, vol. 43, pp. 415–423, 2016.
[27]X. Mou, D.-I. Xie, and W. Yan. Research based on genetic algorithm traveling sealer problem of trajectory optimization. J. Syst. Simul, vol. 25, pp. 86–89, 2013.
[28]G. Reinelt. Tsplib http://www. iwr. uni-heidelberg. de/groups/comopt/software. TSPLIB95, 1995.
[29]S. Yuan, B. Skinner, S. Huang, and D. Liu. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research, vol. 228, pp. 72–82, 2013.
[30]A. Hussain and Y. S. Muhammad. Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator. Complex & Intelligent Systems, DOI: 10.1007/s40747-019-0102-7, 2019.