International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 7, No. 11, 8 Oct. 2015
Cover page and Table of Contents: PDF (size: 1141KB)
Assessing Different Crossover Operators for Travelling Salesman Problem
Full Text (PDF, 1141KB), PP.19-25
Views: 0 Downloads: 0
Author(s)
Index Terms
Crossover Operators, Travelling Salesman Problem, Evaluation of Crossover Operators, Evolutionary Algorithms
Abstract
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. In this study, eight different crossover operators specially designed for travelling salesman problem, namely, Two-Point Crossover, Partially Mapped Crossover, Cycle Crossover, Shuffle Crossover, Edge Recombination Crossover, Uniform Order-based Crossover, Sub-tour Exchange Crossover, and Sequential Constructive Crossover are evaluated empirically. The select crossover operators were implemented to build an experimental setup upon which simulations were run. Four benchmark instances of travelling salesman problem, two symmetric (ST70 and TSP225) and two asymmetric (FTV100 and FTV170), were used to thoroughly assess the select crossover operators. The performance of these operators was analyzed in terms of solution quality and computational cost. It was found that Sequential Constructive Crossover outperformed other operators in attaining 'good' quality solution, whereas Two-Point Crossover outperformed other operators in terms of computational cost. It was also observed that the performance of different crossover operators is much better for relatively small number of cities, both in terms of solution quality and computational cost, however, for relatively large number of cities their performance greatly degrades.
Cite This Paper
Imtiaz Hussain Khan, "Assessing Different Crossover Operators for Travelling Salesman Problem", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.11, pp.19-25, 2015. DOI:10.5815/ijisa.2015.11.03
Reference
[1]Rechenberg. Evolutionsstrategie: optimierung technischer systeme und prinzipien der biologischen evolution. Frommann-Holzboog, Stuttgart Germany, 1973.
[2]J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975.
[3]J. R. Koza and R. Poli. Genetic Programming: On the programming of computers by means of natural selection (complex adaptive systems). MIT Press, Cambridge, MA, 1992.
[4]K.A. De Jong. An analysis of the behaviour of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan, 1975.
[5]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.
[6]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.
[7]D. Whitley, T. Starkweather and D. Shaner. The travelling salesman and sequence scheduling: quality solutions using genetic edge recombination. In handbook of genetic algorithms, 1990, 350-372.
[8]T. Starkweather, S. Mcdaniel, K. E. Mathias, L. D. Whitley and C. Whitley. A comparison of genetic sequencing operators. In proceedings of the fourth international conference on genetic algorithms, 1991, 69-76.
[9]M. Yamamura, T. Ono and S. Kobayashi. Character-preserving genetic algorithms for travelling salesman problem. Journal of the Japanese society for artificial intelligence, 1992: 7(6), 1049-1059.
[10]G. Syswerda. Order-based genetic algorithms and the graph coloring problem. In handbook of genetic algorithms, L. Davis, ed. Van Nostrand Reinhold. 1991.
[11]G. Reinelt. Tsplib, universit?t heidelberg, 1995. Retrieved March 14, 2015, from http://www.iwr.uniheidelberg. de/groups/comopt/software/TSPLIB95/.
[12]R. A. Caruana, L. J. Eshelman and J. D. Schaffer. Representation and hidden bias II: eliminating defining length bias in genetic search via shuffle crossover. In proceedings of the eleventh international joint conference on artificial intelligence, Detroit, Michigan, USA, 1989, 750–755.
[13]K. A. De Jong W. M. and Spears. A formal analysis of the role of multi-point crossover in genetic algorithms, Annals of Mathematics and Artificial Intelligence, 1992, 5(1): 1–26.
[14]M. Mitchell. An introduction to genetic algorithms. The MIT Press, Cambridge, USA, 1999.
[15]S. Picek, M. Golub and D. Jakobovic. Evaluation of Crossover Operator Performance in Genetic Algorithms with Binary Representation. In proceedings of bio-inspired computing and applications (lecture notes in computer series), Springer Berlin Heidelberg, 2012, 223-230.
[16]K. Puljic and R. Manger. Comparison of eight evolutionary crossover operators for the vehicle routing problem. Journal of mathematical communications, 2013: 18, 359-375.
[17]V. K. Dabhi and S. Chaudhary. Performance comparison of crossover operators for postfix genetic programming. International journal of metaheuristics, 2014: 3(3), 244-264.
[18]D. Dumitrescu, B. Lazzerini, B., L. C. Jain and A. Dumitrescu. Evolutionary Computation. CRC Press, Florida, USA, 2000.
[19]S. Picek and M. Golub. Comparison of a crossover operator in binary-coded genetic algorithms. WSEAS transactions on computation, 2010: 9(9), 1064-1073.
[20]I. H. Khan. A comparative study of EAG and PBIL on large-scale global optimization problems. Journal of applied computational intelligence and soft computing. Hindawi publications, 2014, 10 pages.