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

Year 2018, Volume: 2 Issue: 2, 29 - 43, 01.02.2019

Waled Milad Abulsasem Alashheb Adil Deniz Duru Oğuz Bayat Osman Nuri Uçan

Abstract

Özet

Polinom zamanda çözülebilecek (P) ve polinom zamanda doğrulanabilecek (NP) problemlerin bilinen etkin

bir algoritmasının olmaması, hesaplamadaki karmaşıklık teorisinin teorik hesaplama ve matematiğin gerekli

bir 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 olarak

aynı ş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şimini

temel almaktadır. Günümüzde, karınca kolonisi eniyileştirmesi (KKE) ve genetik algoritma (GA) bu tür

algoritmalara ö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.

Keywords

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

Abstract

The Theory of computational complexity is an essential branch of study in the science of theoretical computing

and mathematics. The resolution of Polynomial and Non Polynomial problems is one of the main

problems that have open solutions, for which no famous efficient algorithm exist. The Problem of Traveling

Salesman (TSP) is an example of these problems. Such a problem include, a count of specified cities must

be visited by a traveling salesman where both start and end points will be the same city and getting a tour

of all cities so that the complete distance or time is minimized will be the aim. The application of Optimization

algorithms is one of the famous methods of the solution regarding to the TSP. These algorithms usually

simulate the occurring phenomena in nature. Currently there exist several of such algorithms; for example,

Genetic Algorithm (GA) and Optimization of Ant Colony (ACO).

This paper aimed to compare two approaches, GA and ACO for solution of TSP. The results obtained from

our experiments showed that the ACO is better than GA since it requires less execution time for solving the

same problem.

Keywords

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

References

• 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.