Call for Paper - November 2020 Edition
IJCA solicits original research papers for the November 2020 Edition. Last date of manuscript submission is October 20, 2020. Read More

A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem

Print
PDF
International Journal of Computer Applications
© 2011 by IJCA Journal
Number 1 - Article 1
Year of Publication: 2011
Authors:
ABDOUN Otman
ABOUCHABAKA Jaafar
10.5120/3945-5587

ABDOUN Otman and ABOUCHABAKA Jaafar. Article:A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem. International Journal of Computer Applications 31(11):49-57, October 2011. Full text available. BibTeX

@article{key:article,
	author = {ABDOUN Otman and ABOUCHABAKA Jaafar},
	title = {Article:A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem},
	journal = {International Journal of Computer Applications},
	year = {2011},
	volume = {31},
	number = {11},
	pages = {49-57},
	month = {October},
	note = {Full text available}
}

Abstract

Genetic algorithm includes some parameters that should be adjusting so that the algorithm can provide positive results. Crossover operators play very important role by constructing competitive Genetic Algorithms (GAs). In this paper, the basic conceptual features and specific characteristics of various crossover operators in the context of the Traveling Salesman Problem (TSP) are discussed. The results of experimental comparison of more than six different crossover operators for the TSP are presented. The experiment results show that OX operator enables to achieve a better solutions than other operators tested.

Reference

  • Alireza Arab Asadi, Ali Naserasadi and Zeinab Arab Asadi. Article: A New Hybrid Algorithm for Traveler Salesman Problem based on Genetic Algorithms and Artificial Neural Networks. International Journal of Computer Applications 24(5):6–9, June 2011. Published by Foundation of Computer Science.
  • Dr. Nitin S Choubey. A Novel Encoding Scheme for Traveling Tournament Problem using Genetic Algorithm. IJCA Special Issue on Evolutionary Computation (2):79–82, 2010. Published by Foundation of Computer Science.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, MIT press, 2010.
  • Randy L. Haupt and Sue Ellen Haupt, PRACTICAL GENETICALGORITHMS, 2nd edition, A JOHN WILEY & SONS, INC., PUBLICATION, 2004.
  • C. DARWIN. The origin of species by means of natural selection, 1859.
  • Sue Ellen Haupt. Introduction toGenetic Algorithms. Artificial Intelligence Methods in the Environmental Sciences. Springer Science (103-126), 2009.
  • Sue Ellen Haupt, ValliappaLakshmanan, CarenMarzban, AntonelloPasini, and John K. Williams. Environmental Science Models and Artificial Intelligence. Artificial Intelligence Methods in the Environmental Sciences. Springer Science (3-14, 103-126), 2009.
  • D. Goldberg, Genetic Algorithm in Search, Optimization, ans Machine Learning. Addison Wesley, 1989.
  • Misevicius, A. (2004). Using iterated Tabu search for the traveling salesman problem. Information Technology and Control, 3(32), 29–40.
  • Elaoud S, Loukil T, Teghem J (2007) A Pareto Fitness Genetic Algorithm: test function study. European Journal Operational Research, 177 (3), 1703-1719.
  • Murat AlbayrakNovruzAllahverdi Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Systems with Applications 38 (2011) 1313–1320.
  • Albayrak Murat (2008). Determination of route by means of Genetic Algorithms for printed circuit board driller machines. Master dissertation (p. 180). Selcuk University.
  • F. Glover, Artificial intelligence, heuristic frameworks and tabu search, Managerial & Decision Economics 11 (1990) 365–378.
  • Lust T, Teghem J MEMOTS (2008) Amemetic algorithm integrating tabusarch for combinatorial multiobjective optimization. RAIRO, 42, 3-33.
  • Oliver, I. M., Smith, D. J., & Holland, J. R. C. (1987). A study of permutation crossover operators on the traveling salesman problem. In Proceedings of the second international conference. on genetic algorithms (ICGA’87) (pp. 224–230). Cambridge, MA:Massachusetts Institute of Technology.  
  • Chakraborty, B and Chaudhuri, P (2003) On the use of genetic algorithm with elitism in robust and nonparametric mulltivariate analysis. Austrian Journal of Statistics, 32 . 13--27.
  • Dorigo, M., &Gambardella, L. M. (1997). Ant colonies for the traveling salesman problem. BioSystems, 43, 73–81.
  • Zakir H. Ahmed. Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator. IJBB 3(6). 2010.
  • D. E. Goldberg and R. Lingle. Alleles, loci, and the traveling salesman problem. In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pages 154–159, 1985.
  • V. A. Cicirello. Non-wrapping order crossover : An order preserving crossover operator that respects absolute position. GECCO, pages 1125–1131, 2006.
  • V. A. Cicirello and S. F. Smith. Modeling ga performance for control parameter optimization. GECCO, pages 235–242, 2000.
  • R.K. Ahuja, T.L. Mangnanti, J.B. Orlin, Network Flows, Prentice-Hall, New Jersey, 1993.
  • G. Laporte, The vehicle roting problem: an overview of exact and approximate algorithms, Eur. J. Oper. Res. 59 (2) (1992) 345–358.
  • G.C. Onwubolu, M. Clerc, Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization, Int. J. Prod. Res. 42 (3) (2004) 473–491.
  • G. Carpaneto, P. Toth, Some new branching and bounding criteria for the asymmetric traveling salesman problem, Management Science 26 (1980) 736–743.
  • M. Gen, R. Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
  • M. Fischetti, P. Toth, An additive bounding procedure for combinatorial optimization problems, Operations Research 37 (1989) 319–328.
  • 29 G. Finke, A. Claus, E. Gunn, A two-commodity network flow approach to the traveling salesman problem, CongressusNumerantium 41 (1984) 167–178.
  • 30 L. Gouveia, J.M. Pires, The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker– Zemlin constraints, European Journal of Operational Research 112 (1999) 134–146.
  • 31 S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Configuration space analysis of travelling salesman problem, Journal Physique 46 (1985) 1277–1292.
  • 32 A. Langevin, F. Soumis, J. Desrosiers, Classification of travelling salesman problem formulation, Operational Research Letters 9 (1990) 127–132.
  • 33 S. Lin, B.W. Kernighan, An effective heuristic algorithm for travelling salesman problem, Operations Research (1973) 498–516.
  • 34 J. Lysgaard, Cluster based branching for the asymmetric traveling salesman problem, European Journal of Operational Research 119 (1999) 314–325.
  • 35 P. Miliotis, Using cutting planes to solve the symmetric travelling salesman problem, Mathematical programming 15 (1978) 177–188.
  • 36 J.Y. Potvin, Genetic algorithms for the travelling salesman problem, Annals of Operations Research 63 (1996) 339–370.
  • 37 R. Wong, Integer programming formulations of the travelling salesman problem, in: Proceedings of the IEEE International Conference of Circuits and Computers, 1980, pp. 149–152.
  • 38 B. Shirrish, J. Nigel, M.R. Kabuka, A boolean neural network approach for the travelling salesman problem, IEEE Transactions on Computers 42 (1993) 1271–1278.
  • 39 T. E. Davis and J.C. Principe. A simulated annealing-like convergence theory for the simple genetic algorithm. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms, pages 174–181. Morgan Kaufmann, San Mateo, CA, 1991.