Analysis of crossover, mutation methods and rates of genetic algorithms applied on traveling salesman problem
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Galatasaray Üniversitesi, Mühendislik ve Teknoloji Fakültesi, Bilgisayar Mühendisligi, Türkiye
Tezin Onay Tarihi: 2018
Tezin Dili: İngilizce
Öğrenci: ADNAN BAL
Danışman: MURAT AKIN
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Tüm endüstrinin(otomotiv ve özellikle lojistik alanında) ve yazılım endüstrisinde ki hızlı gelişmelerle, artan müşteri talepleri ve üreticilerin arzları sayesinde optimizasyon her gün daha çok önem kazanmaktadır. Optimizasyonla kastımız, üretim zamanlarının düşürülmesi, ürün lojistiğinin artırılması veya taşıma maliyetlerinde yakıt tüketiminin düşürülmesi anlatılmak istenmektedir. Endüstrinin bu tarz optimizasyon talepleri ayrıca optimizasyon algoritmalarının/tekniklerinin gelişerek evrilmesine katkıda bulunmuştur. Bilgisayarların gelişimi ve hesap kabiliyetlerinin gelişmesiyle, klasik optimizasyon teknikleri de evrilmiştir. Evolutionary optimizasyon tekniklerinden olan Genetik algoritmalar ve genetik programlama, optimizasyon alanında ki yüklü talebe yanıt vermeye çalışmaktadır. Temel olarak, generik algoritmalar, biyolojik genetik ve Sir Charles Darwin'in genetik alanında ki çaprazlama ve mutasyon uygulamalarından türetilmiştir. Genetik algoritmaları kullanarak, zor problemlerin daha optimize edilmiş sonuçlarına daha kolay olarak ulaşma şansına sahip oluruz. Genel olarak, aynı doğada olduğu gibi, rastgele çözümler bularak/seçerek, bu sonuçlara çaprazlama ve mutasyon teknikleri uygulayarak daha optimize sonuçlar bulmayı hedefliyoruz. Rastgele sonuçları birbiri arasında, parçalı olarak anlamlı verilerini çaprazlama ve mutasyon uygulayarak, daha optimize edilmiş sonuçlara varmayı umuyoruz. Genellikle, optimize edilmiş sonuca, doğru ve daha iyi çaprazlama ve mutasyon oranları seçerek ulaşmayı deniyoruz. Diğer bir deyişle, parametreler için kötü oranlar seçmek, bizi çoğunlukla daha kötü ve ya optimize olmayan sonuçlara ulaştıracaktır. Bu çalışmamızda, öncelikle, genetik algoritmaların genel konseptlerini tanıtıyoruz, daha sonra ise daha derine inerek ve spesifik şekilde genetik algoritmaları kullanarak, ünlü Gezgin Satıcı Problemi'ne optimize çözümler arıyoruz. Bu çalışmamızda, genetik algoritmayı Türkiyenin coğrafi bölgelerine(Marmara, Ege ve karadeniz bölgelerindeki şehirler, toplam 32 şehir) uygulayarak bu şehirler arasında ki en kısa yolu bulmaya çalışıyoruz. Genetik algoritmayı uygularken, çaprazlama metodlarını, mutasyon metodlarını, çaprazlama ve mutasyon oranlarını değiştirerek, en optimize yolu bulmaya çalışıyoruz ve sonuç olarak bulunan optimize sonuçları tüm bu parametler için ayrı ayrı analiz edip ortaya koyuyoruz. Sonuçta ise, karşılaştırılmış sonuçları grafik üzerinde göstererek, her parametrenin sonuca ne denli etki ettiğini ortaya koyuyoruz. Bu araştırmayı yaparak, gerçek hayatta lojistik endüstrisinde de aktif olarak kullanılan use caseler için daha doğru parametrelerin seçimine katkıda bulunarak, şirketlerin daha iyi yakıt tasarrufu elde etmelerine katkı sağlamayı amaçlıyoruz.