Waled Milad Abulsasem ALASHHEB, Adil Deniz DURU, Oğuz BAYAT, Osman Nuri UÇAN

GEZGİN SATICI PROBLEMİNİN ÇÖZÜMÜ İÇİN KARINCA KOLONİ VE GENETİK ALGORİTMALARININ KARŞILAŞTIRILMASI

ÖzetPolinom zamanda çözülebilecek (P) ve polinom zamanda doğrulanabilecek (NP) problemlerin bilinen etkinbir algoritmasının olmaması, hesaplamadaki karmaşıklık teorisinin teorik hesaplama ve matematiğin gereklibir bilimsel çalışma kolu olmasını sağlamıştır. Gezgin satıcı problemi (GSP) bu tür problemlere örnektir.Bu problemde, satıcı tarafından belli sayıda şehirin ziyaret edilmesi istenir. Başlangıç ve bitiş şehri olarakaynı şehir ele alınır. GSP’nin amacı bir turu en az mesafe ve zamanda bitirmesidir. Evrimsel algoritmalar, GSPçözümü için kullanılan popüler yöntemlerdendir. Bu algoritmalar genelde doğada oluşan olayların benzeşiminitemel almaktadır. Günümüzde, karınca kolonisi eniyileştirmesi (KKE) ve genetik algoritma (GA) bu türalgoritmalara örnektir. Bu tez kapsamında, GSP çözümü KKE ve GA ile gerçekleştirilerek sonuçları karşılaştırılmıştır.Deneyler sonucu elde edilen sonuçlar, KKE nun GA dan daha başarılı sonuç verdiği ve aynı probleminçözümü için daha az zaman kullandığı görülmüştür.

Anahtar Kelimeler:

Gezgin satıcı problem, Eniyileştirme, Genetik Algoritma, Karınca Kolonisi Eniyileştirme

COMPARISION OF ANT COLONY AND GENETIC ALGORITHMS FOR THE SOLUTION OF TRAVEL SALESMAN PROBLEM

Abstract

Keywords:

Problem of Traveling Salesman, Optimization, Genetic Algorithm, Optimization of Ant Colony,

PDF

___

A. Hashim, H. Muhammad , H. Fazl, Ahmadullah, Salman, and S. Yasir. 2016. “Solving Traveling Salesman Problem through Optimization Techniques Using Genetic Algorithm and Ant Colony Optimization”, Journal of Applied Environmental and Biological Sciences, 6(4S)55-62, 2016.
B. Kylie. 2000. Genetic Algorithms and the Traveling Salesman Problem, Harvey Mudd college, Department of Mathematics
B.Shuoben, D. Xueshi and M. Yan. 2012. ” The Design and Analysis of TSP Problem Based on Genetic Algorithm and Ant Colony Algorithm”, I.J. Education and Management Engineering, vol. 9, p. 56-60, 2012.
Ç. Cergibozan. 2013. “Meta-Heuristic Solution Approaches For Traveling Salesman And Traveling Repairman Problems,” Dokuz Eylül University Master Thesis, İzmir, Turkey
E. Chen and X. Liu. 2011. “Multi-Colony Ant Algorithm,” Ant Colony Optimization , Methods And Applications, A. Ostfeld, Ed., InTech Publisher, pp. 3-12.
H. Demez. 2013. “Combinatorial Optimization: Solution Methods of Traveling Salesman Problem,” Eastern Mediterranean University Master Thesis, Gazimağusa, Turkish Republic of Northern Cyprus
H.Z.C.S. Su and K.M. Aye. 2011. ”An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem”, International Conference on Information Communication and Management IPCSIT vol.16
J. J. Mwemezi and Y. Huang. 2011. “Optimal Facility Location on Spherical Surfaces: Algorithm and Application,” New York Science Journal, vol. 4, no. 7,
K. PANDEY and P. JAIN. 2015. “Comparison Of Different Heuristic, Metaheuristic, Nature Based Optimization Algorithms For Travelling Salesman Problem Solution”, International Journal of Management and Applied Science, ISSN: 2394-7926 Volume-1, Issue-2
M. Alhanjouri, B. Alfarra. 2011. Ant Colony versus Genetic Algorithm based on Travelling Salesman Problem. International Journal of Computer Technology and Applications, 2011. 2(3).
M. R. Bonyadi, M. R. Azghadi and H. Shah-Hosseini. 2008. “Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem,” Travelling Salesman Problem, I-Tech Education and Publishing, pp. 1-34.
R. Matai, S. P. Singh and M. L. Mittal. 2010. “Traveling Salesman Problem: An Overview of Applications, Formulations,and Solution Approaches,” Traveling Salesman Problem, Theory And Applications, D. Davendra, Ed., InTech,
R. Stanec. 2011. “Solving of Travelling Salesman Problem for large number of cities in environment with constraints”, Mendel University Faculty of Business and Economics Diploma thesis, Brno, Czech Republic
S. Al-hayali, O.N. Ucan, O. Bayat. 2018. “Genetic Algorithm for finding shortest paths Problem”, Proceedings of the Fourth International Conference on Engineering & MIS
S. BURILLE. 2016. “Traveling Salesman Problem,” Department of Mathematics, Saint Mary’s College of California Senior Essay, California
S. Subiyanto, T. Narwadi. 2017. “An Application of Traveling Salesman Problem Using the Improved Genetic Algorithm on Android Google Maps,” American Institute of Physics Publishing.
T.A. Mohammed, S. Sahmoud, O. Bayat. 2017. “Efficient hybrid memetic algorithm for multi-objective optimization problems”, International Conference on Engineering and Technology (ICET), 2017.
T. Pellonpera. 2014. “Ant colony optimization and the vehicle routing problem”
T. Stautlez and M. Dorigo. 1999. “ACO algorithms for the traveling salesman problem,” Evolutionary Algorithms in Engineering and Computer Science,Wiley.