A novel meta-heuristic for graph coloring problem: Simulated annealing with backtracking
Çizge boyama problemi icin yeni bir sez ötesi algoritma: Geriye dönüş yöntemiyle benzetilmiş tavlama
- Tez No: 305830
- Danışmanlar: DOÇ. DR. EMİN ERKAN KORKMAZ
- Tez Türü: Yüksek Lisans
- Konular: Mühendislik Bilimleri, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Engineering Sciences, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Yeditepe Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Çizge Boyama Problemi (ÇBP) üzerinde en yaygn çalisilan tümlesik optimizasyonproblemlerinden biridir. ÇBP'yi etkin sekilde çözmek için birçok algoritma tasarlanmstir.Hibrit algoritmalarin elde ettigi umut verici sonuçlar, bu algoritmalarin standard teknik veyaklasimlar kadar iyi oldugunu kantlamaktadr. Bu tezde, ÇBP'yi çözmek için, yeni birüst-sezgisel algoritma olan Geriye Dönüs Yöntemiyle Benzetilmis Tavlama (GDBT) yöntemigelistirilmistir. Tasarlanan algoritmada benzetilmis tavlama teknigi (BT) ile geriye dönüsyöntemi birlestirilmistir. GDBT, gruplama problemlerini çözmek için tasarlanmis hibritve genel amaçli bir algoritmadir ve bu algoritmada tanim kümesine özgü bilgi kullanmaz.DIMACS challenge suit'ten birçok kyaslama noktasi örnegi üzerinde yaplan testlerde umutverici sonuçlar elde edilmistir. Diger yandan, GDBT'nin en son gelismeleri yanstan birçokalgoritmayla karsilastirmasi ve algoritmanin performans analizi de tezde sunulmustur.
Özet (Çeviri)
Graph coloring problem (GCP) is one of the most extensively studied combinatorialoptimization problems. Many algorithms have been proposed to solve GCP efciently. It hasbeen proved that hybrid algorithms are competitive with their pure counterparts as they yieldpromising results. This thesis presents a new meta-heuristic named as Simulated Annealingwith Backtracking (SABT) for solving GCP. The algorithm proposed combines simulatedannealing approach (SA) with a backtracking mechanism. SABT is a hybrid general purposealgorithm designed to solve any grouping problem. It does not exploit any domain-specicinformation. Several tests have been run on a collection of benchmarks from DIMACSchallenge suite and promising results are obtained. A comparison of SABT with someother state-of-the-art algorithms is also presented along with a performance analysis of thealgorithm.
Benzer Tezler
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- Bazı esterlerin kinetik incelenmesi ve termodinamik parametrelerin belirlenmesi
Kinetic study and detesmination of thermodnamic parameters of some esters
İBRAHİM TAŞ
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
- Atherosklerotik kalp hastalıklarında risk faktörleri
Risk factors in the coronary artery disease
MURAT SUHER