We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

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

by ABDOUN Otman, ABOUCHABAKA Jaafar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 31 - Number 11
Year of Publication: 2011
Authors: ABDOUN Otman, ABOUCHABAKA Jaafar
10.5120/3945-5587

ABDOUN Otman, 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 ( October 2011), 49-57. DOI=10.5120/3945-5587

@article{ 10.5120/3945-5587,
author = { ABDOUN Otman, 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 },
issue_date = { October 2011 },
volume = { 31 },
number = { 11 },
month = { October },
year = { 2011 },
issn = { 0975-8887 },
pages = { 49-57 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume31/number11/3945-5587/ },
doi = { 10.5120/3945-5587 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:17:57.155393+05:30
%A ABDOUN Otman
%A ABOUCHABAKA Jaafar
%T Article:A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 31
%N 11
%P 49-57
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
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.

References
  1. 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.
  2. 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.
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, MIT press, 2010.
  4. Randy L. Haupt and Sue Ellen Haupt, PRACTICAL GENETICALGORITHMS, 2nd edition, A JOHN WILEY & SONS, INC., PUBLICATION, 2004.
  5. C. DARWIN. The origin of species by means of natural selection, 1859.
  6. Sue Ellen Haupt. Introduction toGenetic Algorithms. Artificial Intelligence Methods in the Environmental Sciences. Springer Science (103-126), 2009.
  7. 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.
  8. D. Goldberg, Genetic Algorithm in Search, Optimization, ans Machine Learning. Addison Wesley, 1989.
  9. Misevicius, A. (2004). Using iterated Tabu search for the traveling salesman problem. Information Technology and Control, 3(32), 29–40.
  10. Elaoud S, Loukil T, Teghem J (2007) A Pareto Fitness Genetic Algorithm: test function study. European Journal Operational Research, 177 (3), 1703-1719.
  11. 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.
  12. Albayrak Murat (2008). Determination of route by means of Genetic Algorithms for printed circuit board driller machines. Master dissertation (p. 180). Selcuk University.
  13. F. Glover, Artificial intelligence, heuristic frameworks and tabu search, Managerial & Decision Economics 11 (1990) 365–378.
  14. Lust T, Teghem J MEMOTS (2008) Amemetic algorithm integrating tabusarch for combinatorial multiobjective optimization. RAIRO, 42, 3-33.
  15. 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.
  16. 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.
  17. Dorigo, M., &Gambardella, L. M. (1997). Ant colonies for the traveling salesman problem. BioSystems, 43, 73–81.
  18. Zakir H. Ahmed. Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator. IJBB 3(6). 2010.
  19. 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.
  20. V. A. Cicirello. Non-wrapping order crossover : An order preserving crossover operator that respects absolute position. GECCO, pages 1125–1131, 2006.
  21. V. A. Cicirello and S. F. Smith. Modeling ga performance for control parameter optimization. GECCO, pages 235–242, 2000.
  22. R.K. Ahuja, T.L. Mangnanti, J.B. Orlin, Network Flows, Prentice-Hall, New Jersey, 1993.
  23. G. Laporte, The vehicle roting problem: an overview of exact and approximate algorithms, Eur. J. Oper. Res. 59 (2) (1992) 345–358.
  24. 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.
  25. G. Carpaneto, P. Toth, Some new branching and bounding criteria for the asymmetric traveling salesman problem, Management Science 26 (1980) 736–743.
  26. M. Gen, R. Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
  27. M. Fischetti, P. Toth, An additive bounding procedure for combinatorial optimization problems, Operations Research 37 (1989) 319–328.
  28. 29 G. Finke, A. Claus, E. Gunn, A two-commodity network flow approach to the traveling salesman problem, CongressusNumerantium 41 (1984) 167–178.
  29. 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.
  30. 31 S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Configuration space analysis of travelling salesman problem, Journal Physique 46 (1985) 1277–1292.
  31. 32 A. Langevin, F. Soumis, J. Desrosiers, Classification of travelling salesman problem formulation, Operational Research Letters 9 (1990) 127–132.
  32. 33 S. Lin, B.W. Kernighan, An effective heuristic algorithm for travelling salesman problem, Operations Research (1973) 498–516.
  33. 34 J. Lysgaard, Cluster based branching for the asymmetric traveling salesman problem, European Journal of Operational Research 119 (1999) 314–325.
  34. 35 P. Miliotis, Using cutting planes to solve the symmetric travelling salesman problem, Mathematical programming 15 (1978) 177–188.
  35. 36 J.Y. Potvin, Genetic algorithms for the travelling salesman problem, Annals of Operations Research 63 (1996) 339–370.
  36. 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.
  37. 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.
  38. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Travelers Salesman Problem Genetic Algorithm NP-Hard Problem Crossover Operator probability of crossover Genetic Algorithm

Powered by PhDFocusTM