SavedAdd your journal

Journals / Turkish Journal of Mathematics and Computer Science / 2018 / Cilt: 9 - Sayı: 9

An Improved Genetic Algorithm Crossover Operator for Traveling Salesman Problem

Abid HUSSAİNA
Yousaf Shad MUHAMMAD
Muhammad Nauman SAJİD
Pages
1–13
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Also, it requires less time for tuning of genetic parameters and provides narrower confidence intervals on the results than other operators.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The genetic algorithm is one of the best algorithms in order to solve many combinatorial optimization problems, especially traveling salesman problem.
📊
Key Findings & Data:The application of genetic algorithms to problems which are not amenable to bit string representation and traditional crossover has been a growing area of interest.
💡
Conclusion & Impact:Also, it requires less time for tuning of genetic parameters and provides narrower confidence intervals on the results than other operators.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Genetic algorithms · NP-hard · traveling salesman problems

Abstract

The genetic algorithm is one of the best algorithms in order to solve many combinatorial optimization problems, especially traveling salesman problem. The application of genetic algorithms to problems which are not amenable to bit string representation and traditional crossover has been a growing area of interest. One approach has been to represent solutions by permutations of a list, and “permutation crossover” operators have been introduced to preserve the legality of offspring. There are many existing schemes for permutation representation like PMX, OX, and CX etc. In this paper, we extend the CX scheme which produces healthy offspring based upon survival of the fittest theory. Comparison of the proposed operator with other ones for ten benchmarks TSPLIB instances vividly shows its pros at the same accuracy level. Also, it requires less time for tuning of genetic parameters and provides narrower confidence intervals on the results than other operators.

🔖

Cite This Article

HUSSAİNA, A., MUHAMMAD, Y. S., SAJİD, M. N. (2018). An Improved Genetic Algorithm Crossover Operator for Traveling Salesman Problem. Turkish Journal of Mathematics and Computer Science, Cilt: 9 - Sayı: 9, 1–13. https://ajindex.com/articles/374769

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (17)

  1. Ahmed, Z.H., Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator, Int J Biom Bioinformatics. 3(2010), 96–105.
  2. Bhide, S., John, N., Kabuka, M.R., A Boolean neural network approach for the traveling salesman problem, IEEE T COMPUT., 42(1993), 1271–1278.
  3. Bland, R.G., Shallcross, D.F., Large traveling salesmen problems arising from experiments in x-ray crystallography, Oper. Res. Lett., 8(1988), 125–128.
  4. Bolanos, R.I., Eliana, M.T.O., Mauricio, G.E., A population-based algorithm for the multi traveling salesman problem, International Journal of Industrial Engineering Computations, 7(2016), 245–256.
  5. Davis, L., Applying Adaptive Algorithms to Epistatic Domains, In: Proceedings of the International Joint Conference on Artificial Intelligence, 1985, 162–164.
  6. Deep, K., Adane, H.M., New variations of order crossover for traveling salesman problem International Journal of Combinatorial Optimization Problems and Informatics, 2(2011), 2–13.
  7. Dorigo, M., Gambardella, L.M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE T EVOLUT COMPUT., 1(1997), 53–66.
  8. Dorigo, M., Maniezzo, V., Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1996), 29–41.
  9. Finke, G., Claus, A., Gunn, E., A two-commodity network flow approach to the traveling salesman problem, Congressus Numerantium, 41(1984), 167–178.
  10. Gen M, Cheng R. Genetic algorithms and Engineering design. John Wiley and Sons, London, UK. 1997.
  11. Ghadle, K.P., Muley, Y.M., Traveling salesman problem with MATLAB programming, International Journal of Advances in Applied Mathematics and Mechanics, 2(2015), 258–266.
  12. Glover, F., Artificial intelligence, heuristic frameworks and tabu search, Managerial and Decision Economics, 11(1990), 365–375.
  13. Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Company, 1989.
  14. Goldberg, D.E., Lingle, R., Alleles, loci, and the traveling salesman problem, In: Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications. Hillsdale, New Jersey: Lawrence Erlbaum, 1985, 154–159.
  15. Holland, J.H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, University of Michigan Press,
  16. Oxford, UK, 1975.
  17. Hussain, A., Muhammad, Y.S., Sajid M.N., Hussain, I., Shoukr