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: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Mühendislik Bilimleri, Computer Engineering and Computer Science and Control, Engineering Sciences
- 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ı: 89
Ö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
- A novel metaheuristic for graph and graphset-T coloring problem
Çizge boyama ve çizgeyi kümeli boyama problemi üzerine metasezgisel algoritma
ÇAĞRI YEŞİL
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMİN ERKAN KORKMAZ
- Optimization of SPARQL queries using artificial intelligence techniques
Yapay zeka teknikleri kullanılarak SPARQL sorgularının optimizasyonu
ELEM GÜZEL KALAYCI
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. DERYA BİRANT
- Integrating path planning and image processing with UAVs for disease detection and yield estimation in indoor agriculture
Kapalı alan tarımda hastalık tespiti ve verim tahmini için rota planlama ve görüntü işlemenin İHA'larla entegre edilmesi
ONAT ERDOĞMUŞ
Yüksek Lisans
İngilizce
2024
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDİNÇ ALTUĞ
- Yüksek düzeyde sentezlemede hızlı tasarım alanı keşfi için makine öğrenmesi tabanlı yeni bir optimizasyon yöntemi
A novel machine learning-based optimization methodology for fast design space exploration in high-level synthesis
ESRA ÇELİK
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAtatürk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ DAL
- Optimization methodology for application mapping in wireless network-on-chip
Kablosuz yonga-üstü-ağlar için uygulama eşleme optimizasyon metodolojisi
ALPEREN ÇAKIN
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SÜLEYMAN TOSUN