Sezgisel fonksiyonlar temelinde tabu arama ve genetik algoritmalarının gezgin satıcı problemine uygulanması
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Karadeniz Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2005
Tezin Dili: Türkçe
Öğrenci: MUSTAFA BİLGEHAN İMAMOĞLU
Danışman: Vasıf Nabıyev
Özet:ÖZET Bu çalışmada problem karmaşıklığından dolayı yapay zeka yöntemleri kullanılarak gerçekleştirilen arama algoritmaları temelinde Türkiye haritası örneği ile gezgin satıcı problemi ele alınmaktadır. Yerel arama teknikleri kullanılarak mevcut çözümün komşularının araştırılmasıyla, kompleks problemlere optimum ya da optimuma yakın çözüm bulunabilmektedir. Bu tekniklerde karşılaşılan iki temel problem yerel optimuma yakalanma ve aşırı zaman kaybıdır. Günümüzde bu problemlere stokastik algoritmalar ile çözümler aranmaktadır. Stokastik arama yöntemlerinden birisi olan Genetik Algoritma çözüm uzayında en iyi sonuca ulaşmak için Seçim, Çaprazlama ve Mutasyon olarak anılan üç temel işlemden yararlanmaktadır. Algoritmanın amacı belirlenen uygunluk kriterlerini sağlayan bireylerde bulunduğu kabul edilen iyi özelliklerin, çaprazlama sonucunda ebeveynlerden sonraki nesillere geçirilmesiyle daha iyi bireyler oluşturmaktır. Bireyler arasında çeşitlilik yaratabilmek, iyi özellikleri kazanabilmek ve en iyi çözüme ulaşabilmek için bireyler belli aralıkla değişime (mutasyon) uğratılmaktadır. Tabu arama tekniği, arama süresinde incelemiş olduğu çözümleri listede tutarak, bu çözümlere yeniden geri dönülmesini bir süreliğine yasaklamaktadır. Bu davranış sayesinde arama işlemi çözüm uzayının farklı noktalarına ulaşabilmektedir. Yerel optimum noktasında ise, yasaklı olarak anılmayan veya yasaklı olsa bile belli kriterleri sağlayan en iyi komşuyu seçerek yerel optimumda takılınmasını önlemektedir. Çalışmada, değiştirilerek geliştirilmiş Tabu Arama ve Genetik Algoritma ile Gezgin Satıcı Problemine yaklaşılmış, her iki algoritma sonuçlan optimumluk açısından tartışılmıştır. Anahtar Kelimeler : Tabu Arama, Genetik Algoritmalar, Akıllı Ajanlar, Gezgin Satıcı Problemi, Yaklaşım Algoritmaları, Sezgisel Algoritmalar, Optimizasyon, Bileşenler VII