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

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

Pages : 29-43

View : 23 | Download : 17

Publication Date : 2019-02-01

Article Type : Research Paper

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