Gezgin Satıcı Problemlerinin Metasezgiseller ile Çözümü

Abstract

Bu çalışmada, NP-zor problem sınıfından olan gezgin satıcı probleminin (GSP), stokastik optimizasyon tekniklerinin en genel sınıfı olan metasezgisel yöntemlerle çözümü ele alınmıştır. Klasik matematiksel yöntemlerle çözümü zor ve belli bir boyuttan sonra imkânsız olan problemler için metasezgisel yöntemler etkin bir çözüm alternatifidir. Uluslararası literatürde sıklıkla kullanılan metasezgisel yöntemlerin GSP problemlerine uygulanması konusunda genel bir bakış içeren çalışmaya, ulusal literatürde rastlanmamıştır. Bu amaçla yaygın kullanıma sahip 8 metasezgisel yöntem tanıtılmış ve literatürden alınan farklı boyutlardaki problemlere uygulanmıştır. Sonuçlar raporlanmış ve farklı açılardan yorumlanmıştır.

Keywords

• Gezgin Satıcı Problemi, Metasezgisel Yöntemler, Benchmark Problemleri, Optimizasyon

-

Abstract

Bu çalışmada, NP-zor problem sınıfından olan gezgin satıcı probleminin (GSP), stokastik optimizasyon tekniklerinin en genel sınıfı olan metasezgisel yöntemlerle çözümü ele alınmıştır. Klasik matematiksel yöntemlerle çözümü zor ve belli bir boyuttan sonra imkânsız olan problemler için metasezgisel yöntemler etkin bir çözüm alternatifidir. Uluslararası literatürde sıklıkla kullanılan metasezgisel yöntemlerin GSP problemlerine uygulanması konusunda genel bakış içeren çalışmaya, ulusal literatürde rastlanmamıştır. Bu amaçla yaygın kullanıma sahip 8 metasezgisel yöntem tanıtılarak bu yöntemler literatürden alınan farklı boyutlarda problemlere uygulanmıştır. Sonuçlar raporlanmış ve farklı açılardan yorumlanmıştır

Keywords

• Gezgin Satıcı Problemi, Metasezgisel Yöntemler, Benchmark Problemleri,Optimizasyon

References

1. E. Ateş, Karınca Kolonisi Optimizasyonu Algoritmaları İle Gezgin Satıcı Probleminin Çözümü Ve 3 Boyutlu Benzetimi, Basılmamış Lisans Tezi, Ege Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, İzmir, 2012.
2. V. V. Nabiyev, Yapay Zeka - İnsan Bilgisayar Etkileşimi, Seçkin Yayıncılık, Ankara, 2007.
3. E. Önder, M. Özdemir, B.F. Yıldırım, Combinatorial Optimization Using Artificial Bee Colony Algorithm And Particle Swarm Optimization. Kafkas Üniversitesi İktisadi ve İdari Bilimler Fakültesi (KAUİİBF) Dergisi, 4, 6, 59-70 (2013).
4. C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Mineola, NY: Dover, 308-309, 1998.
5. İ. Kara, T. Derya, E. Demir, T. Bektaş, “Genelleştirilmiş Gezgin Satıcı Probleminin Tamsayılı Doğrusal Karar Modeli”, Yöneylem Araştırması / Endüstri Mühendisliği 25. Ulusal Kongresi, Koç Üniversitesi, 4-6 Temmuz, İstanbul, 2005.
6. R. Matai, S.P. Singh, M.L. Mittal, “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches” in Traveling Salesman Problem, Theory and Applications Donald Davendra (Ed.), InTech, Croatia, 2010, 1- 24.
7. P. Mattsson, The Asymmetric Traveling Salesman Problem, Uppsala Universitet, 2010
8. N. Aras, B. Boyacı, D. Koşucuoğlu, D. Aksen, Karlı Gezgin Satıcı Problemi için Sezgisel Yöntemler, Yöneylem Araştırması / Endüstri Mühendisliği 27. Ulusal Kongresi, İzmir, 2007.

9. Ö.N. Koç, Zaman Pencereli Gezgin Satıcı Problemi İçin Yeni Karar Modelleri, Başkent Üniversitesi, Fen Bilimleri Enstitüsü, Basılmamış Yüksek Lisans Tezi, 2012.
10. B. Zhang, J. Peng, “Uncertain Traveling Salesman Problem”. Erişim linki: http://orsc.edu.cn/online/110731.pdf, 24 Ocak 2014 .
11. S. Yadlapalli, S.Rathinam, S. Darbha, 3-Approximation Algorithm for a Two Depot, Heterogeneous Traveling Salesman Problem. Optimization Letters, 6, 1, 141-152 (2012).
12. B.W. Haskell, A. Toriello, M. Poremba, D.J. Epstein, A Dynamic Traveling Salesman Problem with Stochastic Arc Costs Department of Industrial and Systems Engineering University of Southern California Los Angeles, California (2013).
13. İ. Kara, E. Demir, Genelleştirilmiş Gezgin Satıcı Poblemi İçin Yeni Tamsayılı Karar Modelleri, Yöneylem Araştırması / Endüstri Mühendisliği 26. Ulusal Kongresi, Kocaeli Üniversitesi, 3-5 Temmuz, Kocaeli, 2006.
14. C.S. Helvig, G. Robins, A. Zelikovsky, The Moving-Target Traveling Salesman Problem Volition Inc. Journal of Algorithms, 153-174 (1998).
15. M. Diaby, The Traveling Salesman Problem: A Linear Programming Formulation. WSEAS Transactions on Mathematics, 6, 6, 745–754 (2007).
16. C. Malandraki, RB. Dial, A Restricted Dynamic Programming Heuristic Algorithm for Time Dependent Traveling Salesman Problem. European Journal of Operations Research, 90, 1, 45–55 (1996).
17. M.Padherg, R. Rinaldi, Optimization of a 532-City Symmetric Travelling Salesman Problem by Branch and Cut. Operations Research Letters, 6, 1, 1-7 (1987).
18. M. Padberg, G. Rinaldi, Branch-and-Cut Approach to a Variant of the Traveling Salesman Problem. Journal of Guidance, Control, and Dynamics, 11, 5, 436–440 (1988).
19. S.Lin, B. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21, 2, 498-516 (1973).
20. A. Punnen, F. Margot, S.Kabadi, TSP Heuristics: Domination Analysis and Complexity. Algorithmica, 35, 111–127 (2003).
21. O. Martin, S. Otto, E. Felten, Large-step markov chains for the traveling salesman problem. Complex Systems, 5, 3, 299-326 (1991).
22. S. Kirkpatrick, C. D. Gelatt, M. P. Vechi, Optimization by Simulated Annealing. Science, 220, 4598, 671-680 (1983).
23. S. Kirkpatrik, Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, 34, 1984, 975-986 (1984).
24. JB. Wu, SW. Xiong, N. Xu, Simulated Annealing Algorithm Based on Controllable Temperature for Solving TSP. Application Research of Computers, 24, 5, 66–89 (2007).
25. M.Dam, M. Zachariasen, Tabu Search on the geometric travelling salesman problem. Meta-heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, 571-587, 1996.
26. Y. Wu, X. Zhou, Meliorative Tabu Search Algorithm for TSP Problem. Journal of Computer Engineering and Applications, 44, 1, 57–59 (2008).
27. C.A. Hurkens, G.J. Woeginger, On the Nearest Neighbor Rule for the Traveling Salesman Problem. Operations Research Letters, 32, 1, 1-4 (2004).
28. M. Dry, K. Preiss, J. Wagemans, Clustering, Randomness, and Regularity: Spatial Distributions and Human Performance on the Traveling Salesperson Problem and Minimum Spanning Tree Problem. The Journal of Problem Solving, 4, 1, 2 (2012).
29. S.Akyol, B. Alataş, Güncel Sürü Zekası Optamizasyon Algoritmaları. Nevşehir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 1, 1, 36-50 (2012).
30. M.B. Fogel, The Genetic Algorithm for TSP. IEEE Transaction on systems, 16, 1-13 (1986).
31. S. Chatterjee, C. Carrera, L. A. Lynch, Genetic Algorithms and Traveling Salesman Problems. European Journal of Operational Research, 93, 3, 490-510 (1996).
32. P. Larranaga, C.M.H. Kujipers, R.H. Murga, I.Innza, S. Dizdarevic, Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13, 2, 129-170 (1999).
33. H.K. Tsai, J.M. Yang, Y.F. Tsai, C.Y. Kao, Heterogeneous Selection Genetic Algorithms for Traveling Salesman Problems. Engineering Optimization, 35, 3, 297– 311 (2003).
34. S.S. Ray, S. Bandyopadhyay, S.K. Pal, New Operators of Genetic Algorithms for Travelling Salesman Problem. Proceedings of the 17th International Conference on Pattern Recognition, 23 – 26 August 2004, Cambridge, 497-500, (2004).
35. J.H. Yang, C.G. Wu, H.P. Lee, Y.C. Liang, Solving Traveling Salesman Problems Using Generalized Chromosome Genetic Algorithm. Progress in Natural Science, 18, 887–892 (2008).
36. Z. Tao, TSP Problem Solution Based On Improved Genetic Algorithm. In proceedings of the 2008 Fourth International Conference on Natural Computation, ICNC, IEEE Computer Society, Washington, DC, vol. 01, 686-690, 2008.
37. B.F. Al-Dulaimi, A.A. Hamza, Enhanced Travelling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA). Proceedıngs Of World Academy Of Scıence, Engıneerıng And Technology, 28, 296-302 (2008).
38. M. Bhattacharyya, A.K. Bandyopadhyay, Comparative Study of Some Solution Methods for Traveling Salesman Problem Using Genetic Algorithms. Cybernetics and Systems, 40, 1–24 (2009).
39. O.M. Sallabi, Y. El-Haddad, An Improved Genetic Algorithm to Solve the Travelling Salesman Problem. World Academy of Science, Engineering and Technology, 3, 403-406 (2009).
40. L. Shi, Z.Li, An Improved Pareto Genetic Algorithm for Multi-Objective TSP. Fifth International Conference on Natural Computation, Tianjian, China, 585–588, 2009.
41. S. Elaoud, J. Teghem, T. Loukil, Multiple Crossover Genetic Algorithm for the Multi- Objective Traveling Salesman Problem. Electron Notes Discrete Math, 36, 939–946 (2010).
42. M.Albayrak, N. Allahverdi, Development a New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms. Expert Systems with Applications, 38, 1313–1320 (2011).
43. M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53–66 (1997).
44. T. Stutzle, H. Hoos, “The MAX–MIN Ant System and Local Search for the Traveling Salesman Problem”. In Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, USA, 309–314, 1997.
45. J. Montgomery, M. Randall, The Accumulated Experience Ant Colony for the Traveling Salesman Problem. International Journal of Computational Intelligence and Applications, 3, 189–198 (2003).
46. C. Garcı´a-Martı´nez, O. Cordo´n, F. Herrera, An Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-Criteria TSP. Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), 61–72, (2004).
47. J. L. Liu, Rank-Based Ant Colony Optimization Applied to Dynamic Traveling Salesman Problems. Engineering Optimization, 37, 8, 831–847 (2005).
48. Q. Zhu, S. Chen, “A new Ant Evolution Algorithm to Resolve TSP Problem”. IEEE Sixth Conference On Machine Learning and Applications (ICMLA), Cicinnati, Ohio, USA, 62-66, 2007.
49. F. Herrera, C. Garcia-Martinez, O. Cordon, A Taxonomy and an Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-Criteria TSP. European Journal of Operations Research, 80, 1, 116–148 (2007).
50. C. Xu, J. Xu, H. Chang, “Ant Colony Optimization Based on Estimation of Distribution For The Traveling Salesman Problem”, Fifth international conference on natural computation, Tianjin, China, 19–23, 2009.
51. L. Wong, Y.H.P. Low, C.S. Chong, “A Bee Colony Optimization Algorithm for Traveling Salesman Problem. Modeling ve Simulation”, AICMS 08. Second Asia International Conference on Modelling and Simulation, Kuala Lumpur, Malaysia, 818-823, 2008.
52. L. Wong, Y.H.P. Low, C.S. Chong, A Bee Colony Optimization with Local Search for Travelling Salesman. International Journal on Artificial Intelligence Tools, 19, 3, 305–334 (2010).
53. X. Zhang, Q. Bai, X. Yun, “A New Hybrid Artificial Bee Colony Algorithm for the Traveling Salesman Problem”, IEEE 3rd International Conference on Communication Software and Networks, China, 155-159, 2011.
54. D. Karaboğa, B. Görkemli, “A combinatorial Artificial Bee Colony Algorithm for Traveling Salesman Problem”, INISTA 2011 - 2011 International Symposium on Innovations in Intelligent Systems and Applications, İstanbul, Turkey, 50-53, 2011.
55. T. Nakaguchi, K. Jin’no, M. Tanaka, “Hysteresis Neural Networks for Solving Travelling Salesman Problems”, 2000 IEEE International Symposium on Circuits and Systems, Switzerland, 03, 153-156, 2000.
56. K.S. Leung, H.D. Jin, Z.B. Xu, An Expanding Self-Organizing Neural Network for the Traveling Salesman Problem. Neurocomputing, 6, 267–292, (2004).
57. T.A.S. Masutti, L.N. de Castro, A Self-Organizing Neural Network Using İdeas From The İmmune System To Solve The Traveling Salesman Problem. Information Sciences, 179, 1454–1468 (2009).
58. M. Li, Z. Yi, M. Zhu, Solving TSP by using Lotka-Volterra Neural Networks. Neurocomputing, 72, 16–18, 3873–3880 (2009).
59. L.N. De Castro, F.J. Von Zuben, The Clonal Selection Algorithm With Engineering Applications. In Proceedings of GECCO, 2000, 36-39, (2000).
60. S. Gao, H. Dai, G. Yang, Z. Tang, A Novel Clonal Selection Algorithm and İts Application to Traveling Salesman Problem. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences Series A, 90, 10, 2318 (2007).
61. H. Dai, Y. Yang, C. Li, Distance Maintaining Compact Quantum Crossover Based Clonal Selection Algorithm. Journal of Convergence Information Technology, 5, 10, 56-65 (2010).
62. A. Baykasoglu, A. Saltabas, A. S. Tasan, K. Subulan, Yapay Bagışıklık Sisteminin Çoklu Etmen Benzetim Ortaminda Realize Edilmesi ve GSP Uygulanması, Journal of the Faculty of Engineering ve Architecture of Gazi University. 27, 4, 901-909 (2012).
63. K.P. Wang, L. Huang, C.G. Zhou, W. Pang, “Particle swarm optimization for traveling salesman problem. In Machine Learning and Cybernetics”, 2003 International Conference on Machine Learning and Cybernetics, China 3, 1583-1585 2003.
64. H. Shah-Hosseini, “Problem Solving by Intelligent Water Drops”, 2007 IEEE Congress on Evolutionary Computation (CEC 2007), Siingapore, 3226-3231, 2007.
65. N. Javadian, M.G. Alikhani, R. Tavakkoli-Moghaddam, A Discrete Binary Version of the Electromagnetism-Like Heuristic for Solving Traveling Salesman Problem. In Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence, 123-130 (2008).
66. M. Gerşil, T. Palamutçuoğlu, Ders Çizelgeleme Probleminin Melez Genetik Algoritmalar İle Performans Analizi. Niğde Üniversitesi İİBF Dergisi, 6, 1, 242-262 (2013).
67. V. Yiğit, O. Türkbey, Tesis Yerleşim Problemlerine Sezgisel Metotlarla Yaklaşım, Gazi Üniversitesi Mühendislik. Mimarlık Fakültesi Dergisi, 18, 4, 45-56 (2003).
68. S. Luke, Essentials of Metaheuristics, Second Edition, Lulu, USA, 2013.
69. H.R. Lourenço, O.C. Martin, T. Stutzle, “A Beginner’s Introduction to Iterated Local Search”, 4th Metaheuristics International Conference (MIC’01), Porto, Portugal, 16- 20, 2001.
70. A. Juan, H.R. Lourenço, M. Mateo, R. Luo, Q. Castella, Using Iterated Local Search For Solving the Flow-Shop Problem:Paralleization. Parametrization and Randomization Issues, 103-126 (2013).
71. N.S. Kumbharana, G.M. Pandey, A Comparative Study of ACO, GA and SA for Solving Travelling Salesman Problem. International Journal of Societal Applications of Computer Science, Vol 2, Issue 2, (February 2013).
72. A. Söke, Z. Bingül, İki Boyutlu Giyotinsiz Kesme Problemlerinin Benzetilmiş Tavlama Algoritması ile Çözümlerinin İncelenmesi. Politeknik Dergisi, 8, 1, 25-35 (2005).
73. A. Tokgöz, S. Bulkan, Weapon Target Assignment with Combinatorial Optimization Techniques. (IJARAI) International Journal of Advanced Research in Artificial Intelligence, 2, 7 (2013).
74. F. Glover, Future Paths For İnteger Programming and Links to Artificial İntelligence, Computer and Operation Research, 13, 533-549 (1986).
75. P. Hansen, “The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming”, Proceedings of the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986.
76. T. Cura, Modern Sezgisel Teknikler ve Uygulamaları, Papatya Yayıncılık, İstanbul, 2008.
77. D. Karaboğa, Yapay Zekâ Optimizasyon Algoritmaları, Genişletilmiş II. Basım, Nobel Yayın Dağıtım, İstanbul, 2011.
78. K. Güney, A. Akdağlı, “Tabu Araştırma Algoritması İle Lineer Anten Dizisinin Genlik Uyarım Katsayılarının Belirlenmesi”, 8. Ulusal Elektrik Elektronik Bilgisayar Mühendisliği Kongresi, Gaziantep Üniversitesi, 456-459, 1999.
79. J.M. Pollard, Monte Carlo Methods for Index Computation (mod p). Mathematics of Computation, 32, 143, 918–924 (1978).
80. P. van Oorschot, M. Wiener, On Diffie-Hellman Key Agreement with Short Exponents. Advances in Cryptology, 332-343 (1996).
81. L. Duta, J.M. Henrioud, I. Caciula, “A Real Time Solution to Control Disassembly Processes”, Proceedings of the 4th IFAC Conference on Management and Control of Production and Logistics, Sibiu, 2007.
82. Y.E. Demirtaş, T. Keskintürk, Kanguru Algoritması ve Gezgin Satıcı Problemine Uygulanması. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 10, 19, 51-63 (2011).
83. D. Karaboğa, An İdea Based On Honey Bee Swarm For Numerical Optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
84. J. McCaffrey, “Natural Algorithms: Use Bee Colony Algorithms to Solve Impossible Problems”, MSDN Magazines, erişim linki: http://msdn.microsoft.com/en- us/magazine/gg983491.aspx, 24 Ocak 2014.
85. D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley Publishing Company, USA, 1989.
86. Z. Michalewicz, Genetic Algorithms + Data Structure = Evolution Programs, Springer-Verlag, Berlin, 1992.
87. C.R. Reeves, Modern heuristic techniques for combinatorial problems, McGraw-Hill Book Company Inc., Europe. 1995. [88] M. Obitko, Genetic Algorithms, (Online), erişim linki: http://cs.felk.cvut.cz/~xobitko/ga/ Hochschule für Technik und Wirtschaft Dresden (FD), (1998).
88. R. Sarker, C. Newton, A Genetic Algorithm for Solving Economic Lot Size Scheduling Problem. Computer & Industrial Engineering, 12, 5, 195-196 (2002).
89. R. Cheng, M. Gen, T. Yasuhiro, A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies. Computers and Industrial Engineering, 36, 343-364 (1999).
90. T. Keskintürk, S. Şahin, Doğrusal Olmayan Regresyon Analizinde Gerçek Değer Kodlamalı Genetik Algoritma. İTÜ Sosyal Bilimler Dergisi, 8, 167-178 (2009).
91. T. Keskintürk, H. Söyler, Global Karınca Kolonisi Optimizasyonu. Gazi Üniversitesi Mimarlık ve Mühendislik Dergisi, 21,689-698 (2006).
92. H. Söyler, T. Keskintürk, “Karınca Kolonisi Algoritması İle Gezen Satıcı Probleminin Çözümü”, 8. Türkiye Ekonometri ve İstatistik Kongresi, Malatya, 1-11, 2007.
93. M. Dorigo, Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale (Optimization, Learning and Natural Algorithms), Ph.D.Thesis, Politecnico di Milano, Italy, in Italian. DT.01-POLIMI92, 1992.
94. J. Brownlee, Clever Algorithms, Nature-Inspired Programming Recipes, Open Source Book, erişim linki: http://www.CleverAlgorithms.com, 2012. [96] TSPLIB. Erişim linki:
95. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ Online, 12.12.2013.
96. K. Deep, H. Mebrahtu, Variant of partially mapped crossover for the Travelling Salesman Problems. International Journal of Combinatorial Optimization Problems and Informatics, 3, 1, 47-69, (2012).
97. T. Keskintürk, “Permutasyon Kodlamalı Genetik Algoritmada Operatörlerin Etkinliklerinin Araştırılması”, VI. Ulusal Üretim Araştırmaları Sempozyumu, İstanbul, 225-231, 2006.