Gezgin Satıcı Probleminin Genetik Algoritmalar Kullanarak Çözümünde Çaprazlama Operatörlerinin Örnek Olaylar Bazlı İncelenmesi

Year 2019, Volume: 34 Issue: 2, 225 - 243, 30.06.2019

Meryem Pulat , İpek Deveci Kocakoç

https://doi.org/10.24988/ije.2019342825

Cited By: 4

Abstract

Gezgin
satıcı problemi, optimizasyon alanında araştırmacı ve akademisyenler tarafından
üzerinde uzun yıllardır yoğun olarak çalışılan çözümü zor (NP-hard) bir
problemdir. Genetik algoritmalar GSP (gezgin satıcı problemi) gibi çeşitli
NP-hard problemleri çözmek için kullanılan en iyi yöntemlerden biridir. GSP
problemi için çok sayıda çaprazlama operatörü önerilmiştir ve her çalışmada
yenileri önerilmeye devam etmektedir. Bu çalışmanın amacı GSP çözümünü
araştıran çalışmalarda kullanılan TSPLIB örnek olaylarının ve incelenen
çaprazlama operatörlerinin detaylı bir envanterini çıkarmak ve bu konuda
çalışmak isteyen araştırmacılara yön göstermektir. Literatürdeki çalışmalar
geniş bir kapsamda (anahtar kelime ve yıl bazında) incelenerek ortak kullanılan
örnek olayların ve bulunan sonuçların analizi yapılarak tablolaştırılmıştır.

Keywords

Gezgin Satıcı Problemi, Genetik Algoritmalar, Çaprazlama operatörü, TSPLIB

Investigation Of Crossover Operators Using Genetic Algorithms In The Solution Of The Traveling Salesman Problem Based On Case Studies

Abstract

The
Traveling salesman problem is a difficult (NP-hard) problem that has been
studied intensively by researchers and academics in the field of optimization
for many years. Genetic algorithms are one of the best methods used to solve
various NP-hard problems, such as TSP (traveling salesman problem). Many
crossover operators have been proposed for the tsp problem and new ones have
been proposed in each study. Our aim in this study is to guide the researchers
who want to work on this subject by taking out a detailed inventory of the
TSPLIB case studies and the crossover operators that are used in the studies
that are investigating the tsp solution. Studies in the literature have been
examined in a wide range of contexts (based on keyword and year), and the
sample events and the results have been analyzed.

Keywords

Traveling Salesman Problem, Genetic Algorithms, Crossover operator, TSPLIB

References

• ABDEL-MOETTY, S. M., HEAKIL, A. O. (2012), “Enhanced Traveling Salesman Problem Solving Using Genetic Algorithm Technique with Modified Sequential Constructive Crossover Operator”, International Journal of Computer Science and Network Security (IJCSNS), 12(6), 134.
• ABDOUN, O., ABOUCHABAKA, J., TAJANI, C. (2012), “Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem”, International Journal of Emerging Sciences, 2(1), 61-77.
• AFFENZELLER, M., WAGNER, S. (2003), “A Self-Adaptive Model for Selective Pressure Handling Within the Theory of Genetic Algorithms”, In International Conference on Computer Aided Systems Theory, 384-393.
• AFFENZELLER, M., WAGNER, S. (2003, June), “SASEGASA: An Evolutionary Algorithm for Retarding Premature Convergence by Self-Adaptive Selection Pressure Steering”, In International Work-Conference on Artificial Neural Networks, 438-445. Springer, Berlin, Heidelberg.
• AFFENZELLER, M., WAGNER, S. (2004), “Reconsidering the Selection Concept of Genetic Algorithms from A Population Genetics Inspired Point of View”, Cybernetics and Systems, 701–706.
• AGARWAL, T., SINGH, K. (2013), “Using New Variation Crossover Operator of Genetic Algorithm for Solving the Traveling Salesmen Problem”, MIT International Journal of Computer Science and Information Technology, 3(1), 35-37.
• AHMED, Z. H. (2010), “Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator”, International Journal of Biometrics & Bioinformatics (IJBB), 3(6), 96–105.
• ALLAOUA, H., BRAHIM, B. (2015), “A Mono Crossover Genetic Algorithm for TSP”, Global Journal on Technology, Issue 7 (2015): 4th World Conference on Innovation and Computer Sciences (INSODE-2014).
• AMOUS, S. K., LOUKIL, T., ELAOUD, S., DHAENENS, C. (2008), “A New Genetic Algorithm Applied to the Traveling Salesman Problem”, International Journal of Pure and Applied Mathematics, 48(2), 1-16.
• CHAWLA, G., BALA, M. Y. (2014), “Solving Optimization Problem by Hybrid Genetic Algorithm Using Hill Climbing in Replacement Operator”, Journal of Recent Research Aspects, 2(4), 73-78.
• CHEN, S., SMITH, S. F. (1996), “Commonality And Genetic Algorithms”, Carnegie Mellon University, The Robotics Institute.
• CONTRERAS-BOLTON, C., PARADA, V. (2015), “Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem”, PloS one, 10(9).
• ÇOLAK, S. (2010), “Genetik Algoritmalar Yardımı ile Gezgin Satıcı Probleminin Çözümü Üzerine Bir Uygulama”, Ç.Ü. Sosyal Bilimler Enstitüsü Dergisi, 19(3), 423–438.
• DEEP, K., MEBRAHTU, H. (2011), “Combined Mutation Operators of Genetic Algorithm for the Travelling Salesman problem”, International Journal of Combinatorial Optimization Problems and Informatics, 2(3), 1–23.
• DEEP, K., MEBRAHTU, H. (2012), “Variant of Partially Mapped Crossover for the Travelling Salesman Problems”, International Journal of Combinatorial Optimization Problems and Informatics, 3(1), 38-60.
• ELHADDAD, Y. R., GANNOUS, A. S. (2012), “Two Individual Genetic Algorithm”, World Academy of Science, Engineering and Technology, International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, 6(3), 209-212.
• ELMAS, Ç. (2016), Yapay Zekâ Uygulamaları, Seçkin Yayıncılık, Ankara.
• ESMKHAN, H. I., ZAMANIFAR, K. (2012), “Developing Improved Greedy Crossover to Solve Symmetric Traveling Salesman Problem”, International Journal of Computer Science Issue, 4(3), 1-6.
• FREISLEBEN, B., MERZ, P. (1996, September), “New Genetic Local Search Operators for the Traveling Salesman Problem”, In International Conference on Parallel Problem Solving from Nature, 890-899.
• FREISLEBEN, B., MERZ, P. (1996), “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems”, In Proceedings of IEEE İnternational Conference on Evolutionary Computation, IEEE, 616-621.
• GERŞİL, M., ALKAYA, A. (2011), “Gezgin Satıcı Problemi için Sezgisel Metotların Performans Analizi”, XI. Üretim Araştırmaları Sempozyumu, 23-24 Haziran 2011, 405–412.
• GHOSEIRI, K., SARHADI, H. (2007), “A 2opt-DPX Genetic Local Search for Solving Symmetric Traveling Salesman Problem”, In 2007 IEEE İnternational Conference on İndustrial Engineering and Engineering Management, 903-906.
• GIRDHAR GOPAL, R. K., JAWA, I., KUMAR, N. (2015), “Enhanced Order Crossover for Permutation Problems”, International Journal of Innovative Research in Science, Engineering and Technology (An ISO 3297: 2007 Certified Organization), 4(2).
• GOG, A., CHIRA, C. (2011, May), “Comparative Analysis of Recombination Operators in Genetic Algorithms for The Travelling Salesman Problem”, In International Conference on Hybrid Artificial Intelligence Systems, 10-17. Springer, Berlin, Heidelberg.
• GOPAL, G., KUMAR, R., JAWA, I., KUMAR, N. (2015), “Enhanced Order Crossover for Permutation Problems”, International Journal of Innovative Research in Science, Engineering and Technology, 4(2), 151–157.
• HEYMENDRAN, J., PRIYATHARSAN, U., HEMIJA, P. (2015), “A Representation with Novel Crossover Technique of the Genetic Algorithm for the Travelling Salesmen Problem”, Research Journal of Mathematical and Statistical Sciences, 3(2), 1-3.
• ISMKHAN, H., ZAMANIFAR, K. (2015), “Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, Using Symmetric Travelling Salesman Problem”, International Journal of Computer Applications, 80 (6).
• ISMKHAN, H., ZAMANIFAR, K. (2012), “Developing Improved Greedy Crossover to Solve Symmetric Traveling Salesman Problem”, Int J. Comput. Sci., 9 (4), 121-126.
• JAVIDI, M. M., FARD, R. H., JAMPOUR, M. (2015), “Research in Random Parameters of Genetic Algorithm and Its Application on TSP and Optimization Problems”, Walailak Journal of Science and Techonology, 12(1), 27–34.
• JONG, K. A. De, SPEARS, W. M. (1989), “Using Genetic Algorithms to Solve NP-Complete Problems”, In:ICGA, 124–132.
• JYOTISHREE, R. K. (2012), “Novel Knowledge Based Tabu Crossover in Genetic Algorithms”, International Journal, 2(8).
• KARABOĞA, D. (2014), Yapay Zekâ Optimizasyon algoritmaları, Nobel Yayın Dağıtım, İstanbul.
• KATAYAMA, K., HIRABAYASHI, H., NARIHISA, H. (1999), “Performance Analysis for Crossover Operators of Genetic Algorithm”, Systems and Computers in Japan, 30(2), 20-30.
• KHAN, I. H. (2015), “Assessing Different Crossover Operators for Travelling Salesman Problem”, IJ Intelligent Systems and Applications, 11, 19-25.
• KUMAR, R., GOPAL, G., KUMAR, R. (2013), “Alpha Cut based Novel Selection for Genetic Algorithm”, International Journal of Computer Applications, 13-17.
• KUMAR, N., KARAMBIR, KUMAR, R. (2012), “A Comparative Analysis of PMX, CX and OX Crossover operators for solving Travelling Salesman Problem”, International Journal of Latest Research in Science and Technology, 1(2).
• KUMAR, R., GOPAL, G., KUMAR, R. (2013), “Novel Crossover Operator for Genetic Algorithm for Permutation Problems”, International Journal of Soft Computing and Engineering (IJSCE), 3(2), 252-258.
• LARRANAGA, P., KUJPERS, C. M. H., MURGA, R. H., INZA, I., DIZDAREVIC, S. (1999), “Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators”, Artificial Intelligence Review, 13(2), 129–170.
• LI, L., ZHANG, Y. (2007, August), “An İmproved Genetic Algorithm for the Traveling Salesman Problem”, In International Conference on Intelligent Computing, 208-216.
• LOUIS, S. J., ve LI, G. (2000), “Case Injected Genetic Algorithms for Traveling Salesman Problems”, Information sciences, 122(2-4), 201-225.
• MAEKAWA, K., MORI, N., TAMAKI, H., KITA, H., NISHIKAWA, Y. (1997), “A Genetic Solution for The Traveling Salesman Problem by means of a Thermodynamical Selection Rule”, Transactions of the Society of Instrument and Control Engineers, 33(9), 939-946.
• MAJUMDAR, J., BHUNIA A.K. (2011), “Genetic Algorithm for Asymmetric Traveling Salesman Problem with Imprecise Travel Times”, Journal of Computational and Applied Mathematics, 235 (9), 3063–3078.
• MARTINOVIC, G., BAJER, D. (2011), “Impact of Double Operators on The Performance of a Genetic Algorithm for Solving the Traveling Salesman Problem”, In International Conference on Swarm, Evolutionary and Memetic Computing, Springer, Berlin, Heidelberg, 290-298.
• MATHIAS, K., WHITLEY, D. (1992), "Genetic Operators, The Fitness Landscape and the Traveling Salesman Problem", In PPSN, 219-228.
• MERZ, P. (2002, July), “A Comparison of Memetic Recombination Operators for The Traveling Salesman Problem”, In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, 472-479.
• MERZ, P., FREISLEBEN, B. (1997, April), “Genetic Local Search for the TSP: New Results”, In Proceedings of 1997 Ieee International Conference on Evolutionary Computation (Icec'97), 159-164.
• MICHALEWICZ, Z. (1992), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Vergal, Berlin.
• MITCHELL, G. G., O'DONOGHUE, D., TRENAMAN, A. (2000), “A New Operator for Efficient Evolutionary Solutions to The Travelling Salesman Problem”, In Proc. Applied Informatics, 771-774.
• MOHEBPOUR, G. H., DELAVAR, A. G. (2014), “CCGDC: A New Crossover Operator for Genetic Data Clustering”, The Journal of Mathematics and Computer Science, 11, 191-208.
• NAVEEN, K., KARAMBIR, R. K. (2012), “A Comparative Analysis of PMX, CX and OX Crossover Operators for Solving Travelling Salesman Problem”, International Journal of Latest Research in Science and Technology, 1(2), 98-101.
• NGUYEN, H. D., YOSHIHARA, I., YASUNAGA, M. (2000), “Modified Edge Recombination Operators of Genetic Algorithms for The Traveling Salesman Problem”, In 2000 26th Annual Conference of the IEEE Industrial Electronics Society. IECON 2000, 2815-2820.
• NGUYEN, H. D., YOSHIHARA, I., YAMAMORİ, K., YASUNAGA, M. (2002), “Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs”, IPSJ Transactions on Mathematical Modeling and Its Applications, 43(10), 165-175.
• NILSSON, C. (2003), “Heuristics for the Traveling Salesman Problem”, Linköping University, Sweden, 1-6.
• OSABA, E., CARBALLEDO, R., DÍAZ, F., PERALLOS, A. (2013, May), “Analysis of the Suitability of Using Blind Crossover Operators in Genetic Algorithms for Solving Routing Problems”, In 2013 IEEE 8th International Symposium on Applied Computational Intelligence and Informatics (SACI), 17-22. IEEE.
• PONGCHAROEN, P., CHAINATE, W., THAPATSUWAN, P. (2007), “Exploration of Genetic Parameters and Operators through Travelling Salesman Problem”, ScienceAsia, 33(2), 215–222.
• POTVIN, J.-Y. (1996), “Genetic Algorithms for the traveling salesman problem”, Annals of Operations Research, 63(3), 337–370.
• RANI, K., KUMAR, V. (2014), “Solving Travelling Salesman Problem Using Genetic Algorithm Based on Heuristic Crossover and Mutation Operator”, International Journal of Research in Engineering & Technology, 2(2), 27-34.
• RAY, S. S., BANDYOPADHYAY, S., PAL, S. K. (2005), “New Genetic Operators for Solving TSP: Application to Microarray Gene Ordering”, In International Conference on Pattern Recognition and Machine Intelligence, 617-622.
• RAY, S. S., BANDYOPADHYAY, S., PAL, S. K. (2004), “New Operators of Genetic Algorithms for Traveling Salesman Problem”, In Proceedings of the 17th International Conference on Pattern Recognition (ICPR), (2), 497–500.
• RAZALI, N. M., GERAGHTY, J. (2011), “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP”, In Proceedings of the World Congress on Engineering, Hong Kong, 2(1), 1-6.
• SCHNEIDER, J. J., KIRKPATRICK, S. (2006), “Application of genetic algorithms to TSP”, Stochastic Optimization, 415-422.
• SENGOKU, H., YOSHIHARA, I. (1998, January), “A Fast TSP Solver Using GA on JAVA”, In Third International Symposium on Artificial Life and Robotics (AROB III’98), 283-288.
• STARKWEATHER, T., MCDANIEL, S., MATHIAS, K. E., WHITLEY, L. D., ve WHITLEY, C. (1991, July), “A Comparison of Genetic Sequencing Operators”, In ICGA 69-76.
• TANG, A. Y. C., LEUNG, K. S. (1994, October), “A Modified Edge Recombination Operator for the Travelling Salesman Problem”, In International Conference on Parallel Problem Solving from Nature, 180-188.
• TAO, Z. (2008, October), “TSP Problem Solution Based on Improved Genetic Algorithm”, In 2008 Fourth International Conference on Natural Computation, Vol.1, 686-690.
• TAO, G., MICHALEWICZ, Z. (1998, September), “Inver-Over Operator for the TSP”, In International Conference on Parallel Problem Solving from Nature, 803-812.
• TSAI, H. K., YANG, J. M., TSAI, Y. F., KAO, C. Y. (2004) “Some Issues of Designing Genetic Algorithms for Traveling Salesman Problems”, Soft Computing, 8(10), 689-697.
• YANG, Y., DAI, H., LI, H. (2010), “Adaptive Genetic Algorithm with Application for Solving Traveling Salesman Problems”, International Conference on Internet Technology and Applications, 1–4.
• https://tinyurl.com/y8z5vezt