Tez No İndirme Tez Künye Durumu
233566
A genetic algorithm for TSP with backhauls based on conventional heuristics / Dağıtım ve toplamalı güzergahı bulma problemi için bilinen sezgisellere dayalı bir genetik algoritma
Yazar:İLTER ÖNDER
Danışman: DOÇ.DR. HALDUN SÜRAL ; PROF. DR. NUR EVİN ÖZDEMİREL
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Enformatik Enstitüsü / Bilişim Sistemleri Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin:Genetik algoritmalar = Genetic algorithms ; Mutasyon = Mutation 		Onaylandı
Yüksek Lisans
İngilizce
2007
123 s.
Bu çalısmada toplamalı gezgin satıcı problemi için bilinen sezgisel yöntemleri operatör olarak kullanan bir genetik algoritma incelenmistir. En yakın komsu sezgiseline dayalı bir çaprazlama yönteminin (En yakın komsu çaprazlaması, EYKÇ) özellikleri ve ikiden fazla ebeveyn kullanılması bir dizi deneyle incelenmistir. Farklı ebeveyn seçilimi ve birden fazla çocuk yaratma stratejileri de kıyaslanmıstır. Bilinen sezgisel yöntemler mutasyon operatörü olarak kullanılmıstır. 2-kenar degisimi ve dügüm sokma yöntemlerinin EYKÇ ile iyi sonuçlar verdigi gözlemlenmistir. Farklı alternatifler arasında en iyi sonuçları veren alternatifler Dagıtım ve Toplama Güzergâhı Bulma Problemine uygulanmıstır. DTGBP içinde iki grup sehir bulunan bir problemdir. Amacı, ikinci gruptakiler ancak birinci gruptakilerin tamamı gezildikten sonra gezilebilir sartını saglayacak sekilde, tüm sehirleri gezen en kısa yolu bulmaktır. Kullandıgımız yöntem rasgele üretilmis DTGBP'de etkileyici sonuçlar vermistir. Anahtar Kelimeler: Genetik Algoritmalar, Çaprazlama Yöntemleri, Dagıtım ve Toplama Güzergâhı Bulma Problemi (DTGBP), Sezgisel Yöntemler
A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are also tried as well. Conventional improvement heuristics are also used as mutation operators. It has been observed that 2-edge exchange and node insertion heuristics work well with NNX using only two parents. The best settings among different alternatives experimented are applied on traveling salesman problem with backhauls (TSPB). TSPB is a problem in which there are two groups of customers. The aim is to minimize the distance traveled visiting all the cities, where the second group can be visited only after all cities in the first group are already visited. The approach we propose shows very good performance on randomly generated TSPB instances. Keywords: Genetic Algorithms, Crossover operator, Mutation Operator, TSP with Backhauls, Conventional Heuristics