A COMPARATIVE STUDY OF CROSSOVER OPERATORS FOR GENETIC ALGORITHMS TO SOLVE TRAVELLING SALESMAN PROBLEM

Wafaa Mustafa Hameed; Asan Baker Kanbar

doi:10.29121/granthaalayah.v5.i2.2017.1740

Authors

Wafaa Mustafa Hameed Assistant Lecturer, Department of Computer Science, Cihan University \ Campus \ Sulaimaniya, Iraq
Asan Baker Kanbar Assistant Lecturer, Department of Computer Science, Cihan University \ Campus \ Sulaimaniya, Iraq

DOI:

https://doi.org/10.29121/granthaalayah.v5.i2.2017.1740

Keywords:

Genetic Algorithms, Crossover Operator, Traveling Salesman Problem, Order Crossover, Parameters, Natural Evaluation, Evolutionary Algorithms

Abstract [English]

Genetic algorithms (GAs) represent a method that mimics the process of natural evolution in effort to ﬁnd good solutions. In that process, crossover operator plays an important role. To comprehend the genetic algorithms as a whole, it is necessary to understand the role of a crossover operator. Today, there are a number of different crossover operators that can be used , one of the problems in using genetic algorithms is the choice of crossover operator Many crossover operators have been proposed in literature on evolutionary algorithms, however, it is still unclear which crossover operator works best for a given optimization problem. This paper aims at studying the behavior of different types of crossover operators in the performance of genetic algorithm. These types of crossover are implemented on Traveling Salesman Problem (TSP); Whitley used the order crossover (OX) depending on specific parameters to solve the traveling salesman problem, the aim of this paper is to make a comparative study between order crossover (OX) and other types of crossover using the same parameters which was Whitley used.

Downloads

Download data is not yet available.

References

Syswerda, G., “Uniform Crossover in Genetic Algorithms”,Proceedings of the 3th International Conference on Genetic Algorithms, San Mateo ,1989.

Jorge magalhaes-mendes rua Dr.Antonio.”A Comparative Study of Crossover Operators For Genetic Algorithms To Solve Job Scheduling Problem”,,West transaction on computers, ISSN 4,volum 12 April 2013.

Eshelman, L. J., Carnana, R. A,, and Schaffer, J. D. “Biases in the Crossover Landscape”, Proceedings of the 3th International Conference on Genetic Algorithms, San Mateo, 1989.

Koza J. R., “Genetic Programming”, 2nd Edition, 1992.

Grant K., “An Introduction to Genetic Algorithm”, C/C++ Users journal , 1995.

Abdoun Otman,Abouchbaka Jaffar,”Acomparative Study of Adaptive Opaerators For Genetic Algorithms To Resolve The Traviling Salesman Problem”, intrnational journal of computer application, volum 31,No 11,october 2011.

Jhon Grefenstelle, Rajev Gopal,”Genetic Algorithms for the Traveling salesman problems”, Computer Science dep. Veaderbilt University.

Elaoud S. Loukilt, Teghmj,”Apareto Fitness Genetic Algorithms , Test Function study”.Europen Journal Operational Research”, 177(3),1703-1719.2007. DOI: https://doi.org/10.1016/j.ejor.2005.10.018

Lust T. Teghem ,J. memots “Amemetic Algorithms integrating tabusarch for Combinatorial Mutiobjective Optimizationzation, RAIRO,42,3-33. DOI: https://doi.org/10.1051/ro:2008003

Speras, W.M, De Jong, K.A,”On The Virues if Paramitrize Uniform Crossover”, Proceeding of the 4th International Conference on Genetic Algorithms, San Mateu 1991.

Imtiaz Hussain Khan,”Assesing Different Crossover Operators For Travelling Salesman Problem”, I.J.Intelligent Systems and Applications,2015,11,19-25. DOI: https://doi.org/10.5815/ijisa.2015.11.03

J. Lysgaard, “Cluster Based Branching For the AsymmetricTtraveling Salesman Problem”, European Journal of Operational Research 119 (1999) 314–325 DOI: https://doi.org/10.1016/S0377-2217(99)00133-2

Wafaa Mustafa Hameed,” The Role of Crossover on Optimization of a Function Problem Using Genetic Algorithms”, IJCSMC, Vol. 5, Issue. 7, July 2016, pg.425 – 429 .

Dorigo, M., &Gambardella, L. M. “Ant Colonies For the Traveling Salesman Problem. BioSystems, 43, 73–81. (1997). DOI: https://doi.org/10.1016/S0303-2647(97)01708-5

R.R.Sharapov,”Genetic Algorithms : Basic idea Variants and Analysis, vision Sysdtems:Segmantation and Pattern Recognition “,Goro Obinata and Ashish Dutta (ED), 2007.PP.407-422,ISbN:978-3-902613-05-9.

Whitley D., Starkweather, T., and Fuquay, D. A., “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator”,1989.

D. Goldberg and R. Lingle. Alleles, loci, and the travelling salesman problem. In proceedings of the first international conference on genetic algorithms and their applications, 1985, 154-159.

I. Oliver, D. Smith and J. Holland. A study of permutation crossover operators on the travelling salesman problem. In proceedings of the second international conference on genetic algorithms and their applications, 1987, 224-230.

M. Yamamura, T. Ono and S. Kobayashi. Characterpreserving genetic algorithms for travelling salesman problem. Journal of the Japanese society for artificial intelligence, 1992: 7(6), 1049-1059.

Gridhar Gopal, Rakesh Kumar, Ishan Jawa, Nveen Kumar,”Enhanced Order Crossover For Permutation Problems”,IJIRSET,Vol.4,issue 2. Feb.2015.

Michalewicz, Z., “Genetic Algorithm + Data Structure = Evolution Programs”, 3rd Revised and Extended Edition, Springer- Verlag Berlin Heidelberg, New York, 1996. DOI: https://doi.org/10.1007/978-3-662-03315-9_15

Zakir H. Ahmed. Genetic Algorithm for the Traveling Salesman Problem using Sequential Constractive Crossover Operator . IJBB 3(6).2010.

D. Goldberg, Genetic Algorithm in Search, Optimization, ans Machine Learning. Addison Wesley, 1989.