Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Elektrik ve Elektronik Mühendisliği Bölümü, Türkiye
Tezin Onay Tarihi: 1992
Tezin Dili: İngilizce
Öğrenci: Adnan Açan
Danışman: BAKİ ZAFER ÜNVER
Özet:ÖZ TAVLAMA BENZETİMİ ÎLE KANAL VE ANAHTAR KUTUSU 1ZGELEME AÇAN, Adnan Doktora Tezi, Elektrik ve Elektronik Mühendisliği Anabil im Dalı Tez Yöneticisi: Prof. Dr. Zafer ÜNVER Eylül, 1992, 147 sayfa. Bu çalışmada iki katmanlı kanal ve anahtar kutusu izgeleme problemleri Manhattan modeli kullanılarak incelenmiş ve bu problem¬ lerin çözümüne yönelik başarımı yüksek yeni algoritmalar geliştiril¬ miştir. Algoritmalarda eniyileme için kullanılan temel yöntem rast¬ lantısal tepe tırmanmaya dayalı ve özellikle birleşimsel eniyileme problemleri için başarımı ispatlanmış tavlama benzetimi yöntemidir. Kanal izgeleme problemine yönelik iki yeni algoritma gelişti¬ rilmiştir. Birinci algoritma dikey sınırlama çizgesini kullanarak her su yolunun bir çözüm içinde yer alabileceği yatay kanal hatları küme¬ sinin belirlenmesiyle başlar. Başlangıç biçimlenmesi her su yolunu kendisine karşı düşen yatay kanal kümesinden rastgele seçilen bir hat üzerine yerleştirmeyle belirlenir. Başlangıç biçimlenmesinin genelde içerdiği çakışmalar eniyileme süreci boyunca ortadan kaldırılırlar. Bu algoritmanın önemli özelliklerinden biri, biçimlenme uzayını tamamen izgelenmiş ancak çakışmalar içeren biçimlenmeler üzerinden çakışma içermeyen bir biçimlenme buluncaya kadar araştırmasıdır. Algoritma literatürde kanal izgelemeyle ilgili test problemlerine uygulanmış ve viher problem 1ç1n şimdiye kadar ulaşılabilmiş en küçük kanal geniş¬ liğine sahip bir çözüm makul hesaplama zamanlan içerisinde elde edilmiştir. Hesaplama zamanını düşük tutmak amacıyla sadece yatay su yolu kırılması içermeyen çözümler göz önüne alınmıştır. Kanal izgeleme ile ilgili ikinci algoritma yatay kanal hatla¬ rını teker teker ele alarak işler. Birinci yatay kanal hattından başlayarak işlenmekte olan hat üzerine konulmaya aday su yolları kümesi seçilir. Bu aday su yollarına belli ölçütler gözönüne alınarak puanlar verilir. Aday su yolları arasından aralarında çakışma olmayan ve puanları toplamı mümkün tüm seçenekler arasında en yüksek olan bir alt küme oluşturulur ve bu alt kümedeki su yolları işlenmekte olan yatay hat üzerine yerleştirilirler. Kanal izgelemeyle ilgili test problemleri yatay su yolu parçalarının kırımsız veya kırımlı olmaları dikkate alınarak çözülmüş ve her durumda şimdiye kadar ulaşılabilen en iyi kaliteye sahip çözümler elde edilmiştir. Algoritma tavlama benze¬ timi yöntemine dayalı diğer algoritmalarla karşılaştırıldığında çok daha az hesaplama zamanına ihtiyaç duymaktadır. Anahtar kutusu izgeleme problemi üzerine yönelik de başarımı yüksek iki yeni algoritma geliştirilmiştir. Birinci algoritma uyar¬ lanmış Lee algoritmasını kullanarak su yollarının ratgele izgelenme- siyle elde edilen bir başlangıç biçimlenmesiyle başlar. Başlangıç biçimlenmesinin genelde içerdiği çakışmalar eniyileme süreci boyunca toplam delik içi kaplama sayısı ve toplam su yolu uzunluğu en aza indirilecek şekilde ortadan kaldırılırlar. Algoritma biçimlenme uzayı¬ nı tamamen izgelenmiş ancak çakışmalar içeren biçimlenmeler üzerinden ve çakışma içermeyen en iyi biçimlenme bulununcaya kadar araştırır. viiAlgoritma uçların katmanlara serbest veya önceden belirlenmiş yerle¬ şimleri için kullanılabilir. Test problemleri üzerinde elde edilen çözümlerin kalitesi en az, bazı çok bilinen algoritmalar kullanılarak elde edilen çözümlerin kalitesine eşdeğerdir. Burstein'ın zor problemi gibi bazı tipik test problemleri dikkate alındığında ise, algoritma literatürdeki diğer tüm algoritmalara üstünlük sağlamaktadır. Basit bir öğrenme yöntemine dayanan ikinci algoritmada anahtar kutusu izgeleme problemi için su yollarının en iyi izgeleme sırasının bulunması problemi incelenmiştir. Bu amaçla her su yoluna izgeleme sırasının belli bir konumunda bulunmasının ne kadar iyi olduğunu gösterir bir ağırlık verilir, öğrenme süreci deneme ve kabul¬ lenmeye dayanır; su yolları için bir izgeleme sırası seçilir, uyar¬ lanmış Lee algoritması kullanılarak su yolları bu sırada izgelenir, ve her su yoluna ait ağırlık çakışma sayısının azlığını ödüllendirecek şekilde ayarlanır. Algoritma bazı önemli anahtar kutusu izgeleme problemlerini başarıyla çözerken bazılarında ise az sayıda çakışma içeren sonuçlar vermektedir. Çakışma içeren sonuçların ilk algoritma için başlangıç biçimlenmesi olarak kullanılmasıyla çakışmalar hızlıca kaldırılabilirler. Her iki durumda da ilk algoritmanın doğrudan kulla¬ nılmasına kıyasla hesaplama zamanı önemli miktarlarda düşürülmektedir. Anahtar Kelimeler: Kanal îzgeleme, Anahtar Kutusu Izgeleme, Tavfama Benzetimi, Değiştirilmiş Lee Algoritması, öğrenme Algoritmaları. Bilim Dalı Sayısal Kodu: 609.03.04 viii